数据结构课程设计1 .doc

《数据结构课程设计1 .doc》由会员分享，可在线阅读，更多相关《数据结构课程设计1 .doc（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1. 一元稀疏多项式计算器(不选)问题描述设计一个一元稀疏多项式简单计算器。基本要求输入并建立多项式；输出多项式，输出形式为整数序列：n, c1, e1, c2, e2, cn, en ，其中n是多项式的项数，ci, ei分别是第i项的系数和指数，序列按指数降序排序；多项式a和b相加，建立多项式a+b;多项式a和b相减，建立多项式a-b;测试数据(2x+5x8-3.1x11)+(7-5x8+11x9)=(-3.1x11+11x9+2x+7)(6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2-x2+7.8x15)=(-7.8x15-1.2x9-x+12x-3)(1+x+x2+x3

2、+x4+x5)+(-x3-x4)=(x5+x2+x+1)(x+x3)+(-x-x3)=0(x+x2+x3)+0=(x3+x2+x)实现提示用带头结点的单链表存储多项式，多项式的项数存放在头结点中。2. 背包问题的求解（一人）问题描述假设有一个能装入总体积为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）实现提示可利用回溯法的设计思想来解决背包问题。首

3、先，将物品排成一列，然后顺序选取物品转入背包，假设已选取了前i件物品之后背包还没有装满，则继续选取第i+1件物品，若该件物品“太大”不能装入，则弃之而继续选取下一件，直至背包装满为止。但如果在剩余的物品中找不到合适的物品以填满背包，则说明“刚刚”装入背包的那件物品“不合适”，应将它取出“弃之一边”，继续再从“它之后”的物品中选取，如此重复，直至求得满足条件的解，或者无解。由于回溯求解的规则是“后进先出”因此自然要用到栈。3. 完全二叉树判断（一人）用一个二叉链表存储的二叉树，判断其是否是完全二叉树。4. 最小生成树求解（一人）任意创建一个图，利用克鲁斯卡尔算法，求出该图的最小生成树。5. 最小

4、生成树求解（一人）任意创建一个图，利用普里姆算法，求出该图的最小生成树。6. 树状显示二叉树（一人）编写函数displaytree(二叉树的根指针，数据值宽度，屏幕的宽度)输出树的直观示意图。输出的二叉树是垂直打印的，同层的节点在同一行上。问题描述假设数据宽度datawidth=2,而屏幕宽度screenwidth为64=26,假设节点的输出位置用（层号，须打印的空格数）来界定。第0层：根在（0，32）处输出；第1层：因为根节点缩进了32个空格，所以下一层的偏移量（offset）为32/2=16=screenwidth/22。即第一层的两个节点的位置为（1，32-offset）,(1,32+o

5、ffset)即（1，16），（1，48）。第二层：第二层的偏移量offset为screenwidth/23。第二层的四个节点的位置分别是（2，16-offset），（2，16+offset），（2，48-offset），（2，48+offset）即（2，8），（2，24），（2，40），（2，56）。第i层：第i层的偏移量offset为screenwidth/2i+1。第i层的每个节点的位置是访问第i-1层其双亲节点时确定的。假设其双亲的位置为（i-1，parentpos）。若其第i层的节点是其左孩子，那末左孩子的位置是（i，parentpos-offset），右孩子的位置是（i，parent

6、pos+offset）。实现提示利用二叉树的层次遍历算法实现。利用两个队列Q，QI。队列Q中存放节点信息，队列QI中存相应于队列Q中的节点的位置信息，包括层号和需要打印节点值时需要打印的空格数。当节点被加入到Q时，相应的打印信息被存到QI中。二叉树本身采用二叉链表存储。7. 综合排序（一人）问题描述利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。基本要求分别采用插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序以及归并排序。统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。8. 哈夫曼编码/译码器（一人） 问题描述要

7、传输一些数据（比如英文单词），设计一个利用哈夫曼算法的编码系统，为这些单词编码。并在接收端进行译码。基本要求 将需要传输的数据存放在数据文件data.txt 中。 读入数据文件并为其编码，将编码后的内容存入文件code.txt中。 读入code.txt，译码。并将译码后的内容输出在屏幕上。9. 停车场管理（二人）问题描述设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在南端，最先到达的第一辆车停放在停车场的最北端），若停车场内已停了n辆汽车，则后来的汽车只能在门外的通道上等候，一旦有车开走，收排在通道上的第一辆车

8、即可开入；当停车场内每辆车要离开时，在它之后进入的车辆必须先退出停车场为其让路，待该辆车开出大门，其他车辆再按原次序进入停车场，每辆停放在停车场的车在它离开停车场时必须按它停留在停车场内的时间长短交纳停车费。试为停车场编写按上述要求进行管理的模拟程序。基本要求 要求以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理； 要求处理的数据元素包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻； 该系统完成以下功能：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收

9、费）； 要求栈以顺序结构实现，队列以链表实现。测试数据设n=2，输入数据为：（A，1，5），（A，2，10），（D，1，15），（A，3，20），（A，4，25），（D，2，35），（D，4，40），（E，0，0）。其中A表示到达，D表示离开，E表示输入结束。10. 约瑟夫环（一人）问题描述约瑟夫问题的一种描述是：编号为1，2，n 的n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个整数作为报数上限值m,从第一个人开始顺时针自1开始顺序报数，报到m 时停止报数。报m 的人出列，将他的密码作为新的m 值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有的人全

10、部出列为止。试设计一个程序，求出出列顺序。基本要求利用单向循环链表作为存储结构模拟此过程，按照出列顺序打印出各人的编号。测试数据m 的初值为20；n =7，7个人的密码依次是：3，1，7，2，4，8，4，出列的顺序为6，1，4，7，2，3，5。11. 纸牌游戏（一人）问题描述编号为1-52张牌，正面向上，从第2张开始，以2为基数，是2的倍数的牌翻一次，直到最后一张牌；然后，从第3张开始，以3为基数，是3的倍数的牌翻一次，直到最后一张牌；然后从第4张开始，以4为基数，是4的倍数的牌翻一次， 直到最后一张牌；.再依次5的倍数的牌翻一次，6的，7的 直到 以52为基数的 翻过，输出：这时正面向上的牌

11、有哪些？12. 猴子吃桃子问题（一人）问题描述有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。基本要求1)采用数组数据结构实现上述求解2)采用链数据结构实现上述求解3)采用递归实现上述求解13. 文章编辑（一人）问题描述输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过80个字符，共N行；要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。基本要求存储结构使用线性表，

12、分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出全部字母数、数字个数、空格个数、文章总字数（3）输出删除某一字符串后的文章；14. 字符串的操作（一人）基本要求 （1） 字符串采用数组存储，建立两个字符串String1和String2。输出两个字符串。 （2） 将字符串String2的头n个字符添加到String1的尾部。输出结果。 （3） 查找串String3在串String1中的位置，若String3在String1中不存在，则插入String3在String1中的m位置上。

13、输出结果。 测试数据： （1） String1: “typedefstructArcBox” String2: “VertexTypedata” String3: “data” n:6,m:7 （2） String1: “structArcBox” String2: “VertexType” String3: “Box” n:3,m:315. 宿舍管理查询软件（二人）基本要求为宿舍管理人员编写一个宿舍管理查询软件, 程序设计要求：A 采用交互工作方式B 建立数据文件 ，数据文件按关键字（姓名、学号、房号）进行排序(冒泡、选择、插入排序等任选一种)查询菜单: (用二分查找实现以下操作)按姓名查询

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

15、现.17. 数制转换问题（一人）基本要求任意给定一个M进制的数x ，请实现如下要求1) 求出此数x的10进制值（用MD表示）2) 实现对x向任意的一个非M进制的数的转换。至少用两种或两种以上的方法实现上述要求（用栈解决，用数组解决，其它方法解决）。18. 教学计划安排检验程序（拓扑排序）（一人）问题描述针对学院的计算机系本科课程，根据课程之间的依赖关系，制定课程安排计划，并满足各学期课程数大致相同。按照用户输入的课程数，学期数，课程间的先后关系数目以及课程间两两间的先后关系，程序执行后会给出每学期应学的课程。基本要求(1) 输入的形式和输入值的范围：输入间用空格隔开。要求用户输入的课程数小于2

16、0，学期数小于或是等于8，课程名的长度小于等于10个字符。(2) 程序所能达到的功能：按照用户的输入，给出每学期应学的课程。(4) 测试数据：输入：学期数：，课程数：12，课程间的先后关系数：16，课程的代表值：v1,v2,v3,v4,v5,v6,v7,v8,v9,v10,v11,v12。课程间两两间的先后关系：v1 v2,v1 v3, v1 v4,v1 v12,v2 v3,v3 v5,v3 v7,v3 v8,v4 v5, v5 v7,v6 v8,v9 v10, v9 v11 , v9 v12,v10 v12,v11 v6输出：第1学期应学的课程：v1 v9第2学期应学的课程：v2 v4 v1

17、0 v11第3学期应学的课程：v3 v6 v12第4学期应学的课程：v5 v8第5学期应学的课程：v719. 迷宫问题（一人）问题描述以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。基本要求 1）实现一个以链表作储存结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i，j，d)的形式输出，其中：(i，j)表示迷宫中的一个坐标，d表示走到下一个坐标的方向。2）编写递归形式的算法，求得迷宫中所有可能的通路。测试数据迷宫的测试数据如下：左上角(1，1)为入口，右下角(8，9)为出口。1

18、 2 3 4 5 6 7 8001000100010001000001101011100100001000001000101011110011100010111000000实现提示 计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向20. 航空客运订票系统（限2人）基本要求录入： 可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定） ；查询： 可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）； 可以输入起飞抵达城市，查询飞机航班情况；订票：（订票情况可以存在一个数据文件中，结构自己设定） 可以订票，

19、如果该航班已经无票，可以提供相关可选择航班；退票： 可退票，退票后修改相关数据文件； 客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。修改航班信息： 当航班信息改变可以修改航班数据文件 根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能。实现提示每条航线应包含的信息有：终点站名、航班号、飞机号、飞行日期（星期几）、乘员定额、余票额、已订票的客户名单（包括姓名、订票额、座位号）和预约登记的客户名单（包括日期、姓名、所需票额）。这最后两项显然是一个线性表和一个队列。为查找方便、已订票客户的线性表应按客户姓名有序，并且，为插入和删除方便，应以链表作存储结构。由于预约人数无

20、法预料，队列也应以链表作存储结构。整个系统需汇总各条航线的情况登录在一张线性表上，由于航线基本不变，可采用顺序存储结构，并按航班有序或按终点站名有序。每条航线是这张表上的一个记录，包含上述八个域，其中乘员名单域为指向乘员名单链表的头指针，预约登记客户名单域为分别指向队头和队尾的指针。21. 运动会分数统计（限2人）问题描述参加运动会有n个学校，学校编号为1n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1m，女子m+1m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m=20,n=20

21、）基本要求1) 可以输入各个项目的前三名或前五名的成绩；2) 能统计各学校总分，3) 可以按学校编号或名称、学校总分、男女团体总分排序输出；4) 可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。5) 数据存入文件并能随时查询 6) 规定：输入数据形式和范围：可以输入学校的名称，运动项目的名称输出形式：有中文提示，各学校分数为整型界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。22. 图书管理系统(2人)基本要求1)每种书的登记内容包括书号、书名

22、、著作者、现存量和库存量；2)对书号建立索引表（线性表）以提高查找效率；3)系统主要功能如下：a) 采编入库：新购一种书，确定书号后，登记到图书帐目表中，如果表中已有，则只将库存量增加；b)借阅：如果一种书的现存量大于0，则借出一本，登记借阅者的书证号和归还期限，改变现存量c)归还：注销对借阅者的登记，改变该书的现存量。23. 个人帐簿管理系统(2人)问题描述个人帐簿管理系统记录某人每月的全部收入及各项开支情况，包括食品消费，房租，子女教育费用，水电费，医疗费，储蓄等。进入系统后可以输入和修改某月的收支情况，可以对每月的开支从小到大进行排序，可以根据输入的月份查询每月的收支情况。提示1)初步完

23、成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2)完成最低要求：建立一个文件，包括某人5个月的收支情况，能对文件中的信息进行扩充（追加），修改和删除；3)进一步要求：完成对每月的开支排序，以及完成系统查询功能。有兴趣的同学可以自己扩充系统功能。24. 图的遍历（一人）实现图的深度优先, 广度优先遍历算法，并输出原图结构及遍历结果。25. 学生成绩管理系统(2人)（1）界面友好，易于操作。可采用菜单或其它人机对话方式进行选择。（2）实现对学生成绩信息进行排序与查找。可按学生学号、姓名等信息进行查询。每个学生信息包含：学号，姓名，班级，语文，数学，英语，物理，化学等项。学生信息的存储结构

24、可以选择顺序结构，也可以选择链式结构。26. 电话号码查询系统(2人)问题描述设计散列表实现电话号码查找系统基本要求1） 设每个记录有下列数据：电话号码、用户名、地址2） 从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；3） 采用一定的方法解决冲突；4） 查找并显示给定电话号码的记录；5） 查找并显示给定用户名的记录。27. 成绩分析问题(2人)问题提描述录入、保存一个班级学生多门课程的乘积，并对成绩进行分析。基本要求1） 通过键盘输入各学生的多门课程的乘积，建立相应的文件input.dat。2） 对文件input.dat中的数据进行处理，要求具有如下功能：A. 按各门课程成绩排序

25、，并生成相应的文件输出。B. 计算每人的平均成绩，按平均成绩排序，并生成文件。C. 求出各门课程的平均成绩、最高分、最低分、不及格人数、6069分人数、7079分人数、8089分人数、90分以上人数。D. 根据姓名或学号查询某人的各门课成绩，重名情况也能处理。28. 表达式求值（1人）问题描述 见课本P5229. 二叉排序树与平衡二叉树的实现（1人）问题描述采用二叉链表储存结构，实现对二叉排序树与平衡二叉树的操作。基本要求1） 以回车符(n)为输入结束标志，输入数列L，生成一棵二叉排序树T；2） 对二叉排序树T作中序遍历，输出结果；3） 计算二叉排序树T查找成功的平均查找长度，输出结果；4）

26、输入元素x，查找二叉排序树T，若存在含x的结点，则删除该结点，并作中序遍历；否则，输出信息“无x”。5） 用数列L，生成平衡二叉树BT，当插入新元素之后，发现当前的二叉排序树BT不是平衡二叉排序树，则立即将它转换成新的平衡的二叉排序树BT；6） 计算平衡二叉排序树BT的平均查找长度，输出结果。30. 二叉排序树与平衡二叉树的实现（1人）问题描述采用顺序表储存结构，实现对二叉排序树与平衡二叉树的操作。基本要求1） 以回车符(n)为输入结束标志，输入数列L，生成一棵二叉排序树T；2） 对二叉排序树T作中序遍历，输出结果；3） 计算二叉排序树T查找成功的平均查找长度，输出结果；4） 输入元素x，查找

27、二叉排序树T，若存在含x的结点，则删除该结点，并作中序遍历；否则，输出信息“无x”。5） 用数列L，生成平衡二叉树BT，当插入新元素之后，发现当前的二叉排序树BT不是平衡二叉排序树，则立即将它转换成新的平衡的二叉排序树BT；6） 计算平衡二叉排序树BT的平均查找长度，输出结果。31. 线索二叉树（一人） 建立中序二叉树，并且中序遍历；求中序二叉树上已知结点的中序遍历的前驱和后继。32. 校园导游咨询（限2人）问题描述设计一个校园导游程序，为来访的客人提供各种信息查询服务。基本要求1)设计你的学校的校园平面图，所含景点不少于十个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息，以边表示路径，存放路径长度等相关信息。2)为来访客人提供图中任意景点相关的信息查询。3)为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短路径。测试数据可由自己根据实际情况指定。实现提示校园平面图是一个无向网。顶点和边均含有相关信息。