数据结构实验指导(1)

1、目 录实验说明2实验要求3实验1 线性表的顺序存储结构的实现及其应用4实验2 线性表的链式存储结构的实现及其应用9实验3 栈和队列的存储结构的实现16实验4 树和二叉树的存储结构的实现17实验5 图的存储结构的实现18实验6 图的简单应用19实验7 查找算法的实现20实验8 排序算法的实现2121实验说明A每班学习委员或班长在上机实验前一周到软件学院教务室（创新大楼西楼4楼教务室）购买上机实验报告B上机实验报告封面上要写完整：班级、姓名、指导老师姓名，学期、报告日期等。C其它1) 本学期上机实验一共16学时，大家需要完成8个实验。2) 上机前写好预习报告（即上机报告中调试分析之前的内容），准备

2、好程序和测试数据。3) 报告要简洁明了，一个实验报告只有3页，书写时字体大小不要太大，以免写不下。4) 请按照指定时间完成上机报告，上机报告于课程结束后上交存档，缺交上机报告达三分之一者取消考试资格。5) 请大家认真完成上机任务及上机报告，严禁抄袭。有任何问题可以及时跟任课教师联系！6) 希望在愉快的环境中完成本学期的学习，请大家积极配合！谢谢！实验要求一、实验步骤 问题分析充分地分析和理解问题本身，弄清要求做什么，包括功能要求、性能要求、设计要求和约束以及基本数据特性，数据元素之间的关系等。 数据结构设计针对要求解决的问题，考虑各种可能的数据结构，并且力求从中找出最佳方案(必须连同算法一起考

3、虑)，确定主要的数据结构（可以采用抽象数据类型描述）及全局变量。对引入的每种数据结构和全局变量要详细说明其功能、初值和操作特点。 算法设计算法设计分概要设计和详细设计。概要设计着重解决程序的模块设计问题，这包括考虑如何把被开发的问题程序自顶向下分解成若干顺序模块，并决定模块的接口，即模块间的相互关系以及模块之间的信息交换问题。概要设计可以由模块的功能说明和模块之间的调用关系图完成。详细设计则要决定每个模块内部的具体算法，包括输入、处理和输出，采用类C语言描述。 测试用例设计准备典型测试数据和测试方案，测试数据要有代表性、敏感性，测试方案包括模块测试和模块集成测试。 上机调试对程序进行编译，纠正

4、程序中可能出现的语法错误。测试前，先运行一遍程序看看究竟将会发生什么，如果错误较多，则根据事先设计的测试方案并结合现场情况进行错误跟踪，包括打印执行路径或输出中间变量值等手段。二、实验报告每次上机实验前，应该写好预习报告。预习报告包括如下内容：（1）问题描述：简述题目要做什么。（2）设计部分：包括抽象数据类型描述，其他各个模块的功能说明，模块之间的调用关系图，存储结构的定义、基本操作的实现、其他模块的算法等。（3）测试用例设计每次实验结束后，在预习报告的基础上撰写完整的实验报告。实验报告应包括如下内容： （1）、（2）同预习报告（3）调试报告：调试过程中遇到的问题以及如何解决；对设计和编码的讨

5、论和分析。（4）测试结果。根据预习报告中设计的测试用例进行程序测试，可以贴相应的运行结果截图。（5）算法分析与改进：重要算法的时间复杂度和空间复杂度分析；算法改进的设想。（6）总结和体会所有实验做完后，上交上机实验源程序（.h， .cpp）、可执行文件（.Exe）和相应的运行结果截图。源程序要加注释。如果题目规定了测试数据，则截图结果要包含这些测试数据和运行输出，当然还可以含有其它测试数据和运行输出（有时需要多组数据）。实验1 线性表的顺序存储结构的实现及其应用实验目的1 熟悉C语言的上机环境，掌握使用VC环境上机调试程序的基本方法；2 会定义线性表的顺序存储结构。3 熟悉对顺序表的一些基本操

6、作和具体的函数定义。4 理解利用基本操作进行一些实际的应用型程序设计。实验要求1 独立完成。2 程序调试正确，有执行结果。实验内容（基础题必做，应用题任选）1、基础题：编写应用程序（填空），实现可以在顺序表中插入任意给定数据类型数据的功能（定义为ElemType抽象数据类型）。要求在主函数中定义顺序表并对该顺序表插入若干个整数类型的数据（正整数），对它们求和并输出。请把主函数设计为一个文件SqList.cpp，其余函数设计为另一个文件SqList.h。请填空完成以下给出的源代码并调试通过。（1） 文件SqList.h:typedef struct List ElemType *elem; in

7、t length; SqList;void InitList(SqList &L) /构造一个空的顺序表 void ClearList(SqList &L) /清空线性表，不销毁 int ListLength (SqList L) /求线性表长度.bool ListInsert (SqList &L, int i , ElemType e) /在线性表L中第i个数据元素之前插入新数据元素e .ElemType GetElem(SqList L, int i) /在线性表L中求序号为i的元素，该元素作为函数返回值. （2）文件SqList.cpp：#include #include typede

8、f ElemType; /填空1#define MAXSize 10#include SqList.hvoid main(void)SqList myList;int i=1, x, sum=0, n;InitList ( ); /填空2scanf(“%d”, &x);while ( x!= -1 ) if (ListInsert (myList, i, )=false) /填空3printf(错误!n);return ; i+; scanf(“%d”, &x);n = ListLength (myList);for (i=1; i=n; i+) /求所有数据元素的和x=GetElem(myL

9、ist, i);sum = + x; /填空4printf(%dn , sum); ClearList(myList); 2.应用题（1）编写函数bool DeleteElem(SqList &L, int min, int max) 实现从顺序表中删除其值在给定值min和max之间（min “新建”“工程”“win32 Console Application”输入“工程名称”和存储“位置”“确定”。2.默认创建“一个空工程”“完成”“确定”。3. “文件”菜单“新建”“文件” “C/C+ Header File”输入文件名SqList.h（默认为.h类型，可省去.h）“确定”4.“文件”菜单

10、“新建”“文件” “C+ Source File”输入文件名SqList.cpp（默认为.cpp类型，可省去.cpp）“确定”。 5.打开FileView双击SqList.h，完成头文件的编写。SqList.h主要含结构体的定义和函数的实现。6.打开FileView双击SqList.cpp，完成源文件的编写和填空。SqList.cpp主要含main()函数的实现。7.编译运行。实验2 线性表的链式存储结构的实现及其应用实验目的1 掌握线性表的建立、插入、删除等基本操作的编程实现，进一步编程实现查找、排序等操作，存储结果采用顺序表存储结构。2 理解利用基本操作进行一些实际的应用型程序设计。实验要

11、求1 可以依次完成主要功能来体现功能的正确性，也可以用菜单管理完成大部分功能，要求可以重复运行。2 准备好测试数据，程序调试正确，有执行结果。3 程序是自己开发的，在界面上注明*原创；参考或改写他人的，注明*参考他人版。实验内容（基础题必做，应用题任选1个）1、基础题：线性表基本操作的实现(演示单链表的创建、插入、删除、查找、输出等操作)，通过简单实例测试各基本操作函数算法的正确性。基本操作函数如下：Status InitList(LinkList &L) /初始化只含有头结点的空的单链表，返回函数状态值void DestroyList(LinkList &L) /销毁单链表void Clea

12、rList(LinkList &L) /清空单链表，仅保留头结点bool ListEmpty(LinkList L) /判断是否为空链表int ListLength(LinkList L) /返回单链表的长度void PrintList(LinkList L) /遍历函数，顺序输出单链表中的各元素的值Status GetElem(LinkList L,int i,ElemType &e) /用参数e返回单链表L中第i个元素的值Status ListInsert(LinkList &L,int i,ElemType e) /在单链表L的第i个数据元素之前插入数据元素eStatus ListDel

13、ete(LinkList &L,int i,ElemType &e) /删除单链表L中第i个结点，并用e返回其值int LocateElem(LinkList L,ElemType e) /返回e元素在单链表L中的位序，若不存在，返回02、应用题：（1）将一个已知的单链表进行逆置运算，如（a1,a2,an）变为（an,a2,a1）。（2）求集合A、B的并集C。（3）归并两个有序表La和Lb成一个新的有序表Lc。有序指值非递减。实验步骤参考：1.打开Visual C+6.0，“文件”菜单“新建”“工程”“win32 Console Application”输入“工程名称”和存储“位置”“确定”。

14、2.默认创建“一个空工程”“完成”“确定”。 3. “文件”菜单“新建”“文件” “C/C+ Header File”输入文件名LinkList.h（默认为.h类型，可省去.h）“确定”4.“文件”菜单“新建”“文件” “C+ Source File”输入文件名LinkList.cpp（默认为.cpp类型，可省去.cpp）“确定”。 5.打开FileView双击LinkList.h，完成头文件的编写。LinkList.h主要含结构体的定义和函数的实现。 6.打开FileView双击LinkList.cpp，完成源文件的编写。LinkList.cpp主要含main()函数的实现。7.编译运行。

15、运行结果如下图所示：实验3 栈和队列的存储结构的实现实验目的1 掌握栈的存储结构及基本操作。2 掌握队列的存储结构及基本操作。3 通过具体的应用实例，进一步熟悉和掌握栈和队列的实际应用。实验要求1 独立完成；2 程序调试正确，有执行结果。实验内容（基础题必做，应用题任选）1. 基础题：（1）按照教材中抽象数据类型栈的定义，采用顺序存储结构（用动态数组）或链式存储结构，编写主函数演示顺序栈/链栈的基本操作。（2）按照教材中抽象数据类型队列的定义，采用顺序存储结构（循环队列）或链式存储结构，编写主函数演示循环队列/链队列的基本操作。2. 应用题：（1）算符优先算法为表达式求值（2）舞伴问题：假设在

16、周末舞会上，男士们和女士们进入舞厅时，各自排成一队，跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴，若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。设计一个函数partner()，模拟上述舞伴配对问题。基本要求：1) 由键盘输入数据，每对数据包括姓名和性别；2) 输出结果包括配成舞伴的女士和男士的姓名，以及未配对者的队伍名称和队头者的姓名；实验4 树和二叉树的存储结构的实现实验目的1 熟悉二叉树结点的结构和对二叉树的基本操作。2 掌握对二叉树每一种操作的具体实现。3 学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。4 在二叉树基本操作的基础上掌握对二叉树的一些其

17、它操作的具体实现方法。实验要求1 独立完成；2 程序调试正确，有执行结果。实验内容（基础题必做，应用题任选）1. 基础题：按照教材中抽象数据类型二叉树的定义，采用二叉链表存储结构，编写主函数演示二叉树的基本操作，如：说明：二叉树的基本操作可包括：(1) void InitBT( BTreeNode *&BT ) /初始化二叉树BT (2) void CreateBT( BTreeNode *&BT, char *a ) /根据字符串a所给出二叉树的描述，建立二叉链表存储结构 (3) int EmptyBT( BTreeNode *BT) /检查二叉树BT是否为空，空返回1，否则返回0 (4)

18、int DepthBT( BTreeNode *BT) /求二叉树BT的深度并返回该值 (5) int FindBT( BTreeNode *BT, ElemType x) /查找二叉树BT中值为x的结点，若查找成功返回1，否则返回0 (6) void PreOrder( BTreeNode *BT) /先序遍历二叉树BT(7) void InOrder( BTreeNode *BT) /中序遍历二叉树BT(8) void PostOrder( BTreeNode *BT) /后序遍历二叉树BT(9) void LevelOrder( BTreeNode *BT ) /按层次遍历二叉树BT (

19、10) void LeafCount(BTreeNode *BT , int & count)/求二叉树b的叶子结点个数(11) int NodeCount(BTreeNode *BT)/求二叉树BT的总结点个数(12) void ClearBTree( BTreeNode *&BT ) /清除二叉树BT 2应用题(1)输入n个叶子结点的权值，根据Huffman算法，构造一棵哈夫曼树。(2)家谱管理：本题目对家谱管理进行简单的模拟，以实现查看祖先和子孙个人信息、插入家族成员、删除家族成员等功能。实验5 图的存储结构的实现实验目的1 掌握图的各种存储结构，特别要熟练掌握邻接矩阵和邻接表存储结构。

20、2 遍历是图各种应用的算法的基础，要熟练掌握图的深度优先遍历和广度优先遍历算法，复习栈和队列的应用。实验要求1 独立完成；2 程序调试正确，有执行结果。实验内容1、基础题（至少做一个）（1）图的邻接矩阵定义及实现：定义图的邻接矩阵存储结构，并编写图的初始化、建立图、深度优先/广度优先输出图、输出图的每个顶点的度等基本操作实现函数。以下图为例，建立一个验证操作实现的主函数进行测试。0124653（2）图的邻接表的定义及实现：定义图的邻接表存储结构，并编写图的初始化、建立图、深度优先/广度优先输出图、输出图的每个顶点的度等基本操作实现函数。同时在主函数中调用这些函数进行验证（以下图为例）。0011

21、22334实验6 图的简单应用实验目的1. 掌握图的最短路径概念。2. 掌握生成最小生成树的Prim算法（用邻接矩阵表示图）/克鲁斯卡尔算法。3. 理解求最短路径的DijKstra算法（用邻接矩阵表示图）。实验要求1 独立完成；2 程序调试正确，有执行结果。实验内容（基础题必做，应用题任选）1、基础题编写用邻接矩阵表示有向带权图时图的基本操作的实现函数，主要包括： 初始化邻接矩阵表示的有向带权图 建立邻接矩阵表示的有向带权图 （即通过输入图的每条边建立图的邻接矩阵） 出邻接矩阵表示的有向带权图（即输出图的每条边）。 编写求最短路径的DijKstra算法函数 void Dijkstra( adjmatrix GA, int dist, edgenode *path, int i, int n) ，该算法求从顶点i到其余顶点的最短路径与最短路径长度，并分别存于数组 path 和 dist 中。（可选） 编写打印输出从源点到每个顶点的最短路径及长度的函