数据结构-数据结构上机实验指导书

遍草栗喟工大劈

得！於EASTCHINAUNIVERSITYOFSCIENCEANDTECHNOLOGY

《算法与数据结构》

实验指导书

2

第一部分算法与数据结构课程实验概述

实验目的

《算法与数据结构》是计算机专业的主干课程和必修课程之一，其目的

是让大家学习、分析和研究数据对象特征，掌握数据组织方法和计算机的表

示方法，以便选择合适的数据逻辑结构和存储结构，设计相应的运算操作，

把现实世界中的问题转化为计算机内部的表示与处理的方法,要求掌握算法

的时间、空间复杂度分析基本技术，培养良好的程序设计风格，掌握进行复

杂程序设计的技能。在计算机科学领域，尤其是在系统软件和应用软件的设

计和应用中要用到各种数据结构，因此，掌握数据结构对提高软件设计和程

序编制水平有很大的帮助。

二.实验要求

2.1实验步骤

设计步骤的规范不但可以培养学生科学的工作方法和作风，而且还能有

效地减少错误，提高工作效率。因此必须严格执行良好的实验步骤规范（包

括上机操作规范）。本课程实验的基本步骤是：

2.1.1问题分析

充分地分析和理解问题本身，明确问题要求做什么。对问题的描述应避

开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。例如；

输入、输出数据的类型、值的范围以及形式等。同时为调试程序准备好测试

数据，包含合法的输入数据和非法形式输入的数据。

2.1.2设计和编码

3

设计即是对问题描述中涉及的操作对象定义相应的数据类型，定义主程

序模块和各抽象数据类型；定义相应的存储结构并写出各过程和函数的伪码

算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简

单和易于调试。

编码即把详细设计的结果进一步求精为程序设计语言程序，写出源程

序。对程序中的疑问应作出记号，以便上机时注意解决。每个明确的功能模

块程序一般不超过60行，程序的每一行不得超过60个字符，否则要进一步

划分。

2.1.3上机前程序静态检查

上机前程序静态检查可有效提高调试效率，减少上机调试程序时的无谓

错误。

静态检查主要有两种途径：用一组测试数据手工执行程序；通过阅读或

给别人讲解自己的程序而深入全面地理解程序逻辑。把程序中的明显错误事

先排除。

2.1.4上机调试程序

上机实验时要带上《C语言》教材、《数据结构》教材、《数据结构上机

实验指导书》，调试最好分模块进行，自底向下，即先调试低层过程或函数。

调试过程中应多动手确定疑点，通过修改程序来证明。

调试正确后，认真整理源程序及其注释，写出或打印出带有完整注释的

且格式良好的源程序清单和结果。

2.1.5完成上机实验报告

2.2实验报告格式

4

得;睁EASTCHINAUNIVERSITYOFSCIENCEANDTECHNOLOGY

《算法与数据结构》

实验报告本

班级:___________________

学号：___________________

姓名:___________________

指导教师：___________________

5

2.3实验过程

需求分析

以无歧义的陈述说明程序设计的任务，强调程序要做什么。明确规定：

(1).输入的形式和输入值的范围；

(2)输出的形式

(3)程序所能达到的功能

(4)测试数据：包括正确的输入及其输出结果，含有错误的输入及其

输出结果。

1.系统设计

1.说明本程序中用到的所有抽象数据类型的定义；

2.主程序的流程以及各程序模块之间的层次调用关系，画出函数的调用关

系图。

3.列出各个功能模块的主要功能及输入输出参数。

3.调试分析

内容包括：

(1).调试过程中遇到的问题是如何解决的及对设计与实现的回顾讨论与分

析。

(2)算法的时间复杂度分析(包括基本操作和其他算法)和改进设想；

(3)经验与体会等。

4.测试结果

列出你的测试结果，包括输入与输出，这里的测试数据应完整和严格，可用

需求分析中的测试数据。

5、用户手册

说明如何使用你编写的程序，详细列出每一步操作步骤。

6、附录

6

即带注释的源程序清单和结果。除原有注释外再加一些必要的注释和断

言（关键语句或函数功能的注释）。对填空和改错题还要写出正确答案，如

果题目规定了测试数据，则结果要包含这些测试数据和运行输出，当然还可

以含其它测试数据及其运行输出。

2.4考核及评分办法

上机实验成绩根据上机考勤、调试情况、实验报告评分，分为五级制：

优、良、中、及格、不及格。

7

第二部分上机实验内容

序

实验实验每组课程

号

实验名称主要内容目标

类型时数人数

C/C++语言的循环、条件

数据结构实现基础实

1控制语句，数组、链表A211

验

等数据存储

熟练掌握顺序和链式线性

2线性表实验B21

表的基本操作1,2

熟练掌握堆栈和队列的

基本操作，栈在表达式

3栈和队列实验B211,2

求解中的应用，双端队

列的应用

熟练掌握二叉树的存储

结构，二叉树的先序、

4树的应用实验B411,2

中序遍历，二叉搜索树、

哈夫曼编码

熟练掌握图的存储结构、连

通性、广度优先和深度优先

5图的应用实验搜索、Dijkstra单原点最短B411,2

路径、拓扑排序、Floyd算

法

熟练掌握选择、插入、

6排序算法B211,2

交换、归并算法的应用

8

实验一数据结构实现基础

一、实验目的

1.了解数据结构的语法基础。

二、实验内容

1.数组元素循环左移问题2-2；

2.整数分解问题2-3；

3.数列求和问题2-6.

9

实验二线性表

一、实验目的

1.了解线性表的特性，以便灵活应用。

2.熟练掌握线性表的各种操作和应用

二、实验内容

10

实验三栈和队列

一、实验目的

1.掌握栈和队列的概念及存储方法。

2.掌握顺序栈、链式栈、循环队列的算法。

3.熟练掌握编写实现栈和队列的各种运算的算法。

二、实验内容

11

实验四树和二叉树

一、实验目的

1.掌握二叉树，二叉树排序数的概念及存储方法。

2.掌握二叉树的遍历算法。

3.熟练掌握编写实现树的各种运算的算法。

二、实验内容

12

实验五图

一、实验目的

1.熟悉图的各种存储方法。

2.掌握遍历图的递归和非递归的算法。

3.理解图的有关算法。

二、实验内容

1、任务调度的合理性

假定一个工程项目由一组子任务构成，子任务之间有的可以并行执行，

有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任

务、以及每个子任务可以执行所依赖的子任务集。例如完成一个专业的所

有课程学习和毕业设计可以看成一个本科生要完成的一项工程，各门课程可

以看成是子任务。有些课程可以同时开设，比如英语和C程序设计，它们

没有必须先修哪门的约束；有些课程则不可以同时开设，因为它们有先后的

依赖关系，比如C程序设计和数据结构两门课，必须先学习前者。

但是需要注意的是，对一组子任务，并不是任意的任务调度都是一个可

行的方案。比如方案中存在“子任务A依赖于子任务B,子任务B依赖于子

任务C,子任务C又依赖于子任务A"，那么这三个任务哪个都不能先执行,

这就是一个不可行的方案。你现在的工作是写程序判定任何一个给定的任务

调度是否可行。

输入说明：输入第一行给出子任务数N（S100）,子任务按1~N编号。随后

N行，每行给出一个子任务的依赖集合：首先给出依赖集合中的子任务数K,

随后给出K个子任务编号，整数之间都用空格分隔。

输出说明：如果方案可行，则输出1,否则输出0。

测试样例：输入

11

11

223

输出：1

13

2、社交网络图中结点的“重要性”计算

在社交网络中，个人或单位(结点)之间通过某些关系(边)联系起来。

他们受到这些关系的影响，这种影响可以理解为网络中相互连接的结点之间

戛延的一种相互作用，可以增强也可以减弱。而结点根据其所处的位置不同，

其在网络中体现的重要性也不尽相同。

“紧密度中心性”是用来衡量一个结点到达其它结点的“快慢”的指标，即

一个有较高中心性的结点比有较低中心性的结点能够更快地(平均意义下)

到达网络中的其它结点，因而在该网络的传播过程中有更重要的价值。在有

N个结点的网络中，结点vi的“紧密度中心性”Cc(vi)数学上定义为vi到其余

所有结点vj。为)的最短距离d(vi,vj)的平均值的倒数：

N

N-l

Cc（v,）=T—rErf（v.>vP

~~N

IV—1

"J

对于非连通图，所有结点的紧密度中心性都是0。

给定一个无权的无向图以及其中的一组结点，计算这组结点中每个结点

的紧密度中心性。

输入格式：输入第一行给出两个正整数N和M,其中N(<104)是图

中结点个数，顺便假设结点从1到N编号；M(<105)是边的条数。随后

的M行中，每行给出一条边的信息，即该边连接的两个结点编号，中间用

空格分隔。最后一行给出需要计算紧密度中心性的这组结点的个数K(ROO)

以及K个结点编号，用空格分隔。

输出格式：按照Cc(i)=x.xx的格式输出K个给定结点的紧密度中心性,

每个输出占一行，结果保留到小数