数据结构实验大纲

《数据结构实验》课程实验教学大纲

一、课程基本信息

课程名称：数据结构实验

英文名称：DataStructure

课程编码：1112112B

课程性质：独立设课

课程类别：专业必修课程

课程总学时：16

课程总学分：1

适用专业：计算机科学与技术/网络工程方向

先修课程：高级语言程序设计，离散数学，概率论与数理统计

开课系部：计算机科学与技术系

二、实验课程的目的与要求

三、这门课程的主要任务是培养学生的算法设计能力及良

好的程序设计习惯。通过学习，要求学生能够掌握典型

算法的设计思想及程序实现，能够根据实际问题选取

合适的存储方案设计出简洁、高效、实用的算法，为后

续课程的学习及软件开发打下良好的基础。学习这门课

程，习题和实验是两个关键环节。学生理解算法，上机

实验是最佳的途径之一。因此，实验环节的好坏是学生

能否学好《数据结构》的关键。通过实验课程更好的训

练学生算法分析及算法设计的能力。

四、主要仪器设备与实验基本要求

硬件要求：微型计算机一台（Pentium或以上）

软件要求：Windows操作系统，TurboC或VC++6.0等

实验要求：

1.上机前要作好充分准备，根据实验题目编写好源程序。

2.对上机操作过程中可能出现的问题预先分析，确定调试步骤和测试方法，对运行结

果如何分析等。

3.上•机实验完成后，认真写出实验报告,对上•机中出现的问题进行分析、总结。

4.上机过程中要遵守实验室的各项规章制度,爱护实验设备,服从指导老师安排。

5.本课程的实验过程中，不得进行游戏、上网等操作。

五、实验项目名称和课内学时分配

序时实验实验者必开每套仪器人实验类

实验项目名称

号数属性类别选开数型

1简单算法实验2专业类本科生选开1验证

2线性表的基本操作2专业类本科生必开1综合

3栈和队列的应用2专业类本科生必开1设计

二叉树两种存储结综合

42专业类本科生必开1

构的应用

5图2专业类本科生必开1综合

数据结构综合性实

66专业类本科生必开1设计

验

六、注：设计性和综合性实验如课内学时不够，学生可利用

开放实验室利用课余时间完成本次实验内容。

七、实验内容及要求

实验项目一

实验项目名称：简单算法实验

1.实验项目的目的和要求：

2.复习C语言指针的用法

3.复习C语言结构体的用法

4.理解时间复杂度分析的基本方法

上机实验内容：

1.用指针方式编写程序：从键盘输入N个整型数据，并存入数组，要求将N个数中最大的

数与第一个数交换；将其中最小的数最后•个数交换。

2.有N个学生，每个学生的数据包括字号、姓名、三门课的成绩、平均分。要求从键盘依

次输入N个学生的学号、姓名、三门课的成绩，自动计算三门课的平均分数，并将N个学

生的数据输出。

实验项目二

实验项目名称：线性表的基本操作

1.实验项目的和要求：

2.掌握线性表的特点

3.掌握线性表的顺序存诸结构和链式存储结构的基本运算。

4.尽可能考虑算法的健壮性

5.实验报告中要写出测忒数据、错误分析以及收获。

上机实验内容一：线性表两种存储结构的基本运算

1.用结构体类型描述线性表的两种存储结构

2.完成课堂上所讲的两种存储结构的基本运算

3.要求用二级菜单实现

*****************************

*1------顺序表*

*2------链表*

*0------退出*

*****************************

请输入的选择：（0-2）:

线性表的链式存储

############特##############期

#1一一前插建立链表#

#2一一后插建立链表#

#3一一访问第i个元素#

#4——插入#

#5——删除#

#6——求线性表的表长#

#0—退出#

加肥岫附加##埔海#油特#卯岫仲加

请输入选择（0-6）:

上机实验内容二：超市密码存储箱系统的设计与实现

1.顾客使用箱子的流程为“投一元硬币”--------“找到一个空箱子，同时产生密码”

（系统完成）--------“打印密码，打开箱子”（系统完成）---------“取密码纸存包，并

关闭箱子，入超市购物”--------“购物结束”---------“输入密码”---------“找到对应

charcallL12J;/*手1机号码*/

}DataType：/*员工通讯信息的结构类型*/

typedefstructnode

{DataTypcdata;/*结点的数据域*/

structnode*next;/*结点的指针域*/

}ListNode,*LinkList；/*通讯录链表的结构类型*/

上机实验内容四：运动会记分子系统或学生成绩管理子系统

1.参加运动会的N个学校编号为比赛分成M个男子项目和W个女子项目，每个项

目取前3名，得分分别为5,3,2。写一个程序产生各种成绩心和得分报表。

2.完成功能包括如下：

①产生一总成绩表，包括：系名、男子团体总分、女子团体总分、团体总分

存储结构要求用线性表的顺序存储。

②实验报告中要写出测试数据、错误分析以及收衣。

③若选择学生成绩管理子系统，可仿照运动会记分子系统完成用关的插入、删除'查找及各

种统计工作。

实验项目三

实验名称：栈和队列的应用

1.实验目的和要求：

2.掌握栈和队列的概念和特点

3.掌握栈和队列在顺序和链式存储结构下的插入、删除党法

认真分析项目实例中的内容，将相关程序在计算机上运行实现

上机实验内容■：表达式求值问题

1.求一个数学表达式的隹:：用户输入一个包含正整数、括号和四则运算符（“+”、“一”、

“*”、“/”）的算术表达式，计算其结果。

2.设计分析

首先置操作数栈为空栈，表达式起始符为运算符栈底元素；依次读入表达式中

每个字符，若是操数则进操作数栈，若是操作符则和操作符栈顶的运算符进行比较优先权后

作相应的操作，直到整个表达式求值完毕（即操作符栈顶元素和当前读入的字符均为“#"）

3.结点结构类型描述如下

typedefstruct

（

char*base,*top;

intstacksizc：

}sqstack;

上机实验内容二：迷宫求解问题

1.迷宫是一个m行n列的矩阵，其中0表示无障碍，1表示有障碍。设入口为（1,1）,

出口为（m,n）,即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿

原路退回，换一个方向再继续探索，直到出口为止。

2.迷宫的功能

要求随机生成一个m行n列的矩阵，为了操作方便可以在矩阵外围生成一圈障碍，设

置东南西北四个方向，采用链栈进行操作。最后迷宫如不是通路给出“此迷宫元解”，如是

通路要求输出所走过的路径。

3.结点结构类型描述如下

typedefstructnode

{introw;

intcol;

structnode*ncxt;

）；

实验项目四

实验名称：二叉树两种存储结构的应用

1.实验目的和要求：

2.掌握二叉树的遍历思想及二叉树的存储实现。

3.掌握二叉树的基本操作：建立二叉树、二叉树的遍历

4.选择一种形式完成二叉树的显示

5.掌握二叉树的常见算法的程序实现

6.实验报告中要写出测试数据、错误分析以及收获

上机实验内容一：二叉树的建立及相关算法的实现

1.完成的功能包括如卜几点：

①编程实现建立一棵二叉树，然后对其进行先序、中序和后序遍历。

分析：将要输入的二叉树按照其对应的完全二叉树的顺序输入，若当前位置不存在

结点则输入@

②显示二叉树

③求二叉树的高度及二叉树的叶子个数等等

④在主函数中设计一个简单的菜单，分别调试上述算法

上机实验内容二：哈夫曼编码/译码系统

1.要求编写一程序模拟传输过程，实现在发送前将要发送的字符信息进行编码,

然后进行发送，接收后将传来的数据进行译码，即将信息还原成发送前的字符信息。

2.设计分析

在本例中的克法主要有：哈夫曼树的建立：哈夫曼编码的生成；对编码信息的翻译。

要求设置发送者和接收者两个功能。

发送者的功能包括：

①输入待传送的字符佶息;②统计字符信息中出现的字符类数和各字符出现的次数

(频率)：③根据字符的种类数和各字符出现的次数建立哈夫曼树：④利用以上哈夫曼树求

出各字符的哈夫曼编码：⑤将字符信息转换成对应的编码信息进行传送。

接收者的功能包括：

①接收发送者传送来的编码信息；②利用上述哈夫曼树对编码进行翻译，即将编码信

息还原成发送前的字符信息。

3.结点的类型定义

①哈夫曼树的存储结构类型定义为：

typedefstruct

(

chardata;/*编码对应的字符*/

intweight;/=♦结点的权值*/

intIchiId,rchild,parent;/*左右孩子及双亲的下标*/

}HTNode;

②哈夫曼编码的存储结构类型定义为：

typedefstruct

(

charbits[N];/*存放哈夫属编码的字符数组*/

intstart;/*记录编码的起始位置，因为每种字符的编码长度不同*/

}HCode;

说明：只占用2个课内学时.学生在开放实验室利用课余时间完成本次实验内容。

实验项目五

实验名称：图子系统

实验目的和要求：

1.掌握图的存储思想及其存储实现

2.掌握图的深度、广度优先遍历算法思想及其程序实现

3.掌握图的常见应用算法的思想及其程序实现

实验内容一：图的遍历问题

1.键盘输入以下结点数据：太原、成都、北京、上海、天津、大连、河北。建立一个有

向图或无向图（自定）的邻接表并输出该邻接表

2.在图的邻接表的基础上计算各顶点的度，并输出

3.以有向图的邻接表为基础实现输出它的拓扑排序序列

4.采用邻接表存储实现无向图的深度优先遍历

5.采用邻接表存储实现无向图的广度优先遍历

6.采用邻接矩阵存储实现无向图的最小生成树的PRIM算法

7.在主函数中设计一个简单的菜单，分别调试上述算法

实验内容二：所有顶点对的最短路径

1.设置.4个村庄之间的交通，村庄之间的距离用各边上的权值来表示。现在要求从这

4个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最

远的村庄到医院最近。

2.设计分析

用有向加权图表示的交通图中，有向边Qi,vj＞表示第i个村庄和第j个村庄之间

有道路，边上的权表示这条道路的长度。该问题的实质是求解任意两顶点间的最短

路径问题。即求出每个顶点到其他顶点的最短路径的最大值，最大值最小的顶点作

为医院所在村庄。

3.结构类型定义

typedefcharvextype;/*顶点数据类型*/

typedefintedgetype;/*边数据类型*/

typcdofstruct

{

vextypevex[maxsize];

edgetypearcEmaxsizc][maxsizc];

intvexnum,arcnuir;

}Mgraph;

说明：只占用2个课内学时，学生在开放实验室利用课余时间完成本次实验内容。

实验项目六

实验名称：数据结构综合性实验

实验目的和要求：

掌握小型系统开发方法，提高学生综合开发能力。根据实际问题，设计方案，综合运用

课程知识，完成《学生成绩管理系统》或《数据结构克法演示系统》的设计、编程与调试工

作。

上机实验内容一：

分析、调研数据结构课程所学的匏法（功能模块）或学生成绩管理的相关功能模块，采

用结构化设计思想、模块分解的规则构成一个易使用的小型管理系统。

具体要求见《数据结构实验》课程设计

上机实验内容二：手机短信中电话号码和手机号码的识别与提取

1.在使用手机收发短信时，收到的短信内容中常会包含对方发来的电话号码或手机号码，

为了方便用户能直接提取其中的号码并存入到其手机的通讯录中，现要求开发手机系统软

件中的一个子功能，实现从手机短信内容中识别和提取电话号码（7位或8位）和手机号码

（11位），并将其存入通讯录中。

2.设计分析

要从手机短信的内容中识别电话号码或手机号码，必须从题信的第一个字符开始查找，

找到第一个数值型字符（'0'〜'9D,然后依次判断其后的字符，若其后有连续的6个或

7个数值型字符，则将其识别成电话号码并提取，若其后有连续的10个数值型字符，则将

其识别成手机号码并提取。继续向后搜索直到整个短信查找完毕。

3.存储结构类型定义

①短信的存储结构类型定义

typedefstruct

{

charword[200];/*短信内容*/

intlength;/*短信长度*/

iMessage;

②通讯录中记录的存储结构类型的定义

typedefstruct

（

charname[8];/*姓名*/

charphone[11];/*电话号码或手机号码*/

}Notc;

上机实验内容三：药店的药品销售统计系统

L设计一系统，实现医药公司定期对各药品的销售记录进行统计，并按药品编号、单价、销

售量或销售额做出排序。

2.设计分析

在设计中，首先从数据文件读出各药品的信息记录，存储在顺序表中。各药品的信息包

括：药品编号、药品名称、单价、销售量、销售额。其中药品编号共4位，采用字母和数字

混合编号，如：B125,前一位为大写字母，后三位为数字。

3.存储结构类型定义

①药品信息的存储结构类型定义

typcdcfstructnode

{

charnum[4];/*药品编号*/

charname[10]:/*药品名称*/

floatprice;/*单价*/

intcount;/*销售量*/

floatsale;/*销售额*/

}DataType;

②存储药品信息的顺序表的定义

typedefstruct

（

DataTyperfmaxsize];

intlength;

}sequcnList;

上机实验内容四：电视大赛观众投票及排名系统

1.在很多电视大赛中，通常当选手表演结束后，现场观众通过手中的按键对参赛选手进行

投票，然后对选于获得的票数进行统计，从高到低进行降序排列，从而自动产生冠军、亚军

和李军。现要求编写一程序模拟实现上述系统的功能。

2.设计分析

在本系统中，首先输入参赛选手的人数（范围为1-9个），然后根据人数通过malloc

函数来开辟存放选手信息的顺序表。将选手的编号和姓名依次存入顺序表单元中，观众通过

按健进行投票，按“1”表示为1号选手投票，按“2”表示为2号选手投票，依次类推。以

按“0”作为投票结束标志。投票结束后进行排序。

3.存储结构类型定义

①选手信息的存储结构类型定义

typedefstructnod