《数据结构》课程设计任务书[2023-06-14]

数据结构课程组
2023/5/12

目录
一、设计目的2
二、设计要求2
三、设计选题2

单位员工通讯录管理系统（线性表）3
停车场管理（栈和队列）3
哈夫曼编码/译码系统（树）4
校园导游咨询（图）4
药店的药品销售统计系统（排序）4
一元稀疏多项式的计算（线性表）5
敢死队问题（线性表）5
散列表的设计与实现（查找）6
商店存货管理系统（线性结构）6
迷宫求解（图）7
教学计划编制问题（图）7
二叉排序树的基本操作（查找）8
最小生成树问题（图）8
内部排序算法比较（排序）9
六、课程设计报告10
七、成绩考核10
八、资料上交10
附件：课程设计报告格式要求11

《数据结构》课程设计任务书
学期：22-23春季班级：双学位21级
一、设计目的
《数据结构》是一门实践性较强的软件基础课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。
二、设计要求
1、通过这次设计，要求在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。
2、学生必须仔细研读《数据结构》课程设计(实习)要求，以学生自学为主、指导教师指导为辅，认真、独立地完成课程设计的任务，有问题及时主动与指导教师沟通。
3、本次课程设计按照教学要求需要在两周时间内独立完成，学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时地向指导教师汇报。
4、编程语言任选。
三、设计选题
选题说明：本次课设共提供若干个题目，请同学们至少选择3个不同知识点的题目完成。根据实际选做题目的难度和数量以及实现程序的完善性可以适当加减分。

1.单位员工通讯录管理系统（线性表）

[题目描述]
为某个单位建立一个员工通讯录管理系统，可以方便查询每一个员工的手机号、及电子邮箱。其功能包括通讯录链表的建立、员工通讯信息的查询、修改、插入与删除、以及整个通讯录表的输出。
操作分为查询、修改、添加、删除、打印

查询：输入员工姓名，输出员工信息，若员工不存在，输出“NOT FOUND!”
修改：输入员工姓名、要修改的属性，修改信息。姓名为name、电话为tel、邮箱为mail。
添加：输入员工编号、姓名、电话号码、邮箱。
删除：输入员工姓名，将其从通讯录中删除。
打印：输出通讯录。
[实现提示]
可以采用单链表的存储结构，如可定义如下的存储结构：

typedef struct {  /*员工通讯信息的结构类型定义*/
    char num[5];       /*员工编号*/
    char name[10];      /*员工姓名*/ 
    char tel[15];     /*办公室电话号码*/
char call[15];     /*手机号码*/
char mail[25];      /*邮箱*/
}DataType;
/*通讯录单链表的结点类型*/
typedef struct node
{ DataType data;   /*结点的数据域*/
  struct node *next;   /*结点的指针域*/
}ListNode,*LinkList;

源码

https://pan.baidu.com/s/1J--MYtUyPilpJKTD15-SgA?pwd=1111

2.停车场管理（栈和队列）

[题目描述]
设停车场是一个可以停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆车，那么后来的车只能在门外的便道上等候，一旦停车场内有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场。试为停车场编制按上述要求进行管理的模拟程序。
以栈模拟停车场，以队列模拟车场外的便道。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；当车辆将要离去时，若车在停车场内，模拟输出汽车出入情况并输出汽车在停车场内停留的时间，若车在便道上，直接输出汽车在停车场内停留的时间：0。栈以顺序存储结构实现，队列以链表结构实现。

源码

https://pan.baidu.com/s/1J--MYtUyPilpJKTD15-SgA?pwd=1111

3.哈夫曼编码/译码系统（树）

[题目描述]
利用哈夫曼编码进行通信，可以压缩通信的数据量，提高传输效率，缩短信息的传输时间，还有一定的保密性。现在要求编写一程序模拟传输过程，实现在发送前将要发送的字符信息进行编码，然后进行发送，接收后将传来的数据进行译码，即将信息还原成发送前的字符信息。
现在有两个功能：
1 发送者：将待传送的字符信息转化为哈夫曼编码。
2 接受者：将接受的编码信息进行译码，得到还原成发送前的字符信息。

源码

https://pan.baidu.com/s/1J--MYtUyPilpJKTD15-SgA?pwd=1111

4.校园导游咨询（图）

[题目描述]
设计一个校园导游程序，为来访的客人提供各种信息查询服务。
（1）设计学校的校园平面图（保证各个景点之间连通），以图中顶点表示校内各景点，存放景点名称、代号、简介、编号；以边表示路径，存放路径长度等相关信息；
（2）提供基本信息的修改功能；
（3）为来访客人提供图中任意景点相关信息的查询；
（4）为来访客人提供景点的问路查询，查询两景点间的最短路径及长度。

源码

https://pan.baidu.com/s/1J--MYtUyPilpJKTD15-SgA?pwd=1111

5.药店的药品销售统计系统（排序）

[问题描述]
设计一系统，实现医药公司定期对销售各药品的记录进行统计，可按药品的编号、单价、销售量或销售额做出排名。
[实现提示]
在本设计中，首先从数据文件中读出各药品的信息记录，存储在顺序表中。各药品的信息包括：药品编号、药名、药品单价、销出数量、销售额。药品编号共4位，采用字母和数字混合编号，如：A125，前一位为大写字母，后三位为数字，按药品编号进行排序时，可采用基数排序法。对各药品的单价、销售量或销售额进行排序时，可采用多种排序方法，如直接插入排序、冒泡排序、快速排序，直接选择排序等方法。在本设计中，对单价的排序采用冒泡排序法，对销售量的排序采用快速排序法，对销售额的排序采用堆排序法。
药品信息的元素类型定义：
typedef struct node
{ char num[4]; /药品编号/
char name[10]; /药品名称/
float price; /药品单价/
int count; /销售数量/
float sale; /本药品销售额/
}DataType;
存储药品信息的顺序表的定义：
typedef struct
{ DataType r[MaxSize];
int length;
}SequenList;

源码

https://pan.baidu.com/s/1J--MYtUyPilpJKTD15-SgA?pwd=1111

6.一元稀疏多项式的计算（线性表）

[问题描述]
能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减，并将结果输出；
[基本要求]
以链式存储结构实现多项式。
7.敢死队问题（线性表）
[问题描述]
有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完成为止。
排长是不愿意去的，假设排长为1号，请你设计一程序，求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。
[基本要求]
至少采用两种不同的数据结构的方法实现。

源码

https://pan.baidu.com/s/1J--MYtUyPilpJKTD15-SgA?pwd=1111

8.散列表的设计与实现（查找）

[问题描述]
设计散列表实现电话号码查找系统。

[基本要求]
(1)设每个记录有下列数据项：用户名、电话号码、地址；
(2)从键盘输入各记录，以用户名（汉语拼音形式）为关键字建立散列表；
(3)采用线性探测再散列法解决冲突；
(4)查找并显示给定电话号码的记录；
(5)通讯录信息文件保存；
(6)要求人机界面友好，使用图形化界面；
[选作内容]
(7)系统功能的完善；
(8)设计不同的散列函数，比较冲突率；
(9)在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。

源码

https://pan.baidu.com/s/1J--MYtUyPilpJKTD15-SgA?pwd=1111

9.商店存货管理系统（线性结构）

[问题描述]
建立一商店存货管理系统，要求每次出货时取进货时间最早且最接近保质期中止时间的货物。
[分步实施]
1.初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；
2.完成最低要求：建立一个文件，包括5个种类的货物情况，能对商品信息进行扩充（追加），修改和删除以及简单的排序；
3.进一步要求：扩充商品数量，以及完成系统查询功能。有兴趣的同学可以自己扩充系统功能。

源码

https://pan.baidu.com/s/1J--MYtUyPilpJKTD15-SgA?pwd=1111

10.迷宫求解（图）

[问题描述]
以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
[基本要求]
1.深度优先搜索：首先实现一个栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i,j,d)的形式输出，其中(i,j)指示迷宫中的一个坐标，d表示走到下一坐标的方向。
2.广度优先搜索：用队列实现。求得的通路以三元组(i,j,d)的形式输出，其中(i,j)指示迷宫中的一个坐标，d表示走到下一坐标的方向。

源码

https://pan.baidu.com/s/1J--MYtUyPilpJKTD15-SgA?pwd=1111

11.教学计划编制问题（图）

[问题描述]
大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等，每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。
[基本要求]
（1）输入参数包括：学期总数，一学期的学分上限，每门课的课程号(固定占3位的字母数字串)、学分和直接先修课的课程号。
（2）允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。
（3）若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。计划的表格格式自行设计。
[测试数据]
学期总数：6；学分上限：10；该专业共开设12门课，课程号从C01到C12，学分顺序为2,3,4,3,2,3,4,4,7,5,2,3。先修关系如下：
课程编号课程名称先决条件
C1程序设计基础无
C2离散数学C1
C3数据结构C1，C2
C4汇编语言C1
C5语言的设计和分析C3，C4
C6计算机原理C11
C7编译原理C5，C3
C8操作系统C3，C6
C9高等数学无
C10线性代数C9
C11普通物理C9
C12数值分析C9，C10，C1
[实现提示]
可设学期总数不超过12，课程总数不超过100。如果输入的先修课程号不在该专业开设的课程序列中，则作为错误处理。应建立内部课程序号与课程号之间的对应关系。

源码

https://pan.baidu.com/s/1J--MYtUyPilpJKTD15-SgA?pwd=1111

12.二叉排序树的基本操作（查找）

[问题描述]
编写算法实现对依次输入的关键字序列建立二叉排序树，并能实现二叉排序树的查找、插入和删除运算。

源码

https://pan.baidu.com/s/1J--MYtUyPilpJKTD15-SgA?pwd=1111

13.最小生成树问题（图）

[问题描述]
若要在n个城市之间建设通信网络，只需要假设n-1条线路即可。如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。
[基本要求]
(1)利用克鲁斯卡尔算法求网的最小生成树。
(2)利用普里姆算法求网的最小生成树。
(3)要求输出各条边及它们的权值。
[测试数据]
由学生任意指定，但报告上要求写出多批数据测试结果。
[实现提示]
通信线路一旦建成，必然是双向的。因此，构造最小生成树的网一定是无向网。设图的顶点数不超过30个，并为简单起见，网中边的权值设成小于100的整数，可利用C语言提供的随机函数产生。
图的存储结构的选取应和所作操作相适应。为了便于选择权值最小的边，此题的存储结构既不选用邻接矩阵的数组表示法，也不选用邻接表，而是以存储边（带权）的数组表示图。
[进阶]
利用堆排序实现选择权值最小的边。

源码

https://pan.baidu.com/s/1J--MYtUyPilpJKTD15-SgA?pwd=1111

14.内部排序算法比较（排序）

[问题描述]
各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大
概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。
[基本要求]
（1）对以下10种常用的内部排序算法进行比较：直接插入排序；折半折入排序；二路插入排序；希尔排序；起泡排序；快速排序；简单选择排序；堆排序；归并排序；基数排序。
（2）待排序表的表长不少于10000；其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字移动次数（关键字交换计为3次移动）。
[测试数据]
由随机产生器决定。
[实现提示]
主要工作是设法在程序中适当的地方插入计数操作。程序还可以包括计算几
组数据得出结果波动大小的解释。注意分块调试的方法。
[选作内容]
对不同的输入表长做试验，观察检查两个指标相关于表长的变化关系。还可
以对稳定性做验证。

源码

https://pan.baidu.com/s/1J--MYtUyPilpJKTD15-SgA?pwd=1111

六、课程设计报告
课程设计报告的内容：设计题目、需求分析、算法设计（包含算法思想、算法设计分析、流程图等）、调试分析、测试结果、课设总结（收获及体会）、附录（源代码）。
其它情况根据界面设计、实现方法、功能效果、设计报告来评定。主要从以下几个方面考察：
项目得分备注
程序运行情况25分
程序的结构合理与否15分
算法说明的清晰程度20分
总结的深刻程度10分
独立完成情况20分
加分因素10分
八、资料上交
上交课程设计报告和相关题目源文件（均为电子版）。一个学生一个文件夹，文件夹的命名规则为：“学号_姓名”，如“学号_张三”。该文件夹下至少包括：“源代码”、“课程设计报告”，源代码按题目分列清楚，按老师规定的时间按时提交至指定地方。

附件：课程设计报告格式要求

目录
题目1：单位员工通讯录管理系统…………………………………………1
1.问题描述
2.需求分析
3.算法设计
3.1 算法思想
3.2 数据结构
3.3 算法设计
3.4 函数之间的调用关系
4.调试分析
4.1调试中出现的问题及解决方案
4.2优点及不足
4.3 算法的性能分析
4.4 改进思路
5.实验结果
题目2：……………………………………7
……
题目n：……………………………………25
课设总结…………………………………………………………………26
附录………………………………………………………………………27