数据结构实验指导书Word文档下载推荐.docx
《数据结构实验指导书Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《数据结构实验指导书Word文档下载推荐.docx（34页珍藏版）》请在冰点文库上搜索。
三、实验目的、内容与要求
实验一线性表的应用—Josephus环算法的设计
（一）实验目的
本实验的目的是进一步理解线性表的逻辑结构和存储结构，进一步提高应用理论知识解决实际问题的能力。
（二）实验内容
1.Josephus环问题
设编号为1、2、…n的n个人围坐一圈，约定编号为k（1≤k≤n）的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。
2.百货公司仓库中有一批电视机，按其价格从低到高的次序构成了一个单链表并存于计算机中，链表的每个结点指出同样价格的若干台。
现在又新到m台价格为h元的电视机入库。
试编写出仓库电视机链表增加电视机的算法。
3.设有一个循环双链表，假设所有结点的data域值不相同，编写一个算法将data域值为x的结点与其右边的一个结点进行交换。
（三）实验要求
实验前充分预习实验指导书内容及相关理论知识内容；
实验中严格遵守实验室规范和制度，认真完成实验内容并做好实验纪录；
实验后必须按照要求独立完成实验报告。
实验二二叉树的应用—二叉树遍历算法的设计
本实验的目的是通过理解二叉树的逻辑结构和存储结构，进一步提高应用理论知识解决实际问题的能力。
1.以二叉链表存储结构的方式创建如下图的二叉树creatree。
2.试以上题已建立的二叉链表为已知二叉树，编写按层次顺序遍历二叉树的算法。
3.写一个算法find，查找二叉树中的结点。
4.已知一棵二叉树的先序序列和中序序列，写一个建立该二叉树的二叉链表存储结构的算法。
5.判断一棵二叉树是否是完全二叉树。
6.设计一个算法，在以t为根结点的线索二叉树中，插入一个data域值为x的结点作为结点p的右孩子。
实验三图的应用—BFS和DFS算法的设计
本实验的目的是通过理解图的逻辑结构和存储结构，进一步提高应用理论知识解决实际问题的能力。
1.分别编写BFS、DFS算法。
2.判断无向图G是否连通，若连通则返回1，否则返回0。
3.判断无向图G是否是一棵树。
若是树，返回1；
否则返回0。
4.判断有向图中是否存在回路。
5.假设图G采用邻接表存储，求距离顶点v0的最短路径长度为k的所有顶点，要求尽可能节省时间。
四、考核方式及成绩评定
实验的考核方式:
根据课上实验能力、原型系统效果验收与实验报告的完成情况确定最终的实验成绩，实验成绩占课程总成绩的10%。
五、教材及主要参考资料
1．教材
[1]数据结构（C语言版）.严蔚敏,吴伟民主编.北京：
清华大学出版社，2002
[2]数据结构实验指导书.张丽霞，吕岩编.自编，2005
2．教学参考书
[1]数据结构.刘振鹏主编.北京：
中国铁道出版社，2003
[2]数据结构题集（C语言版）．严蔚敏，吴伟民主编．北京：
清华大学出版社，1999
六、其它说明
实验报告格式参照信息工程学院实验报告规范要求。
一、目的
本实验的目的是进一步理解线性表的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力。
二、题目
线性表的应用—Josephus环算法的设计
三、实验类型
设计性。
本实验设计了一个循环链表，并涉及到了对链表的一些基本操作：
建立、删除等
基本操作。
四、要求及提示
说明：
以下3个题中，题1是必做题，题2、3可任意选作。
1、Josephus环问题
实验提示：
（1）、由于当某个人退出圆圈后，报数的工作要从下一个人开始继续，剩下的人仍然是围成一个圆圈的，可以使用循环表，由于退出圆圈的工作对应着表中结点的删除操作，对于这种删除操作频繁的情况，选用效率较高的链表结构，为了程序指针每一次都指向一个具体的代表一个人的结点而不需要判断，链表不带头结点。
所以，对于所有人围成的圆圈所对应的数据结构采用一个不带头结点的循环链表来描述。
设头指针为p，并根据具体情况移动。
可以采用数据类型定义：
typedefstructnode
{
intnumber;
//每个人的编号
structnode*next;
//指向表示下一个人的结点的指针
}lnode
（2）、为了记录退出的人的先后顺序，采用一个顺序表进行存储。
程序结束后再输出依次退出的人的编号顺序。
由于只记录各个结点的number值就可以，所以定义一个整型一维数组。
如：
intquit[n];
n为一个根据实际问题定义的一个足够大的整数。
2、百货公司仓库中有一批电视机，按其价格从低到高的次序构成了一个单链表并存与计算机中，链表的每个结点指出同样价格的若干台。
3、设有一个循环双链表，假设所有结点的data域值不相同，编写一个算法将data域值为x的结点与其右边的一个结点进行交换。
五、实验报告
1、写出每个算法的思想。
2、画出算法流程图。
3、调试程序出现的问题及解决的方法。
4、打印实验报告及程序清单。
5、报告给出测试的结果并写出设计体会。
六、范例参考
1、问题描述
这是单链表的一个综合练习，包括以下各项内容的函数，可共享被调用，可以通过菜单选择方式运行单链表的各种操作。
1）建立单链表
（1）：
将用户输入的数据按头插入法建立一个不带头结点的单链表。
输入结点数据时以输入一串字符的方式实现，$字符为结束输入字符
2）建立单链表
（2）：
将用户输入的数据按头插入法建立一个带头结点的单链表。
输入数据方式同上。
3）建立单链表（3）：
将用户输入的数据按尾插入法建立一个不带头结点的单链表。
4）建立单链表（4）：
将用户输入的数据按尾插入法建立一个带头结点的单链表。
5）逆置单链表：
按头插入法建立一个不带头结点的单链表，用最少的辅助空间实现单链表元素的逆置。
6）有序链表插入元素：
建立一个带头结点的单链表，表中元素从小到大有序排列。
输入一个元素并将其插入到单链表中正确的位置上。
7）有序链表删除重复元素：
建立一个带头结点的单链表，表中元素递增有序。
删除表中值相同的多余元素（即重复元素只保留一个）
8）无序链表删除重复元素建立一个带头结点的单链表，元素按输入的次序排列。
删除表中值相同的多余元素（即重复元素只保留一个）。
9）两链表合并：
建立两个带头结点的单链表a1和a2，元素均递增有序。
将两个单链表归并成新的单链表c,c中元素也递增有序，相同值的元素均保留在c中。
10）两链表并集：
按用户输入的数据建立两个集合a1和a2，同一集合中无重复元素，以带头结点的单链表形式存放。
对两集合进行并集运算，结果放在a1表中。
2、程序清单
#include"
datastru.h"
#include<
stdio.h>
malloc.h>
#defineDATATYPE2char
{DATATYPE2data;
}LINKLIST;
intlocate（LINKLIST*a,charx）
/*检查元素x是否在a表中*/
{LINKLIST*la;
la=a->
next;
while（la!
=NULL）
if（la->
data==x）return1;
elsela=la->
return0;
}
insert（LINKLIST*a,charx）
/*将x元素加入a表中*/
{LINKLIST*p;
p=（LINKLIST*）malloc（sizeof（LINKLIST））;
p->
data=x;
next=a->
a->
next=p;
voidunionn（LINKLIST*a1,LINKLIST*b1）{
/*两有序表交集*/
LINKLIST*lb;
lb=b1->
while（lb!
=NULL）
{if（!
locate（a1,lb->
data））/*如果b1表中的一个元素不在a1表中*/
insert（a1,lb->
data）;
/*则将b1表中的该元素加入a1表中*/
lb=lb->
voidunite（LINKLIST*a,LINKLIST*b,LINKLIST*c）{
/*a,b为两有序链表，合并到c表，并保持有序*/
LINKLIST*la,*lb,*lc,*p;
lb=b->
lc=c;
=NULL&
&
lb!
{if（la->
data<
=lb->
data）
{p=（LINKLIST*）malloc（sizeof（LINKLIST））;
p->
data=la->
data;
next=NULL;
lc->
lc=lc->
la=la->
}
else
data=lb->
while（la!
voiddelete1（LINKLIST*a）{
/*无序链表中删除重复元素，重复元素保留一个*/
LINKLIST*la,*p,*q;
{q=la;
p=la->
while（p!
{if（p->
data==la->
{p=p->
q->
else{q=p;
p=p->
voiddelete（LINKLIST*a）{
/*有序链表中删除重复元素，重复元素保留一个*/
LINKLIST*la;
la->
next!
if（la->
next->
next=la->
inser_order（DATATYPE2x,LINKLIST*head）{
/*有序表中插入元素x,并保持表有序*/
LINKLIST*pr,*pn,*pp;
pr=head;
pn=head->
while（pn!
pn->
x）
{pr=pn;
pn=pn->
pp=（LINKLIST*）malloc（sizeof（LINKLIST））;
pp->
next=pr->
pr->
next=pp;
LINKLIST*invertlink（LINKLIST*head）{
/*单链表元素逆置*/
LINKLIST*p,*q,*r;
q=NULL;
p=head;
{r=q;
q=p;
next=r;
returnq;
intcount_nohead（LINKLIST*head）{
/*不带头结点的单链表：
输出单链表元素值并计数*/
inti=0;
LINKLIST*p;
printf（"
输出单链表元素值:
"
）;
{printf（"
%c"
p->
i++;
\n"
returni;
intcount_head（LINKLIST*head）{
/*带头结点的单链表：
p=head->
LINKLIST*creatlink_nohead_head（LINKLIST*head）{
/*用头插入法建立不带头结点的单链表*/
LINKLIST*t;
charch;
单链表元素值为单个字符,连续输入，$为结束字符:
while（（ch=getchar（））!
='
$'
）
{t=（LINKLIST*）malloc（sizeof（LINKLIST））;
t->
data=ch;
next=head;
head=t;
return（head）;
LINKLIST*creatlink_head_head（LINKLIST*head）{
/*用头插入法建立带头结点的单链表*/
t=（LINKLIST*）malloc（sizeof（LINKLIST））;
{t=（LINKLIST*）malloc（sizeof（LINKLIST））;
next=head->
head->
next=t;
return（head）;
LINKLIST*creatlink_nohead_rail（LINKLIST*head）{
/*用尾插入法建立不带头结点的单链表*/
LINKLIST*last,*t;
last=head;
while（（ch=getchar（））!
{t=（LINKLIST*）malloc（sizeof（LINKLIST））;
if（head==NULL）{head=t;
last=t;
else{last->
return（head）;
LINKLIST*creatlink_head_rail（LINKLIST*head）{
/*用尾插入法建立带头结点的单链表*/
last->
LINKLIST*creatlink_order_head（LINKLIST*head）
/*建立带头结点的有序单链表*/
{LINKLIST*t,*p,*q;
q=head;
while（p!
=ch）{
q=p;
main（）
{LINKLIST*head,*a1,*a2,*c;
intnum=0,loop,j;
loop=1;
while（loop）{
\n\n"
1--建立单链表（头插入，不带头结点）\n"
2--建立单链表（头插入，带头结点）\n"
3--建立单链表（尾插入，不带头结点）\n"
4--建立单链表（尾插入，带头结点）\n"
5--逆置单链表\n"
6--有序链表插入\n"
7--有序链表删除重复元素\n"
8--无序链表删除重复元素\n"
9--两链表合并并排序\n"
10--两链表并集\n\n"
请选择项号：
scanf（"
%d"
&
j）;
fflush（stdin）;
if（j>
=1&
j<
=10）
switch（j）{
case1:
\n建立单链表\n\n"
head=NULL;
head=creatlink_nohead_head（head）;
fflush（stdin）;
num=count_nohead（head）;
printf（"
单链表元素个数=%d\n"
num）;
break;
case2:
head=creatlink_head_head（head）;
num=count_head（head）;
case3:
head=creatlink_nohead_rail（head）;
case4:
head=creatlink_head_rail（head）;
case5:
head=NULL;
\n逆置单链表\n\n"
head=invertlink（head）;
b
升级会员 