2023年计算机本科数据结构集中实训指导书.doc

《数据结构》集中实训指导书
2023-12
课程设计周数：2周 指导老师：康平

一、课程设计的目的
数据结构课程重要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。
学习数据结构是为了将实际问题中所涉及的对象在计算机中表达出来并对它们进行解决。通过课程实训可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。通过本次课程实训重要达成以下目的：
n 了解并掌握数据结构与算法的设计方法，具有初步的独立分析和设计能力；
n 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；
n 提高综合运用所学的理论知识和方法独立分析和解决问题的能力；
n 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具有的科学的工作方法和作风。
二、课程设计的基本规定
1、独立思考，独立完毕：课程实训中各任务的设计和调试规定独立完毕，碰到问题可以讨论，但不可以拷贝。
2、做好上机准备：每次上机前，要事先编制好准备调试的程序，认真想好调试环节和有关环境的设立方法，准备好有关的文献。
3、按照课程设计的具体规定写课程实训报告，规定题目按照如下几个内容认真完毕；
其中涉及：
　　a）需求分析：
　　在该部分中叙述，每个模块的功能规定
　　b）概要设计
　　在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（假如指定存储结构请写出该存储结构的定义。
　　c）具体设计
　　各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组源程序，每个功能模块采用不同的函数实现）
　　源程序要按照写程序的规则来编写。要结构清楚，重点函数的重点变量，重点功能部分要加上清楚的程序注释。
　　d）调试分析
测试数据，测试输出的结果，和每个模块设计和调试时存在问题的思考（问题是哪些？问题如何解决？），算法的改善设想。
课程实训总结：（保存在word文档中）总结可以涉及：课程实训过程的收获、碰到问题解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程实训过程中对《数据结构》课程的结识等内容；
4、每组实现的结果必须进行检查和演示；程序源代码和程序的说明文献必须上交，作为考核内容的一部分；（上交时每人交一份，文献夹的取名规则为：“学号 姓名”，如“ 高魁”。该文献夹下至少涉及：“源代码”、“课程实训报告”、“可执行文献”。由学习委员收集刻盘按规定期间统一上交）。
5、课程实训报告不要附原代码，可以对重点函数及结构进行说明。报告格式参照附件。
6、报告提交
时间：第19周星期五检查，迟交无成绩。
形式：课程设计报告(规定打印）和电子文档(统一刻盘）。
三、课程设计内容：
1、内部排序演示
【问题描述】
设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受。【基本规定】
(1) 对起泡排序、直接排序、简朴选择排序、快速排序、希尔排序、堆排序算法进行比较；(2) 待排序的元素的关键字为整数。其中的数据要用10个，使用各种算法对其进行排序。
(3) 演示程序以人机对话的形式进行。
(4) 界面和谐，易与操作。采用菜单方式进行选择。

2、校园导游征询
【问题描述】
设计一个校园导游程序，为来访的客人提供各种信息查询服务。
【基本规定】
(1) 设计南昌工程学院的校园平面图，所含景点不少于10个。以图中顶点表达校内各景点，存放景点名称、代号、简介等信息；以边表达途径，存放途径长度等相关信息。
(2) 为来访客人提供图中任意景点相关信息的查询。
(3) 为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简朴途径。

3、建通讯录
【问题描述】
设实现通讯录查找系统。
【基本规定】
(1) 设每个记录有下列数据项：电话号码、用户名、地址；
(2) 从键盘输入各记录，分别以电话号码为关键字建立表；
(3) 显示、插入、删除、查找并显示给定电话号码的记录；
(4) 规定人机界面和谐，使用图形化界面；
【实现提醒】
主函数：根据选单的选项调用各函数，并完毕相应的功能。
Menu()的功能：显示英文提醒选单。
Quit()的功能：退出选单。
Create()的功能：创建新的通讯录。
Append()的功能：在通讯录的末尾写入新的信息，并返回选单。
Find()：查询某人的信息，假如找到了，则显示该人的信息，假如没有则提醒通讯录中没有此人的信息，并返回选单。
Alter()的功能：修改某人的信息，假如未找到要修改的人，则提醒通讯录中没有此人的信息，并返回选单。
Delete()的功能：删除某人的信息，假如未找到要删除的人，则提醒通讯录中没有此人的信息，并返回选单。
List()的功能：显示通讯录中的所有记录。

4、哈夫曼树的建立
【问题描述】
从键盘输入字符集大小n，n个字符和n个权植，建立哈夫曼树。
【基本规定】
(1) 输入后，生成哈夫曼树；
(2)运用哈夫曼树进行编码。打印相应字符的哈夫曼编码

5、一元多项式计算
【问题描述】
一元多项式计算
【基本规定】
(1) 可以按照指数降序排列建立并输出多项式；
（2）可以完毕两个多项式的相加、相减，并将结果输入；

6、猴子选大王
【问题描述】
一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。
【基本规定】
(1) 输入数据：输入m,n， m,n 为整数，n<m
（2）中文提醒按照m个猴子，数n 个数的方法，输出为大王的猴子是几号 ，建立一个函数来实现此功能

7、图的遍历
【问题描述】
创建图，并运用图的深度优先, 广度优先遍历算法对图进行遍历
【基本规定】
(1) 实现图的深度优先, 广度优先遍历算法，并输出原图结构及遍历结果
8、教学计划编制问题
【问题描述】
针对计算机系本科课程，根据课程之间的依赖关系（如离散数学应在数据结构之前开设）制定课程安排计划，并满足各学期（4学期）课程数目大体相同。
【基本规定】
（1）建立各课程之间的关系图（可运用教材中的例子）
（2）按先后顺序打印输出各学期所学的课程名

9、小型图书馆管理系统
【问题描述】
创建一个图书馆管理系统，可进行还书（插入），排序，查找，借书（删除）操作
【基本规定】
（1）所有信息存储在一个带头结点的单向链表中，每个结点存储一条图书记录，即结构体(book)，其中各域为：书号(number)、书名(title)、作者(writer)、定价(pricing)、出版社(publishinghouse)，指针域(next)。
（2）系统初始时图书记录为空，由用户录入信息，进行插入（涉及创建），排序，查找，删除操作。
（3）有两种排序算法可选：选择排序和直接插入排序，均由链表实现。
（4）如输入有错，给出犯错提醒。

10、考试报名管理系统
【问题描述】
对考试报名管理的简朴模拟，用菜单选择方式完毕下列功能。
【基本规定】
（1）所有信息存储在线性表中（可以是顺序表或链表），每个结点存储一名考生信息，即结构体(book)，其中各域为：准考证号、姓名、性别、年龄、报考类别，指针域(next)。
（2）系统初始时记录为空，由用户录入信息，进行插入（涉及创建），修改、查找，删除操作，完毕输出学生数据；学生数据查询；添加学生数据；修改学生数据；删除学生数据。
（3）如输入有错，给出犯错提醒。

11、电网建设造价模拟系统
【问题描述】
假设一个城市有n个社区，要实现n个社区之间的电网都可以互相接通，构造这个城市n个社区之间的电网，使总工程造价最低。
【基本规定】
（1）用连通图来表达n个城市之间以及n个城市之间也许设立的电网线路。
（2）用菜单选择方式完毕下列功能：创建电网顶点；添加电网的边；构造最小生成树；显示最小生成树；退出程序。
四、上交作业及成绩评估
1、上交规定
上交实训报告和相关光盘。其中设计报告要以打印文稿的形式上交。光盘内容涉及程序源码设计报告的电子文档。整个班级的设计均刻在一张光盘上，可按姓名或分组建立相关文献夹进行存储。
2、评分标准
根据完毕任务的情况(必须进行系统演示)、课程实训报告书的质量和课程实训过程中的工作态度等按照30%、50%、20%加权综合打分。上机程序检查未通过者、无实训报告者以及严重抄袭别人设计者，成绩为不及格。

注：
班级分为16个小组，每组4人。
每组选做任意两题。
附 实训报告封面

数据结构
课程实训报告

设计题目：
（1）
（2）
专 业
班 级
学 生
学 号
指导教师
起止时间

南昌工程学院

2023 年 12 月