C+数据结构与算法之链表（一）单链表的创建与查找

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.小结
单链表作为链表中最简单的一种，摆脱了顺序表对空间的束缚，可以很好的支持动态操作。但是其问题也很明显，每个节点只能找到其直接后继，而找不到其前一节点。在查找时需要从表头开始遍历表，会增加时间复杂度。