《数据结构课程设计》实施方案（201612）（部分）--课题要求3 教学内容及基本要求3-1总体设计要求1、采用C/C++编程语言，推荐使用C++的类来完成综合训练题目，使用C++的模板类（STL），来完成研究性学习与创新性设计题目。

2、软件采用模块化结构，划分功能模块，确定模块间的联系，实现模块的算法。

3、软件测试与调试，给出必要的测试用例数据。

4、软件要完成界面设计，推荐设计可视化界面。

5、完成设计要求中规定的基本功能。

6、在完成基本设计要求的基础上，可以增加和完善功能。

7、对所完成的课题的算法进行时间和空间的性能评价。

8、针对创新性应用课题，在数据结构或算法设计中有所创新。

9、学生在软件开发中要体现团队协作精神和程序设计的调试能力。

3-2 综合训练性题目（A类）综合训练性题目的设计考虑到与课堂讲授的内容相衔接，以问题为中心，体现数据结构的综合应用。

本次课程设计共安排15个综合训练性A类可选题目。

1、立体化停车场管理【问题描述】设停车场有地上和地下两层，统一管理。

地下停车场采用单入口和单出口。

地上停车场采用南北方向的双口，每个口都有一个入口和出口。

停车顺序先地上，后地下。

地上入口处各有一个单车道的等候通道，并允许等候的车辆因急事从等候通道直接开走。

【设计要求】设计停车场模拟管理程序。

（1）采用栈、队列和有序表等数据结构。

（2）可以随机、文件及人工输入数据。

（3）等候车辆的管理。

（4）地下、地上停车位的管理。

（5）停车计费功能。

（6）其它完善性或扩展性功能。

2、运动会竞赛成绩统计【问题描述】东北大学第54届运动大会成功举行。

共有N个学院的学生男女代表队和教工代表队参赛。

大会共设M个学生男子项目和W个学生女子项目、R个教工团体项目。

大会即将闭幕，准备公布成绩。

【设计要求】设计运动会竞赛成绩统计程序。

（1）采用顺序表、集合等数据结构。

（2）可以随机、文件及人工输入数据。

（3）统计各代表队的男女总分和团体总分。

（4）采用堆排序，公布各单项成绩的前六名和团体成绩的前三名。

（5）可以查询和更新数据。

（6）其它完善性或扩展性功能。

3、银行业务模拟【问题描述】银行有N个窗口对外接待客户。

从早晨银行营业开始到晚间营业终止不断有客户办理业务。

银行门口设有取号机，分为一般业务和特殊业务，设每个一般业务不超过5分钟，每个特殊业务不超过15分钟。

客户在等候区内等候叫号。

【设计要求】设计银行客户业务的模拟程序。

（1）采用有序链表、队列等数据结构。

（2）可以随机、文件及人工输入数据。

（3）分类统计一天内客户在银行逗留的平均时间和人数。

（4）若特殊业务窗口空闲，可办理一般业务。

（5）可以查询和更新数据。

（6）其它完善性或扩展性功能。

4、电梯运行模拟【问题描述】东北大学综合办公楼有14层，设有4部自动电梯。

每梯最多载客12人。

从上班到下班不断有乘客使用电梯。

电梯运行每上下一层需5秒，空闲时，在某一层最多停留10秒，否则返回1层待命。

乘客等待电梯时间不超过T时间。

【设计要求】设计电梯工作运行的模拟程序。

（1）采用有序链表、队列、数组等数据结构。

（2）可以随机、文件及人工输入数据。

（3）实时显示电梯的工作运行状况。

（4）统计一天内每楼层电梯的使用人次数。

（5）可以查询和更新数据。

（6）其它完善性或扩展性功能。

5、哈夫曼压缩软件设计【问题描述】采用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。

利用哈夫曼编码对文本或图像进行数据压缩，设计数据压缩软件。

【设计要求】设计基于哈夫曼编码的文本和图像压缩软件。

（1）采用静态链表的二叉树等数据结构。

（2）可以随机、文件及人工输入数据。

（3）创建哈夫曼树，生成哈夫曼编码和译码。

（4）源码、编码和压缩后的信息均以文件形式保存。

（5）可以查询和更新数据。

（6）其它完善性或扩展性功能。

6、教务课程计划安排【问题描述】拓扑集合的划分可以解决教务课程安排问题。

高校每学年含两学期，每学期的教学周数和学分均有上限。

在教学计划一定的情况下，开设的课程必须满足次序关系。

拓扑集合的划分与拓扑排序的算法类似。

【设计要求】设计基于拓扑集合划分的教务课程编排模拟程序。

（1）采用图邻接表、栈等数据结构。

（2）可以随机、文件及人工输入数据。

（3）计算课程安排的最优划分，尽量使学期最短。

（4）可以统计数据并满足必要的约束条件。

（5）可以查询和更新数据。

（6）其它完善性或扩展性功能。

7、城市旅游购物交通咨询模拟【问题描述】沈阳城内有若干旅游观光景点和商业区。

游客主要以公交车为交通工具出游。

假设往返于每个景点和商业区的公交线路不少于6路。

旅客希望中转次数最少、时间最短、费用最省。

【设计要求】设计城市交通咨询模拟程序。

（1）采用图结构、集合等数据结构。

（2）可以随机、文件及人工输入数据。

（3）可以完成旅游、购物一日游的最佳线路。

（4）可以统计数据并满足必要的约束条件。

（5）可以查询和更新数据。

（6）其它完善性或扩展性功能。

8、校园光纤网络铺设【问题描述】东北大学铺设校园光纤网络。

假设有N个学院和办公楼，只需要铺设N-1条光缆通道。

采用最小生成树的算法，给出一个最佳铺设方案。

【设计要求】设计基于最小生成树的校园光缆铺设程序。

（1）采用图结构、并集树等数据结构。

（2）可以随机、文件及人工输入数据。

（3）采用克鲁斯卡尔算法设计最小代价生成树（4）可以采用堆排序算法选择权值最小的边。

（5）采用并集树完成树边的查询和合并。

（6）其它完善性或扩展性功能。

9、汽车牌照的快速查询【问题描述】在汽车数据的信息模型中，汽车牌照是具有结构特点的一类关键字。

汽车牌照是字母和数字混编的，例如01B7238。

利用查找和排序算法，实现辽宁省内汽车牌照的快速查找。

【设计要求】设计汽车牌照的快速查询程序。

（1）采用顺序表、静态链表等数据结构。

（2）可以随机、文件及人工输入数据。

（3）利用静态链表对汽车牌照进行链式基数排序。

（4）采用折半查找汽车牌照。

（5）可以按城市进行分块索引查找。

（6）其它完善性或扩展性功能。

10、十进制四则运算计算器【问题描述】由输入的四则运算表达式字符串，动态生成算术表达式所对应的二叉树，通过表达式二叉树自动求值并输出。

【设计要求】设计十进制整数四则运算计算器。

（1）采用二叉树、栈等数据结构。

（2）可以随机、文件及人工输入数据。

（3）给定表达式字符串，生成二叉链表的表达式二叉树。

（4）对表达式二叉树采用后序遍历求值并输出。

（5）具有计算整数和复数四则运算的功能。

（6）其它完善性或扩展性功能。

11、互联网域名信息管理系统【问题描述】互联网域名系统是一个典型的树形层次结构。

从根节点往下的第一层是顶层域，如cn、com等，最底层（第四层）是叶子结点，如www等。

【设计要求】设计互联网域名信息管理的模拟程序。

（1）采用树的孩子兄弟链表等存储结构。

（2）可以随机、文件及人工输入数据。

（3）实现域名的创建、分类、插入、删除、修改等管理功能。

（4）实现域名的查询和统计功能。

（5）考虑采用优化的查询和排序算法。

（6）其它完善性或扩展性功能。

12、无向图的关节点问题【问题描述】对无向连通图，若删除某个结点使其成为非连通图，则称该结点为关节点。

假设某一地区公路交通网，求解关节点。

【设计要求】设计求解无向连通图关节点的模拟程序。

（1）采用邻接表或邻接矩阵存储结构。

（2）可以随机、文件及人工输入数据。

（3）采用深度优先遍历求解关节点。

（4）实现关节点的查询和统计功能。

（5）实现将关节点改造为非关节的功能。

（6）其它完善性或扩展性功能。

13、手机个人通讯录信息管理系统【问题描述】对手机个人通讯录的创建和查询等信息管理作一个简单的模拟。

【设计要求】设计手机个人通讯录管理的模拟程序。

（1）采用顺序表或结构体链表存储结构。

（2）可以随机、文件及人工输入数据。

（3）实现通讯录的创建、修改、插入、删除、分组等管理功能。

（4）实现通讯录的各种查询和统计功能。

（5）实现人机交互界面功能。

（6）其它完善性或扩展性功能。

14、超市商品库存信息管理系统【问题描述】对一个中小型超市的库存商品信息管理作一个简单的模拟。

【设计要求】设计超市库存商品信息维护管理的模拟程序。

（1）采用顺序表或结构体链表存储结构。

（2）可以随机、文件及人工输入数据。

（3）实现超市商品的创建、分类、出库、入库、修改等管理功能。

（4）实现库存商品的各种查询和统计功能。

（5）实现人机交互界面功能。

（6）其它完善性或扩展性功能。

15、图书馆图书借阅信息管理系统【问题描述】对图书馆的图书借阅业务管理作一个简单的模拟。

【设计要求】设计图书借阅信息管理的模拟程序。

（1）采用顺序表或结构体链表存储结构。

（2）可以随机、文件及人工输入数据。

（3）实现图书的创建、分类、插入、删除、修改、借阅等管理功能。

（4）实现图书的各种借阅查询和统计功能。

（5）实现人机交互界面功能。

（6）其它完善性或扩展性功能。

3-3 研究性学习与创新性设计题目（B类）研究性学习与创新性设计题目的设计重点是在巩固基本数据结构知识的基础上，激发学生的自主性学习热情和创造性思维能力，扩充数据结构课程的知识量。

一方面可以将课堂上及书本上的内容做应用扩展；另一方面可以设计基于STL框架的数据结构应用程序。

本次课程设计共安排15个研究性学习与创新性设计B类可选题目。

1、二进制堆及其应用【问题描述】堆是设计很巧妙的数据结构，堆排序的算法也有很多应用。

但当堆比较庞大时，选取堆顶元素及重新建堆的工作量也较大。

利用堆的定义构建二进制堆，应用于优先队列有很大的优势。

二进制堆是在二进制树B k上建立的数据结构。

一个整数可以表示为二进制数，一组关键字组成的序列可以由一组二进制堆表示。

【设计要求】设计基于STL框架的二进制堆的抽象数据类型及其实现。

（1）实现二进制堆H k的ADT。

（2）应用基本运算，实现二进制堆的简单应用。

2、线段树及其应用【问题描述】在实际应用中，常遇到与区间有关的操作，比如统计若干矩形并集的面积，记录一个区间的最大最小值及总量，并在区间的插入、删除和修改中维护这些数据。

线段树的定义是利用树形二分结构所建立的一种数据结构，能够高效的完成这些操作。

【设计要求】设计基于STL框架的线段树的抽象数据类型及其实现。

（1）实现线段树的ADT。

（2）应用基本运算，实现线段树的简单应用。

3、邮局选址问题【问题描述】n个居民小区规则的坐落在城市中，用x表示东西向，用y表示南北向。

如何选择邮局的最佳位置，才能使n个居民小区到邮局的费用为最省。

【设计要求】采用最短路径算法求解。

（1）采用STL数据结构或设计基于STL框架的数据结构。

（2）应用基本运算，设计算法求解。

4、男女运动员最佳组合【问题描述】设有N个男羽毛球运动员和N个女羽毛球运动员，现组成N对男女混合最佳组合。