数据结构实验指导(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

联系客服:779662525#qq.com(#替换为@)