15级 数据结构课程设计

数据结构课程设计教学大纲

名 称： 数据结构 英文名称： Data Structure 实习周数： 2周

其中实验学时： 32学时 学 分： 2学分

安排学期： 第二学年第1学期 适用专业： 计算机科学与技术

课程编码：

一、课程设计目的及任务

1、培养学生运用所学《数据结构》课程的理论知识和技能，分析解决数据结构应用实际问题的能力。

2、培养学生综合运用《数据结构》的知识，分析设计计算机课题的思想和方法。 3、通过课程设计，要求学生在指导教师的指导下，以课题小组协作方式完成设计课题的全部内容，包括：

(1) 通过调查研究和上机实习，收集和调查有关技术资料。 (2) 掌握设计课题的基本步骤和方法。 (3) 根据课题的要求进行上机实验调试。

二、课程设计的基本要求

在指导教师的指导下，根据自己实际的知识掌握情况和动手能力确定相符的题目，课题小组（1-3人）对于每个题目，理解题目的相关理论知识，掌握正确的操作和调试方法，并写出详细的课程设计报告。

测试数据：要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；

三、课程设计地点及要求

地点：计算机实验室 3教9楼

四、课程设计的选题原则

根据学生所学的数据结构相关知识点，布置适当难度的题目，学生可在老师布置的题目中选择自己感兴趣的题目，独立或合作完成。布置的题目尽量涉及数据结构知识的各个方面，尽量结合实际项目。

五、课程设计的内容

1、建通讯录 设计内容：

设计散列表实现通讯录查找系统，使得平均查找长度不超过2，完成相应的建表和查表程序。

设计要求：

(1) 设每个记录有下列数据项：用户名、电话号码、地址；

(2) 从键盘输入各记录，分别以姓名为关键字建立散列表；

(3) 假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均

查找长度的上限为2；

(4) 构造哈希函数，可采用除留余数法，采用二次探测再散列法解决冲突； (5) 查找并显示给定电话号码的记录； (6) 通讯录信息保存。 2、哈夫曼编码与译码

设计内容：

(1) 输入一个文本，统计各字符出现的频度，输出结果。 (2) 使用字符出现的频度构造哈夫曼树。 (3 ) 确定和输出各字符的哈夫曼码。

(4) 输入一个由0和1组成的代码序列，翻译并输出与之对应的文体，若最后的代码子序列不能译为文本，则输出相关信息。 3、乡卫生所选址

设计内容：

某乡有A，B，C，D，E 5个村庄，如下图所示，图中边上的权值表示两村之间的距离。现要在5个村庄中选某个村庄建立卫生所。其选址应使得距离卫生所最远的村庄到卫生所最近。

3 A 8 10 E C B 6

D 6 4 设计要求：

(1) 给出各村庄之间最短距离的矩阵A。

(2) 卫生所应设在哪个村庄？输出各村庄到卫生所的路径和路径长度。 4、生成字符串

设计内容：

假定字符串只由“0”，“1”，“*”组成，其中字符“*”表示该字符可由字符“0”或“1”替代。输入一些字符串，根据这些字符串生成所有可生成的字符串。 例如：{10,0*}可生成 {10，01，00}

{101，001，*01}可生成 {101，001} 5、 文章编辑

设计内容：

输入一页文字，程序可以统计出文字、数字、空格的个数。 （1）静态存储一页文章，每行最多不超过80个字符，共N行； （2）分别统计出其中英文字母数和空格数及整篇文章总字数； （3）统计某一字符串在文章中出现的次数，并输出该次数； （4）删除某一子串，并将后面的字符前移。

设计要求：

存储结构使用顺序表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。 输出形式：

（1）分行输出用户输入的各行字符； （2）分4行输出“全部字母数”、“数字个数”、“空格个数”、“文章总字数” （3）输出删除某一字符串后的文章； 6、新产品研制工序序列 设计内容：

一个农业生产工具制造厂，完成一件农用新产品研制工程的各个工序以及相互之间的关系如图所示。只有各子工序顺利完成，完整的新产品才能研制完成。由于资源等条件的限制，需要一项一项地安排实施各个工序，请给出使新产品顺利完成的各个工序安排的可行方案。 设计要求：

(1) 选用一种存储结构，实现网络图的存储。

(2) 定义另一种存储结构，不在通过用户输入，而是直接将（1）中的存储结构中的数

据导过来，编写算法实现此功能。

(3) 求出并输出保证工程顺利完成的各个工序按时间先后排列的一个线性序列。

工序表

工序代号 A B C D E F G H 工序名称 产品设计 工艺设计 主件制造 下料，锻件加工 外购配套件 模具制造 组装 调试试用 紧前工序 -- -- A B A A C D E F G 7、插入/交换排序算法效率的比较

设计内容：

随机产生若干组数据元素序列，分别使用不同的插入/交换排序算法排序，统计它们各自基本操作的次数，以此作为标准，评价交换排序算法的效率。 其中：基本操作包括记录的移动和关键字的比较 设计要求：

待排序数据元素序列的长度分别取不同的值，每个规模的数据元素序列取值组数由用户确定。

选做内容：

（1）系统功能的完善

（2）设计不同的散列函数，比较冲突率

（3）在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化

8、校园导游咨询 设计内容：

设计一个校园导游程序，为来访的客人提供各种信息查询服务。 设计要求：

(1) 设计你所在的学校的校园平面图，所含景点不少于10个。以图中顶点表示校内各

景点，存放景点的名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。

(2) 为来访客人提供图中任意景点相关信息的查询。 (3) 为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的最短的简单

路径。

选作内容：

(1) 求校园图的关键点

(2) 提供图中任意景点问路查询，即求任意两个景点之间的所有路径。

(3) 提供校园图中多个景点的最佳路线查询，即求途经这多个景点的最佳（短）路径。 (4) 校园导游图的景点和道路的修改扩充功能。 (5) 扩充道路信息，如道路类别（车道、人行道等），沿途景色等级，以至可按客人所

需分别查询人行路径或车街上路径或观景路径等。 (6) 扩充每个景点的邻接景点的方向等信息，使得路径查询结果能提供详尽的导向信息。 9、以队列实现的仿真技术预测理发馆的经营状况 设计内容：

理发馆一天的工作过程如下：

(1) 理发馆有N把理发椅，可同时为N位顾客进行理发。 (2) 理发师分三个等级（一级、二级、三级），对应不同的服务收费。

(3) 当顾客进门时，需选择某级别理发师，只要该级别的理发师有空椅，则可立即

坐下理发，否则需排队等候。

(4) 一旦该级别的理发师有顾客理发完离去，排在队头的顾客便可开始理发。 (5) 若理发馆每天连续营业T分钟，求

a) 一天内顾客在理发馆内的平均逗留时间； b) 顾客排队等候理发的队列长度平均值；

c) 营业时间到点后仍需完成服务的收尾工作时间； d) 统计每天的营业额；

e) 统计每天不同级别理发师的创收。

设计要求：

(1) 模拟理发馆一天的工作过程：必须采用事件驱动的离散模型（参考教科书3.5

节离散事件模拟p65）；

(2) 每个顾客到达和下一顾客到达时间的间隔应是随机的； (3) 理发师编号、理发师级别和每天的营业时间由用户输入；

(4) 某顾客挑选某一个级别的理发师而不得时，选第一个队列排队等待 ； (5) 每个顾客进门时将生成三个随机数:

a) durtime:进门顾客理发所需服务时间（简称：理发时间）； b) intertime:下一顾客将到达的时间间隔（简称：间隔时间）； c) select:服务选项 ；