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

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

一、 《数据结构课程实验》的地位与作用

“数据结构”是计算机专业一门重要的专业技术基础课程，是计算机专业的一门核心的

关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并做了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： （1） 内容丰富，学习量大，给学习带来困难；

（2） 贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点；

（3） 所用到的技术多，而在此之前的各门课程中所介绍的专业性知识又不多，因而加大了学习难度；

（4） 隐含在各部分的技术和方法丰富，也是学习的重点和难点。

根据《数据结构课程》课程本身的技术特性，设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练，突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为10。

二、《数据结构课程实验》的目的和要求

不少学生在解答习题尤其是算法设计题时，觉得无从下手，做起来特别费劲。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。

为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法，如算法设计的构思方法，动态链表，算法的编码，递归技术，与特定问题相关的技术等，要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上，掌握分析、解决实际问题的能力。

三、 《数据结构课程实验》内容

课程实验共10学时，要求完成以下五个题目：

实习一 约瑟夫环问题（2学时）

用循环链表实现约瑟夫环问题，熟悉链表结构的使用。 实习二 八皇后问题 （2学时）

在8×8的棋盘上放置彼此不受攻击的8个皇后，熟悉递归与回溯程序设计方法。 实习三 二叉树基本操作（2学时）

创建、遍历、显示二叉树，通过二叉树的基本操作，掌握树结构的处理方法。 实习四 哈夫曼编码与译码

针对字符集A及其各字符的频率值（可统计获得）给出其中给字符哈夫曼编码，并

针对一段文本（定义在A上）进行编码和译码，实现一个哈夫曼编码/译码系统。

实习五 最小生成树问题（2学时）

在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。

四、 《数据结构课程实验》考核方式

采用上机情况、程序质量、实习报告相结合的形式，满分为100分。

1． 上机情况（30%）

包括出勤情况、调试表现、是否上网、玩游戏。 2． 程序质量（50%） 3． 实习报告（20%）

《数据结构课程实验》指导书

实习一 线性表

本次实习的主要目的在于熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉各种链表的操作为侧重点。通过本次实习还可帮助读者复习高级语言的使用方法。

1、城市链表 [问题描述]

将若干城市的信息，存入一个带头结点的单链表。结点中的城市信息包括：城市名，城市的位置坐标。要求能够利用城市名和位置坐标进行有关查找、插入、删除、更新等操作。 [基本要求]

（1） 给定一个城市名，返回其位置坐标；

（2） 给定一个位置坐标P和一个距离D，返回所有与P的距离小于等于D的城市。 [测试数据]

由学生依据软件工程的测试技术自己确定。注意测试边界数据。

2、约瑟夫环 [问题描述] 约瑟夫（Joeph）问题的一种描述是：编号为1,2,?,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 [基本要求]

利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 [测试数据]

m的初值为20；密码：3，1，7，2，4，8，4（正确的结果应为6，1，4，7，2，3，5）。 [实现提示]

程序运行后首先要求用户指定初始报数上限值，然后读取各人的密码。设n≤30。 [选作内容]

向上述程序中添加在顺序结构上实现的部分。

3、线性表的逆置 [问题描述]

分别以不同存储结构实现线性表的就地逆置。线性表的就地逆置就是在原表的存储空间内将线性表（a1,a2,a3,?,an）逆置为（an，an-1，?，a2，a1）。 [基本要求]

用顺序存储结构实现线性表的就地逆置，并将结果输出。 [测试数据]

由学生依据软件工程的测试技术自己确定。注意测试边界数据，如空表。

[实现提示]

设三个连续的指针，分别指向当前结点、当前结点的前趋、当前结点的后继。 [选作内容]

利用单链表作为存储结构。首先先建立线性表的带头结点的单链表表示形式，之后在不借助辅助结点空间的情况下实现单链表的逆置，并将结果输出。

4、长整数运算 [问题描述]

设计一个程序实现两个任意长的整数求和运算。 [基本要求]

利用双项循环链表实现长整数的存储，每个结点含一个整型变量。任何整型变量的范围是 -（215-1）~（215-1）。输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。 [测试数据]

（1） 0；0；应输出“0”。

（2） -2345,6789；-7654,3211；应输出“-1,0000,0000”。

（3） -9999,9999；1,0000,0000,0000；应输出“9999,0000,0001”。 （4） 1,0001,000；-1,0001,0001；应输出“0”。 （5） 1,0001,0001；-1,0001,0000；应输出“1”。

[实现提示]

（1） 每个结点中可以存放的最大整数为215-1=32767，才能保证两数相加不会溢出。但若这样存，即相当于按32768进制数存，在十进制数与32768进制数之间的转换十分不方便。故可以在每个结点中仅存十进制数的4位，即不超过9999的非负整数，整个链表视为万进制数。 （2） 可以利用头结点数据域的符号代表长整数的符号。用其绝对值表示元素结点数目。相加过程中不要破坏两个操作数链表。两操作数的头指针存于指针数组中是简化程序结构的一种方法。不能给长整数位数规定上限。 [选作内容]

修改上述程序，使它在整型量范围是-（2n-1）~（2n-1）的计算机上都能有效地运行。其中，n是由程序读入的参量。输入数据的分组方法可以另行规定。

实习二 栈、队列与递归算法设计

仅仅认识到栈和队列是两种特殊的线性表是远远不够的，本次实习的目的在于使读者深入了解栈和队列的特征，以便在实际问题背景下灵活运用它们；同时还将巩固这两种结构的构造方法，接触较复杂问题的递归算法设计。

1、数制转换问题 [问题描述]

将十进制数N和其它d进制数的转换是计算机实现计算的基本问题，其解决方案很多，其中最简单方法基于下列原理：即除d取余法。例如：（1348）10=（2504）8

N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 从中我们可以看出，最先产生的余数4是转换结果的最低位，这正好符合栈的特性即后进先出的特性。所以可以用顺序栈来模拟这个过程。 [基本要求]

对于键盘输入的任意一个非负的十进制整数，打印输出与其等值的八进制数。由于上述的计算过程是从低位到高位顺序产生的八进制数的各个数位，而打印输出，一般来说应从高位到地位进行，恰好和计算过程相反。因此可以先将计算过程中得到的八进制数的各位进栈，待相对应的八进制数的各位均产生以后，再使其按顺序出栈，并打印输出。即得到了与输入的十进制数相对应的八进制数。 [测试数据]

由学生依据软件工程的测试技术自己确定。注意测试边界数据。

2、回文判断 [问题描述]

试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如‘序列1 & 序列2’模式的字符序列。其中序列1和序列2 中都不含字符‘&’，且序列2 是序列1的逆序列。例如，‘a+b&b+a’是属该模式的字符序列，而‘１+３&３－１’则不是。 [实现提示]

首先，序列1进栈，然后序列1出栈并与序列2比较。 [测试数据]

由学生依据软件工程的测试技术自己确定。注意测试边界数据，如序列1和序列2均为空串。

3、商品货架管理 [问题描述]

商品货架可以看成一个栈，栈顶商品的生产日期最早，栈底商品的生产日期最近。 上货时，需要倒货架，以保证生产日期较近的商品在较下的位置。 [基本要求]

针对一种特定商品，实现上述管理过程。 [实现提示]

用栈模拟货架和周转空间。 [测试数据]

由学生依据软件工程的测试技术自己确定。注意测试边界数据，如空栈。

4、括号匹配的检验 [问题描述]

假设表达式中允许有两种括号：圆括号和方括号，其嵌套的顺序随意，即（（）[ ]）或 [（[ ] [ ]）]等为正确格式，[（ ]）或（（（]均为不正确的格式。检验括号是否匹配的方法可用“期待的紧迫程度”这个概念来描述。例如：考虑下列的括号序列： [ ( [ ] [ ] ) ]

1、二叉排序树 [问题描述]

从键盘读入一组数据，建立二叉排序树并对其进行查找、遍历、格式化打印等有关操作。 [基本要求]

建立二叉排序树并对其进行查找，包括成功和不成功两种情况，并给出查找长度。 [测试数据]

由学生依据软件工程的测试技术自己确定。注意测试边界数据。 [选作内容]

实现二叉排序树的插入、删除操作。

2、哈希表设计 [问题描述]

针对某个集体中人名设计一个哈希表，使得平均查找长度不超过R，并完成相应的建表和查表程序。 [基本要求]

假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用线性探测再散列法或链地址法处理冲突。 [测试数据]

取读者周围较熟悉的30个人名。 [选作内容] （1） 从教科书上介绍的集中哈希函数构造方法中选出适用者并设计几个不同的哈希函数，比较他们的地址冲突率（可以用更大的名字集合作实验）。

（2） 研究这30个人名的特点，努力找一个哈希函数，使得对于不同的拼音名一定不发生地址冲突。

（3） 在哈希函数确定的前提下尝试各种不同处理冲突的方法，考察平均查找长度的变化和造好的哈希表中关键字的聚集性。

3、内部排序算法比较 [问题描述]

各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。 [基本要求]

（1） 对以下10种常用的内部排序算法进行比较：直接插入排序；折半折入排序；二路插入排序；希尔排序；起泡排序；快速排序；简单选择排序；堆排序；归并排序；基数排序。

（2） 待排序表的表长不少于100；其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字移动次数（关键字交换计为3次移动）。 [测试数据]

由随机产生器决定。 [实现提示]

主要工作是设法在程序中适当的地方插入计数操作。程序还可以包括计算几组数据得出结果波动大小的解释。注意分块调试的方法。

[选作内容]

对不同的输入表长做试验，观察检查两个指标相关于表长的变化关系。还可以对稳定性做验证。

3、统计成绩 [问题描述]

给出n个学生的m门考试的成绩表，每个学生的信息由学号、姓名以及各科成绩组成。对学生的考试成绩进行有关统计，并打印统计表。 [基本要求]

（1） 按总数高低次序，打印出名次表，分数相同的为同一名次； （2） 按名次打印出每个学生的学号、姓名、总分以及各科成绩。 [测试数据]

由学生依据软件工程的测试技术自己确定。注意测试边界数据。 [选作内容]

对各科成绩设置不同的权值。

附录2

实验报告示例

__________级 __________班 _______年_______月_____日 姓名____________ 学号____________ 电话_____________

1．实验题目

编制一个演示单链表插入、删除、查找等操作的程序 2．需求分析

本演示程序用TC编写，完成单链表的生成，任意位置的插入、删除，以及确定某一元素在单链表中的位置。

① 输入的形式和输入值的范围：插入元素时需要输入插入的位置和元素的值；删除元素时输入删除元素的位置；查找操作时需要输入元素的值。在所有输入中，元素的值都是整数

② 输出的形式：在所有三种操作中都显示操作是否正确以及操作后单链表的内容。其中删除操作后显示删除的元素的值，查找操作后显示要查找元素的位置。 ③ 程序所能达到的功能：完成单链表的生成（通过插入操作）、插入、删除、查找操作 ④ 测试数据：

A． 插入操作中依次输入11，12，13，14，15，16，生成一个单链表 B． 查找操作中依次输入12，15，22返回这3个元素在单链表中的位置 C． 删除操作中依次输入2，5，删除位于2和5的元素 3．概要设计

1）为了实现上述程序功能，需要定义单链表的抽象数据类型： ADT LinkList {

数据对象：D={ai|ai∈IntegerSet,i=0,1,2,?,n,n≥0} 数据关系：R={|ai,ai+1 ∈D} 基本操作：

InitLinkList(&L)

操作结果：构造一个空的单链表L. InsLinkList(&L,pos,e) 初始条件：单链表L已存在

操作结果：将元素e插入到单链表L的pos位置 DelLinkList(&L,pos,&e) 初始条件：单链表L已存在

操作结果：将单链表L中pos位置的元素删除， 元素值置入e中返回 LocLinkList(L,e)

初始条件：单链表L依存在

操作结果：单链表L中查找是否元素e，

若存在，返回元素在表中的位置；若不存在，返回-1. Menu()

操作结果：在屏幕上显示操作菜单 2）本程序包含7个函数： ① 主函数main()

② 初始化单链表函数InitLinkList()

③ 显示操作菜单函数menu()

④ 显示单链表内容函数dispLinkList() ⑤ 插入元素函数InsLinkList() ⑥ 删除元素函数DelLinkList() ⑦ 查找元素函数LocLinkList() 各函数间关系如下：

4．详细设计

实现概要设计中定义的所有的数据类型，对每个操作给出伪码算法。对主程序和其他模块也都需要写出伪码算法。 1) 结点类型和指针类型 typedef struct node { int data;

struct node *next; }Node,*LinkListl; 2) 单链表的基本操作

为了方便，在单链表中设头结点，其data域没有意义。 bool InitLinkList(LinkList &L) （伪码算法）

void DispLinkList(LinkList L) （伪码算法） void menu() （伪码算法）

bool InsLinkList(LinkList &L,int pos,int e) （伪码算法）

bool DelLinkList(LinkList &L,int pos,int &e) （伪码算法）

int LocLinkList(LinkList L,int e) （伪码算法）

3) 其他模块伪码算法 5．调试分析 (略)

6．使用说明

程序名为LinkList.exe，运行环境为DOS。程序执行后显示 ======================== 0----EXIT 1----INSERT 2----DELETE 3----LOCATE

======================= SELECT:

在select后输入数字选择执行不同的功能。要求首先输入足够多的插入元素，才可以进行其他的操作。每执行一次功能，就会显示执行的结果（正确或错误）以及执行后单链表的内容。

选择0：退出程序

选择1：显示“INSERT pos,e =” ，

要求输入要插入的位置和元素的值（都是整数）。 选择2：显示“DELETE pos =” ，

要求输入要删除元素的位置，执行成功后返回元素的值。 选择3：显示“LOCATE e = ” ，

要求输入要查找元素的值，执行成功后返回元素在表中的位置 7．测试结果

1） 建立单链表：

? 选择1，分别输入（0，11），（0，12），（0，13），（0，14）（0，15）。得到单链表（15，14，13，12，11） 2） 插入：

? 选择1输入（1，100），得到单链表（15，100，14，13，12，11） ? 选择1输入（-1，2），显示输入错误 ? 选择1输入（7，2），显示输入错误 ? 选择1输入（6，2），得到单链表（15，100，14，13，12，11，2） 3） 删除：

? 选择2，输入1。返回e=100，得到单链表（15，14，13，12，11，2） ? 选择2，输入0。返回e=15，得到单链表（14，13，12，11，2） ? 选择2，输入4。返回e=2，得到单链表（14，13，12，11） ? 选择2，输入5。返回输入错误 4） 查找

? 选择3，输入14。返回pos=0 ? 选择3，输入100。返回输入错误

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