线性表实验报告.docx
《线性表实验报告.docx》由会员分享,可在线阅读,更多相关《线性表实验报告.docx(24页珍藏版)》请在冰点文库上搜索。
线性表实验报告
一.实验名称
1.线性表基本操作;2.处理约瑟夫环问题
二.试验目的:
1.熟悉C语言的上机环境,掌握C语言的基本结构。
2.定义单链表的结点类型。
3.熟悉对单链表的一些基本操作和具体的函数定义。
4. 通过单链表的定义掌握线性表的链式存储结构的特点。
5.熟悉对单链表的一些其它操作。
三.实验内容
1.编制一个演示单链表初始化、建立、遍历、求长度、查询、插入、删除等操作的程序。
2.编制一个能求解除约瑟夫环问题答案的程序。
实验一线性表表的基本操作
问题描述:
1.实现单链表的定义和基本操作。
该程序包括单链表结构类型以及对单链表操作的具体的函数定义
程序中的单链表(带头结点)结点为结构类型,结点值为整型。
/*定义DataType为int类型*/
typedefintDataType;
/*单链表的结点类型*/
typedefstructLNode
{DataTypedata;
structLNode*next;
}LNode,*LinkedList;
LinkedListLinkedListInit()//初始化单链表
voidLinkedListClear(LinkedListL)//清空单链表
intLinkedListEmpty(LinkedListL)//检查单链表是否为空
voidLinkedListTraverse(LinkedListL)//遍历单链表
intLinkedListLength(LinkedListL)//求单链表的长度
/*从单链表表中查找元素*/
LinkedListLinkedListGet(LinkedListL,inti)
/*从单链表表中查找与给定元素值相同的元素在链表中的位置*/
intLinkedListLocate(LinkedListL,DataTypex)
voidLinkedListInsert(LinkedListL,inti,DataTypex)//向单链表中插入元素
/*从单链表中删除元素*/
voidLinkedListDel(LinkedListL,DataTypex)
/*用尾插法建立单链表*/
LinkedListLinkedListCreat()
2.约瑟夫环问题:
任给正整数N和K,按下述方法可以得到1,2,…,n的一个置换,将数字1,2,…,n环形排列,按顺时针方向自1开始报数,报到K时输出该位置上的数字,并使其出列。
然后从他在顺时针方向的下一个数字继续报数,如此下去,直到所有的数字全部出列为止。
例如N=10,K=3,则正确的出列顺序应为3,6,9,2,7,1,8,5,10,4。
3.试单链表实现一个简单的电子通讯本管理软件,要求能查找联系地址,增加和删除联系人。
联系方式假定包括姓名、电话和地址。
基本要求:
1.上机前要做好准备工作,包括程序框图、数据结构以及算法。
2.按时实验
3.服从实验室老师的安排
4.独立实验,有问题可以讨论,但不得翻版。
5.遵守实验室的各项纪律。
四、概要设计
1.单链表的操作
(1)为了实现上述程序功能,需要定义单链表的抽象数据类型:
ADT LinkedList {
数据对象:
D={ai|ai∈struct LNode set,i=0,1,2,…,n,n≥0}
数据关系:
R={|ai,ai+1 ∈D}
基本操作:
LinkedListInit()
操作结果:
构造了一个带头节点的空链表L;
LinkedListCreat()
初始条件:
单链表L已存在;
操作结果:
建立了一个带头节点的非空链表;
LinkedListClear(&L)
初始条件:
单链表L已存在;
操作结果:
将L重置为带头节点的空链表;
LinkedListEmpty(&L)
初始条件:
单链表L已存在;
操作结果:
如果链表L为空则返回1,链表L非空则返回0;
LinkedListLength(&L)
初始条件:
单链表L已存在;
操作结果:
返回单链表L中数据元素的个数,若L为空表则返回0;
LinkedListTraverse(&L)
初始条件:
单链表L已存在;
操作结果:
依次返回单链表L中各节点的元素值,若L为空表则显示链表为空;
LinkedListGet(&L,i)
初始条件:
单链表L已存在;
操作结果:
显示链表L中第i个节点个元素值,若链表L中没有第i个节点则显示查询位置不正确;
LinkedListLocate(&L,x)
初始条件:
单链表L已存在;
操作结果:
显示链表L中元素x的位置,若链表L中没有元素x则显示所查找元素不存在;
LinkedListInsert(&L,i,x)
初始条件:
单链表L已存在;
操作结果:
在单链表L第i个节点后插入一个元素值为x的节点,L的长度加1,若单链表L中没有第i个节点则显示插入位置不正确;
LinkedListDel(&L,i)
初始条件:
单链表L已存在;
操作结果:
在单链表L中删除第i个节点,L的长度减1,若单链表L中没有第i个节点则显示删除位置不正确;
(2)本程序包含11个函数:
1. 主函数main()
2. 初始化单链表函数LinkListInit()
3. 清空单链表函数LinkedListClear()
4. 检查单链表是否为空函数LinkedListEmpty()
5. 遍历遍历单链表函数LinkedListTraverse()
6. 求单链表的长度函数LinkedListLength()
7. 从单链表表中查找元素函数LinkedListGet()
8 从单链表表中查找指定元素的位序函数LinkedListLocate()
9. 插入元素函数LinkedListInsert()
10. 删除元素函数LinkedListDel()
11.建立单链表函数LinkedListCreat( )
各函数之间的关系:
五.详细设计
1结点类型和指针类型
typedefstructLNode
{intdata;
structLNode*next;
}LNode,*LinkedList;
2单链表的基本操作
(1)初始化单链表
LinkedListLinkedListInit()
{LinkedListL;
L=(LinkedList)malloc(sizeof(LNode));
L->next=NULL;
returnL;
}
(2)清空单链表
voidLinkedListClear(LinkedListL)
{L->next=NULL;
printf("链表已经清空\n");
}
(3)检查单链表是否为空
intLinkedListEmpty(LinkedListL)
{if(L->next==NULL)returnTRUE;
elsereturnFALSE;
}
(4)遍历单链表
voidLinkedListTraverse(LinkedListL)
{LinkedListp;
p=L->next;
if(p==NULL)printf("单链表为空表\n");
else
{printf("链表中的元素为:
\n");
while(p!
=NULL)
{printf("%d",p->data);p=p->next;}
}
printf("\n");
}
(5)求单链表长度
intLinkedListLength(LinkedListL)
{LinkedListp;
intj;
p=L->next;
j=0;
while(p!
=NULL)
{j++;p=p->next;}
returnj;
}
(6)从链表中查找元素
LinkedListLinkedListGet(LinkedListL,inti)
{LinkedListp;intj;
p=L->next;j=1;
while(p!
=NULL&&j
{p=p->next;j++;}
if(j==i)returnp;
elsereturnNULL;
}
(7)从链表中查找与给定元素值相同的元素在顺序表中的位置
intLinkedListLocate(LinkedListL,intx)
{LinkedListp;intj;
p=L->next;j=1;
while(p!
=NULL&&p->data!
=x)
{p=p->next;j++;}
if(p)returnj;
elsereturn0;
}
(8)向链表中插入元素
voidLinkedListInsert(LinkedListL,inti,intx)
{LinkedListp,s;
intj;
j=1;p=L;
while(p&&j
{p=p->next;j++;}
if(p==NULL||j>i)
printf("插入位置不正确\n");
else{s=(LNode*)malloc(sizeof(LNode));
s->data=x;
s->next=p->next;
p->next=s;
printf("%d已插入到链表中\n",x);
}
}
(9)从链表中删除元素
voidLinkedListDel(LinkedListL,inti)
{LinkedListp,q;
intj;
j=1;p=L;
while(p->next&&j
{p=p->next;j++;}
if(p->next==NULL)
printf("删除位置不正确\n");
else{q=p->next;p->next=q->next;free(q);
printf("第%d个元素已从链表中删除\n",i);
}
}
(10)建立单链表
LinkedListLinkedListCreat()
{LinkedListL=LinkedListInit(),p,r;
intx;
r=L;
printf("请依次输入链表中的元素,输入负数时结束\n");
scanf("%d",&x);
while(x>=0)
{p=(LinkedList)malloc(sizeof(LNode));
p->data=x;
r->next=p;
r=p;
scanf("%d",&x);
}
r->next=NULL;
returnL;
}
(11) 主函数
main()
{
inti,h,d,e,x,j,n,q;
charch;
LinkedListL,p;
while(q!
=0){
printf("请选择要进行的操作\n");
printf("1.初始化2.清空3.求链表长度4.检查链表是否为空\n");
printf("5.遍历链表6.从链表中查找元素\n");
printf("7.从链表中查找与给定元素值相同的元素在顺序表中的位置\n");
printf("8.向链表中插入元素9.从链表中删除元素\n");
printf("10.建立单链表\n");
printf("按其它键结束\n");
scanf("%d",&x);
switch(x)
{case1:
L=LinkedListInit();printf("链表已经初始化\n");break;
case2:
LinkedListClear(L);printf("\n");break;
case3:
printf("链表的长度为%d\n",LinkedListLength(L));break;
case4:
i=LinkedListEmpty(L);if(i)printf("链表为空\n");elseprintf("链表非空\n");break;
case5:
LinkedListTraverse(L);break;
case6:
printf("请输入待查询元素在链表中的位置:
");
scanf("%d",&j);
p=LinkedListGet(L,j);
if(p)printf("链表中第%d个元素的值为:
%d\n",j,p->data);
elseprintf("查询位置不正确\n");
break;
case7:
printf("请输入待查询元素的值:
");
scanf("%d",&e);
h=LinkedListLocate(L,e);
if(h)
printf("%d在链表中的位置是:
%d\n",e,h);
elseprintf("链表中没有值为%d的元素\n",e);
break;
case8:
printf("请输入插入元素的位置和值(中间以空格或回车分隔):
\n");
scanf("%d%d",&d,&e);
LinkedListInsert(L,d,e);
break;
case9:
if(LinkedListLength(L)==0)
printf("链表已经为空,不能删除\n");
else{printf("请输入待删除元素的位置:
\n");
scanf("%d",&n);
LinkedListDel(L,n);}
break;
case10:
L=LinkedListCreat();
printf("\n");break;
default:
q=0;}
}
}
六.测试结果
1、单链表的操作
(1)建立单链表:
选择1,然后选择10,输入1.2.3.4.5.6.7.8.9最后一个负数
(2)求链表长度:
选择3,得到执行结果:
链表的长度为9
(3)检查链表是否为空:
选择4,得到执行结果:
单链表非空
(4)遍历链表:
选择5,得到执行结果:
链表中的元素为 1,2,3,4,5,6,7,8,9,
(5) 从链表中查找元素:
选择6,输入5,显示:
链表中第5个元素的值为5
(6) 从链表中查找与给定元素值相同的元素在顺序表中的位置
选择7,输入2,显示:
2在链表中的位置是:
2
选择7,输入25,显示:
链表中没有值为25的元素
(7) 向链表中插入元素
选择8,输入(6,5),显示 5以插入到链表中
选择5:
链表中的元素为 1,2,3,4,5,5,6,7,8,9,
(8) 从链表中删除元素
选择9,输入5,显示 第5个元素已从表中删除
选择9,输入12,显示 删除位置不正确
选择5,显示 链表中的元素为 链表中的元素为 1,2,3,4,5,6,7,8,9,
实验二约瑟夫环
1.问题描述
设有编号1,2,3。
。
。
n(n>0)的N个人围成一个圈,每个人持有一个密码(正整数)。
开始时从第k(1<=k<=n)个人按顺时针方向自1开始顺序报数,报到m(m为第K个人的密码)的人出圈,再以这个人顺时针方向上的下一个人的密码为m,并开始重新从1报数。
如此下去,直至所有人全部出列为止。
试设计一个程序求出出列顺序。
例如,设总人数n的初值为8,他们所持的密码分别为:
3,10,7,1,4,8,4,5,开始报数人的编号k的初值为7,则出列顺序为:
2,1,3,4,8,5,7,6
2.数据结构设计
问题中以序号标示某个人,所以结点的数据域设为一个整型类型的变量
当某人出圈后,报数的工作要从下一个人开始继续,剩下的人仍然围成一圈,可以使用循环表。
由于出圈的人将不再属于圈内,意味着数据元素的删除。
因此,算法中存有频繁的元素删除操作,存储结构宜采用链表。
每个结点中既存储密码还存储初始位置,所以结点有两个数据域,一个指针域。
另外,每个结点代表一个人所以,可以令尾结点指针指向首元结点来进行循环。
//结点类
template
structNode
{
//数据成员:
ElemTypedata;
ElemTypenum;//数据域
Node*next;//指针域
//构造函数:
Node();//无参数的构造函数
Node(ElemTypeitem,ElemTypeitem1,Node*link=NULL);//已知数数据元素值和指针建立结构
};
//结点类的实现部分
template
Node:
:
Node()
//操作结果:
构造指针域为空的结点
{
next=NULL;
}
template
Node:
:
Node(ElemTypeitem,ElemTypeitem1,Node*link)
//操作结果:
构造一个数据域为item和item1,指针域为link的结点
{
data=item;
num=item1;
next=link;
}#endif
3.算法设计
编写一个函数实现结点的删除与输入工作,另编写一个主函数main()完成链表的创建与函数调用工作。
(1)插入
template
StatusLinkList:
:
Insert(intposition,constElemType&e)
//操作结果:
在线性表的第position个位置前插入元素e
//position的取值范围为1≤position≤Length()+1
//position合法时返回SUCCESS,否则函数返回RANGE_ERROR
{
if(position<1||position>Length()+1)
{//position范围错
returnRANGE_ERROR;//位置不合法
}
else
{//position合法
Node*tmpPtr;
//取出指向第position-1个结点的指针
tmpPtr=GetElemPtr(position-1);
Node*newPtr;
if(position>Length())
//如果插入尾结点,则域指针指向首元结点
newPtr=newNode(e,position,head->next);
else
newPtr=newNode(e,position,tmpPtr->next);//生成新结点
tmpPtr->next=newPtr;//将tmpPtr插入到链表中
curPosition=position;//设置当前位置的序号
curPtr=newPtr;//设置指向当前位置的指针
count++;//插入成功后元素个数加1
returnSUCCESS;
}
}
(2)删除
template
StatusLinkList:
:
Delete(intposition,ElemType&e)
//操作结果:
删除线性表的第position个位置的元素,并用e返回其值,
//position的取值范围为1≤position≤Length(),
//position合法时函数返回SUCCESS,否则函数返回RANGE_ERROR
{
//position合法
Node*tmpPtr;
if(position==1)
//如果删除首元结点,取出指向尾结点的指针
tmpPtr=GetElemPtr(Length());
else
//取出指向第position-1个结点的指针
tmpPtr=GetElemPtr(position-1);
Node*nextPtr=tmpPtr->next;
if(position==1)
//头结点与新的首元结点相连
head->next=nextPtr->next;//nextPtr为tmpPtr的后继
tmpPtr->next=nextPtr->next;//删除结点
e=nextPtr->data;//用e返回被删结点元素值
if(position==Length())
{//删除尾结点,当前结点变为头结点
curPosition=1;//设置当前位置的序号
curPtr=head->next;//设置指向当前位置的指针
}
else
{//删除非尾结点,当前结点变为第position个结点
curPosition=position;//设置当前位置的序号
curPtr=tmpPtr->next;//设置指向当前位置的指针
}
count--;//删除成功后元素个数减1
deletenextPtr;//释放被删结点
returnSUCCESS;
}
(3)出圈次序的算法描述
template
intLinkList:
:
Pass(intposition,intn,ElemType&e)
{inti;
curPtr=GetElemPtr(position);//当前指针指向position
curPosition=position;//记录当前位置
for(i=0;i{curPtr=curPtr->next;
curPosition++;
}
cout<num<<"";//输出起始位置
e=curPosition;
}
(4)主程序
#include"assistance.h"
#include"lk_list.h"
intPOS(intn,inti)//计算当前位置的函数
{if(n%i==0)
n=i;
elsen=n%i;
returnn;}
intmain(){inttmp,i,k=0,n=0,key;
intpos;
LinkListlc;//创建空链表
while(n<1||n>20)//限制人数
{cout<<"请输入人数,人数小于20:
";
cin>>n;}
cout<<"请输入每个人的密码,用空格分隔,密码大于0:
"<for(