链表实验报告1

希望对大家有所帮助，多谢您的浏览！实验一线性表的基本操作实现及其应用一、实验目的1、熟练掌握线性表的基本操作在两种存储结构上的实现。2、会用线性链表解决简单的实际问题。二、实验内容题目一链表基本操作该程序的功能是实现单链表的定义和操作。该程序包括单链表结构类型以及对单链表操作的具体的函数定义和主函数。其中，程序中的单链表（带头结点）结点为结构类型，结点值为整型。单链表操作的选择以菜单形式出现，如下所示：pleaseinputtheoperation：1.初始化2.清空3.求链表长度4.检查链表是否为空5.检查链表是否为满6.遍历链表（设为输出元素）7.从链表中查找元素8.从链表中查找与给定元素值相同的元素在表中的位置9.向链表中插入元素10.从链表中删除元素其他键退出。。。。。题目二约瑟夫环问题设编号为1,2,3,……，n的n（n>0）个人按顺时针方向围坐一圈，每个人持有一个正整数密码。开始时任选一个正整数做为报数上限m,从第一个人开始顺时针方向自1起顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的下一个人开始重新从1报数。如此下去，直到所有人全部出列为止。令n最大值取30。要求设计一个程序模拟此过程，求出出列编号序列。structnode//结点结构{intnumber;/*人的序号*/intcipher;/*密码*/structnode*next;/*指向下一个节点的指针*/};三．实验步骤题目一链表基本操作（一）、数据结构与核心算法的设计描述1、单链表的结点类型定义/*定义DataType为int类型*/typedefintDataType;/*单链表的结点类型*/typedefstructLNode{DataTypedata;希望对大家有所帮助，多谢您的浏览！structLNode*next;}LNode,*LinkedList;2、初始化单链表LinkedListLinkedListInit(){〃函数功能：对链表进行初始化参数：链表(linklistL)成功初始化返回1,否则返回0}3、清空单链表voidLinkedListClear(LinkedList&L){//函数功能：把链表清空参数：链表(linklistL)成功清空链表返回1}检查单链表是否为空intLinkedListEmpty(LinkedListL){〃函数功能:判断链表是否为空参数：链表(linklistL)链表为空时返回0,不为空返回1}遍历单链表voidLinkedListTraverse(LinkedListL){〃函数功能:遍历链表，输出每个节点的elem值参数：链表(linklistL)通过循环逐个输出节点的elem值 }求单链表的长度intLinkedListLength(LinkedListL){//函数功能:返回链表的长度参数：链表(linklistL)函数返回链表的长度}从单链表表中查找元素LinkedListLinkedListGet(LinkedListL,inti){〃函数功能：从链表中查找有无给定元素参数;链表(linklistL),给定元素(inti)如果链表中有给定元素(i)则返回1,否则返回0}8、从单链表表中查找与给定元素值相同的元素在链表中的位置LinkedListLinkedListLocate(LinkedListL,DataTypex){//函数功能：从链表中查找给定元素的位置参数;链表(linklistL),给定元素(inti)如果链表中有给定元素i则返回元素的位置，没有则返回0}向单链表中插入元素voidLinkedListInsert(LinkedList&L,inti,DataTypex){//L为带头结点的单链表的头指针，本算法//在链表中第i个结点之前插入新的元素x}从单链表中删除元素voidLinkedListDel(LinkedList&L,DataTypex){删除以L为头指针的单链表中第i个结点}(二)、函数调用及主函数设计zhujiemian();cin>>a;do{switch(a)if(init(L)==1)cout<<”成功初始化！"<<endl;elsecout<<”初始化失败！"<<endl;break;if(makeempty(L)==1)cout<<〃链表已清空！〃<<endl;elsecout<<〃链表清空失败！〃<<endl;break;b=getlength(L);cout<<〃链表的长度为：〃<<b<<endl;break;if(isempty(L)==1)cout<<”链表不为空！"<<endl;elsecout<<〃链表为空！〃<<endl;break;if(isfull(L)==1)cout<<”链表不满！"<<endl;elsecout<<”链表已满！"<<endl;break;show(L);break;cout<<〃输入您要查找的元素：〃；cin>>b;if(find(L,b)==1)cout<<”链表中有该元素"<<b<<endl;elsecout<<〃链表中没有您要查找的元素〃<<b<<endl;break;cout<<〃您要查找的元素为：〃<<endl;cin>>b;if(location(L,b)==0)希望对大家有所帮助，多谢您的浏览！cout<<〃没有您要查找的元素〃<<b<<endl;elsecout<<〃您查找的元素〃<<b<<〃在第〃<<location(L,b)<<〃个位置。“<<endl;break;do{cout<<〃输入你要插入的位置和元素〃<<endl;cin>>b>>c;while(b<=0||b>getlength(L)+1){cout<<〃插入位置错误！请重新插入！〃<<endl;cin>>b>>c;)if(insert(L,b,c)==0)cout<<〃您插入的位置不对，插入失败！〃<<endl;else。。口它/已插入成功！"<<endl;cout<<〃按y或Y键继续插入，其他键则停止插入\/;cin>>YES;}while(YES=='Y'||YES=='y');break;do{if(getlength(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<<〃删除成功！〃<<endl;cout<<〃按Y或y键继续删除，其他键则停止删除！〃；cin>>YES;}while(YES=='Y'||YES=='y');break;default:break;}（三）、程序调试及运行结果分析程序首先要进行初始化，否则程序不能运行。进行初始化之后，可以进行链表的其他操作。（四）、实验总结链表的操作是C++中的重点，这次试验让我看到了对链表的操作能力，发现了不足之处。事实证明：只有不停的练习，实践，才能编号程序。四、程序清单//head.h#include"iostream"#include"stdlib.h"#include"windows.h"#include"malloc.h"usingnamespacestd;#defineMAXSIZE100typedefintelemtype;typedefstructSTD{elemtypeelem;STD*next;}list,*linklist;voidzhujiemian（）{cout<<"链表的基本操作"<<endlcout<<"######################################################"<<endlcout<<"#1链表初始化#"<<endlcout<<"#2清空链表#"<<endlcout<<"#3求链表长度#"<<endlcout<<"#4链表是否为空#"<<endlcout<<"#5检查链表是否为满#"<<endlcout<<"#6遍历链表#"<<endlcout<<"#7从链表中查找元素#"<<endlcout<<"#8从链表中查找与给定元素值相同的元素在表中位置#"<<endlcout<<"#9向链表中插入元素#"<<endlcout<<"#10从链表中删除元素#"<<endlcout<<"#其他键退出#"<<endlcout<<"######################################################"<<endlcout<<"请输入您要进行操作的序号（1-10）:";}intinit(linklist&L){L=(linklist)malloc(sizeof(list));if(!L)return0;L->next=NULL;L->elem=0;return1;}intinsert(linklist&L,inti,elemtypee){linklistp,s;intj=0;p=L;while(p&&j<i-1){p=p->next;j++;}if(j>i-1||!p)return0;s=(linklist)malloc(sizeof(list));s->elem=e;s->next=p->next;p->next=s;L->elem++;return1;}intdeleteelem(linklist&L,inti){linklistp,q;intj=0;p=L;while(p->next&&j<i-1){p=p->next;j++;希望对大家有所帮助，多谢您的浏览！if(j>i-1||!(p->next))return0;q=p->next;p->next=q->next;free(q);L->elem--;return1;}intisempty(linklistL){if(L->next)return1;elsereturn0;}voidshow(linklistL){linklistp;p=L->next;if(isempty(L)==0){cout<<"链表为空！";}while(p){cout<<p->elem<<"";p=p->next;}cout<<endl;}intgetlength(linklistL){linklistp;p=L->next;intj=0;while(p){j++;p=p->next;}returnj;}intmakeempty(linklist&L){linklistp,q;p=L->next;while(p){q=p;p=p->next;free(q);}L->next=NULL;L->elem=0;return1;}intfind(linklistL,inti){linklistp;p=L->next;while(p){if(p->elem==i)return1;p=p->next;}return0;}intlocation(linklistL,inti){linklistp;intj=0;p=L->next;while(p){j++;if(p->elem==i)returnj;p=p->next;}return0;}intisfull(linklistL){if(L->elem<=MAXSIZE)return1;elsereturn0;}//main.cpp#include"iostream"#include"malloc.h"#include"stdlib.h"#include"windows.h"#include"header.h"usingnamespacestd;intmain(){charYES;linklistL;inta,b,c;zhujiemian();cin>>a;cout<<endl;do{switch(a){if(init(L)==1)cout<<"成功初始化！"<<endl;elsecout<<"初始化失败！"<<endl;break;if(makeempty(L)==1)cout<<"链表已清空！"<<endl;elsecout<<〃链表清空失败！〃<<endl;break;b=getlength(L);cout<<〃链表的长度为：〃<<b<<endl;break;if(isempty(L)==1)cout<<”链表不为空！"<<endl;elsecout<<〃链表为空！〃<<endl;break;if(isfull(L)==1)cout<<”链表不满！"<<endl;elsecout<<”链表已满！"<<endl;break;show(L);break;cout<<〃输入您要查找的元素：〃；cin>>b;if(find(L,b)==1)cout<<”链表中有该元素"<<b<<endl;elsecout<<〃链表中没有您要查找的元素〃<<b<<endl;break;cout<<〃您要查找的元素为：〃<<endl;cin>>b;if(location(L,b)==0)cout<<〃没有您要查找的元素〃<<b<<endl;elsecout<<〃您查找的元素〃<<b<<〃在第〃<<location(L,b)<<〃个位置。“<<endl;break;do{cout<<〃输入你要插入的位置和元素〃<<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键继续插入，其他键则停止插入\十;cin>>YES;}while(YES=='Y'||YES=='y');break;do{if(getlength(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<<〃删除成功！〃<<endl;cout<<〃按Y或y键继续删除，其他键则停止删除！〃;cin>>YES;}while(YES=='Y'||YES=='y');break;default:break;}system("pause");system("cls");zhujiemian();cin>>a;}while(a>0&&a<=10);return0;}题目二约瑟夫环问题三、实验步骤(一)、数据结构与核心算法的设计描述1、单链表的结点类型定义typedefstructnode{intnumber;intcipher;structnode*next;}list,*linklist;2、初始化单链表voidinit(linklist&L,intn){//函数功能:初始化n个元素的循环链表参数:链表(linklistL),元素个数(intn)通过后插法对无头结点的链表初始化}3、循环链表的长度intsize(linklistL){//函数功能:求循环链表的长度参数:链表(linklistL)通过各个扫描求循环链表长度}4、显示循环链表voidshow(linklistL){//函数功能:循环链表的显示参数:链表(linklistL)通过各个扫描各个节点输出各个节点的密码}5、约瑟夫环实现voidJoseph(linklist&L,intm){//函数功能:实现所有人的出列次序参数:链表(linklistL)，密码(intm)每次要找到出列者的前驱，把出列者删除}(二)、函数调用及主函数设计intmain(){intn,m;希望对大家有所帮助，多谢您的浏览！cout<<"请输入人数(1-30)和报数上线(大于0)"<<endl;cin>>n>>m;while(n<=0||n>30||m<=0){cout<<"输入错误，请重新输入人数(1-30)和报数上线(大于0)"<<endl;cin>>n>>m;}linklistL;cout<<"请输入"<<*<"个人的密码"<<endl;init(L,n);cout<<n<<”个人的密码："<<endl;show(L);cout<<n<<"个人的出列密码和编号为："<<endl;Joseph(L,m);return0;}(三)、程序调试及运行结果分析main函数先调用初始化循环链表的的函数voidinit(linklist&L,intn)，然后将循环链表输出voidshow(linklistL)，最后调用可以使人出列的函数voidJoseph(linklist&L,intm)。(四)、实验总结链表的操作是C++中的重点，这次试验让我看到了对链表的操作能力，发现了不足之处。事实证明：只有不停的练习，实践，才能编号程序。四、程序清单#include"iostream"#include"stdlib.h"usingnamespacestd;typedefstructnode{intnumber;intcipher;structnode*next;}list,*linklist;voidinit(linklist&L,intn){intkey,i;cout<<"输入第1个人的密码为："；cin>>key;L=newlist;L->number=1;L->cipher=key;L->next=L;for(i=2;i<=n;i++){希望对大家有所帮助，多谢您的浏览！linklistp=newlist;cout<<〃输入第〃<<i<<〃个人的密码为：〃；cin>>key;p->cipher=key;p->number=i;p->next=L->next;L->next