《数据结构》实验指导书(修订版)Word格式.doc
《《数据结构》实验指导书(修订版)Word格式.doc》由会员分享，可在线阅读，更多相关《《数据结构》实验指导书(修订版)Word格式.doc（39页珍藏版）》请在冰点文库上搜索。
4、遵守实验室规章制度、不缺席、按时上、下机。
5、实验学时内必须做数据结构的有关内容，不允许上网聊天或玩游戏，如发现上述现象，取消本次上机资格，平时成绩扣10分。
6、实验报告有一次不合格，扣5分，两次以上不合格者，平时成绩以零分记。
三、实验环境
VC++6.0或其他C++相关的编译环境。
四、说明
1、本实验的所有算法中元素类型应根据实际需要合理选择。
2、实验题目中带＊者为较高要求，学生可自选；
其余部分为基本内容，应尽量完成（至少完成70%，否则实验不合格）。
3、数据结构是很多高校的硕士研究生入学考试的专业课之一，希望有志于考研的学生能够在学习过程中注意各种算法的理解，以便为考研做一定的准备。
4、好的算法决定了好的程序，要有效地实现算法，就需要设计能够有效表达和简化算法的数据结构，因此数据结构是有效进行程序设计的基础，是每个程序员的必修课。
五、实验报告的书写要求
1、明确实验的目的及要求。
2、记录实验的输入数据和输出结果。
3、说明实验中出现的问题和解决过程。
4、写出实验的体会和实验过程中没能解决的问题。
5、实验程序请构建为多文件程序，每一个算法对应的函数原型声明存放在头文件*.h中，对应的函数实现存放在源文件*.c中；
main（）函数存放在另一个源文件中，该文件包含头文件*.h即可。
六、成绩考评办法
1、期末考试占70分，闭卷。
2、平时考评占30分。
其中实验环节占20分（实验准备、上机、报告、验收等）；
平时占10分（出勤、作业、测验等）。
七、参考书目
1、《数据结构》（Ｃ语言版）严蔚敏等清华大学出版社。
2、《数据结构题集》（C语言版）严蔚敏等清华大学出版社。
3、《数据结构与算法分析——C语言描述》，MarkAllenWeiss著，机械工业出版社，2012。
实验01顺序表的基本操作
实验学时：
2学时
实验类型：
上机
背景知识：
顺序表的插入、删除及应用。
目的要求：
1．掌握顺序存储结构的特点。
2．掌握顺序存储结构的常见算法。
实验内容：
编写一个完整的程序，实现顺序表的生成、插入、删除、输出等基本运算。
（1）建立一个顺序表，含有n个数据元素。
（2）输出顺序表。
（3）在顺序表中删除值为x的结点或者删除给定位置i的结点。
（4）实现把该表中所有奇数排在偶数之前，即表的前面为奇数，后面为偶数。
（5）输入整型元素序列，利用有序表插入算法建立一个有序表。
（6）*利用算法5建立两个非递减有序表A和B，并把它们合并成一个非递减有序表C。
（7）在主函数中设计一个简单的菜单，分别测试上述算法。
（8）*综合训练：
利用顺序表实现一个班级学生信息管理（数据录入、插入、删除、排序、查找等）。
实验说明：
1．请构建多文件程序，算法1至算法6对应的函数原型声明存放在头文件SqList.h中，对应的函数实现存放在源文件SqList.c中；
main（）函数存放在另一个源文件中，该文件包含头文件SqList.h即可。
2．类型定义
#defineMAXSIZE100//表中元素的最大个数
typedefintElemType;
//元素类型
typedefstruct
{
ElemType*elem;
//线性表
intlength;
//表的实际长度
intlistsize;
//当前分配的存储容量
}SqList;
//顺序表的类型名
3．建立顺序表时可利用随机函数自动产生数据。
注意问题：
1、插入、删除时元素的移动原因、方向及先后顺序。
2、理解函数形参与实参的传递关系。
部分源代码：
DS.h
#include<
stdio.h>
stdlib.h>
string.h>
math.h>
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
typedefintStatus;
SqList.h
#ifndefSQLIST_H_INCLUDED
#defineSQLIST_H_INCLUDED
#include"
DS.h"
typedefintElemType;
typedefstruct
{
ElemType*elem;
intlength;
intlistsize;
}SqList;
voidmenu（）;
StatusInitList_Sq（SqList&
L,intn）;
/*初始化顺序表*/
StatusCreateList_Sq（SqList&
L）;
/*建立顺序表*/
voidPrintList_Sq（SqListL）;
/*输出顺序表*/
StatusDeleteList_Sq（SqList&
L,inti,ElemType&
e）;
/*删除第i个元素*/
StatusDeleteListX_Sq（SqList&
L,ElemTypex）;
/*删除值为x的元素*/
StatusAdjustList_Sq（SqList&
/*奇数排在偶数之前*/
StatusOrderList_sq（SqList&
/*插入法生成递增有序表*/
voidMergeList_Sq（SqListLa,SqListLb,SqList&
Lc）;
/*两个非递减有序表A和B，并把它们合并成一个非递减有序表C*/
#endif//SQLIST_H_INCLUDED
SqList.cpp
SqList.h"
voidmenu（）
printf（"
\t\t\t顺序表基本操作\n\n"
）;
\t\t\t1.建立顺序表\n"
\t\t\t2.遍历顺序表\n"
\t\t\t3.删除第i个元素\n"
\t\t\t4.删除值为x的元素\n"
\t\t\t5.奇数排在偶数之前\n"
\t\t\t6.插入法生成递增有序表\n"
\t\t\t7.两个非递减有序表La和Lb合并成非递减有序表Lc\n"
\t\t\t0.退出\n\n"
}
L,intn）
L.elem=（ElemType*）malloc（n*sizeof（ElemType））;
if（!
L.elem）exit（OVERFLOW）;
L.length=0;
L.listsize=n;
returnOK;
L）
intn,i;
请输入顺序表长度：
"
scanf（"
%d"
&
n）;
if（InitList_Sq（L,n））
{
printf（"
请输入%d个元素：
n）;
for（i=0;
i<
n;
i++）
{
scanf（"
L.elem[i]）;
L.length++;
}
returnOK;
}
else
returnERROR;
voidPrintList_Sq（SqListL）
inti;
顺序表中元素为：
\n"
for（i=0;
L.length;
%d"
L.elem[i]）;
e）
ElemType*p,*q;
if（（i<
1）||（i>
L.length））returnERROR;
p=&
（L.elem[i-1]）;
e=*p;
q=L.elem+L.length-1;
for（++p;
p<
=q;
++p）*（p-1）=*p;
--L.length;
returnOK;
/*删除值为x的元素，删除成功返回OK，删除失败返回ERROR*/
L,ElemTypex）
ElemType*p,*q;
inttemp;
/*插入法生成递增有序表，有序表生成成功返回OK，失败返回ERROR*/
inti,j,x;
/*x表示每次待插入的元素*/
Lc）
ElemType*pa,*pb,*pc,*pa_last,*pb_last;
pa=La.elem;
pb=Lb.elem;
Lc.listsize=Lc.length=La.length+Lb.length;
pc=Lc.elem=（ElemType*）malloc（Lc.listsize*sizeof（ElemType））;
if（!
Lc.elem）exit（OVERFLOW）;
pa_last=La.elem+La.length-1;
pb_last=Lb.elem+Lb.length-1;
while（pa<
=pa_last&
&
pb<
=pb_last）
if（*pa<
=*pb）*pc++=*pa++;
else*pc++=*pb++;
while（pa<
=pa_last）*pc++=*pa++;
while（pb<
=pb_last）*pc++=*pb++;
main.cpp
intmain（）
intchoice,n,i,x;
SqListL,La,Lb,Lc;
while
（1）
menu（）;
选择你的操作：
scanf（"
&
choice）;
switch（choice）
case1:
if（CreateList_Sq（L））
printf（"
顺序表创建成功\n"
else
顺序表创建失败\n"
break;
case2:
PrintList_Sq（L）;
case3:
printf（"
请输入删除元素的位置：
scanf（"
i）;
if（DeleteList_Sq（L,i,x））
被删除元素值为：
%d\n"
x）;
删除失败\n"
case4:
请输入删除元素值：
x）;
if（DeleteListX_Sq（L,x））
删除成功\n"
case5:
AdjustList_Sq（L）;
新链表为：
case6:
if（OrderList_sq（L,n））
{
值有序顺序表为：
PrintList_Sq（L）;
}
case7:
请输入顺序表La的长度：
OrderList_sq（La,n）;
请输入顺序表Lb的长度：
OrderList_sq（Lb,n）;
MergeList_Sq（La,Lb,Lc）;
合并后的顺序表为：
PrintList_Sq（Lc）;
case0:
return0;
default:
输入错误，请重新输入\n"
实验02单链表的基本操作
单链表的插入、删除及应用。
1．掌握单链表的存储特点及其实现。
2．掌握单链表的插入、删除算法及其应用算法的程序实现。
编写一个完整的程序，实现单链表的生成、插入、删除、输出等基本操作。
（1）随机产生或键盘输入一组元素，建立一个带头结点的单向链表（无序）。
（2）计算单链表的长度，遍历单链表。
（3）把单链表中的元素逆置（不允许申请新的结点空间）。
（4）在单链表中删除所有值为偶数的元素结点。
（5）编写在非递减有序单链表中插入一个元素使链表元素仍有序的函数，并利用该函数建立一个非递减有序单链表。
（6）*利用算法5建立两个非递减有序单链表，然后合并成一个非递增有序链表。
（7）*利用算法5建立两个非递减有序单链表，然后合并成一个非递减有序链表。
（8）*利用算法1建立的链表，实现将其分解成两个链表，其中一个全部为奇数，另一个全部为偶数（尽量利用已知的存储空间）。
（9）*采用单链表实现一元多项式的存储并实现两个多项式相加并输出结果。
（10）在主函数中设计一个简单的菜单，分别调试上述算法。
（11）*综合训练：
1）利用链表实现一个班级学生信息管理（数据录入、插入、删除、排序、查找等，并能够实现将数据存储到文件中）
2）约瑟夫环问题：
设有n个人围坐在圆桌周围，从某个位置开始编号为1，2，3，…，n，坐在编号为1的位置上的人从1开始报数，数到m的人便出列；
下一个（第m+1个）人又从1开始报数，数到m的人便是第二个出列的人；
如此重复下去，直到最后一个人出列为止，得到一个出列的编号顺序。
例如，当n=8，m=4时，若从第一个位置数起，则出列的次序为4，8，5，2，1，3，7，6。
试编写程序确定出列的顺序。
要求用不带头结点的单向循环链表作为存储结构模拟此过程，按照出列顺序打印出个人编号。
1．类型定义
typedefintElemType;
typedefstructnode
ElemTypedata;
structnode*next;
}LinkNode,*LinkList;
2．为了算法实现简单，建议采用带头结点的单链表。
1．重点理解链式存储的特点及指针的含义。
2．注意比较顺序存储与链式存储的各自特点。
3．注意比较带头结点、无头结点链表实现插入、删除算法时的区别。
4．单链表的操作是数据结构的基础，一定要注意对这部分常见算法的理解。
LinkList.h
typedefintElemtype;
typedefstructNode
Elemtypedata;
structNode*next;
}Lnode,*LinkList;
/*菜单*/
StatusInit_Linklist（LinkList&
/*初始化空表*/
StatusCreat_Linklist（LinkList&
/*尾插法建立单链表*/
voidDisp_Linklist（LinkListL）;
/*单链表遍历*/
intlength_Linklist（LinkListL）;
/*计算单链表长度*/
voidReverse_Linklist（LinkListL）;
/*单链表逆置*/
voidDelEven_Linklist（LinkListL）;
升级会员 