实验一线性表的基本操作实现及其应用.docx
《实验一线性表的基本操作实现及其应用.docx》由会员分享，可在线阅读，更多相关《实验一线性表的基本操作实现及其应用.docx（28页珍藏版）》请在冰点文库上搜索。
实验一线性表的基本操作实现及其应用
实验一线性表的基本操作实现及其应用
一、实验目的
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、单链表的结点类型定义
/*预处理命令*/
#defineOK1;
#defineERROR0;
#defineOVERFLOW-1;
/*定义DataType,status为int类型*/
typedefintDataType;
typedefintstatus;
/*单链表的结点类型*/
typedefstructLNode
{
DataTypedata;
structLNode*next;
}LNode,*LinkedList;
2、初始化单链表
LinkedListLinkedListInit（）
{//定义并返回头结点L
}
3、清空单链表
voidLinkedListClear（LinkedListL）
{
//L是带头结点的链表的头指针,释放除头结点外的所有内存空间
}
4．检查单链表是否为空
intLinkedListEmpty（LinkedListL）
{
//L是带头结点的链表的头指针,判断头结点的next是否为空,如果空//返回OK，否则返回ERROR
}
5、遍历单链表
voidLinkedListTraverse（LinkedListL）
{
//L是带头结点的链表的头指针,遍历并输出L所有结点（不包括头//结点）的数据
}
6、求单链表的长度
intLinkedListLength（LinkedListL）
{
//L是带头结点的链表的头指针，通过遍历链表用i记录结点个数（不//包括头结点），并返回i
}
7、从单链表表中查找元素
LinkedListLinkedListGet（LinkedListL,inti）
{
//L是带头结点的链表的头指针,返回第i个元素
}
8、从单链表表中查找与给定元素值相同的元素在链表中的位置（位置）
intLinkedListGet1（LinkedListL,DataTypex）
{
//L是带头结点的链表的头指针,返回值为x元素在链表中的位置的//位置
}
9、从单链表表中查找与给定元素值相同的元素在链表中的位置（指针）
LinkedListLinkedListLocate（LinkedListL,DataTypex）
{
//L是带头结点的链表的头指针,返回值为x元素的指针
}
10、向单链表中插入元素
statusLinkedListInsert（LinkedListL,inti,DataTypex）
{
}
（二）函数调用及主函数设计
图1.主函数流程图
（三）程序调试及运行结果分析
1．进入选择界面后，先选择7，进行插入：
2.选择4，进行遍历，结果为：
3.选择2，得出当前链表长度.
4.选择3，得出当前链表为.
5.选择分别选择5、6进行测试.
6.选择8，分别按位置和元素值删除.
7.选择9，或非1-8的字符，程序结束.
（四）实验总结
通过这次实验，我对线性链表有了更深的理解，深入明白了线性存储结构与链式存储结构在内存存储的不同特点，同时我还学会了用这些知识实际解决一些问题，能够更加熟练地将算法转化为实际程序。
同时，在写程序和调试程序的过程中，学会了一些书写技巧和调试技巧，这对于自己能在短时间高效的写出正确地程序有很大作用。
四、主要算法流程图及程序清单
1.主要算法流程图：
（1）从单链表表中查找与给定元素值相同的元素在链表中的位置
2.程序清单：
#include
usingnamespacestd;
#include
#include
/*预处理命令*/
#defineOK1;
#defineERROR0;
#defineOVERFLOW-1;
/*单链表的结点类型*/
typedefstructLNode
{
intdata;
structLNode*next;
}LNode,*LinkedList;
/*初始化单链表*/
LinkedListLinkedListInit（）
{
//定义并返回头结点
LinkedListL;
L=（LinkedList）malloc（sizeof（LNode））;
L->next=NULL;
returnL;
}
/*清空单链表*/
voidLinkedListClear（LinkedListL）
{
//释放除头结点外的所有内存空间
LinkedListp=L->next,q;
L->next=NULL;
while（p）
{
q=p->next;
free（p）;
p=q;
}
cout<<"\t\t\t已清空！
"<}
/*检查单链表是否为空*/
intLinkedListEmpty（LinkedListL）
{
//判断头结点的next是否为空,如果空返回OK，否则返回ERROR
if（!
（L->next））
returnOK;
returnERROR;
}
/*遍历单链表*/
voidLinkedListTraverse（LinkedListL）
{
//遍历并输出L所有结点（不含头结点）的数据
LinkedListp=L->next;
if（!
p）
{
cout<<"\t\t\t链表为空！
"<}
cout<<"\t\t";
while（p）
{
cout<data<<"\t";
p=p->next;
}
cout<}
/*求单链表的长度*/
intLinkedListLength（LinkedListL）
{
//通过遍历链表用i记录结点个数（不含头结点），并返回i
LinkedListp=L->next;
inti=0;
while（p）
{
i++;
p=p->next;
}
returni;
}
/*从单链表表中查找元素*/
LinkedListLinkedListGet（LinkedListL,inti）
{
//L是带头结点的链表的头指针,返回第i个元素
LinkedListp=L->next;
intj=1;
while（j{
p=p->next;
j++;
}
if（!
p）
{
returnNULL;
}
returnp;
}
/*从链表中查找与给定元素值相同的元素在表中的位置,返回位置*/
intLinkedListGet1（LinkedListL,intx）
{
//L是带头结点的链表的头指针,返回值为x元素的位置
LinkedListp=L->next;
inti=1;
while（p&&!
（p->data==x））
{
i++;
p=p->next;
}
if（!
p）
{
return0;
}
returni;
}
/*从单链表表中查找与给定元素值相同的元素在链表中的位置*/
LinkedListLinkedListLocate（LinkedListL,intx）
{
//L是带头结点的链表的头指针,返回值为x元素的指针
LinkedListp=L->next;
while（p&&!
（p->data==x））
{
p=p->next;
}
if（!
p）
{
returnNULL;
}
returnp;
}
/*向单链表中插入元素*/
intLinkedListInsert（LinkedListL,inti,intx）
{
//L为带头结点的单链表的头指针，本算法
//在链表中第i个结点之前插入新的元素x
LinkedLists=（LinkedList）malloc（sizeof（LNode））;
s->data=x;
LinkedListp=L->next,q;
if（i==1）
{
if（p==NULL）
{
L->next=s;
s->next=NULL;
returnOK;
}
else
{
L->next=s;
s->next=p;
returnOK;
}
}
intj=1;
while（j{
p=p->next;
j++;
}
if（!
p）
{
free（s）;
returnERROR;
}
q=p->next;
p->next=s;
s->next=q;
returnOK;
}
/*从单链表中删除元素*/
intLinkedListDel（LinkedListL,intx）
{
//删除以L为头指针的单链表中值为x结点
LinkedListp=L->next,q=L;
while（p&&!
（p->data==x））
{
q=p;
p=p->next;
}
if（!
p）
{
returnERROR;
}
q->next=p->next;
free（p）;
returnOK;
}
intLinkedListDel（LinkedListL,inti,int&x）
{
//删除以L为头指针的单链表中第i个结点,并返回x的值
LinkedListp=L->next,q=L;
intj=1;
while（j<=i-1&&p）
{
q=p;
p=p->next;
j++;
}
if（!
p）
{
x=0;
returnERROR;
}
q->next=p->next;
x=p->data;
free（p）;
returnOK;
}
/*菜单显示*/
voidScreenShow（）
{
cout<<"\t\t\t"<<"1.清空"<cout<<"\t\t\t"<<"2.求链表长度"<cout<<"\t\t\t"<<"3.检查链表是否为空"<cout<<"\t\t\t"<<"4.遍历链表"<cout<<"\t\t\t"<<"5.从链表中查找元素"<cout<<"\t\t\t"<<"6.从链表中查找与给定元素值相同的元素在表中的位置"<cout<<"\t\t\t"<<"7.向链表中插入元素"<cout<<"\t\t\t"<<"8.从链表中删除元素"<cout<<"\t\t\t"<<"9.退出"<}
/*主函数*/
intmain（）
{
//初始化链表
inti=1;
LinkedListL=LinkedListInit（）;
if（L）
{
cout<<"\t\t\t初始化成功！
\n"<}
//显示菜单
ScreenShow（）;
//进行选择，当选择为1-8时，进行对应功能函数调用，否则退出程序
while（i>=1&&i<=8）
{
cout<<"\t\t"<<"请选择：
";
cin>>i;
switch（i）
{
//1、清空链表
case1:
LinkedListClear（L）;break;
//2.求链表长度
case2:
{
cout<<"\t\t\t链表长度为：
"<getch（）;
}
break;
//3.检查链表是否为空
case3:
{
if（!
LinkedListEmpty（L））
{
cout<<"\t\t\t链表不为空！
"<}
else
{
cout<<"\t\t\t链表为空！
"<}
getch（）;
}
break;
//4.遍历链表
case4:
{
LinkedListTraverse（L）;
getch（）;
}
break;
//5.从链表中查找元素
case5:
{
cout<<"\t\t\t请输入要查询的位置i：
";
intj;
cin>>j;
if（LinkedListGet（L,j））
{
cout<<"\t\t\t位置i的元素值为：
"<data<}
else
{
cout<<"\t\t\ti大于链表长度！
"<}
getch（）;
}
break;
//6.从链表中查找与给定元素值相同的元素在表中的位置
case6:
{
cout<<"\t\t\t请输入要查找的元素值：
";
intb;
cin>>b;
if（LinkedListGet1（L,b））
{
cout<<"\t\t\t要查找的元素值位置为：
"<cout<<"\t\t\t要查找的元素值内存地址为：
"<}
else
{
cout<<"\t\t\t该值不存在！
"<}
getch（）;
}
break;
//7.向链表中插入元素
case7:
{
cout<<"\t\t\t请输入要插入的值：
";intx;cin>>x;
cout<<"\t\t\t请输入要插入的位置：
";intk;cin>>k;
if（LinkedListInsert（L,k,x））
{
cout<<"\t\t\t插入成功！
"<}
else
{
cout<<"\t\t\t插入失败！
"<}
getch（）;
}
break;
//8.从链表中删除元素
case8:
{
cout<<"\t\t\t1.按位置删除"<cout<<"\t\t\t2.按元素删除"<intd;
cout<<"\t\t请选择：
";cin>>d;
switch（d）
{
case1:
{
cout<<"\t\t\t请输入删除位置：
";
cin>>d;
inty;
if（LinkedListDel（L,d,y））
{
cout<<"\t\t\t"<"<}
else
{
cout<<"\t\t\t删除失败！
"<}
}break;
case2:
{
cout<<"\t\t\t请输入删除元素：
";
inty;
cin>>y;
if（LinkedListDel（L,y））
{
cout<<"\t\t\t"<"<}
else
{
cout<<"\t\t\t删除失败！
"<}
}
}
getch（）;
}
break;
}
}
return1;
}
题二约瑟夫环问题
算法、思想
为了解决这一问题，可以先定义一个长度为30（人数）的数组作为线性存储结构，并把该数组看成是一个首尾相接的环形结构，那么每次报m的人，就要在该数组的相应位置做一个删除标记，该单元以后就不再作为计数单元。
这样做不仅算法较复杂，而且效率低，还要移动大量的元素。
用单循环链表来解决这一问题，实现的方法相对要简单得的多。
首先定义链表结点，单循环链表的结点结构与一般单链表的结点结构完全相同，只是数据域用一个整数来表示位置；然后将它们组成一个具有n个结点的单循环链表。
接下来从位置为1的结点开始数，数到第m个结点，就将此结点从循环链表中删去，然后再从删去结点的下一个结点开始数起，数到第m个结点，再将其删去，如此进行下去，直至全部删去为止。
代码分析
（一）创建单循环链表
structLink
{
intData;
Link*next;
};
Link*Creat（intn）
{
Link*head,*s,*r;
head=newLink;
r=head;
for（inti=0;i{
s=newLink;
cin>>s->Data;
r->next=s;
r=s;
}
r->next=head->next;
returnhead;
}
（二）“约瑟夫环”的操作模块；
Link*Jose（Link*p,intm）
{
ints=m;
if（p==p->next）
returnp;//递归出口即循环链表只剩下一个结点，将该结点指针返回
Link*q=NULL;//指针q用来保存删除结点的前驱
for（intj=1;j{
q=p;
p=p->next;
}//查找要删除结点
q->next=p->next;//删除节点
cout<Data<<"";//输出结点序号
Jose（p->next,s）;//递归调用
}
（三）主程序
intmain（）
{
cout<<"请输入Jose环中人数：
";
intn,m;
cin>>n;
cout<<"请输入每个人手中的序号：
"<Link*head=Creat（n）;
cout<<"请输入报数的数值";
cin>>m;
Link*p=head->next;
cout<cout<<"离开的序号依次是：
";
Link*Result=Jose（p,m）;
cout<Data<return0;
}
测试数据
调试分析
1、早期程序只写了约瑟夫环的实现部分，没有对输入数据进行筛选，调试的时候会经常出错。
比如是输入字母，或者输入0，大于32767溢出；
2、早期的循环过程中没有进行优化，导致循环次数过多，浪费时间；
3、为了输出时美观，分别在input和main函数主体内做了两次，输入非零的判断，浪费了资源；
4、算法的时空分析
为了限制在输入过程中不会上溢，只在输入中限定为四个不全为零的数字，但是做的是do……while循环，复杂度为o
（1）;
当n大于1时：
在数据输入中，链表的创建是for循环，时间复杂度为o（n-1）
在约瑟夫环实现程序中，为for循环。
时间复杂度为o（m%n-1）
当n=1时，复杂度为o
（1）。
实验心得
1、巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。
2、培养了我选用参考书，查阅手册及文献资料的能力。
培养独立思考，深入研究，分析问题、解决问题的能力。
3、通过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。
4、通过课程设计，培养了我严肃认真的工作作风，逐步建立正确的生产观念、经济观念和全局观念。
升级会员 