数据结构实验指导(3)

据 结 实 验 指 导 书

构1

数

目 录

实验说明 ................................................. 3 实验要求 ................................................. 4 实验1 线性表的顺序存储结构的实现及其应用 ................ 5 实验2 线性表的链式存储结构的实现及其应用 ............... 10 实验3 栈和队列的存储结构的实现 ......................... 17 实验4 树和二叉树的存储结构的实现 ....................... 26 实验5 图的存储结构的实现 ............................... 34 实验6 图的简单应用 .................................... 39 实验7 查找算法的实现................................... 44 实验8 排序算法的实现................................... 47 上机实验报告（仅供参考） ................................ 52

2

实验说明

A．每班学习委员或班长至少在上机实验前一周到软件学院教务室（创新大楼西楼4楼教务室）购买上机实验报告 B．上机实验报告封面上要写完整：班级、姓名、指导老师姓名，

学期、报告日期等。

C．其它

1) 本学期上机实验一共16学时，大家需要完成8个实验。 2) 上机前写好预习报告（即上机报告中调试分析之前的内容），准备好程序和测试数据。

3) 报告要简洁明了，一个实验报告只有3页，书写时字体大小不要太大，以免写不下。

4) 请按照指定时间完成上机报告，上机报告于课程结束后上交存档，缺交上机报告达三分之一者取消考试资格。

5) 请大家认真完成上机任务及上机报告，严禁抄袭。有任何问题可以及时跟任课教师联系！

6) 希望在愉快的环境中完成本学期的学习，请大家积极配合！谢谢！

3

实验要求

一、实验步骤

⒈ 问题分析

充分地分析和理解问题本身，弄清要求做什么，包括功能要求、性能要求、设计要求和约束以及基本数据特性，数据元素之间的关系等。

⒉ 数据结构设计

针对要求解决的问题，考虑各种可能的数据结构，并且力求从中找出最佳方案(必须连同算法一起考虑)，确定主要的数据结构（可以采用抽象数据类型描述）及全局变量。对引入的每种数据结构和全局变量要详细说明其功能、初值和操作特点。

⒊ 算法设计

算法设计分概要设计和详细设计。概要设计着重解决程序的模块设计问题，这包括考虑如何把被开发的问题程序自顶向下分解成若干顺序模块，并决定模块的接口，即模块间的相互关系以及模块之间的信息交换问题。概要设计可以由模块的功能说明和模块之间的调用关系图完成。详细设计则要决定每个模块内部的具体算法，包括输入、处理和输出，采用类C语言描述。

⒋ 测试用例设计

准备典型测试数据和测试方案，测试数据要有代表性、敏感性，测试方案包括模块测试和模块集成测试。

⒌ 上机调试

对程序进行编译，纠正程序中可能出现的语法错误。测试前，先运行一遍程序看看究竟将会发生什么，如果错误较多，则根据事先设计的测试方案并结合现场情况进行错误跟踪，包括打印执行路径或输出中间变量值等手段。

二、实验报告

每次上机实验前，应该写好预习报告。预习报告包括如下内容： （1）问题描述：简述题目要做什么。

（2）设计部分：包括抽象数据类型描述，其他各个模块的功能说明，模块之间的调用关系图，存储结构的定义、基本操作的实现、其他模块的算法等。

（3）测试用例设计 每次实验结束后，在预习报告的基础上撰写完整的实验报告。实验报告应包括如下内容： （1）、（2）同预习报告

（3）调试报告：调试过程中遇到的问题以及如何解决；对设计和编码的讨论和分析。 （4）测试结果。根据预习报告中设计的测试用例进行程序测试，可以贴相应的运行结果截图。

（5）算法分析与改进：重要算法的时间复杂度和空间复杂度分析；算法改进的设想。 （6）总结和体会

所有实验做完后，上交上机实验源程序（.h， .cpp）、可执行文件（.Exe）和相应的运行结果截图。源程序要加注释。如果题目规定了测试数据，则截图结果要包含这些测试数据和运行输出，当然还可以含有其它测试数据和运行输出（有时需要多组数据）。

4

实验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的元素，该元素作为函数返回值

实验步骤参考：

1.打开Visual C++6.0，“文件”菜单——>“新建”——>“工程”——>“win32 Console Application”——>输入“工程名称”和存储“位置”——>“确定”。

2.默认创建“一个空工程”——>“完成”——>“确定”。

11

3. “文件”菜单——>“新建”——>“文件” ——>“C/C++ Header File”——>输入文件名LinkList.h（默认为.h类型，可省去.h）——>“确定”

4.“文件”菜单——>“新建”——>“文件” ——>“C++ Source File”——>输入文件名LinkList.cpp（默认为.cpp类型，可省去.cpp）——>“确定”。

5.打开FileView双击LinkList.h，完成头文件的编写。LinkList.h主要含结构体的定义和函数的实现。

12

13

14

6.打开FileView双击LinkList.cpp，完成源文件的编写。LinkList.cpp主要含main()函数的实现。

15

4、 哈希查找

46

实验8 排序算法的实现

实验目的

1． 掌握各种排序算法的思想。

2． 学会分析各种排序算法的效率和稳定性。

实验要求

1． 独立完成；

2． 程序调试正确，有执行结果。

实验内容（基础题必做，应用题任选）

1.基础题

实现教材中给出的排序算法。编写主函数以菜单形式测试各个排序算法。 2.应用题

编写程序，完成以下任务：

a) 通过键盘输入n个学生的考试成绩表(设计为一个线性表)，表中每个元素由学号、

姓名与分数组成；

b) 按分数高低次序，打印出每个学生在考试中获得的名次，分数相同的为同一名次； c) 按名次打印出每个学生的姓名与分数。

实验提示：

1、 直接插入排序

47

2、 希尔排序

48

3、 冒泡排序

49

4、 快速排序

5、 简单选择排序

6、 堆排序

50

本文来源：https://www.bwwdw.com/article/lt82.html