链表基本操作

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

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

3、=NULLL->elem=0; /清空后链表中元素为0return 1; /清空后返回15、求链表长度 /*函数功能:返回链表的长度。 参数;链表(linklist L)。 函数返回链表的长度 */int getlength(linklist L)linklist p;p=L->next;int j=0;while(p)j+; /统计链表中元素p=p->next;return j; /最后返回链表长度.6、判断链表是否为空/*函数功能:判断链表是否为空。参数;链表(linklist L)。链表为空时返回0,不为空返回1*/int isempty(linklist L) if(

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

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

6、)如果链表中有给定元素(i)则返回1,否则返回0*/int find(linklist L, int i) linklist p; p=L->next; while(p) if(p->elem=i) /判断有无元素I,有返回1 return 1; p=p->next; return 0; /没有找到返回010、从链表中查找与给定元素值相同的元素在表中的位置/*函数功能: 从链表中查找给定元素的位置。参数;链表(linklist L),给定元素(int i)如果链表中有给定元素i则返回元素的位置, 没有则返回0*/int location(linklist L,int i) l

7、inklist p; int j=0; p=L->next; while(p) j+; if(p->elem=i) /判断有无元素i,有返回其的位置j return j; p=p->next; return 0; /没有则返回011、向链表中插入元素/*函数功能:向链表中的某个位置插入元素。参数;链表(linklist L),位置(int i),元素(elemtype e)。成功插入返回1,否则返回0 */int insert(linklist &L, int i, elemtype e) linklist p, s; int j = 0; p = L; while

8、(p&&j<i-1) /查找第i个元素的前驱 p = p->next; j +; if(j>i-1|!p) /不符合条件返回0 return 0; s = (linklist)malloc(sizeof(list); /给节点s分配内存 s->elem = e; s->next = p->next; /插入操作 p->next = s; L->elem+; /插入完成后头结点的elem加1 return 1; /成功插入返回112、从链表中删除元素/*函数功能:在链表中的某个位置删除元素。参数;链表(linklist L),位置(

9、int i),元素(elemtype e)。成功删除返回1,否则返回0 */int deleteelem(linklist &L,int i)linklist p,q;int j=0;p=L;while (p->next&&j<i-1) /查找第i个元素的前驱p=p->next;j+;if(j>i-1|!(p->next) /不符合条件返回0return 0;q=p->next;p->next=q->next; /删除操作free(q);L->elem-; /插入完成后头结点的elem减1return 1; /成功删

10、除返回113、主界面函数/* 函数功能:显示所有操作功能。参数;无*/void zhujiemian()cout<<endl<<endl;cout<<"tttt数据结构实验一"<<endl;cout<<"tt-"<<endl<<endl;cout<<"tt 1 链表初始化"<<endl;cout<<"tt 2 清空链表"<<endl;cout<<"tt 3 求链表

11、长度"<<endl;cout<<"tt 4 链表是否为空"<<endl;cout<<"tt 5 检查链表是否为满"<<endl;cout<<"tt 6 遍历链表"<<endl;cout<<"tt 7 从链表中查找元素"<<endl;cout<<"tt 8 从链表中查找与给定元素值相同的元素在表中的位置"<<endl;cout<<"tt

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

13、要进行的操作的序号cout<<endl;doswitch(a) /用switch语句进行选择操作case 1: /初始化if(init(L)=1)cout<<"初始化成功！"<<endl;elsecout<<"初始化失败！"<<endl;break;case 2:if(makeempty(L)=1) /链表置空cout<<"链表已清空！"<<endl;elsecout<<"链表清空失败！"<<endl;bre

14、ak;case 3: /链表的长度b=getlength(L);cout<<"链表的长度为："<<b<<endl;break;case 4: /判断链表是否空if(isempty(L)=1)cout<<"链表不空！"<<endl;elsecout<<"链表为空！"<<endl;break;case 5: /判断链表是否满if(isfull(L)=1)cout<<"链表不满！"<<endl;elsecout&l

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

16、t;您要查找的元素为："<<endl;cin>>b;if(location(L,b)=0)cout<<"没有您要查找的元素"<<b<<endl;elsecout<<"您查找的元素"<<b<<"在第"<<location(L,b)<<"个位置。"<<endl;break;case 9:do cout<<"输入你要插入的位置和元素"<<

17、endl;cin>>b>>c;while (b<=0|b>getlength(L)+1)/* 此处可以对错误的输入进行判断 */cout<<"插入位置错误！请重新插入！"<<endl;cin>>b>>c;if(insert(L,b,c)=0)cout<<"您插入的位置不对，插入失败！"<<endl;elsecout<<"插入成功！"<<endl;cout<<"是否继续插入元素(Y/y

18、继续),其他键停止插入n"/提示是否继续进行插入操作cin>>YES; while(YES='Y'|YES='y');break;case 10:do if(getlength(L)=0)/判断链表是否为空若是则输出链表为空，并继续cout<<"链表为空无法删除！"<<endl;break;cout<<"输入你要删除元素的位置："<<endl;cin>>b;while(b<=0|b>getlength(L)/* 此处可以对错误的输

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

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

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

22、AXSIZE 100 /链表的最大长度typedef int elemtype;typedef struct STDelemtype elem;STD *next;list, * linklist;void zhujiemian() cout<<endl<<endl;cout<<"【*数据结构实验一*】"<<endl; cout<<"【*】"<<endl<<endl;cout<<"【1 链表初始化】"<<endl; cout&l

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

24、定元素值相同的元素在表中的位置】"<<endl;cout<<"【9向链表中插入元素】"<<endl;cout<<"【10从链表中删除元素】"<<endl;cout<<"【其他键退出】"<<endl;cout<<【*】"<<endl<<endl;cout<<"【*请选择要进行操作的序号（1-10）:*】"<<endl;int init(linklist &

25、amp;L)L=(linklist)malloc(sizeof(list);if(!L)return 0;L->next=NULL;L->elem=0;return 1;int insert(linklist &L, int i, elemtype e)linklist p, s;int j = 0;p = L;while (p&&j<i-1)p = p->next;j +;if(j>i-1|!p)return 0;s = (linklist)malloc(sizeof(list);s->elem = e;s->next = p

26、->next;p->next = s;L->elem+;return 1;int deleteelem(linklist &L,int i)linklist p,q;int j=0;p=L;while (p->next&&j<i-1)p=p->next;j+;if(j>i-1|!(p->next)return 0;q=p->next;p->next=q->next;free(q);L->elem-;return 1;int isempty(linklist L)if(L->next)retur

27、n 1;elsereturn 0;void show(linklist L)linklist p;p=L->next;if(isempty(L)=0)cout<<"链表为空！"while(p)cout<<p->elem<<" "p=p->next;cout<<endl;int getlength(linklist L)linklist p;p=L->next;int j=0;while(p)j+;p=p->next;return j;int makeempty(linklist

28、 &L)linklist p,q;p=L->next;while(p)q=p;p=p->next;free(q);L->next=NULL;L->elem=0;return 1;int find(linklist L, int i)linklist p;p=L->next;while(p)if(p->elem=i)return 1;p=p->next;return 0;int location(linklist L,int i)linklist p;int j=0;p=L->next;while(p)j+;if(p->elem=i)

29、return j;p=p->next;return 0;int isfull(linklist L)if(L->elem <= MAXSIZE)return 1;elsereturn 0;/main.cpp#include "iostream"#include "malloc.h"#include "stdlib.h"#include "实验一.h"using namespace std;int main()char YES;linklist L;int a,b,c;zhujiemian();ci

30、n>>a;cout<<endl;doswitch(a)case 1:if(init(L)=1)cout<<"初始化成功！"<<endl;elsecout<<"初始化失败！"<<endl;break;case 2:if(makeempty(L)=1)cout<<"链表已清空！"<<endl;elsecout<<"链表清空失败！"<<endl;break;case 3:b=getlength(L);c

31、out<<"链表的长度为："<<b<<endl;break;case 4:if(isempty(L)=1)cout<<"链表不空！"<<endl;elsecout<<"链表为空！"<<endl;break;case 5:if(isfull(L)=1)cout<<"链表不满！"<<endl;elsecout<<"链表已满！"<<endl;break;case 6:sh

32、ow(L);break;case 7:cout<<"您要查找的元素："cin>>b;if(find(L,b)=1)cout<<"链表中有元素"<<b<<endl;elsecout<<"链表没中有元素"<<b<<endl;break;case 8:cout<<"您要查找的元素为："<<endl;cin>>b;if(location(L,b)=0)cout<<"没有您

33、要查找的元素"<<b<<endl;elsecout<<"您查找的元素"<<b<<"在第"<<location(L,b)<<"个位置。"<<endl;break;case 9:do cout<<"输入你要插入的位置和元素"<<endl;cin>>b>>c;while (b<=0|b>getlength(L)+1)cout<<"插入位

34、置错误！请重新插入！"<<endl;cin>>b>>c;if(insert(L,b,c)=0)cout<<"您插入的位置不对，插入失败！"<<endl;elsecout<<"插入成功！"<<endl;cout<<"是否继续插入元素(Y/y继续),其他键停止插入n"cin>>YES; while(YES='Y'|YES='y');break;case 10:do if(getlength(

35、L)=0)cout<<"链表为空无法删除！"<<endl;break;cout<<"输入你要删除元素的位置："<<endl;cin>>b;while(b<=0|b>getlength(L)cout<<"输入错误！请重新输入！"<<endl;cin>>b;if(deleteelem(L,b)=0)cout<<"您删除的位置不对，删除失败！"<<endl;elsecout<<&

36、quot;删除成功！"<<endl;cout<<"是否继续删除元素(Y/y继续),其他键停止删除n"cin>>YES; while(YES='Y'|YES='y');break;default:break;system("pause");system("cls");zhujiemian();cin>>a;cout<<endl;while(a>0&&a<=10);return 0;题目二 约瑟夫环问题一、循环

37、链表的结点类型定义/* 单链表的结点类型 */typedef struct nodeint number; /* 人的序号 */int cipher; /* 密码 */ struct node *next; /* 指向下一个节点的指针 */List, *ListLink;二、循环链表的初始化/* 函数功能:初始化n个元素的循环链表。参数;链表(linklist L)，元素个数（int n）通过后插法对无头结点的链表初始化。 */void InitList(ListLink &L,int n)int m,i;cout<<"输入第1个人的密码："cin>

38、;>m;L=new List;L->number=1;L->cipher=m;L->next=L;for(i=2;i<=n;i+)ListLink lpp;cout<<"输入第"<<i<<"个人的密码："cin>>m;lpp=new List;lpp->number=i;lpp->cipher=m;lpp->next=L->next;L->next=lpp;L=L->next;cout<<endl;L=L->next;三、循

39、环链表的长度/* 函数功能:求循环链表的长度。参数;链表(linklist L) 通过各个扫描求循环链表长度 */int ListLength(ListLink L)ListLink lpp;if(L=NULL)cout<<"链表是空的."return 0;int i=1;lpp=L->next;while(lpp!=L)i+;lpp=lpp->next;return i;四、显示循环链表/*函数功能:循环链表的显示。参数;链表(linklist L) 。通过各个扫描各个节点输出各个节点的密码 */void ListTraverse(ListLink

40、 L)ListLink lpp;lpp=L;int i=1;cout<<"输入第1个人的密码："<<lpp->cipher<<endl;lpp=lpp->next;while(lpp!=L)i+;cout<<"输入第"<<i<<"个人的密码："<<lpp->cipher<<endl;lpp=lpp->next;cout<<endl;五、约瑟夫环实现/*函数功能:实现所有人的出列次序。参数;链表(linkl

41、ist L) ，密码（int m）。每次要找到出列者的前驱，把出列者删除 */void ListTraverse(ListLink L)ListLink lpp;lpp=L;int i=1;cout<<"输入第1个人的密码："<<lpp->cipher<<endl;lpp=lpp->next;while(lpp!=L)i+;cout<<"输入第"<<i<<"个人的密码："<<lpp->cipher<<endl;lpp=lp

42、p->next;cout<<endl;int ListLength(ListLink L)ListLink lpp;if(L=NULL)cout<<"链表是空的."return 0;int i=1;lpp=L->next;while(lpp!=L)i+;lpp=lpp->next;return i;void shixian(ListLink &L,int m)ListLink lpp=L;ListLink l; while(lpp->next!=L) lpp=lpp->next;for(int n=ListLen

43、gth(L);n>0;n-)cout<<"密码为："<<m<<endl;cout<<"出列人的编号是："for(int i=1;i<=m%n-1;i+)lpp=lpp->next;cout<<lpp->next->number<<endl;m=lpp->next->cipher;l=lpp->next;lpp->next=l->next;delete l;函数调用及主函数设计：int main()int m,n;ListLi

44、nk L;cout<<"输入人数(一个大于0小于30的数)和密码(一个大于0的数)："<<endl;cin>>n>>m;while(n<0|n>30|m<0)cout<<"输入的数字不符合要求，请重新输入："<<endl;cin>>n>>m;cout<<"请输入"<<n<<"个人的密码："<<endl;InitList(L,n);cout<<n

45、<<"个人的密码分别为："<<endl;ListTraverse(L);cout<<n<<"个人的出列密码和编号分别是："<<endl;shixian(L,m);return 0;总结：main函数先调用初始化循环链表的的函数void init(linklist &L,int n)，然后将循环链表输出void show(linklist L)，最后调用可以使人出列的函数void Joseph(linklist &L,int m)。本程序可以很好地运行，具有一定的除错能力，输入数据

46、时可以对其进行判断，减少程序出现bug的可能性。通过对本实验的操作，我熟悉了循环链表的基本操作，而且对循环链表的基本操作有了很好的掌握。程序清单#include "iostream"#include "stdlib.h"using namespace std;typedef struct nodeint number; /* 人的序号 */int cipher; /* 密码 */ struct node *next; /* 指向下一个节点的指针 */List, *ListLink;void InitList(ListLink &L,int n)int m,i;cout<<"输入第1个人的密码："cin>>m;L=new List;L->number=1;L->ciphe