B131000920数据结构课程设计课题要求201612计15008物15002

1、-0-数据结构课程设计实施方案（201612）（部分）-课题要求3 教学内容及基本要求3-1 总体设计要求1、 采用 C/C+编程语言，推荐使用 C+勺类来完成综合训练题目，使用 C+啲模板类（STL）,来完成研究性学习与创新性设计题目。2、 软件采用模块化结构，划分功能模块，确定模块间勺联系，实现模块勺算法。3、 软件测试与调试，给出必要勺测试用例数据。4、 软件要完成界面设计，推荐设计可视化界面。5、 完成设计要求中规定勺基本功能。6、 在完成基本设计要求勺基础上，可以增加和完善功能。7、 对所完成勺课题勺算法进行时间和空间勺性能评价。8、 针对创新性应用课题，在数据结构或算法设计中有所创

2、新。9、 学生在软件开发中要体现团队协作精神和程序设计勺调试能力。3-2 综合训练性题目（ A 类）综合训练性题目勺设计考虑到与课堂讲授勺内容相衔接，以问题为中心，体现数据结构 的综合应用。本次课程设计共安排 15 个综合训练性 A 类可选题目。1、立体化停车场管理【问题描述】设停车场有地上和地下两层，统一管理。地下停车场采用单入口和单出口。地上停车场 采用南北方向的双口，每个口都有一个入口和出口。停车顺序先地上，后地下。地上入口处 各有一个单车道的等候通道，并允许等候的车辆因急事从等候通道直接开走。【设计要求】设计停车场模拟管理程序。（ 1 ）采用栈、队列和有序表等数据结构。（ 2）可以随机

3、、文件及人工输入数据。（ 3 ）等候车辆的管理。（ 4 ）地下、地上停车位的管理。（ 5）停车计费功能。（ 6）其它完善性或扩展性功能。2、运动会竞赛成绩统计【问题描述】东北大学第 54 届运动大会成功举行。共有 N 个学院的学生男女代表队和教工代表队参 赛。大会共设 M 个学生男子项目和 W 个学生女子项目、 R 个教工团体项目。大会即将闭幕， 准备公布成绩。【设计要求】 设计运动会竞赛成绩统计程序。（ 1 ）采用顺序表、集合等数据结构。（ 2）可以随机、文件及人工输入数据。（ 3）统计各代表队的男女总分和团体总分。（4）采用堆排序，公布各单项成绩的前六名和团体成绩的前三名。（5）可以查询和

4、更新数据。-1-（6）其它完善性或扩展性功能。3、银行业务模拟 【问题描述】 银行有 N 个窗口对外接待客户。从早晨银行营业开始到晚间营业终止不断有客户办理业 务。银行门口设有取号机，分为一般业务和特殊业务，设每个一般业务不超过5 分钟，每个特殊业务不超过 15 分钟。客户在等候区内等候叫号。【设计要求】 设计银行客户业务的模拟程序。（1）采用有序链表、队列等数据结构。（2）可以随机、文件及人工输入数据。（3）分类统计一天内客户在银行逗留的平均时间和人数。（4）若特殊业务窗口空闲，可办理一般业务。（5）可以查询和更新数据。（6）其它完善性或扩展性功能。4、电梯运行模拟 【问题描述】 东北大学综

5、合办公楼有 14 层，设有 4 部自动电梯。每梯最多载客12 人。从上班到下班 不断有乘客使用电梯。电梯运行每上下一层需 5 秒，空闲时，在某一层最多停留 10 秒，否则 返回 1 层待命。乘客等待电梯时间不超过 T 时间。【设计要求】 设计电梯工作运行的模拟程序。（1）采用有序链表、队列、数组等数据结构。（2）可以随机、文件及人工输入数据。（3）实时显示电梯的工作运行状况。（4）统计一天内每楼层电梯的使用人次数。（5）可以查询和更新数据。（6）其它完善性或扩展性功能。5、哈夫曼压缩软件设计 【问题描述】 采用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。利用哈夫曼编码对文本或 图像进行数

6、据压缩，设计数据压缩软件。【设计要求】 设计基于哈夫曼编码的文本和图像压缩软件。（1）采用静态链表的二叉树等数据结构。（2）可以随机、文件及人工输入数据。（3）创建哈夫曼树，生成哈夫曼编码和译码。（4）源码、编码和压缩后的信息均以文件形式保存。（5）可以查询和更新数据。（6）其它完善性或扩展性功能。6、教务课程计划安排 【问题描述】 拓扑集合的划分可以解决教务课程安排问题。高校每学年含两学期，每学期的教学周数 和学分均有上限。在教学计划一定的情况下，开设的课程必须满足次序关系。拓扑集合的划 分与拓扑排序的算法类似。【设计要求】设计基于拓扑集合划分的教务课程编排模拟程序。（1）采用图邻接表、栈等

7、数据结构。（2）可以随机、文件及人工输入数据。（3）计算课程安排的最优划分，尽量使学期最短。（4）可以统计数据并满足必要的约束条件。（5）可以查询和更新数据。（6）其它完善性或扩展性功能。7、城市旅游购物交通咨询模拟 【问题描述】 沈阳城内有若干旅游观光景点和商业区。游客主要以公交车为交通工具出游。假设往返 于每个景点和商业区的公交线路不少于 6 路。旅客希望中转次数最少、时间最短、费用最省。【设计要求】 设计城市交通咨询模拟程序。-2-（1）采用图结构、集合等数据结构。（2）可以随机、文件及人工输入数据。（3）可以完成旅游、购物一日游的最佳线路。（4）可以统计数据并满足必要的约束条件。（5）

8、可以查询和更新数据。（6）其它完善性或扩展性功能。8、校园光纤网络铺设 【问题描述】 东北大学铺设校园光纤网络。假设有 N 个学院和办公楼，只需要铺设 N-1 条光缆通道 采用最小生成树的算法，给出一个最佳铺设方案。【设计要求】 设计基于最小生成树的校园光缆铺设程序。（ 1 ）采用图结构、并集树等数据结构。（2）可以随机、文件及人工输入数据。（3） 采用克鲁斯卡尔算法设计最小代价生成树（4） 可以采用堆排序算法选择权值最小的边。（5） 采用并集树完成树边的查询和合并。（6） 其它完善性或扩展性功能。9、汽车牌照的快速查询 【问题描述】 在汽车数据的信息模型中，汽车牌照是具有结构特点的一类关键字

9、。汽车牌照是字母和数字混编的，例如 01B7238。利用查找和排序算法，实现辽宁省内汽车牌照的快速查找。 【设计要求】 设计汽车牌照的快速查询程序。（1） 采用顺序表、静态链表等数据结构。（2） 可以随机、文件及人工输入数据。（3） 利用静态链表对汽车牌照进行链式基数排序。（4） 采用折半查找汽车牌照。（5） 可以按城市进行分块索引查找。（6） 其它完善性或扩展性功能。10、十进制四则运算计算器 【问题描述】 由输入的四则运算表达式字符串，动态生成算术表达式所对应的二叉树，通过表达式二叉树自动求值并输出。【设计要求】 设计十进制整数四则运算计算器。（1）采用二叉树、栈等数据结构。（2）可以随机

10、、文件及人工输入数据。（3）给定表达式字符串，生成二叉链表的表达式二叉树。（4）对表达式二叉树采用后序遍历求值并输出。（5）具有计算整数和复数四则运算的功能。（6）其它完善性或扩展性功能。11、互联网域名信息管理系统 【问题描述】 互联网域名系统是一个典型的树形层次结构。从根节点往下的第一层是顶层域，如cn、com 等，最底层（第四层）是叶子结点，如 www 等。【设计要求】 设计互联网域名信息管理的模拟程序。（1）采用树的孩子兄弟链表等存储结构。（2）可以随机、文件及人工输入数据。（3）实现域名的创建、分类、插入、删除、修改等管理功能。（4）实现域名的查询和统计功能。（5）考虑采用优化的查询

11、和排序算法。（6）其它完善性或扩展性功能。12、无向图的关节点问题 【问题描述】 对无向连通图，若删除某个结点使其成为非连通图，则称-3-该结点为关节点。假设某一地 区公路交通网，求解关节点。【设计要求】 设计求解无向连通图关节点的模拟程序。（1）采用邻接表或邻接矩阵存储结构。（2）可以随机、文件及人工输入数据。（3）采用深度优先遍历求解关节点。（4）实现关节点的查询和统计功能。（5）实现将关节点改造为非关节的功能。（6）其它完善性或扩展性功能。13、手机个人通讯录信息管理系统 【问题描述】 对手机个人通讯录的创建和查询等信息管理作一个简单的模拟。【设计要求】 设计手机个人通讯录管理的模拟程序

12、。（1）采用顺序表或结构体链表存储结构。（2）可以随机、文件及人工输入数据。（3）实现通讯录的创建、修改、插入、删除、分组等管理功能。（4）实现通讯录的各种查询和统计功能。（5）实现人机交互界面功能。（6）其它完善性或扩展性功能。14、超市商品库存信息管理系统 【问题描述】对一个中小型超市的库存商品信息管理作一个简单的模拟。 【设计要求】 设计超市库存商品信息维护管理的模拟程序。（1）采用顺序表或结构体链表存储结构。（2）可以随机、文件及人工输入数据。（3）实现超市商品的创建、分类、出库、入库、修改等管理功能。（4）实现库存商品的各种查询和统计功能。（5）实现人机交互界面功能。（6）其它完善性

13、或扩展性功能。15、图书馆图书借阅信息管理系统【问题描述】 对图书馆的图书借阅业务管理作一个简单的模拟。【设计要求】设计图书借阅信息管理的模拟程序。（1）采用顺序表或结构体链表存储结构。（2）可以随机、文件及人工输入数据。（3）实现图书的创建、分类、插入、删除、修改、借阅等管理功能。（4）实现图书的各种借阅查询和统计功能。（5）实现人机交互界面功能。（6）其它完善性或扩展性功能。3-3 研究性学习与创新性设计题目（ B 类） 研究性学习与创新性设计题目的设计重点是在巩固基本数据结构知识的基础上，激发学 生的自主性学习热情和创造性思维能力，扩充数据结构课程的知识量。一方面可以将课堂上 及书本上的

14、内容做应用扩展；另一方面可以设计基于STL 框架的数据结构应用程序。本次课程设计共安排 15 个研究性学习与创新性设计 B 类可选题目。1、 二进制堆及其应用【问题描述】 堆是设计很巧妙的数据结构，堆排序的算法也有很多应用。但当堆比较庞大时，选取堆 顶元素及重新建堆的工作量也较大。利用堆的定义构建二进制堆，应用于优先队列有很大的-4-优势。二进制堆是在二进制树 Bk上建立的数据结构。一个整数可以表示为二进制数，一组关 键字组成的序列可以由一组二进制堆表示。【设计要求】 设计基于 STL 框架的二进制堆的抽象数据类型及其实现。（1）实现二进制堆 Hk的 ADT。（2）应用基本运算，实现二进制堆的

15、简单应用。2、 线段树及其应用【问题描述】 在实际应用中，常遇到与区间有关的操作，比如统计若干矩形并集的面积，记录一个区 间的最大最小值及总量，并在区间的插入、删除和修改中维护这些数据。线段树的定义是利用树形二分结构所建立的一种数据结构，能够高效的完成这些操作。【设计要求】 设计基于 STL 框架的线段树的抽象数据类型及其实现。（ 1 ）实现线段树的 ADT 。（2）应用基本运算，实现线段树的简单应用。3、邮局选址问题 【问题描述】 n 个居民小区规则的坐落在城市中，用 x 表示东西向，用 y 表示南北向。如何选择邮局 的最佳位置，才能使 n 个居民小区到邮局的费用为最省。【设计要求】 采用最

16、短路径算法求解。(1)采用 STL 数据结构或设计基于 STL 框架的数据结构。( 2)应用基本运算，设计算法求解。4、男女运动员最佳组合 【问题描述】 设有 N 个男羽毛球运动员和 N 个女羽毛球运动员，现组成N 对男女混合最佳组合。 每 个男运动员对每个女运动员都有一个满意度排序， 用矩阵 mf0:n-10:n-1表示。 mfij 表示 第 i 个男运动员对第 j 个女运动员的满意度，满意度值越高，满意程度越高。同理，每个女运 动员对每个男运动员也有一个满意度排序，用矩阵 fm0:n-10:n-1 表示。男女运动员之间的 一个完全匹配称为一个组合。【设计要求】 设计对于给定的满意度，求最佳

17、组合的程序，使得满意度总和达到最大。(1)采用 STL 的一维向量类构造构造二维向量矩阵。 ( 2)应用基本运算，设计算法求解。5、最佳任务分配方案 【问题描述】 设有 n 个人，准备承担 m 项课题任务，每个人只能承担其中的1 项。一般情况下 nm, 可以有多种任务分配方案。假设每个人完成不同的课题所需的经费不同，则一定存在一种最 佳方案，使得完成所有课题的总的费用最省。【设计要求】 设计对于给定的任务分配方案，求最佳任务分配方案，使得费用最省。( 1 )采用 STL 一维向量类构造二维向量矩阵。 ( 2)应用基本运算，通过搜索状态空间树实现问题求解。6、 排队购票问题【问题描述】 世界杯足

18、球亚洲区预选赛正在激烈进行。决赛门票处于热卖。为使门票公平、安全的销 售，售票处决定采用如下售票规则：( 1 )购票者到购票处领取一个随机编号。购票者按随机编号从小到大排序。 ( 2)随机编号处于最小编号与最大编号之间的购票者，可直接到窗口排队购票。( 3)售票窗口空闲时随机发出 0 或 1 指令，指令为 0 时，最小编号者到窗口购票，指令 为 1时，最大编号者到窗口购票。【设计要求】 设计算法实现按上述规则的排队售票程序。(1)采用 STL 的双端队列类等数据结构。 ( 2)应用基本运算，设计算法求解。7、 投票选举问题【问题描述】 在一次投票选举中，要从 n 个候选人中选出 1 个优胜者。

19、每个候选人有一张选票，只能 投给一位候选者，超过半数选票的候选人为优胜者。用一个长度为 n 的选举向量 v 表示收集 到的 n 张选票。投票选举问题要求根据选举向量 v 计算选举产生的优胜者。【设计要求】 设计算法实现投票选举问题的程序。（1）采用 STL 的向量等数据结构。 （2）应用基本运算，设计算法求解。-5-8、学生成绩条形图统计问题 【问题描述】 条形图问题描述：给定 n 个数据，绘出表示这 n 个数据的条形统计图。即统计出这 n 个 数据中有多少个不同的值， 以及每个值出现的频率是多少。 条形图常用于表示数据分布情况。 例如，学生考试成绩统计、居民收入分布情况等。假设输入数据为正整

20、数，利用二叉排序树 完成输入数据频率统计。【设计要求】 设计基于二叉排序树的学生成绩条形图统计程序。（1）采用 STL 的二叉排序树等数据结构。 （2）应用基本运算，设计算法求解。9、红黑平衡二叉树及其应用 【问题描述】 一棵红黑树本身就是一棵二叉排序树。红黑树中的结点颜色是黑色或红色。从红黑树的 根结点到叶子结点的路径上的黑色结点数目相同，最短的路径就是所有结点都是黑色。根据 红黑树的性质，红黑树在平衡类二叉排序树中有许多应用。【设计要求】 设计红黑平衡二叉树实现动态查找表及其应用。（1）采用 STL 红黑平衡二叉树数据结构。 （2）应用基本运算，实现红黑树的简单应用。10、动态选择求第 k

21、 小元素问题 【问题描述】集合中的元素是动态构成的。要求对集合中的n 个元素求解第 k 小的元素。【设计要求】设计应用红黑平衡二叉树实现动态查找第 k 小的元素。（1） 实现动态查找表的三种基本功能：查找、插入、删除。（2） 应用基本运算，设计算法求解。11、 基于紧缩图的邻接表的拓扑排序问题 【问题描述】 紧缩邻接表将图的每个顶点的邻接表紧凑的存储在两个向量 list 和 h 中。其中向量 list依次存储顶点 0, 1,，n-1 的邻接顶点。向量单元 hi存储顶点 i 的邻接表在向量 list 中的 起始位置。【设计要求】 设计基于紧缩图的邻接表的拓扑排序程序。（1） 采用 STL 的图、紧缩邻接表、栈等数据结构。（2） 应用基本运算，设计算法求解。12、 教务排课表的二分图问题 【问题描述】 如果一个无向图的顶点集合可以分为两个互不相交的子集，并且图中每条边的两个顶点都属于两个不同的顶点集。则称该图为一个二分图。可以用一个二分图表示教师与课程的排 课关系