数据结构大作业题目.doc

数据结构大作业专 业：班 级：题 目：学生姓名：（课程设计报告撰写的基本要求）题目（三号，黑体，居中）（空一行）一、任务与目标（标题均为小三号，宋体）（正文均为小四号，宋体，行距1.5倍）（这一部分需简单介绍题目内容，即该题目到底要做什么。如果涉及明确的算法，最好再简单介绍一下算法产生的背景，还要列出各项本设计要达到的具体的目标。）二、方案设计与论证（对目标进行总体分析，说明要采用的基本思路，说明遇到的问题和解决方法。说明完成本次课程设计的完整过程。要描述程序的设计思想，重点描述你自己提出的与已有工作不同的程序设计思想。）三、算法说明（这一部分需详细描述解决问题所需要用到的算法和重要的数据结构，即该课程设计到底应该怎么做。基本要求：处理问题中所用到的关键算法都要描述清楚，而不是仅描述主函数。算法和数据结构可用伪码和图示描述，不要只写源代码和注释。这一部分的目的是让读者在短时间内清楚地理解作者解决问题的整体思路，表达方式必须比源代码更通俗易懂。如果读者感觉还不如直接读源代码来得明白，这一部分内容就失去了意义。）四、全部源程序清单（给出本次大作业所编写全部源程序已经调试好的可运行代码清单，字体可以用宋体 五号，页数可增加，每个程序开头用注释文字说明此程序的用途和大体工作过程，程序中必要部分也要加入足够多的注释行。）五、程序运行的测试与分析（这一部分内容需要紧扣课程设计的题目类型和要求，设计提供相应的测试方法和结果。这部分包括运行图。对于需要比较不同算法性能优劣的题目，应设计并填写一张性能比较表格，列出不同算法在同一指标下的性能表现。仅仅罗列出一堆数据是不够的，还应将数字转化为图形、曲线等方式，帮助读者更直观地理解测试结果。对于需要利用某算法解决某问题的题目，应设计并填写一张测试用例表。每个测试用例一般应包括下列内容：测试输入：设计一组输入数据；测试目的：设计该输入的目的在于测试程序在哪方面可能存在漏洞；正确输出：对应该输入，若程序正确，应该输出的内容；实际输出：该数据输入后，实际测试得到的输出内容；错误原因：如果实际输出与正确输出不符，需分析产生错误的可能原因；当前状态：分为“通过”(实际输出与正确输出相符)、“已改正(实际输出与正确输出不符，但现在已修改正确)、“待修改”(实际输出与正确输出不符，且尚未改正)三种状态。需要注意的是，测试员的态度，不是提供几组简单的数据让程序员容易通过，从而宣称该程序是正确的；而应该是千方百计设计“刁难”的数据，想办法让所测试的程序暴露出问题，这样才能真正帮助程序员完成正确的程序，最后通过严格的裁判数据测试。）六、结论与心得（主要说明程序调试中发现的问题和解决办法，包括你学到了什么，哪里遇到了困难，解决的办法，可能但因时间关系没有来得及完成的想法，今后的目标等。）七、参考资料（用五号，宋体，按照规范格式列出。）（要列出在完成设计中查看过并有所利用的所有参考资料，包括各类技术书籍、期刊论文和相关网页的网址。注意你看过但没有利用的资料不要列入，要能够回答你列出资料中的相关问题。）附录：供选择的数据结构大作业题目可选题目：1.航空客运订票系统42.散列法的实验研究53.学生搭配问题54.二叉排序树的实现55.利用栈求表达式的值56.走迷宫游戏67.顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现。68.线索二叉树的应用69.稀疏矩阵实现与应用710.树的应用711.图的遍历和生成树求解实现712.排序综合713.纸牌游戏714.利用栈求表达式的值，可供小学生作业，并能给出分数。715.数制转换问题816.停车场问题817.哈夫曼编码/译码器818.约瑟夫环919.任意长的整数加法920.关键路径问题91. 航空客运订票系统通过此系统可以实现如下功能： 录入： 可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定） ；查询： 可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）； 可以输入起飞抵达城市，查询飞机航班情况； 订票：（订票情况可以存在一个数据文件中，结构自己设定） 可以订票，如果该航班已经无票，可以提供相关可选择航班； 退票： 可退票，退票后修改相关数据文件； 客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。 修改航班信息： 当航班信息改变可以修改航班数据文件 要求： 根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能；2. 散列法的实验研究基本要求：1、 设每个记录有下列数据项：电话号码、用户名、地址；2、 从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；3、 采用一定的方法解决冲突；4、 查找并显示给定电话号码的记录；5、 查找并显示给定用户名的记录。进一步完成内容：1、 设计不同的散列函数，比较冲突率；2、 在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。3. 学生搭配问题一班有m个女生,有n个男生(m不等于n),现要开一个舞会. 男女生分别编号坐在舞池的两边的椅子上.每曲开始时,依次从男生和女生中各出一人配对跳舞, 本曲没成功配对者坐着等待下一曲找舞伴.请设计一系统模拟动态地显示出上述过程,要求如下:1、 输出每曲配对情况2、 计算出任何一个男生(编号为X)和任意女生(编号为Y),在第K曲配对跳舞的情况.至少求出K的两个值.3、 尽量设计出多种算法及程序4、 提示:用队列来解决比较方便.4. 二叉排序树的实现用顺序和二叉链表作存储结构1) 以回车(n)为输入结束标志,输入数列L，生成一棵二叉排序树T；2) 对二叉排序树T作中序遍历，输出结果；3) 输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”；5. 利用栈求表达式的值编写程序实现表达式求值，即验证某算术表达式的正确性，若正确，则计算该算术表达式的值。主要功能描述如下：1、从键盘上输入表达式。2、分析该表达式是否合法：（1）是数字，则判断该数字的合法性。若合法，则压入数据到堆栈中。（2）是规定的运算符，则根据规则进行处理。在处理过程中，将计算该表达式的值。（3）若是其它字符，则返回错误信息。3、若上述处理过程中没有发现错误，则认为该表达式合法，并打印处理结果。程序中应主要包含下面几个功能函数：void initstack()：初始化堆栈int Make_str()：语法检查并计算int push_operate(int operate)：将操作码压入堆栈int push_num(double num)：将操作数压入堆栈int procede(int operate)：处理操作码int change_opnd(int operate)：将字符型操作码转换成优先级int push_opnd(int operate)：将操作码压入堆栈int pop_opnd()：将操作码弹出堆栈int caculate(int cur_opnd)：简单计算+，-，*，/double pop_num()：弹出操作数6. 走迷宫游戏程序开始运行时显示一个迷宫地图，迷宫中央有一只老鼠，迷宫的右下方有一个粮仓。游戏的任务是使用键盘上的方向键操纵老鼠在规定的时间内走到粮仓处。要求：老鼠形象可辨认，可用键盘操纵老鼠上下左右移动；迷宫的墙足够结实，老鼠不能穿墙而过；正确检测结果，若老鼠在规定时间内走到粮仓处，提示成功，否则提示失败；添加编辑迷宫功能，可修改当前迷宫，修改内容：墙变路、路变墙；找出走出迷宫的所有路径，以及最短路径。利用序列化功能实现迷宫地图文件的存盘和读出等功能7. 顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现。设有一元多项式Am(x)和Bn(x). Am(x)=A0+A1x1+A2x2+A3x3+ +Amxm Bn(x)=B0+B1x1+B2x2+B3x3+ +Bnxn请实现求M(x)= Am(x)+Bn(x)、M(x)= Am(x)-Bn(x)和M(x)= Am(x)Bn(x)。8. 线索二叉树的应用要求：实现线索树建立、插入、删除、恢复线索的实现。9. 稀疏矩阵实现与应用要求：实现三元组，十字链表下的稀疏矩阵的下列应用。（1）稀疏矩阵的存储（2）稀疏矩阵加法（3）矩阵乘法（4）矩阵转置10. 树的应用要求：实现树与二叉树的转换的实现。以及树的前序、后序的递归、非递归算法，层次序的非递归算法的实现，应包含建树的实现。11. 图的遍历和生成树求解实现要求：先任意创建一个图；图的DFS,BFS的递归和非递归算法的实现最小生成树（两个算法）的实现，求连通分量的实现要求用邻接矩阵、邻接表、十字链表多种结构存储实现12. 排序综合利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。要求：至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。如果采用4种或4种以上的方法者，可适当加分。13. 纸牌游戏任务：编号为1-52张牌，正面向上，从第2张开始，以2为基数，是2的倍数的牌翻一次，直到最后一张牌；然后，从第3张开始，以3为基数，是3的倍数的牌翻一次，直到最后一张牌；然后从第4张开始，以4为基数，是4的倍数的牌翻一次， 直到最后一张牌；.再依次5的倍数的牌翻一次，6的，7的 直到 以52为基数的 翻过，输出：这时正面向上的牌有哪些？14. 利用栈求表达式的值，可供小学生作业，并能给出分数。要求：建立试题库文件，随机产生n个题目；题目涉及加减乘除，带括弧的混合运算；随时可以退出；保留历史分数，能回顾历史，给出与历史分数比较后的评价15. 数制转换问题 任意给定一个M进制的数x ，请实现如下要求1)求出此数x的10进制值（用MD表示）2)实现对x向任意的一个非M进制的数的转换。3)至少用两种或两种以上的方法实现上述要求（用栈解决，用数组解决，其它方法解决）。16. 停车场问题停车场是一条可以停放n辆车的狭窄通道，且只有一个大门汽车停放安到达时间的先后依次由北向南排列（大门在最南端，最先到达的第一辆车停在最北端）若停车场已经停满n辆车，后来的汽车在便道上等候，一旦有车开走，排在便道上的第一辆车可以开入；当停车场的某辆车要离开时，停在他后面的车要先后退为他让路，等它开出后其他车在按照原次序开入车场，每两停在车场的车要安时间长短缴费。 要求：以栈模拟停车场，以队列车场外的便道，按照从终端输入的数据序列进行模拟管理。每一组数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码、以及到达或离去的时刻。对每一组数据进行操作后的信息为：若是车辆到达，则输出汽车在停车场的内或便道上的位置：若是车辆离去则输出汽车在停车场内的停留时间和应缴纳的费用（在便道上的停留时间不收费）。栈以顺序结构实现，队列以链表结构实现。17. 哈夫曼编码/译码器【问题描述】设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。【基本要求】1)将权值数据存放在数据文件(文件名为data.txt，位于执行程序的当前目录中) 2)分别采用动态和静态存储结构3)初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；4)编码：利用建好的哈夫曼树生成哈夫曼编码；5)输出编码；6)设字符集及频度如下表：字符 空格 A B C D E F G H I J K L M频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20字符 N O P Q R S T U V W X Y Z 频度 57 63 15 1 48 51 80 23 8 18 1 16 1 【进一步完成内容】1)译码功能；2)显示哈夫曼树；3)界面设计的优化。18. 约瑟夫环问题描述：编号为1，2 n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个开始重新从1报数，如此下去，直至所有人全部出列为止，设计一个程序求出出列顺序。 基本要求：1、利用单循环链表作为存储结构模拟此过程；2、键盘输入总人数、初始报数上限值m及各人密码；3、按照出列顺序输出各人