07 数据结构课程设计指导书Word文档下载推荐.docx
《07 数据结构课程设计指导书Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《07 数据结构课程设计指导书Word文档下载推荐.docx（13页珍藏版）》请在冰点文库上搜索。
（4）订票：
（订票情况可以存在一个数据文件中，结构自己设定）
可以订票，如果该航班已经无票，可以提供相关可选择航班；
（5）退票：
可退票，退票后修改相关数据文件；
客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。
（6）修改航班信息：
当航班信息改变可以修改航班数据文件。
根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能。
4.跳马问题,就是64个国际象棋格子,任意位置放一个马,如何不重复地把格子走完。
（8）
1人
实用
5.
运动会（7）
题目描述：
参加运动会的N个学校编号为1—N。
比赛分为M个男子项目和W个女子项目，项目编号分别为1—M和M+1—M+W。
由于各项目的参加人数差别较大，有些项目取前五名，得分顺序为7，5，3，2，1；
还有些项目只取前三名，得分顺序为5，3，2。
写一个统计程序产生各种成绩单和得分报表。
基本要求：
产生各校的成绩单，内容包括各学校所取得每项成绩的项目号，名次（成绩），姓名和得分；
产生团体总分报表，内容包括校号，男子团体总分，女子团体总分和团体总分。
测试数据：
对于N=4，M=3，W=2，编号为奇数的项目取前5名，编号为偶数的项目取前3名，设计一组实例数据。
提示：
可以假设N小于等于20，M小于等于30，W小于等于20，姓名长度不超过20个字符。
每个项目结束时，将其编号，类型符（区分取前5名还是3名）输入，并按名次顺序输入运动员姓名，校号（和成绩）。
6.
建通讯录（7）
第一个模块——主函数main（）的功能是：
根据选单的选项调用各函数，并完成相应的功能。
第二个模块——Menu（）的功能是：
显示英文提示选单。
第三个模块——Quit（）的功能是：
退出选单。
第四个模块——Create（）的功能是：
创建新的通讯录。
第五个模块——Add（）的功能是：
在通讯录的末尾，写入新的信息，并返回选单。
第六个模块——Find（）的功能是：
查询某人的信息，如果找到了，则显示该人的信息，如果未找到，则提示通讯录中没有此人的信息，并返回选单。
第七个模块——Alter（）的功能是：
修改某人的信息，如果未找到要修改的人，则提示通讯录中没有此人的信息，并返回选单。
第八个模块——Delete（）的功能是：
删除某人的信息，如果未找到要删除的人，则提示通讯录中没有此人的信息，并返回选单。
第九个模块——List（）的功能是：
显示通讯录中的所有记录。
7.用扑克牌实现24点游戏。
8.哈夫曼编码/译码器1（8）
【问题描述】
设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。
（1）初始化：
键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；
（2）编码：
利用建好的哈夫曼树生成哈夫曼编码；
（3）输出编码；
（4）译码功能；
（5）设字符集及频度如下表：
字符空格ABCDEFGHIJKLM
频度1866413223210321154757153220
字符NOPQRSTUVWXYZ
频度5763151485180238181161
【选做内容】
（1）显示哈夫曼树；
（2）界面设计的优化。
（3）哈夫曼编码/译码均用二进制处理。
（10）
9.一元稀疏多项式计算器（8）
设计一个一元多项式加法器。
（1）输入并建立多项式；
（2）两个多项式相加；
（3）输出多项式：
n,c1,e1,c2,e2,…cn,en,其中，n是多项式项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列。
（4）计算多项式在x处的值；
（5）求多项式的导函数。
10.停车场管理1（8）
设有一个可以停放n辆汽车的狭长停车场，它只有一个大门可以供车辆进出。
车辆按到达停车时间的早晚依次从停车场最里面向大门口停放（最先到达的第一辆车放在停车场的最里面）。
如果停车场已放满n辆车，则后来的车辆只能在停车场大门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车就进入停车场。
停车场内如有某辆车要开走，在它之后近来的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场。
每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。
如果停留在便道上的车未进停车场就要离去，允许其离去，不收停车费，并且仍然保持在便道上等待的车辆的次序。
编制一程序模拟停车场管理。
实现提示：
汽车的模拟输入信息格式可以是：
（到达/离去，汽车牌照号码，到达/离去的时刻）。
例如：
（'
A'
1,5）表示一号牌照车爱5这个时刻到达，而（'
D'
5,20）表示5号牌照车在20这个时刻离去，整个程序可以在输入信息为（'
E'
0,0）时结束。
要求程序输出每辆车到达后的停车位置（停车场或便道上），以及某辆车离开停车场时应交纳的费用和它在停车场内停留的时间。
11.
停车场管理2（9）
（1）有一个两层的停车场,每层有6个车位,当第一层车停满后才允许使用第二层.（停车场可用一个二维数组实现,每个数组元素存放一个车牌号）每辆车的信息包括车牌号,层号,车位号,停车时间共4项.其中停车时间按分钟计算
（2）假设停车场初始状态为第一层已经停有4辆车,其车位号依次为1—4,停车时间依次为20,15,10,5.即先将这四辆车的信息存入文件”car.dat”中（数组的对应元素也要进行赋值）
（3）停车操作:
当一辆车进入停车场时,先输入其车牌号,再为它分配一个层号和一个车位号（分配前先查询车位的使用情况,如果第一层有空则必须停在第一层）,停车时间设为5,最后将新停入的汽车的信息添加文件”car.dat”中,并将在此之前的所有车的停车时间加5.
（4）收费管理（取车）:
当有车离开时,输入其车牌号,先按其停车时间计算费用,每5分钟0.2元.（停车费用可设置一个变量进行保存）,同时从文件”car.dat”中删除该车的信息,并将该车对应的车位设置为可使用状态（即二维数组对应元素清零）.按用户的选择来判断是否要输出停车收费的总计.
（5）输出停车场中全部车辆的信息.
（6）退出系统.
12.火车订票系统（8）
有订票子系统、售票子系统、退票子系统、统计子系统、查询子系统、生成数据子系统
13.
五子棋（9）
人机对战
14.迷宫问题（7.5）
问题描述：
迷宫实验是取自心理学的一个古典实验。
在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒中设置了许多墙，对行进方向形成了多处阻挡。
盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。
对同一只老鼠重复进行上述实验，一直到老鼠从入口到出口，而不走错一步。
老鼠经多次试验终于得到它学习走迷宫的路线。
设计一个计算机程序对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
在给出入口和出口的前提下，给出动态的迷宫行走路线。
【选做内容】给出所有可行路线。
15.八皇后问题（7）
试编写程序实现将八个皇后放置在国际象棋棋盘的无冲突的位置上的算法，并给出所有的解。
在国际象棋上放置皇后时，任何一个皇后的水平、竖直和斜45º
都不能有另一个皇后。
解决该问题采用逐次试探的方法，即采用递归调用putchess函数的方法。
首先将第一个皇后放于第一行第一列，然后开始向下一行递归。
每一步递归中，首先检测待放置位置是否与已放置的皇后冲突，如不冲突，则进行下一行的放置，否则，选择该行的下一个位置进行检测。
如整行的位置都冲突，则回到上一行，重新选择位置。
1人
16.无向图应用问题（7）
如果以无向网表示n个城市之间通信网络的建设计划，顶点表示城市，边上的权表示该线路的造价，设计一个方案，使这个通讯网的总造价最低。
这是一个求最小生成树的问题。
n个城市名和各边的权值由用户输入，建立图的邻接矩阵，然后以Prim算法来求最小生成树，然后输出方案。
17.中国象棋（10）
3人（人人对战为2人）
18.二叉排序树。
用二叉链表作存储结构。
（1）以回车（'
\n'
）为输入结束标志,输入数列L，生成一棵二叉排序树T；
（2）对二叉排序树T作中序遍历，输出结果；
（3）计算二叉排序树T查找成功的平均查找长度,输出结果；
（4）输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历（执行操作2）；
否则输出信息“无x”。
19.二叉排序树。
用顺序表（一维数组）作存储结构（8）
（2）对二叉排序树T作中序遍历,输出结果；
（4）输入元素x,查找二叉排序树T:
若存在含x的结点,则删除该结点,并作中序遍历（执行操作2）；
否则输出信息“无x”；
20.图的基本操作与实现（8.5）
（1）自选存储结构,输入含n个顶点（用字符表示顶点）和e条边的图G；
（2）求每个顶点的度,输出结果；
（3）指定任意顶点x为初始顶点,对图G作DFS遍历,输出DFS顶点序列（提示:
使用一个栈实现DFS）；
（4）指定任意顶点x为初始顶点,对图G作BFS遍历,输出BFS顶点序列（提示:
使用一个队列实现BFS）；
（5）输入顶点x,查找图G:
若存在含x的顶点,则删除该结点及与之相关连的边,并作DFS遍历（执行操作3）；
（6）判断图G是否是连通图，输出信息“YES”/“NO”；
（7）如果选用的存储结构是邻接矩阵,则用邻接矩阵的信息生成图G的邻接表,即复制图G,然再执行操作
（2）；
反之亦然。
21.
井字过三关（7.5）
设计一个井字棋的游戏程序，棋盘结构如下图：
游戏规则是：
从一个空的棋盘开始，人为x一方，计算机为o一方，人机双方轮流放置棋子，人下的时候，字符x将被放入棋盘中指定的位置，轮到计算机下时，程序将扫描棋盘，并将字符o放入扫描到的第一个空格，某一方有3枚棋子占据了一横行、一竖行或一对角线则获胜，若整个棋盘被占满还没有一方获胜则为和局。
（1）机器扫描策略的优化；
（8.5）
（2）界面设计的优化。
22.银行财务实时处理系统（二叉排序树的应用）（8）
要求:
银行帐户的帐号由科目表和分户号组成.此系统要求把属于一个科目的分户表文件的记录全部找出来,并按记录中的分户号从小到大的顺序排列,以便与按顺序逐户处理信息并查找某一个分户号的记录.
科目表文件每个记录包括科目表及科目表分户二叉结点的指针.分户表文件每个记录的形式为记录号、分户号、左链和右链。
根据题意，本系统应能实现以下三个功能。
（１）构造分户二叉树排序树；
（２）中序遍历分户二叉树排序树；
（３）查找某一分户记录．
23.
全国交通咨询模拟（9）
处于不同目的的旅客对交通工具有不同的要求。
例如，因公出差的旅客希望在旅途中的时间尽可能的短，出门旅游的游客则期望旅费尽可能省，而老年旅客则要求中转次数最少。
编制一个全国城市间的交通咨询程序，为旅客提供两种或三种最优决策的交通咨询。
设计要求：
（1）提供对城市信息进行编辑（如：
添加或删除）的功能。
（2）城市之间有两种交通工具：
火车和飞机。
提供对列车时刻表和飞机航班进行编辑（增设或删除）的功能。
（3）提供两种最优决策：
最快到达和最省钱到达。
全程只考虑一种交通工具
（4）旅途中耗费的总时间应该包括中转站的等候时间。
（5）咨询以用户和计算机的对话方式进行。
由拥护输入起始站、终点站、最优决策原则和交通工具，输出信息：
最快需要多长时间才能到达或者最少需要多少旅费才能到达，并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。
参考教科书7.6节图7.33的全国交通图，自行设计列车时刻表和飞机航班。
（1）对全国城市交通图和列车时刻表及飞机航班表进行编辑，应该提供文件形式输入和键盘输入两种方式。
飞机航班表的信息应包括：
起始站的出发时间、终点站的到达时间和票价；
列车时刻表则需根据交通图给出各个路段的详细信息，例如：
基于教科书7.6节图7.33的交通图，对从北京到上海的火车，需给出北京至天津、天津至徐州及徐州至上海各段的出发时间、到达时间及票价等信息。
（2）以邻接表作交通图的存储结构，表示边的结构内除含有邻接点的信息外，还应包括交通工具、路程中耗费的时间和花费以及出发和到达的时间等多种属性。
选作内容：
增加旅途中转次数最少的最优决策。
24.散列表的设计与实现（7.5）
设计散列表实现电话号码查找系统。
（1）设每个记录有下列数据项：
电话号码、用户名、地址；
（2）从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；
（3）采用双散列法解决冲突；
（4）查找并显示给定电话号码的记录；
（5）查找并显示给定用户名的记录。
（1）系统功能的完善；
（2）设计不同的散列函数，比较冲突率；
（3）在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。
25.
背包问题的求解（8）
假设有一个能装入总体积为T的背包和n件体积分别为w1,w2,…,wn的物品，能否从n件物品中挑选若干件恰好装满背包，即使w1+w2+…+wn=T，要求找出所有满足上述条件的解。
当T=10，各件物品的体积{1，8，4，3，5，2}时，可找到下列4组解：
（1，4，3，2）
（1，4，5）
（8，2）
（3，5，2）。
可利用回溯法的设计思想来解决背包问题。
首先将物品排成一列，然后顺序选取物品装入背包，假设已选取了前i件物品之后背包还没有装满，则继续选取第i+1件物品，若该件物品"
太大"
不能装入，则弃之而继续选取下一件，直至背包装满为止。
但如果在剩余的物品中找不到合适的物品以填满背包，则说明"
刚刚"
装入背包的那件物品"
不合适"
，应将它取出"
弃之一边"
，继续再从"
它之后"
的物品中选取，如此重复，，直至求得满足条件的解，或者无解。
由于回溯求解的规则规则是"
后进先出"
因此自然要用到栈。
26.
内部排序算法的性能分析（7）
设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数。
（1）对起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法进行比较；
（2）待排序表的表长不小于100，表中数据随机产生，至少用5组不同数据作比较，比较指标有：
关键字参加比较次数和关键字的移动次数（关键字交换记为3次移动）；
（3）输出比较结果。
（1）对不同表长进行比较；
（2）验证各算法的稳定性；
（3）输出界面的优化。
28.
哈夫曼编码/译码器2（10）
从指定原文件中读取字符并统计字符的出现频数，由此建哈夫曼树对字符进行二进制编码，产生编码结果文件，然后再对结果文件进行解码，产生解码结果文件，并将其与原文件比较是否一致。
原文件为文本文件，编码结果文件是二进制文件或文本文件，而解码结果文件为文本文件。
29.改进约瑟夫（Joseph）环问题（8）
改进约瑟夫问题的描述是：
编号为1，2，…，n的n个人按顺时针方向围坐一圈,每人有一个密码Ki（整数），留作其出圈后应报到Ki后出圈。
报数方法采用顺时针报数和逆时针报数交替进行，初始密码可任意确定。
求最后剩下的人的编号。
30.稀疏矩阵的操作（8）
（1）稀疏矩阵采用三元组表示；
（2）求两个具有相同行列数的稀疏矩阵A和B的相加矩阵C，并输出C。
（3）求出A的转置矩阵D，输出D。
31．表达式翻译（7）
编写完整程序，将中缀表达式翻译成后缀表达式。
表达式由操作数（变量）、操作（运算符）以及小括弧“（”和“）”组成，其中：
•操作包括算术运算、关系运算和逻辑运算三类；
•操作数应能够识别但个字符或由字母和数字任意多个字符构成；
•能够识别出简单的错误，如括弧不匹配。
输入：
中缀表达式，80个字符以内。
输出：
转换后的后缀表达式。
32．文章编辑（7）
功能：
输入一页文字，程序可以统计出文字、数字、空格的个数。
静态存储一页文章，每行最多不超过80个字符，共N行；
要求
（1）分别统计出其中英文字母数和空格数及整篇文章总字数；
（2）统计某一字符串在文章中出现的次数，并输出该次数；
（3）删除某一子串，并将后面的字符前移。
存储结构使用线性表，分别用几个子函数实现相应的功能；
输入数据的形式和范围：
可以输入大写、小写的英文字母、任何数字及标点符号。
输出形式：
（1）分行输出用户输入的各行字符；
（2）分4行输出"
全部字母数"
、"
数字个数"
空格个数"
文章总字数"
（3）输出删除某一字符串后的文章；
33．关键路径问题（7）
34．以队列实现的仿真技术预测理发馆的经营状况（9）
理发馆一天的工作过程如下：
1）理发馆有N把理发椅，可同时为N位顾客进行理发。
2）理发师分三个等级（一级、二级、三级），对应不同的服务收费。
3）当顾客进门时，需选择某级别理发师，只要该级别的理发师有空椅，则可立即坐下理发，否则需排队等候。
4）一旦该级别的理发师有顾客理发完离去，排在队头的顾客便可开始理发。
5）若理发馆每天连续营业T分钟，求
（1）一天内顾客在理发馆内的平均逗留时间；
（2）顾客排队等候理发的队列长度平均值；
（3）营业时间到点后仍需完成服务的收尾工作时间；
（4）统计每天的营业额；
（5）统计每天不同级别理发师的创收。
35．救护车调度模拟系统
用C++语言设计实现一个用事件驱动的“救护车调度”离散模型，模拟120急救中心响应每个病人的呼救信号统一调度救护车运行的情况。
我们对问题作适当简化，假设：
某城市共有m个可能的呼救点（居民小区、工厂、学校、公司、机关、单位等），分布着n所医院（包含在m个点中），有k辆救护车分派在各医院待命，出现呼救病人时，由急救中心统一指派救护车接送至最近的医院救治。
救护车完成一次接送任务后即消毒，并回原处继续待命。
假定呼救者与急救中心、急救中心与救护车之间的通讯畅通无阻，也不考虑道路交通堵塞的影响。
可以用m个顶点的无向网来表示该城市的各地点和道路。
时间可以分钟为单位，路段长可表示为救护车行驶化费的分钟数。
三．课程设计的程序
1．布置课程设计任务并选题。
2．课程设计准备。
3．上机实践，答辩
4．撰写课程设计报告。
5．课程设计成绩评定。
四．数据结构课程设计学生提交的内容
1．书面，课程设计报告（任务书、内容）。
课程设计任务书模板自己填写，任务书后面直接写报告的内容。
Ø
课程设计题目
分工人员及分工
软硬件运行环境
算法设计的思想
算法的设计与分析（含流程图）
测试结果与分析
总结（收获与体会）:
课程设计过程的收获、遇到问题、遇到问题解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程设计过程中对《数据结构》课程的重新认识等内容。
参考文献（格式）
1林来青,李立．空间技术基础．北京：
宇航出版社，2003
2湛颖．空间最优交会控制理论与方法研究．哈尔滨工业大学博士论文，2004：
30-40
3
4
附：
源代码（可选）
2．电子版，一个文件夹，内容如下：
（1）程序源代码
（2）课程设计报告（任务书、内容）
（3）答辩PPT文件
该文件夹压缩成一个文件，文件命名规则学号后三位+姓名（组长名）．zip；
邮给你们的指导教师。
五．成绩评定方法
《数据结构》课程设计的最后成绩有以下几个方面组成：
（1）准备情况。
（10%）
（2）上机实验：
出勤情况，学生的动手能力，创新精神，程序运行情况，程序的结构合理与否，算法说明的清晰程度，上交程序存放的规范程度，课设过程中的课设进展情况（应该至少有四次），独立完成情况（不允许雷同），以及加分因素。
（50%）
（3）答辩（20%）
（4）课程设计报告：
规范情况，总结的深刻程度。
（20%）
成绩分优、良、中、及格和不及格五等。
升级会员 