单链表完整算法

1、/ 包含头文件#include #include #include / 为结点数据类型和结构体类型起别名typedef int datatype;typedef struct LinkNodedatatype data;/ 数据域struct LinkNode *next;/ 指针域存放下一个结点的地址LNode,*LinkList;LinkList L; / 单链表的头指针/ 1.用头插法创建单链表LinkList CreateListHead(int n)/ 创建头结点LNode *L = (LNode *)malloc(sizeof(LNode);L-next = NULL; / 设置指

2、针域为空LinkList p;/ p指向新结点for(int i=n;i0;i-)/ 先插入最后一个结点，插入次序与逻辑次序相反/ 生成新结点p = (LNode *)malloc(sizeof(LNode);/ 从键盘输入新结点的值printf(请输入要插入第%d结点的值:n,i);scanf(%d, &p-data);p-next = L-next; / 让L原来的后继结点成为p的后继结点L-next = p;/ p成为L新的后继结点return L; / 返回单链表的头指针/ 2.用尾插法创建单链表LinkList CreateListTail(int n)/ 生成头结点L = (LNo

3、de *)malloc(sizeof(LNode);L-next = NULL;/ 设置指针域为空/ p指向新结点，q指向尾结点LinkList p, q = L;/ 依次在末尾插入n个结点for(int i=1;idata); p -next = NULL;/ 新结点（也是尾结点）的指针域为空/ 把新结点链接到单链表的末尾q-next = p;/ 让q指向新的尾结点q = p;return L;/ 返回单链表的头指针/ 3.显示单链表中的元素值void ShowList(LinkList L)if(L = NULL | L-next=NULL)printf(单链表为空。n);return;L

4、inkList p = L; / 指针p首先指向头结点while(p-next!=NULL) / 当指针p没有到达尾结点时p = p-next; / 指针后移一个结点printf(%dn,p-data); / 输出结点数据域的值/ 4.求单链表的长度（结点的个数）int GetLength (LinkList L)LNode *p=L; /*p 先指向头结点*/int n=0;/n代表除头结点外的结点个数while(p-next != NULL)/ 当指针p没有到达尾结点时p=p-next; /指针后挪一个结点n+;/结点个数+1return n;/返回结点的个数/ 5.按序号查找：在单链表中

5、查找第i个结点LinkList LocateElemByIndex(LinkList L, int i)LinkList p = L;/ 指针p先指向头结点，负责后移int j = 0;/ j用来计算到达结点的序号if(L=NULL | L-next=NULL) printf(单链表为空。n);return NULL; / p指针后移的条件：p不是尾结点，而且jnext!=NULL & jnext; / p指针后移j+;/ j递增if(j=i)/ 找到第i个结点时：j=ireturn p; / 返回第i个结点的地址elsereturn NULL;/ 第i个结点不存在，返回NULL/ 6.按值查

6、找：在单链表中查找值为e的结点LinkList LocateElemByData(LinkList L, datatype e)LinkList p = L;/指针p先指向头结点，负责后移if(L=NULL | L-next=NULL) printf(单链表为空。n);return NULL; / p指针后移的条件：p不是尾结点，而且p-data!=ewhile(p-next!=NULL & p-data!=e)p = p-next; / p指针后移/ 找到值为e的结点if(p-data = e)return p;/ 返回结点的地址elsereturn NULL; / 结点不存在，返回NULL

7、/ 7.在单链表的第i个位置插入值为e的结点（在第i-1个结点后面插入新结点）void InsertByIndex(LinkList L, int i, datatype e)LNode *s;LNode *p = LocateElemByIndex(L,i-1);/找到了第i-1个结点if(p!=NULL) s=(LNode *)malloc(sizeof(LNode); s-data=e; / 修改指针域的两行代码次序不能颠倒s-next=p-next; p-next=s;printf(插入结点完成。n);else printf(单链表为空或插入位置有误。n); / 8.在单链表中值为e的

8、结点之后插入新结点void InsertByDataBehind(LinkList L, datatype e)LNode *s; / s指向新结点，p指向值为e的结点LNode *p = LocateElemByData(L,e);/ 找到值为e的结点if(p!=NULL)/ 在值为e的结点之后插入新结点s=(LNode *)malloc(sizeof(LNode); / 从键盘输入新结点的值printf(请从键盘输入新结点的值:n);scanf(%d,&s-data);/ 修改指针域的两行代码次序不能颠倒s-next = p-next;p-next = s;printf(插入结点完成。n)

9、;elseprintf(单链表为空或插入位置有误。n);/ 9.在值为e的结点之前插入void InsertByDataBefore(LinkList L,datatype e)LinkList p=L,q,s;while(p-next !=NULL & p-data !=e)q = p;p = p-next;if(p-data=e)s = (LinkList)malloc(sizeof(LNode);printf(请输入新结点的值：);scanf(%d,&s-data);s-next = p;/s-next=q-next;q-next = s;printf(插入完成。n);else prin

10、tf(插入失败。n);/ 10.在单链表中删除第i个结点void DeleteByIndex(LinkList L, int i)LNode *p = LocateElemByIndex(L,i-1); / p指向第i-1个结点LNode *q = p-next; / q指向第i个结点（待删除结点）if (q!=NULL)p-next = q-next;free(q);elseprintf(单链表为空或删除位置有误。n);/ 11.删除值为e的结点void DeleteByData(LinkList L, datatype e) LNode *p=L,*q; /p指向值为e的结点while(p

11、-next!=NULL & p-data!=e) q=p; /q指向p的前驱结点p=p-next; if (p-data=e) q-next = p-next; free (p); printf(删除成功。n); else printf(删除失败。n); / 12 删除值为e结点的后继结点void DeleteByDataBehind(LinkList L, datatype e)LinkList p = L;/指针p先指向头结点，负责后移/ p指针后移的条件：p不是尾结点，而且p-data!=ewhile(p-next!=NULL & p-data!=e)p = p-next; / p指针后

12、移LNode *q = p-next; / q指向p的后继结点（待删除结点）if (q!=NULL)p-next = q-next;free(q);elseprintf(单链表为空或值为e结点不存在。n);/主函数void main()printf(-n);printf(| 1 头插法创建单链表 |n);printf(| 2 尾插法创建单链表 |n);printf(| 3 求单链表长度 |n);printf(| 4 显示单链表中的元素 |n);printf(| 5 查找第i个结点 |n);printf(| 6 查找值为e的结点 |n);printf(| 7 在第i个位置插入 |n);print

13、f(| 8 在值为e结点之后插入 |n);printf(| 9 在值为e结点之前插入 |n);printf(| 10 删除第i个结点 |n);printf(| 11 删除值为e的结点 |n);printf(| 12 删除值为e结点的后继结点 |n);printf(| 0 退出 |n);printf(-n);int num;/选择操作对应的数字int count;/要插入元素的个数int length;/单链表的长度LinkList p;/存放查找结点的首地址int i;/要查找元素的序号datatype e;/要查找元素的值do printf(请输入要选择操作对应的数字：);scanf(%d,

14、 &num);switch(num)case 1:/头插法创建单链表printf(请输入要插入结点的个数：);scanf(%d,&count);L = CreateListHead(count);if (L=NULL)printf(头插法创建失败。n);else printf(头插法创建成功。n);break;case 2:/尾插法创建单链表printf(请输入要插入结点的个数：);scanf(%d,&count);L = CreateListTail(count);if (L=NULL)printf(尾插法创建失败。n);else printf(尾插法创建成功。n);break;case 3

15、:/求单链表的长度length = GetLength(L);printf(单链表的长度：%d。n, length); break;case 4:/显示单链表中的元素ShowList(L);break;case 5:/查找第i个结点printf(请输入要查找元素的序号(必须大于0):);scanf(%d,&i);p = LocateElemByIndex(L,i);if (p=NULL)printf(未找到。n);elseprintf(找到了。n);break;case 6:/查找值为e的结点printf(请输入要查找元素的值:);scanf(%d,&e);p = LocateElemByDa

16、ta(L,e);if (p=NULL)printf(未找到。n);elseprintf(找到了。n);break;case 7:/在第i个位置插入printf(请输入要插入的位置:n);scanf(%d,&i);printf(请输入要插入元素的值:n);scanf(%d,&e);InsertByIndex(L, i, e);break;case 8:/插入到值为e的结点之后printf(插入到值为e的结点:请输入结点的值：n);scanf(%d,&e);InsertByDataBehind(L,e);break;case 9:/插入到值为e的结点之前printf(插入到值为e的结点之前:请输入结点的值：n);scanf(%d,&e);InsertByDataBefore(L,e);break;case 10:/删除第i个结点printf(请输入要删除元素的位置:n);scanf(%d, &i);DeleteByIndex(L, i);break;c