数据结构实验指导书目录实验说明 (3)实验要求 (4)实验1 线性表的顺序存储结构的实现及其应用 (5)实验2 线性表的链式存储结构的实现及其应用 (10)实验3 栈和队列的存储结构的实现 (17)实验4 树和二叉树的存储结构的实现 (26)实验5 图的存储结构的实现 (34)实验6 图的简单应用 (39)实验7 查找算法的实现 (44)实验8 排序算法的实现 (47)上机实验报告（仅供参考） (52)实验说明A．每班学习委员或班长至少在上机实验前一周到软件学院教务室（创新大楼西楼4楼教务室）购买上机实验报告B．上机实验报告封面上要写完整：班级、姓名、指导老师姓名，学期、报告日期等。
C．其它1)本学期上机实验一共16学时，大家需要完成8个实验。
2)上机前写好预习报告（即上机报告中调试分析之前的内容），准备好程序和测试数据。
3)报告要简洁明了，一个实验报告只有3页，书写时字体大小不要太大，以免写不下。
4)请按照指定时间完成上机报告，上机报告于课程结束后上交存档，缺交上机报告达三分之一者取消考试资格。
5)请大家认真完成上机任务及上机报告，严禁抄袭。
有任何问题可以及时跟任课教师联系！6)希望在愉快的环境中完成本学期的学习，请大家积极配合！谢谢！实验要求一、实验步骤⒈问题分析充分地分析和理解问题本身，弄清要求做什么，包括功能要求、性能要求、设计要求和约束以及基本数据特性，数据元素之间的关系等。
⒉数据结构设计针对要求解决的问题，考虑各种可能的数据结构，并且力求从中找出最佳方案(必须连同算法一起考虑)，确定主要的数据结构（可以采用抽象数据类型描述）及全局变量。
对引入的每种数据结构和全局变量要详细说明其功能、初值和操作特点。
⒊算法设计算法设计分概要设计和详细设计。
概要设计着重解决程序的模块设计问题，这包括考虑如何把被开发的问题程序自顶向下分解成若干顺序模块，并决定模块的接口，即模块间的相互关系以及模块之间的信息交换问题。
概要设计可以由模块的功能说明和模块之间的调用关系图完成。
详细设计则要决定每个模块内部的具体算法，包括输入、处理和输出，采用类C 语言描述。
⒋测试用例设计准备典型测试数据和测试方案，测试数据要有代表性、敏感性，测试方案包括模块测试和模块集成测试。
⒌上机调试对程序进行编译，纠正程序中可能出现的语法错误。
测试前，先运行一遍程序看看究竟将会发生什么，如果错误较多，则根据事先设计的测试方案并结合现场情况进行错误跟踪，包括打印执行路径或输出中间变量值等手段。
二、实验报告每次上机实验前，应该写好预习报告。
预习报告包括如下内容：（1）问题描述：简述题目要做什么。
（2）设计部分：包括抽象数据类型描述，其他各个模块的功能说明，模块之间的调用关系图，存储结构的定义、基本操作的实现、其他模块的算法等。
（3）测试用例设计每次实验结束后，在预习报告的基础上撰写完整的实验报告。
实验报告应包括如下内容：（1）、（2）同预习报告（3）调试报告：调试过程中遇到的问题以及如何解决；对设计和编码的讨论和分析。
（4）测试结果。
根据预习报告中设计的测试用例进行程序测试，可以贴相应的运行结果截图。
（5）算法分析与改进：重要算法的时间复杂度和空间复杂度分析；算法改进的设想。
（6）总结和体会所有实验做完后，上交上机实验源程序（.h， .cpp）、可执行文件（.Exe）和相应的运行结果截图。
源程序要加注释。
如果题目规定了测试数据，则截图结果要包含这些测试数据和运行输出，当然还可以含有其它测试数据和运行输出（有时需要多组数据）。
实验1 线性表的顺序存储结构的实现及其应用实验目的1．熟悉C语言的上机环境，掌握使用VC环境上机调试程序的基本方法；2．会定义线性表的顺序存储结构。
3．熟悉对顺序表的一些基本操作和具体的函数定义。
4．理解利用基本操作进行一些实际的应用型程序设计。
实验要求1．独立完成。
2．程序调试正确，有执行结果。
实验内容（基础题必做，应用题任选）1、基础题：编写应用程序（填空），实现可以在顺序表中插入任意给定数据类型数据的功能（定义为ElemType抽象数据类型）。
要求在主函数中定义顺序表并对该顺序表插入若干个整数类型的数据（正整数），对它们求和并输出。
请把主函数设计为一个文件SqList.cpp，其余函数设计为另一个文件SqList.h。
请填空完成以下给出的源代码并调试通过。
（1）文件SqList.h:typedef struct List{ElemType *elem;int 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 <stdio.h>#include <stdlib.h>typedef ElemType; //填空1#define MAXSize 10#include "SqList.h"void 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(myList, i);sum = + x; //填空4}printf("%d\n ", sum);ClearList(myList);}2.应用题（1）求集合A、B的并集C。
（2）归并两个有序表La和Lb成一个新的有序表Lc。
有序指值非递减。
要求：把该函数添加到文件SqList.h中，并在主函数文件SqList.cpp中添加相应语句进行测试。
实验步骤参考：1.打开Visual C++6.0，“文件”菜单——>“新建”——>“工程”——>“win32 Console Application”——>输入“工程名称”和存储“位置”——>“确定”。
2.默认创建“一个空工程”——>“完成”——>“确定”。
3. “文件”菜单——>“新建”——>“文件”——>“C/C++ Header File”——>输入文件名SqList.h（默认为.h类型，可省去.h）——>“确定”4.“文件”菜单——>“新建”——>“文件”——>“C++ Source File”——>输入文件名SqList.cpp（默认为.cpp类型，可省去.cpp）——>“确定”。
5.打开FileView双击SqList.h，完成头文件的编写。
SqList.h主要含结构体的定义和函数的实现。
6.打开FileView双击SqList.cpp，完成源文件的编写和填空。
SqList.cpp主要含main()函数的实现。
7.编译运行。
实验2 线性表的链式存储结构的实现及其应用实验目的1．掌握线性表的建立、插入、删除等基本操作的编程实现，进一步编程实现查找、排序等操作，存储结果采用顺序表存储结构。
2．理解利用基本操作进行一些实际的应用型程序设计。
实验要求1．可以依次完成主要功能来体现功能的正确性，也可以用菜单管理完成大部分功能，要求可以重复运行。
2．准备好测试数据，程序调试正确，有执行结果。
3．程序是自己开发的，在界面上注明***原创；参考或改写他人的，注明***参考他人版。
实验内容（基础题必做，应用题任选1个）1、基础题：线性表基本操作的实现(演示单链表的创建、插入、删除、查找、输出等操作)，通过简单实例测试各基本操作函数算法的正确性。
基本操作函数如下：Status InitList(LinkList &L)//初始化只含有头结点的空的单链表，返回函数状态值void DestroyList(LinkList &L) //销毁单链表void ClearList(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 ListDelete(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”——>输入“工程名称”和存储“位置”——>“确定”。
2.默认创建“一个空工程”——>“完成”——>“确定”。
3. “文件”菜单——>“新建”——>“文件”——>“C/C++ Header File”——>输入文件名LinkList.h（默认为.h类型，可省去.h）——>“确定”4.“文件”菜单——>“新建”——>“文件”——>“C++ Source File”——>输入文件名LinkList.cpp（默认为.cpp类型，可省去.cpp）——>“确定”。