链表基本操作

1、题目一 链表基本操作、数据结构与核心算法的设计描述1、单链表的最大长度#define MAXSIZE 1002、单链表的结点类型定义/*定义elemtype 为int类型*/typedef int elemtype;/*单链表的结点类型*/typedef struct STDelemtype elem;STD *n ext;list, * lin klist;3、初始化单链表/*函数功能：对链表进行初始化。参数：链表(linklist L)。成功初始化返回1,否则返回0 */int in it(li nklist &L)L=(li nklist)malloc(sizeof(list);

2、头结点申请内存。if(!L)II判断有无申请到空间。return 0;II没有申请到内存，参数失败返回0L-> next=NULL;L->elem=0;II单链表中有多少元素return 1;II成功参数返回14、清空单链表1*II*函数功能：把链表清空。参数：链表(linklist L)。成功清空链表返回int makeempty(l in klist &L)lin klist p,q;p=L->n ext;while(p)II当p非空时，删除pq=p;p=p->n ext;free(q);L-> next=NULL; L->elem=O;retu

3、rn 1;5、求链表长度/*函数功能：返回链表的长度。/只剩头指针，所以 L->next=NULL/清空后链表中元素为0/清空后返回1参数;链表(linklist L)。函数返回链表的长度 */int getle ngth(li nklist L)lin klist p;p=L->n ext;int j=0;while(p)j+；/统计链表中元素return j;p=p->n ext;/最后返回链表长度判断链表是否为空/*函数功能：判断链表是否为空。参数；链表(linklist L)。链表为空时返回0,不为空返回1*/ in t isempty(l in klist L)if

4、(L->next)/头结点后有元素表示链表不空则返回1return 1;elsereturn 0;/头结点后没有元素表示链表不空则返回07、检查链表是否为满/*函数功能：判断链表是否为满。参数；链表(linklist L)。链表为满时返回0,不为满返回1*/ in t isfull(li nklist L)if(L->elem <= MAXSIZE)/头结点的elem储存的为链表的长度。return 1;/其小于 MAXSIZE 表示链表不满elsereturn 0;/否则返回08、遍历链表/*函数功能：遍历链表，输出每个节点的elem值。参数；链表(linklist L)

5、通过循环逐个输出节点的elem值*/void show(li nklist L)li nklist p;p=L->n ext;if(isempty(L)=0)/当链表为空时则输出链表为空cout<<" 链表为空！"while(p)/当链表为不空时则输出链表每个节点的elem值cout<<p->elem<<""p=p->n ext;cout<<e ndl;9、从链表中查找元素/*函数功能：从链表中查找有无给定元素。参数；链表(linklist L),给定元素(int i)如果链表中有给定元素

6、(i)则返回1,否则返回0*/int fin d(li nklist L, i nt i)li nklist p;p=L->n ext;while(p)return 1;p=p->n ext;return 0;/没有找到返回010、从链表中查找与给定元素值相同的元素在表中的位置/*函数功能：从链表中查找给定元素的位置。参数;链表(linklist L),给定元素(int i)如果链表中有给定元素i则返回元素的位置，没有则返回0*/in t locati on( li nklist L,i nt i)li nklist p;int j=0;p=L->n ext;while(p)

7、j+；if(p->elem=i) /判断有无元素i,有返回其的位置jreturn j;p=p->n ext;return 0;/没有则返回011、向链表中插入元素/*函数功能：向链表中的某个位置插入元素。参数；链表(linklistL),位置(int i),元素(elemtypee)。成功插入返回1,否则返回0 */int in sert(l in klist &L, int i, elemtype e)lin klist p, s;int j = 0;p = L;while (p&&j<i-1)/查找第i个元素的前驱p = p_>n ext;j

8、 +;if(j>i-1|!p)/不符合条件返回0return 0;s = (linklist)malloc(sizeof(list);/ 给节点 s 分配内存/插入操作/插入完成后头结点的elem加1/成功插入返回1s->elem = e; s->next = p->n ext; p_>n ext = s;L_>elem+; return 1;12、从链表中删除元素i),元素 (elemtype/*函数功能：在链表中的某个位置删除元素。参数；链表(linklist L),位置(inte)。成功删除返回1,否则返回0 */int deleteelem(li n

9、klist & L,i nt i)lin klist p,q;int j=0;p=L;while (p-> next&&j<i-1)p=p->n ext;j+;if( j>i-1|!(p->next)return 0;q=p->n ext;p_>n ext=q _>n ext;free(q);L->elem-;return 1;13、主界面函数/查找第i个元素的前驱/不符合条件返回0/删除操作/插入完成后头结点的elem减1/成功删除返回1/*函数功能：显示所有操作功能。参数；无*/ void zhujiemia n

10、()cout<<e ndl<<e ndl;cout<<"tttt数据结构实验一 "<<endl;cout<<"tt"<<e ndl<<e ndl;cout<<"tt 1链表初始化"<<endl;cout<<"tt 2清空链表"<<endl;cout<<"tt 3求链表长度"<<endl;cout<<"tt 4链表是否为空

11、"<<endl;cout<<"tt 5检查链表是否为满"<<e ndl;cout<<"tt 6遍历链表"<<endl;cout<<"tt 7从链表中查找元素"<<e ndl;cout<<"tt 8从链表中查找与给定元素值相同的元素在表中的位置"<<e ndl;cout<<"tt 9向链表中插入元素"<<e ndl;cout<<"tt1

12、0从链表中删除元素"<<e ndl<<e ndl;cout<<"tt 其他键退出"<<endl;cout<<"tt"<<e ndl<<e ndl<<e ndl;cout<<"t请选择要进行操作的序号(1-10 ):"二、函数调用及主函数设计主函数主要设计：zhujiemian();/显示主界面cin>>a;/输入要进行的操作的序号cout<<e ndl;doswitch(a)/用switch语句

13、进行选择操作case 1:/初始化if(i nit(L)=1)cout<<"初始化成功！"<<e ndl;elsecout<<"初始化失败！"<<e ndl;break;case 2:if(makeempty(L)=1)/ 链表置空cout<<"链表已清空！"<<e ndl;elsecout<<" 链表清空失败！"<<e ndl;break;case 3:/链表的长度b=getle ngth(L);cout<<

14、;"链表的长度为："<<b<<e ndl; break;case 4:/判断链表是否空if(isempty(L)=1)cout<<"链表不空！"<<e ndl;elsecout<<"链表为空！"<<e ndl;break;case 5:/判断链表是否满if(isfull(L)=1)cout<<"链表不满！"<<e ndl;elsecout<<"链表已满！"<<e ndl;bre

15、ak;case 6:/遍历链表show(L);break;case 7:/链表是否有要查找元素cout<<" 您要查找的元素："cin> >b;if(fin d(L,b)=1)cout<<" 链表中有元素"<<b<<endl;elsecout<<" 链表没中有元素"<<b<<endl;break;case 8: /输出链表要查找元素的位置cout<<" 您要查找的元素为："<<e ndl;cin&

16、gt; >b;if(locatio n(L,b)=O)cout<<" 没有您要查找的元素"<<b<<e ndl;个位置。elsecout<<" 您查找 的元素"<<b<<" 在第"<<location(L,b)<<""<<e ndl;break;case 9:do cout<<"输入你要插入的位置和元素"<<e ndl;cin> >b»c

17、;while (b<=0|b>getle ngth(L)+1)/*此处可以对错误的输入进行判断*/cout<<"插入位置错误！请重新插入！"<<e ndl;cin> >b»c;if(i nsert(L,b,c)=O)cout<<"您插入的位置不对，插入失败！"<<e ndl;elsecout<<"插入成功！ "<<e ndl;提示是否继续cout<<"是否继续插入元素(Y/y继续),其他键停止插入n"

18、;进行插入操作ci n»YES; while(YES='Y'|YES='y');break;case 10:do if(getle ngth(L)=O)/判断链表是否为空若是则输出链表为空，并继续cout<<" 链表为空无法删除！"<<e ndl;break;cout<<"输入你要删除元素的位置："<<e ndl;cin> >b;while(b<=O|b>getle ngth(L)/*此处可以对错误的输入进行判断*/cout<<&

19、quot; 输入错误！请重新输入！"<<e ndl;cin> >b;if(deleteelem(L,b)=O)cout<<"您删除的位置不对，删除失败！"<<e ndl;elsecout<<"删除成功！ "<<e ndl;cout<<"是否继续删除元素(Y/y继续),其他键停止删除n"提示是否继续 进行删除操作ci n»YES; while(YES='Y'|YES='y');break;default

20、:break;system("pause");/按任意键继续system("cls");/清理屏幕上的内容zhujiemia n();/显示主界面cin>>a;/输入要进行操作的序号cout<<e ndl;while(a>0&&a<=10);/对进行输入的数进行判断(不在09则程序结束)说明：通过调用序列号不同的函数进行各种操作。函数根据每次输入的数进行判断不在1 10内的函数将结束，否则将继续进行。三、程序调试及运行结果分析程序第一步必须执行初始化，否则程序不能运行。在程序第一步必须执行初始化后，程序

21、完美运行，在进行任何函数操作程序都是正常运行， 而且本程序对插入和删除时进行错误检测如有的地方不可以插入，有点地方不能删除，如果链表 为空时则程序会输出链表为空，并继续进行其他操作，大大减少了程序的bug。四、实验总结通过这次试验我熟悉了对链表的基本操作，对基本的链表操作有了很好的掌握，知道自己容 易在什么地方出错。五、程序清单/ 实验一 _1.h#i nclude "iostream"#i nclude "malloc.h"#in elude "stdlib.h"using n amespace std;#defi ne MAXSI

22、ZE 100/链表的最大长度typedef int elemtype;typedef struct STDelemtype elem;STD *n ext;list, * lin klist;void zhujiemia n()cout<<e ndl<<e ndl;cout<<"*数据纟结构实验- *】"<<endl;cout<<"*】"<<endl<<endl;cout<<"【1链表初始化】"<<e ndl;cout<&

23、lt;"【2清空链表】"<<endl;cout<<"【3求链表长度】"<<endl;cout<<"【4链表是否为空】"<<endl;cout<<"【5检查链表是否为满"<<endl;cout<<"【6遍历链表】"<<endl;cout<<"【7从链表中查找元素"<<endl;cout<<"【8从链表中查找与给定元素值相同的元

24、素在表中的位置】"<<e ndl;cout<<"【9向链表中插入元素"<<endl;cout<<"【10从链表中删除元素"<<endl;cout<<"【其他键退出】"<<e ndl;cout<<*"<<endl<<endl;cout<<"【*请选择要进行操作的序号1-10) :*"<<endl;int in it(li nklist &L)L=(

25、l in klist)malloc(sizeof(list); if(!L)return 0;L-> next=NULL;L->elem=0;return 1;int in sert(l in klist &L, int i, elemtype e)lin klist p, s;int j = 0;p = L;while (p&&j<i-1)p = p_>n ext;j +;if( j>i-1|!p)return 0;s = (li nklist)malloc(sizeof(list); s->elem = e;s->next

26、= p->n ext;p_>n ext = s;L_>elem+;return 1;int deleteelem(li nklist & L,i nt i)lin klist p,q;int j=0;p=L;while (p-> next&&j<i-1)p=p->n ext;j+；if( j>i-1|!(P->next)return 0;q=p->n ext;p_>n ext=q _>n ext; free(q);L->elem-;return 1;int isempty(li nklist L)i

27、f(L-> next)return 1;elsereturn 0;void show(l in klist L)li nklist p;p=L->n ext; if(isempty(L)=O) cout<<" 链表为空!while(p)cout<<p->elem<<" p=p->n ext;cout<<e ndl;int getle ngth(li nklist L)li nklist p;p=L->n ext;int j=0;while(p)j+；p=p->n ext;return j;i

28、nt makeempty(l in klist &L)lin klist p,q;p=L->n ext;while(p)q=p;p=p->n ext; free(q);L-> next=NULL;L->elem=0;return 1;int fin d(li nklist L, i nt i)li nklist p;p=L->n ext; while(p)if(p->elem=i)return 1;p=p->n ext;return 0;int locati on( li nklist L,i nt i)li nklist p;int j=0;

29、p=L->n ext;while(p)j+； if(p_>elem=i) return j;p=p->n ext;return 0;int isfull(li nklist L)if(L->elem <= MAXSIZE)return 1;elsereturn 0;mai n.cpp#i nclude "iostream"#i nclude "malloc.h"#i nclude "stdlib.h"#include "实验一 .h"using n amespace std;int m

30、ai n()char YES;lin klist L;int a,b,c;zhujiemia n();cin> >a;cout<<e ndl;doswitch(a)case 1:if(i nit(L)=1)cout<<"初始化成功！"<<e ndl;elsecout<<"初始化失败！"<<e ndl;break;case 2:if(makeempty(L)=1)cout<<"链表已清空！"<<e ndl;elsecout<<&q

31、uot; 链表清空失败！"<<e ndl;break;case 3:b=getle ngth(L);cout<<"链表的长度为："<<b<<e ndl; break;case 4:if(isempty(L)=1)cout<<"链表不空！"<<e ndl;elsecout<<"链表为空！"<<e ndl;break;case 5:if(isfull(L)=1)cout<<"链表不满！"<<

32、e ndl;cout<<"链表已满！ "<<e ndl;break;case 6:show(L);break;case 7:cout<<" 您要查找的元素："cin> >b;if(fin d(L,b)=1)cout<<" 链表中有元素"<<b<<endl;elsecout<<" 链表没中有元素"<<b<<endl;break;case 8:cout<<" 您要查找的元素为：&

33、quot;<<e ndl;cin> >b;if(locatio n(L,b)=O)cout<<" 没有您要查找的元素 "<<b<<e ndl;else个位置。cout<<" 您查找 的元素"<<b<<" 在第"<<location(L,b)<<" "<<e ndl;break;case 9:do cout<<"输入你要插入的位置和元素"<<e

34、 ndl;cin> >b»c;while (b<=O|b>getle ngth(L)+1)cout<<"插入位置错误！请重新插入！ "<<e ndl;cin> >b»c;if(i nsert(L,b,c)=O)cout<<"您插入的位置不对，插入失败！"<<e ndl;cout<<"插入成功！ "<<e ndl;cout<<"是否继续插入元素(Y/y继续),其他键停止插入n"

35、ci n»YES; while(YES='Y'|YES='y');break;case 10:do if(getle ngth(L)=O)cout<<" 链表为空无法删除！ "<<e ndl;break;cout<<"输入你要删除元素的位置："<<e ndl;cin> >b;while(b<=O|b>getle ngth(L)cout<<" 输入错误！请重新输入！"<<e ndl;cin> &

36、gt;b;if(deleteelem(L,b)=O)cout<<"您删除的位置不对，删除失败！"<<e ndl;elsecout<<"删除成功！ "<<e ndl;cout<<"是否继续删除元素(Y/y继续),其他键停止删除n"ci n»YES; while(YES='Y'|YES='y');break;default:break;system("pause");system("cls");zh

37、ujiemia n();cin> >a;cout<<e ndl;while(a>0&&a<=10);return 0;题目二约瑟夫环问题一、循环链表的结点类型定义/*单链表的结点类型 */typedef struct node/*人的序号*/*密码*/*指向下一个节点的指针 */int nu mber;int cipher; struct node *n ext;List, *ListLi nk;二、循环链表的初始化int n )/*函数功能：初始化n个元素的循环链表。参数;链表(linklist L)，元素个数( 通过后插法对无头结点的链表

38、初始化。*/void In itList(ListLi nk & L,i nt n)int m,i;cout<<"输入第1个人的密码："cin»m;L=new List;L->nu mber=1;L->cipher=m;L->n ext=L;for(i=2;i<=n ;i+)ListL ink lpp;cout<<" 输入第"<<i<<" 个人的密码："cin»m;lpp=new List; lpp->nu mber=i;Ipp_

39、>cipher=m;Ipp->n ext=L->n ext;L_>n ext=lpp;L=L->n ext;cout<<e ndl;L=L->n ext;三、循环链表的长度/*函数功能：求循环链表的长度。参数；链表(linklist L) 通过各个扫描求循环链表长度*/int ListLe ngth(ListLi nk L)ListL ink lpp;if(L=NULL)cout<<" 链表是空的."return 0;int i=1;lpp=L->n ext;while(lpp!=L)i+;lpp=lpp-&

40、gt;n ext;return i;四、显示循环链表/*函数功能：循环链表的显示。参数；链表(linklist L)。通过各个扫描各个节点输出各个节点的密码*/void ListTraverse(ListL ink L)ListL ink lpp;lpp=L；int i=1;cout<<"输入第 1 个人的密码："<<lpp->cipher<<e ndl;lpp=lpp->n ext;while(lpp!=L)i+；cout<<"输入第"<<i<<"个人的密码：

41、"<<lpp->cipher<<endl;lpp=lpp->n ext;cout<<e ndl;五、约瑟夫环实现/*函数功能：实现所有人的出列次序。参数链表(linklist L)，密码(int m )。每次要找到出列者的前驱，把出列者删除*/void ListTraverse(ListL ink L)ListL ink lpp;lpp=L;int i=1;cout<<"输入第 1 个人的密码："<<lpp->cipher<<e ndl;lpp=lpp->n ext;w

42、hile(lpp!=L)i+;cout<<"输入第"<<i<<"个人的密码："<<lpp->cipher<<endl;lpp=lpp->n ext;cout<<e ndl;int ListLe ngth(ListLi nk L)ListL ink lpp;if(L=NULL)cout<<" 链表是空的."return 0;int i=1;lpp=L->n ext;while(lpp!=L)i+；lpp=lpp->n ext;re

43、turn i;void shixia n( ListL ink &L,i nt m)ListL ink lpp=L;ListLi nk l;while(lpp->n ext!=L)lpp=lpp->n ext;for(i nt n=ListLe ngth(L); n>0;n-)cout<<"密码为："<<m<<e ndl; cout<<"出列人的编号是："for(i nt i=1;i<=m% n-1;i+)lpp=lpp->n ext;cout<<lpp-&

44、gt;n ext->nu mber<<e ndl;m=lpp->n ext->cipher;l=lpp->n ext;lpp->n ext=l->n ext;delete l;函数调用及主函数设计：int mai n()int m,n;ListL ink L;cout<<" 输入人数(一个大于0小于30的数)和密码(一个大于0的数)："<<endl; cin»n»m;while( * 0| n>30|m<0)cout<<"输入的数字不符合要求，请重新

45、输入："<<e ndl;cin»n»m;cout<<" 请输入"<<n<<"个人的密码："<<endl;In itList(L, n);cout <<*<"个人的密码分别为："<<e ndl;ListTraverse(L);cout <<*<"个人的出列密码和编号分别是："<<e ndl;shixia n(L,m);return 0;总结：ma in函数先调用初始化循

46、环链表的的函数void in it(li nklist & L,i nt n)，然后将循环链表输出void show(li nklist L)，最后调用可以使人出列的函数void Joseph(li nklist & L,i nt m)本程序可以很好地运行，具有一定的除错能力，输入数据时可以对其进行判断，减少程序出 现bug的可能性。通过对本实验的操作，我熟悉了循环链表的基本操作，而且对循环链表的基本操作有了很好 的掌握。程序清单#in clude "iostream"#in clude "stdlib.h" using n amespace std; typedef struct node int nu mber;int cipher;struct node *n ext;/*人的序号*/*密码*/*指向下一个节点的指针 */List, *ListLi nk;void In itList(ListLi nk & L,i nt n)int m,i;cout<<"输入第1个人的密码：”； cin»m;L=new List;L->nu mber=1;L_>cipher=m;L->n ext=L