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