大数据结构实验指导书0311.docx
《大数据结构实验指导书0311.docx》由会员分享，可在线阅读，更多相关《大数据结构实验指导书0311.docx（41页珍藏版）》请在冰点文库上搜索。
大数据结构实验指导书0311
《数据结构》
实验指导书
郑州轻工业学院
2016.02.20
前言
《数据结构》是计算机相关专业的一门核心基础课程，是编译原理、操作系统、数据库系统及其它系统程序和大型应用程序开发的重要基础，也是很多高校考研专业课之一。
它主要介绍线性结构、树型结构、图状结构三种逻辑结构的特点和在计算机内的存储方法，并在此基础上介绍一些典型算法及其时、空效率分析。
这门课程的主要任务是研究数据的逻辑关系以及这种逻辑关系在计算机中的表示、存储和运算，培养学生能够设计有效表达和简化算法的数据结构，从而提高其程序设计能力。
通过学习，要求学生能够掌握各种数据结构的特点、存储表示和典型算法的设计思想及程序实现，能够根据实际问题选取合适的数据表达和存储方案，设计出简洁、高效、实用的算法，为后续课程的学习及软件开发打下良好的基础。
另外本课程的学习过程也是进行复杂程序设计的训练过程，通过算法设计和上机实践的训练，能够培养学生的数据抽象能力和程序设计能力。
学习这门课程，习题和实验是两个关键环节。
学生理解算法，上机实验是最佳的途径之一。
因此，实验环节的好坏是学生能否学好《数据结构》的关键。
为了更好地配合学生实验，特编写实验指导书。
一、实验目的
本课程实验主要是为了原理和应用的结合，通过实验一方面使学生更好的理解数据结构的概念和常用的几种数据结构在计算机中的存储和实现的方法，加强学生动手能力；另一方面培养学生从实际问题中抽象出对应的抽象数据类型，进而找到合适的计算机存储方法和算法，为以后课程的学习、大型软件的开发、实际工程问题打下良好的软件开发基础。
二、实验要求
1、每次实验前学生必须根据实验内容认真准备实验程序及调试时所需的输入数据。
2、在指导教师的帮助下能够完成实验内容，得出正确的实验结果。
3、实验结束后总结实验内容、书写实验报告。
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
#include
#include
#include
#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&L）;/*奇数排在偶数之前*/
StatusOrderList_sq（SqList&L,intn）;/*插入法生成递增有序表*/
voidMergeList_Sq（SqListLa,SqListLb,SqList&Lc）;/*两个非递减有序表A和B，并把它们合并成一个非递减有序表C*/
#endif//SQLIST_H_INCLUDED
SqList.cpp
#include"SqList.h"
voidmenu（）
{
printf（"\t\t\t顺序表基本操作\n\n"）;
printf（"\t\t\t1.建立顺序表\n"）;
printf（"\t\t\t2.遍历顺序表\n"）;
printf（"\t\t\t3.删除第i个元素\n"）;
printf（"\t\t\t4.删除值为x的元素\n"）;
printf（"\t\t\t5.奇数排在偶数之前\n"）;
printf（"\t\t\t6.插入法生成递增有序表\n"）;
printf（"\t\t\t7.两个非递减有序表La和Lb合并成非递减有序表Lc\n"）;
printf（"\t\t\t0.退出\n\n"）;
}
/*初始化顺序表*/
StatusInitList_Sq（SqList&L,intn）
{
L.elem=（ElemType*）malloc（n*sizeof（ElemType））;
if（!
L.elem）exit（OVERFLOW）;
L.length=0;
L.listsize=n;
returnOK;
}
/*建立顺序表*/
StatusCreateList_Sq（SqList&L）
{
intn,i;
printf（"请输入顺序表长度：
"）;
scanf（"%d",&n）;
if（InitList_Sq（L,n））
{
printf（"请输入%d个元素：
",n）;
for（i=0;i{
scanf（"%d",&L.elem[i]）;
L.length++;
}
returnOK;
}
else
returnERROR;
}
/*输出顺序表*/
voidPrintList_Sq（SqListL）
{
inti;
printf（"顺序表中元素为：
\n"）;
for（i=0;i{
printf（"%d",L.elem[i]）;
}
printf（"\n"）;
}
/*删除第i个元素*/
StatusDeleteList_Sq（SqList&L,inti,ElemType&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*/
StatusDeleteListX_Sq（SqList&L,ElemTypex）
{
ElemType*p,*q;
}
/*奇数排在偶数之前*/
StatusAdjustList_Sq（SqList&L）
{
ElemType*p,*q;
inttemp;
returnOK;
}
/*插入法生成递增有序表，有序表生成成功返回OK，失败返回ERROR*/
StatusOrderList_sq（SqList&L,intn）
{
inti,j,x;/*x表示每次待插入的元素*/
}
/*两个非递减有序表A和B，并把它们合并成一个非递减有序表C*/
voidMergeList_Sq（SqListLa,SqListLb,SqList&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
#include"SqList.h"
intmain（）
{
intchoice,n,i,x;
SqListL,La,Lb,Lc;
while
（1）
{
menu（）;
printf（"选择你的操作：
"）;
scanf（"%d",&choice）;
switch（choice）
{
case1:
if（CreateList_Sq（L））
printf（"顺序表创建成功\n"）;
else
printf（"顺序表创建失败\n"）;
break;
case2:
PrintList_Sq（L）;
break;
case3:
printf（"请输入删除元素的位置：
"）;
scanf（"%d",&i）;
if（DeleteList_Sq（L,i,x））
printf（"被删除元素值为：
%d\n",x）;
else
printf（"删除失败\n"）;
break;
case4:
printf（"请输入删除元素值：
"）;
scanf（"%d",&x）;
if（DeleteListX_Sq（L,x））
printf（"删除成功\n"）;
else
printf（"删除失败\n"）;
PrintList_Sq（L）;
break;
case5:
AdjustList_Sq（L）;
printf（"新链表为：
\n"）;
PrintList_Sq（L）;
break;
case6:
printf（"请输入顺序表长度：
"）;
scanf（"%d",&n）;
if（OrderList_sq（L,n））
{
printf（"值有序顺序表为：
\n"）;
PrintList_Sq（L）;
}
else
printf（"顺序表创建失败\n"）;
break;
case7:
printf（"请输入顺序表La的长度：
"）;
scanf（"%d",&n）;
OrderList_sq（La,n）;
printf（"请输入顺序表Lb的长度：
"）;
scanf（"%d",&n）;
OrderList_sq（Lb,n）;
MergeList_Sq（La,Lb,Lc）;
printf（"合并后的顺序表为：
\n"）;
PrintList_Sq（Lc）;
break;
case0:
return0;
default:
printf（"输入错误，请重新输入\n"）;
}
}
}
实验02单链表的基本操作
实验学时：
2学时
实验类型：
上机
背景知识：
单链表的插入、删除及应用。
目的要求：
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．单链表的操作是数据结构的基础，一定要注意对这部分常见算法的理解。
部分源代码：
DS.h
#include
#include
#include
#include
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
typedefintStatus;
LinkList.h
#include"DS.h"
typedefintElemtype;
typedefstructNode
{
Elemtypedata;
structNode*next;
}Lnode,*LinkList;
voidmenu（）;/*菜单*/
StatusInit_Linklist（LinkList&L）;/*初始化空表*/
StatusCreat_Linklist（LinkList&L）;/*尾插法建立单链表*/
voidDisp_Linklist（LinkListL）;/*单链表遍历*/
intlength_Linklist（LinkListL）;/*计算单链表长度*/
voidReverse_Linklist（LinkListL）;/*单链表逆置*/
voidDelEven_Linklist（LinkListL）;/*删除值为偶数的结点*/
StatusInsert_Linklist（LinkListL,intx）;/*在有序单链表L中插入元素x，链表仍然有序*/
StatusCreatOrder_Linklist（LinkList&L）;/*创建非递减有序单链表*/
voidMergeDescend_Linklist（LinkListLa,LinkListLb,LinkList&Lc）;/*两个非递减有序单链表La和Lb合并成一个非递增有序链表Lc*/
voidMergeAscend_Linklist（LinkListLa,LinkListLb,LinkList&Lc）;/*两个非递减有序单链表La和Lb合并成一个非递减有序链表Lc*/
voidSplit_Linklist（LinkListLa,LinkList&Lb）;/*链表La按值分解成两个链表，La全部为奇数，Lb全部为偶数*/
LinkList.cpp
#include"LinkList.h"
voidmenu（）
{
printf（"\t\t\t单链表基本操作\n\n"）;
printf（"\t\t\t1.建立单链表\n"）;
printf（"\t\t\t2.遍历单链表\n"）;
printf（"\t\t\t3.计算链表长度\n"）;
printf（"\t\t\t4.链表逆置\n"）;
printf（"\t\t\t5.删除偶数节点\n"）;
printf（"\t\t\t6.生成值有序单链表\n"）;
printf（"\t\t\t7.合并生成降序链表\n"）;
printf（"\t\t\t8.合并生成升序链表\n"）;
printf（"\t\t\t9.分解链表\n"）;
printf（"\t\t\t0.退出\n\n"）;
}
/*初始化空表*/
StatusInit_Linklist（LinkList&L）
{
L=（LinkList）malloc（sizeof（Lnode））;
if（!
L）returnERROR;
L->next=NULL;
returnOK;
}
/*尾插法建立单链表*/
StatusCreat_Linklist（LinkList&L）
{
intx;
LinkListp,rear;
Init_Linklist（L）;
rear=L;
printf（"输入-1表示输入结束\n"）;
while（scanf（"%d",&x）,x!
=-1）
{
p=（LinkList）malloc（sizeof（Lnode））;
if（!
p）returnERROR;
p->data=x;
rear->next=p;
rear=p;
}
rear->next=NULL;
returnOK;
}
/*单链表遍历*/
voidDisp_Linklist（LinkListL）
{
LinkListp;
p=L->next;
while（p）
{
printf（"%d",p->data）;
p=p->next;
}
printf（"\n"）;
}
/*计算单链表长度*/
intlength_Linklist（LinkListL）
{
intcount=0;/*count表示单链表长度*/
LinkListp;
returncount;
}
/*单链表逆置*/
voidReverse_Linklist（LinkListL）
{
LinkListp,q;
}
/*删除值为偶数的结点*/
voidDelEven_Linklist（LinkListL）
{
升级会员 