链表基本操作

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=NULLL-elem=0; /清空后链表中元素为0retur

3、n 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(L-next) /头结点后有元素表示链表不空则返回1 return 1; else r

4、eturn 0; /头结点后没有元素表示链表不空则返回07、检查链表是否为满/*函数功能:判断链表是否为满。参数;链表(linklist L)。链表为满时返回0,不为满返回1*/int isfull(linklist L) if(L-elem next; if(isempty(L)=0) /当链表为空时则输出链表为空 cout链表为空！; while(p) /当链表为不空时则输出链表每个节点的elem值 coutelemnext; coutnext; while(p) if(p-elem=i) /判断有无元素I,有返回1 return 1; p=p-next; return 0; /没有找到返

5、回010、从链表中查找与给定元素值相同的元素在表中的位置/*函数功能: 从链表中查找给定元素的位置。参数;链表(linklist L),给定元素(int i)如果链表中有给定元素i则返回元素的位置, 没有则返回0*/int location(linklist L,int i) linklist 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)

6、,位置(int i),元素(elemtype e)。成功插入返回1,否则返回0 */int insert(linklist &L, int i, elemtype e) linklist p, s; int j = 0; p = L; while (p&jnext; j +; if(ji-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; /

7、成功插入返回112、从链表中删除元素/*函数功能:在链表中的某个位置删除元素。参数;链表(linklist L),位置(int i),元素(elemtype e)。成功删除返回1,否则返回0 */int deleteelem(linklist &L,int i)linklist p,q;int j=0;p=L;while (p-next&jnext;j+;if(ji-1|!(p-next) /不符合条件返回0return 0;q=p-next;p-next=q-next; /删除操作free(q);L-elem-; /插入完成后头结点的elem减1return 1; /成功删除返回113、主界

8、面函数/* 函数功能:显示所有操作功能。参数;无*/void zhujiemian()coutendlendl;couttttt数据结构实验一endl;couttt-endlendl;couttt 1 链表初始化endl;couttt 2 清空链表endl;couttt 3 求链表长度endl;couttt 4 链表是否为空endl;couttt 5 检查链表是否为满endl;couttt 6 遍历链表endl;couttt 7 从链表中查找元素endl;couttt 8 从链表中查找与给定元素值相同的元素在表中的位置endl;couttt 9 向链表中插入元素endl;couttt10 从链

9、表中删除元素endlendl;couttt其他键退出endl;couttt-endlendlendl;couta; /输入要进行的操作的序号coutendl;doswitch(a) /用switch语句进行选择操作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);cout链表的长度为：bendl;break;case

10、 4: /判断链表是否空if(isempty(L)=1)cout链表不空！endl;elsecout链表为空！endl;break;case 5: /判断链表是否满if(isfull(L)=1)cout链表不满！endl;elsecout链表已满！endl;break;case 6: /遍历链表show(L);break;case 7: /链表是否有要查找元素coutb;if(find(L,b)=1)cout链表中有元素bendl;elsecout链表没中有元素bendl;break;case 8: /输出链表要查找元素的位置cout您要查找的元素为：b;if(location(L,b)=0)

11、cout没有您要查找的元素bendl;elsecout您查找的元素b在第location(L,b)个位置。endl;break;case 9:do cout输入你要插入的位置和元素bc;while (bgetlength(L)+1)/* 此处可以对错误的输入进行判断 */cout插入位置错误！请重新插入！bc;if(insert(L,b,c)=0)cout您插入的位置不对，插入失败！endl;elsecout插入成功！endl;coutYES; while(YES=Y|YES=y);break;case 10:do if(getlength(L)=0)/判断链表是否为空若是则输出链表为空，并继

12、续cout链表为空无法删除！endl;break;cout输入你要删除元素的位置：b;while(bgetlength(L)/* 此处可以对错误的输入进行判断 */cout输入错误！请重新输入！b;if(deleteelem(L,b)=0)cout您删除的位置不对，删除失败！endl;elsecout删除成功！endl;coutYES; while(YES=Y|YES=y);break;default:break;system(pause);/按任意键继续system(cls);/清理屏幕上的内容zhujiemian();/显示主界面cina; /输入要进行操作的序号cout0&a=10);/

13、对进行输入的数进行判断(不在09则程序结束)说明：通过调用序列号不同的函数进行各种操作。函数根据每次输入的数进行判断不在110内的函数将结束，否则将继续进行。三、程序调试及运行结果分析程序第一步必须执行初始化，否则程序不能运行。在程序第一步必须执行初始化后，程序完美运行，在进行任何函数操作程序都是正常运行，而且本程序对插入和删除时进行错误检测如有的地方不可以插入，有点地方不能删除，如果链表为空时则程序会输出链表为空，并继续进行其他操作，大大减少了程序的bug。四、实验总结通过这次试验我熟悉了对链表的基本操作，对基本的链表操作有了很好的掌握，知道自己容易在什么地方出错。五、程序清单/实验一_1.

14、h#include iostream#include malloc.h#include stdlib.husing namespace std;#define MAXSIZE 100 /链表的最大长度typedef int elemtype;typedef struct STDelemtype elem;STD *next;list, * linklist;void zhujiemian() coutendlendl;cout【*数据结构实验一*】endl; cout【*】endlendl;cout【1 链表初始化】endl; cout【2清空链表】endl; cout【3求链表长度】endl

15、;cout【4链表是否为空】endl;cout【5检查链表是否为满】endl; cout【6遍历链表】endl;cout【7从链表中查找元素】endl;cout【8 从链表中查找与给定元素值相同的元素在表中的位置】endl;cout【9向链表中插入元素】endl;cout【10从链表中删除元素】endl;cout【其他键退出】endl;cout【*】endlendl;cout【*请选择要进行操作的序号（1-10）:*】next=NULL;L-elem=0;return 1;int insert(linklist &L, int i, elemtype e)linklist p, s;int j

16、 = 0;p = L;while (p&jnext;j +;if(ji-1|!p)return 0;s = (linklist)malloc(sizeof(list);s-elem = e;s-next = p-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&jnext;j+;if(ji-1|!(p-next)return 0;q=p-next;p-next=q-next;free(q);L-elem-;return 1;int is

17、empty(linklist L)if(L-next)return 1;elsereturn 0;void show(linklist L)linklist p;p=L-next;if(isempty(L)=0)cout链表为空！;while(p)coutelemnext;coutnext;int j=0;while(p)j+;p=p-next;return j;int makeempty(linklist &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(l

18、inklist 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)return j;p=p-next;return 0;int isfull(linklist L)if(L-elem a;coutendl;doswitch(a)case 1:if(init(L)=1)cout初始化成功！endl;elsecout初始化失败！endl;

19、break;case 2:if(makeempty(L)=1)cout链表已清空！endl;elsecout链表清空失败！endl;break;case 3:b=getlength(L);cout链表的长度为：bendl;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:show(L);break;case 7:coutb;if(find(L,b)=1)cout链表中有元素ben

20、dl;elsecout链表没中有元素bendl;break;case 8:cout您要查找的元素为：b;if(location(L,b)=0)cout没有您要查找的元素bendl;elsecout您查找的元素b在第location(L,b)个位置。endl;break;case 9:do cout输入你要插入的位置和元素bc;while (bgetlength(L)+1)cout插入位置错误！请重新插入！bc;if(insert(L,b,c)=0)cout您插入的位置不对，插入失败！endl;elsecout插入成功！endl;coutYES; while(YES=Y|YES=y);break

21、;case 10:do if(getlength(L)=0)cout链表为空无法删除！endl;break;cout输入你要删除元素的位置：b;while(bgetlength(L)cout输入错误！请重新输入！b;if(deleteelem(L,b)=0)cout您删除的位置不对，删除失败！endl;elsecout删除成功！endl;coutYES; while(YES=Y|YES=y);break;default:break;system(pause);system(cls);zhujiemian();cina;cout0&a=10);return 0;题目二 约瑟夫环问题一、循环链表的

22、结点类型定义/* 单链表的结点类型 */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;coutm;L=new List;L-number=1;L-cipher=m;L-next=L

23、;for(i=2;i=n;i+)ListLink lpp;cout输入第im;lpp=new List;lpp-number=i;lpp-cipher=m;lpp-next=L-next;L-next=lpp;L=L-next;coutnext;三、循环链表的长度/* 函数功能:求循环链表的长度。参数;链表(linklist L) 通过各个扫描求循环链表长度 */int ListLength(ListLink L)ListLink lpp;if(L=NULL)coutnext;while(lpp!=L)i+;lpp=lpp-next;return i;四、显示循环链表/*函数功能:循环链表的显

24、示。参数;链表(linklist L) 。通过各个扫描各个节点输出各个节点的密码 */void ListTraverse(ListLink L)ListLink lpp;lpp=L;int i=1;cout输入第1个人的密码：ciphernext;while(lpp!=L)i+;cout输入第i个人的密码：ciphernext;coutendl;五、约瑟夫环实现/*函数功能:实现所有人的出列次序。参数;链表(linklist L) ，密码（int m）。每次要找到出列者的前驱，把出列者删除 */void ListTraverse(ListLink L)ListLink lpp;lpp=L;in

25、t i=1;cout输入第1个人的密码：ciphernext;while(lpp!=L)i+;cout输入第i个人的密码：ciphernext;coutendl;int ListLength(ListLink L)ListLink lpp;if(L=NULL)coutnext;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=ListLength(L);n0;n-)cou

26、t密码为：mendl;cout出列人的编号是：;for(int i=1;inext;coutnext-numbernext-cipher;l=lpp-next;lpp-next=l-next;delete l;函数调用及主函数设计：int main()int m,n;ListLink L;cout输入人数(一个大于0小于30的数)和密码(一个大于0的数)：nm;while(n30|m0)cout输入的数字不符合要求，请重新输入：nm;cout请输入n个人的密码：endl;InitList(L,n);coutn个人的密码分别为：endl;ListTraverse(L);coutn个人的出列密码和

27、编号分别是：endl;shixian(L,m);return 0;总结：main函数先调用初始化循环链表的的函数void init(linklist &L,int n)，然后将循环链表输出void show(linklist L)，最后调用可以使人出列的函数void Joseph(linklist &L,int m)。本程序可以很好地运行，具有一定的除错能力，输入数据时可以对其进行判断，减少程序出现bug的可能性。通过对本实验的操作，我熟悉了循环链表的基本操作，而且对循环链表的基本操作有了很好的掌握。程序清单#include iostream#include stdlib.husing namespace std;typedef struct nodeint number; /* 人的序号 */int cipher; /* 密码 */ struct node *next; /* 指向下