线性表的链式存储.docx
《线性表的链式存储.docx》由会员分享，可在线阅读，更多相关《线性表的链式存储.docx（17页珍藏版）》请在冰点文库上搜索。
线性表的链式存储
数据结构实验报告
专业:
班级:
姓名:
学号:
指导老师:
评分:
实验二线性表的链式存储
一、实验目的
1.掌握线性表的链式存储结构。
2.能熟练地利用链式存储结构实现线性表的基本操作。
3.能熟练地掌握链式存储结构中算法的实现。
二、实验内容
1.分别用头插法和尾插法建立带头结点的单链表。
2.实现单链表上的插入、删除、修改、查找、计数、输出等基本
操作。
3.解决约瑟夫问题：
假设有n个人按1、2、3、…、n的顺序围
成一圈，现在，从第s个人开始按1、2、3、…、m的顺序报数，数到m的人出圈，接着从出圈的下一个人开始重复此过程，直到所有人出圈为止。
试用循环链表解决这个问题。
三、算法描述
1.第1题、第2题的算法提示
先定义单链表的数据类型，然后将头插法和尾插法、插入、删除、修改、查找、计数、输出等基本操作都定义成单独的子函数形式，最后在主函数中调用，并将每一种操作前后的结果输出，以查看每一种操作的效果。
2.第3题的算法提示
首先将n个人的信息建立成一个单循环链表，链表中的每个结点信息就是每个人的编号（1～n）。
然后利用循环找到出圈人位置的结点，输出该结点的信息，再在链表中删除该结点，接着从删除的结点的后面重复此步骤，直到链表中剩下一个结点时停止循环，再把链表中的最后一个结点删除。
四.程序清单:
实验1,2：
//LinkList.h的代码为:
#include
usingnamespacestd;
structNode
{
intdata;
Node*next;
};
classLinkList
{
public:
LinkList（intn）;
LinkList（intn,intm）;
voidInsert（inti,intx）;
intDelete（inti）;
intLocate（intx）;
intLength（）;
voidChange（inti）;
voidPrintList（）;
private:
Node*first;
int*arr;
int*arr1;
};
//头插法
LinkList:
:
LinkList（intn）
{
first=newNode;
first->next=NULL;
arr=newint[n];
for（inti=0;i{
cout<<"请输入第"<";
cin>>arr[i];
Node*s=newNode;
s->data=arr[i];
s->next=first->next;
first->next=s;
}
}
//尾插法
LinkList:
:
LinkList（intn,intm）
{
first=newNode;
Node*r,*s;
r=first;
arr1=newint[n];
for（inti=0;i{
cout<<"请输入第"<";
cin>>arr1[i];
s=newNode;
s->data=arr1[i];
r->next=s;
r=s;
}
r->next=NULL;
}
//插入函数
voidLinkList:
:
Insert（inti,intx）
{
Node*p;
p=first;
intj=0;
while（p&&j{
p=p->next;
j++;
}
if（!
p）throw"位置异常";
else
{
Node*s=newNode;
s->data=x;
s->next=p->next;
p->next=s;
}
}
//删除函数
intLinkList:
:
Delete（inti）
{
Node*p;
p=first;
intj=0;
while（p&&j{
p=p->next;
j++;
}
if（!
p||!
p->next）throw"位置异常";
else
{
Node*s=newNode;
intx;
s=p->next;
x=s->data;
p->next=s->next;
deletes;
returnx;
}
}
//查找函数
intLinkList:
:
Locate（intx）
{
Node*p;
p=first->next;
intj=1;
while（p&&p->data!
=x）
{
p=p->next;
j++;
}
if（p）{cout<<"该元素的位置是:
";returnj;}
elsereturn0;
}
//修改函数
voidLinkList:
:
Change（inti）
{
Node*p;
p=first;
intj=0;
while（p&&j{
p=p->next;
j++;
}
if（!
p）throw"位置异常";
else
{
intx;
cout<<"请输入你要修改数据的值:
";
cin>>x;
p->next->data=x;
}
}
//计数函数
intLinkList:
:
Length（）
{
Node*p;
p=first->next;
intj=0;
while（p）
{
p=p->next;
j++;
}
returnj;
}
//输出函数
voidLinkList:
:
PrintList（）
{
Node*p;
p=first->next;
cout<<"该链表当前的数据元素有:
";
while（p）
{
cout<data<<"";
p=p->next;
}
cout<}
//主程序代码为:
#include
usingnamespacestd;
#include"LinkList.h"
voidmenu（）
{
intn;
inti;
intmm2=1;
while（mm2==1）
{
cout<<"\t\t\t\t1.头插法建立链表"<cout<<"\t\t\t\t2.尾插法建立链表"<cout<<"\t\t\t\t3.退出程序"<cout<<"请选择你建立链表的方式:
";
cin>>i;
system（"cls"）;
switch（i）
{
case1:
{
cout<<"请输入初始链表的长度:
";
cin>>n;
LinkListb（n）;
b.PrintList（）;
inti3,i4,i5,i6,i7;
intmm1=1;
while（mm1==1）
{
cout<<"\t\t\t\t1.插入数据"<cout<<"\t\t\t\t2.删除数据"<cout<<"\t\t\t\t3.查找数据"<cout<<"\t\t\t\t4.修改数据"<cout<<"\t\t\t\t5.查看长度"<cout<<"\t\t\t\t6.查看链表"<cout<<"\t\t\t\t7.完成操作"<intmm;
cout<<"请选择你需要的操作:
";
cin>>mm;
switch（mm）
{
case1:
{
cout<<"请输入你要插入数据的位置以及该数据的值:
"<cout<<"数据位置为:
";
cin>>i3;
cout<<"数据的值为:
";
cin>>i4;
try{
b.Insert（i3,i4）;
b.PrintList（）;
}
catch（char*s）{cout<break;
}
case2:
{
cout<<"请输入你要删除数据的位置:
";
cin>>i5;
try{
b.Delete（i5）;
b.PrintList（）;
}
catch（char*s）{cout<break;
}
case3:
{
cout<<"请输入你要查找的数据元素:
";
cin>>i6;
cout<break;
}
case4:
{
cout<<"请输入你要修改元素的位置:
";
cin>>i7;
try{
b.Change（i7）;
b.PrintList（）;
}
catch（char*s）{cout<break;
}
case5:
{
cout<<"当前该链表的长度为:
"<break;
}
case6:
b.PrintList（）;break;
case7:
mm1=0;mm2=1;break;
default:
{cout<<"输入错误,请重新输入1~6!
"<}
}
break;
}
case2:
{
cout<<"请输入初始链表的长度:
";
cin>>n;
LinkListc（n,3）;
c.PrintList（）;
cout<<"尾插法插入,删除,查找,修改等操作与头插法一致"<//menu（）;system（"cls"）;
break;
}
case3:
mm2=0;break;
default:
{cout<<"输入错误,请重新输入1,2或者3!
"<}
}
}
voidmain（）
{
menu（）;
system（"pause"）;
}
实验3求约瑟夫环问题：
//主程序代码为:
#include
usingnamespacestd;
#include"LinkList.h"
voidmain（）
{
intn;
cout<<"请输入人数:
";
cin>>n;
LinkLista（n）;
a.PrintList（）;
inti,j,k,m;//k为当前人数,m为出圈编号?
i为计数开始位置
cout<<"请输入出圈编号:
";
cin>>m;
while（m>=n||m<0）
{
cout<<"输入的值的范围是1~"<";
cin>>m;
}
cout<<"请输入计数开始的位置:
";
cin>>i;
while（i>n||i<0）
{
cout<<"输入的值的范围是1~"<";
cin>>i;
}
i=i-1;
k=n;
while（k>1）
{
j=0;
while（j{
i=i%k+1;
j++;
}
a.Delete（i）;
i=i-1;
k--;
cout<<"当前剩下的人的编号为:
";
a.PrintList（）;
}
cout<<"最后的一个人的编号为:
";
a.PrintList（）;
system（"pause"）;
}
//LinkList.h的程序代码为:
structNode
{
intdata;
Node*next;
};
classLinkList
{
public:
LinkList（intn）;
voidDelete（inti）;
voidPrintList（）;
private:
Node*first;
int*arr1;
};
LinkList:
:
LinkList（intn）
{
first=newNode;
Node*r,*s;
r=first;
for（inti=0;i{
s=newNode;
s->data=i+1;
r->next=s;
r=s;
}
r->next=NULL;
}
voidLinkList:
:
Delete（inti）
{
intj=0;
Node*p;
p=first;
while（p&&jnext;j++;}
if（!
p||!
p->next）throw"位置异常";
else
{
Node*s=newNode;
s=p->next;
p->next=s->next;
deletes;
}
}
voidLinkList:
:
PrintList（）
{
Node*p=newNode;
p=first->next;
while（p）
{
cout<data<<"";
p=p->next;
}
cout<}
心得体会:
通过这次链表的实验，锻炼了我的思考能力。
有不懂的，继续努力。
升级会员 