共计 3394 个字符，预计需要花费 9 分钟才能阅读完成。
1. 单链表定义
每个节点包括一个数据域一个指针域，节点在内存中地址可以不连续，但是节点内部地址必然连续。
2. 结构定义
typedef struct Lnode{
int data;
struct Lnode *next;
}Lnode,*LinkList;
3. 单链表的创建
1）头插法
// 头插法建立带头结点的单链表
LinkList create1(LinkList &L){
Lnode *s;
int x;
L=(LinkList) malloc(sizeof(Lnode));// 创建头结点
L->next = NULL; // 初始化
printf(“ 往链表中添加数据,99999 结束 \n”);
scanf(“%”,&x);
while(x!=99999){
s = (Lnode*)malloc(sizeof(Lnode));// 创建新节点
s->data = x;
s->next = L->next;
L->next = s;
scanf(“%d”,&x);
}
return L;
}
2）尾插法
// 尾插法建立单链表
LinkList create2(LinkList &L){
int x;
L=(LinkList) malloc(sizeof(Lnode));// 创建尾结点
Lnode *s,*r = L;// S 为插入节点指针，r 为尾指针
printf(“ 往链表中添加数据,99999 结束 \n”);
//scanf(“%”,&x);
while(x!=99999){
s = (Lnode*)malloc(sizeof(Lnode));// 创建新节点
scanf(“%d”,&x);
s->data = x;
r->next = s;
r = s; // r 指向新的表尾
}
r->next = NULL;// 尾节点指针置空
return L;
}
4. 单链表的查找
1）按值查找
// 按值查找表节点，返回节点位序，查找失败返回 -1
int locateElem(LinkList L, int e){
Lnode *P = L->next;
int j=1;
while (P!=NULL&&P->data!=e){
P = P->next;
j++;
}
if(P->next == NULL && P->data == e)
return j;
else if(P->next != NULL && P->data == e)
return j;
else
return -1;
}
// 按值查找表节点，返回节点指针, 这是方便链表运算实现
Lnode *locateElem2(LinkList L, int e){
Lnode *P = L->next;
while (P!=NULL&&P->data!=e){
P = P->next;
}
return P;// 失败则返回空指针
}
2）按序号查找
// 按序号查找表节点，返回节点值
int getElem(LinkList L,int i){
int j = 1;
Lnode *P = L->next;
if(i==0)
return 0;// 如果 i =0，则返回头结点的值，但头结点不存值故返回 0
if(i<0)
return -1;// 错误序号则返回 -1
while(P&&j<i)// P 非空
{
P= P->next;
j++;
}
return P->data;
}
// 按序号查找表节点，返回节点指针, 这是方便链表运算实现
Lnode *getElem1(LinkList L, int i){
int j = 1;
Lnode *P = L->next;
if(i==0)
return L;// 如果 i =0，则返回头结点
if(i<0)
return NULL;// 错误序号则返回 NULL
while(P&&j<i)// P 非空
{
P= P->next;
j++;
}
return P;
}
5. 完整代码及运行
#include <stdio.h>
#include <stdlib.h>//malloc 函数头文件
// 单链表定义
typedef struct Lnode{
int data;
struct Lnode *next;
}Lnode,*LinkList;
// 头插法建立带头结点的单链表
LinkList create1(LinkList &L){
Lnode *s;
int x;
L=(LinkList) malloc(sizeof(Lnode));// 创建头结点
L->next = NULL; // 初始化
printf(“ 往链表中添加数据,99999 结束 \n”);
scanf(“%”,&x);
while(x!=99999){
s = (Lnode*)malloc(sizeof(Lnode));// 创建新节点
s->data = x;
s->next = L->next;
L->next = s;
scanf(“%d”,&x);
}
return L;
}
// 尾插法建立单链表
LinkList create2(LinkList &L){
int x;
L=(LinkList) malloc(sizeof(Lnode));// 创建尾结点
Lnode *s,*r = L;// S 为插入节点指针，r 为尾指针
printf(“ 往链表中添加数据,99999 结束 \n”);
//scanf(“%”,&x);
while(x!=99999){
s = (Lnode*)malloc(sizeof(Lnode));// 创建新节点
scanf(“%d”,&x);
s->data = x;
r->next = s;
r = s; // r 指向新的表尾
}
r->next = NULL;// 尾节点指针置空
return L;
}
// 按序号查找表节点，返回节点值
int getElem(LinkList L,int i){
int j = 1;
Lnode *P = L->next;
if(i==0)
return 0;// 如果 i =0，则返回头结点的值，但头结点不存值故返回 0
if(i<0)
return -1;// 错误序号则返回 -1
while(P&&j<i)// P 非空
{
P= P->next;
j++;
}
return P->data;
}
// 按序号查找表节点，返回节点指针, 这是方便链表运算实现
Lnode *getElem1(LinkList L, int i){
int j = 1;
Lnode *P = L->next;
if(i==0)
return L;// 如果 i =0，则返回头结点
if(i<0)
return NULL;// 错误序号则返回 NULL
while(P&&j<i)// P 非空
{
P= P->next;
j++;
}
return P;
}
// 按值查找表节点，返回节点位序，查找失败返回 -1
int locateElem(LinkList L, int e){
Lnode *P = L->next;
int j=1;
while (P!=NULL&&P->data!=e){
P = P->next;
j++;
}
if(P->next == NULL && P->data == e)
return j;
else if(P->next != NULL && P->data == e)
return j;
else
return -1;
}
// 按值查找表节点，返回节点指针, 这是方便链表运算实现
Lnode *locateElem2(LinkList L, int e){
Lnode *P = L->next;
while (P!=NULL&&P->data!=e){
P = P->next;
}
return P;// 失败则返回空指针
}
int main(){
LinkList L,L1;
create1(L);
LinkList temp = L->next;
while(temp->next != NULL)
{
printf(“%d “, temp->data);
temp = temp->next;
}
printf(“ 头插法与存数据的顺序相反 \n”);
create2(L1);
LinkList temp2 = L1->next;
while(temp2 ->next != NULL)
{
printf(“%d “, temp2->data);
temp2 = temp2->next;
}
printf(“ 尾插法与存数据的顺序相同 \n”);
printf(“ 输入取值位序 \n”);
int i;
scanf(“%d”,&i);
printf(“ 第 %d 位值为 %d\n”,i, getElem(L1,i));
printf(“ 输入查找值 \n”);
int e;
scanf(“%d”,&e);
printf(“ 值为：%d 位序为：%d\n”,e, locateElem(L1,e));
return 0;
}
6. 小结
单链表作为链表中最简单的一种，摆脱了顺序表对空间的束缚，可以很好的支持动态操作。但是其问题也很明显，每个节点只能找到其直接后继，而找不到其前一节点。在查找时需要从表头开始遍历表，会增加时间复杂度。
