数据结构设计题目-刘丽.

1、数据结构课程设计要求1、本次设计为期2周；分组进行，每组成员自由组合，要求不超过5人。2、在备选题目中，选择2题进行设计，要求线性结构中必选1题。树型和图形结构中选择1题。任意两个小组的题目不能完全相同。3、题目设计完成后，要提交课程设计报告和实验源代码。课程设计报告要求包括如下内容：1）课程设计报告封面；2）目录；3）设计题目、要求；4）设计题目分析：以流程图、文字描述两种方式给出；5）实验结果：测试数据、结果截图；6）主要源代码：需要添加文字说明其功能。4、设计最后一天为答辩时间，每个小组抽出2人描述设计过程，其他人员回答老师提问。5、整个设计的成绩由实验过程（20%）、设计报告（40%）

2、、答辩（40%）三部分成绩组成。数据结构设计题目线性结构：选题1：简单的职工管理系统【问题描述】对单位的职工进行管理，包括插入、删除、查找、排序等功能。【要求】职工对象包括姓名、性别、出生年月、工作年月、学历、职务、住址、电话等信息。（1）新增一名职工：将新增职工对象按姓名以字典方式职工管理文件中。（2）删除一名职工：从职工管理文件中删除一名职工对象。（3）查询：从职工管理文件中查询符合某些条件的职工。（4）修改：检索某个职工对象，对其某些属性进行修改。（5）排序：按某种需要对职工对象文件进行排序。【实现提示】职工对象数不必很多，便于一次读入内存，所有操作不经过内外存交换。（1）由键盘输入职工

3、对象，以文件方式保存。程序执行时先将文件读入内存。（2）对职工对象中的"姓名"按字典顺序进行排序。（3）对排序后的职工对象进行增、删、查询、修改等操作。选题2：通讯录管理【问题描述】 该设计采用菜单作为应用程序的主要界面，用控制语句来改变程序执行的顺序，控制语句是实现结构化程序设计的基础。该设计的任务是利用一个简单实用的菜单，通过菜单单项进行选择，实现和完成通讯录管理中常用的几个不同的功能。【任务要求】 （1） 菜单内容1、 通讯录链表的建立2、 通讯者结点的插入3、 通讯者结点的查询4、 通讯者结点的删除5、 通讯录链表的输出0、 退出管理系统请选择05：（2） 设计要求

4、使用05来选择菜单项，其他输入则不起作用。（3） 功能函数设计5个不同功能的算法实现编程题，目的是练习利用链表结构来解决实际应用问题的能力，进一步理解和熟悉线形表的链式存储结构。【测试数据】自行设定，注意边界等特殊情况。选题3：运动会分数统计【问题描述】 参加运动会有n个学校，学校编号为1n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1m，女子m+1m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m<=20,n<=20）【任务要求】 功能要求：1).可以输入各个项目的前

5、三名或前五名的成绩；2)能统计各学校总分，3)可以按学校编号、学校总分、男女团体总分排序输出；4).可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。 规定：输入数据形式和范围：20以内的整数（如果做得更好可以输入学校的名称，运动项目的名称）输出形式：有中文提示，各学校分数为整形界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构；测试数据：

6、要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；【测试数据】自行设定，注意边界等特殊情况。选题4：航班信息的查询与检索【问题描述】 该设计要求对飞机航班信息进行排序和查找。可按航班的航班号、起点站、到达站、起飞时间以及到达时间等信息进行查询。【任务要求】对于本设计，可采用基数排序法对一组具有结构特点的飞机航班号进行排序，利用二分查找法对排好序的航班记录按航班号实现快速查找，按其他次关键字的查找可采用最简单的顺序查找方法进行，因此他们用得较少。每个航班记录包括八项，分别是：航班号、起点站、终点站、班期、起飞时间

7、、到达时间、飞机型号以及票价等，假设航班信息表（8条记录）航班号起点站终点站班期起飞时间到达时间机型票价CA1544合肥北京1.2.4.510551240733960MU5341上海广州每日14201615M901280CZ3869重庆深圳2.4.6085510357331010MU3682桂林南京2.3.4.6.720502215M901380HU1836上海北京每日094011207381250CZ3528成都厦门1.3.4.5.715101650CRJ1060MU4594昆明西安1.3.5.6101511403281160SC7425青岛海口1.3.619202120DH41630其中航

8、班号一项的格式为：K0 K1 K2 K3 K4 K5CZ3869其中K0和K1的输入值是航空公司的别称，用两个大写字母标示，后4位为航班号，这种航班号关键字可分成两段，即字母和数字。其余七项输入内容因为不涉及本设计的核心，因此除了票价为数值型外，均定义为字符串即可。【测试数据】自行设定，注意边界等特殊情况。选题5：学生成绩管理【问题描述】本例对学生的成绩管理做一个简单的模拟，用菜单选择方式完成下列功能： 登记学生成绩；查询学生成绩；插入学生成绩；删除学生成绩。【任务要求】 算法输入：操作要求，学生信息算法输出：操作结果算法要点：把问题看成是对线性表的操作。将学生成绩组织成顺序表，则登记学生成绩

9、即是建立顺序表操作；查询学生成绩、插入学生成绩、删除学生成绩即是在顺序表中进行查找、插入和删除操作。【测试数据】自行设定，注意边界等特殊情况。选题6： joseph环【问题描述】 编号是1，2，,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。【任务要求】 利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。测试数据：m的初

10、值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？ 要求： 输入数据：建立输入处理输入数据，输入m的初值，n ，输入每个人的密码，建立单循环链表。 输出形式：建立一个输出函数，将正确的输出序列【测试数据】自行设定，注意边界等特殊情况。选题7：敢死队问题  【问题描述】有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一

11、轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完成为止。   排长是不愿意去的，假设排长为1号，请你设计一程序，求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。 【要求描述】 至少采用两种不同的数据结构的方法实现。选题8：魔王语言解释课程设计（栈和队列）【问题描述】 有一个魔王总是使用自己的一种非常精炼而抽象的语言讲话，没有人能听懂，但他的语言是可以逐步解释成人能听懂的语言，因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的，设大写字母表示魔王语言的词汇；小写字母表示人的语言词汇

12、；希腊字母表示可以用大写字母或小写字母代换的变量。魔王语言可含人的词汇。 魔王语言可以按以下三条规则翻译成人听懂得话：（12n）nn-11 B->tAdA A->sae 要求设计者设计一个魔王语言解释系统，用VC写一个程序满足上述功能。【输入参数的格式和合法取值范围】要求用户输入一串字符串，其中至多包括一对括号，字符串可输入的字母包含规则（2）和规则（3）的A和B。人的语言词汇包含：t，s，a，e，d，z，g，x，n，h。【输出的格式】用户输入字符串后，系统将其翻译成人能听懂的语言。例如:鹅追鹅鹅赶鹅天上一只鹅地上一只鹅。【测试数据】B(ehnxgz)B将解释成tsaedsaeez

13、egexenehetsaedsae 若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是：“天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅”。 选题9：报数问题【问题描述】设有n个人站成一排，从左到右的编号分别是1-n，现从左到右报数“1，2，1，2”，数到1的人出列，数到2的人站在队伍的最右端。报数过程反复进行，直到n个人都出列为止。要求给出他们的出列顺序。ß 例如：n=8，初始序列：ß 1，2，3，4，5，6，7，8ß 出列顺序：1，3，5，7，2，6，4，8【实验要求】（1）使用循环队列完成此题；（2）使用链队完成此题；选题10：编制一个

14、表达式求值的程序。【问题描述】1. 利用堆栈存储结构存储读入的运算符，输入的限定范围是数字（09），以及+*/()。输入字符串限定长度为20，可以根据需要进行改变。如果遇到不是以上范围或者连续输入两个运算符，如：+，则会提示输入错误，请重新输入。输出的结果是转换后的后序表达式，以及float型数字，不会含有非法字符。2. 演示程序采用的是文件输入，只需要在源代码中输入要输入的文件的地址，然后就可以在文本文件中进行输入，运行过程中会自动读取，输出文本输入的表达式，及运算结果。3. 程序执行的命令包括：1） 构造字符优先级比较表，比较优先关系 2）文件输入 3）构造堆栈，运算符入栈4）堆栈输出，变

15、为后序表达式，并计算 5）输出结果，结束4.测试数据 文件地址：C:UserslenovoDesktop4.txt 1) 输入：(35+20/2)*2-4/2+12正确输出结果是：100.00002)输入：(35+20/2)*2-/2+12结果是:error input 3) 输入：a+ar/3=135结果是:error input选题11：内部排序算法比较【问题描述】在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机数据比较各种算法的关键字比较次数和关键字移动次数，以取得直观感受。【任务要求】1) 对以下7种常用的内部排序算法进行比较：冒泡排

16、序、直接插入排序、简单选择排序、希尔排序、堆排序、归并排序、快速排序。2) 待排序表的表长不小于100；其中的数据要用伪随机数程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）。3) 最后要对结果作出简单分析，包括对各组数据得出结果波动大小的解释。【测试数据】由随机数产生器生成选题12：马踏棋盘【问题描述】 将马随机放在国际象棋的8* 8棋盘Bord88的某个方格中，马按走棋规则进行移动。要求每个方格上只进入一次，走遍棋盘上全部64个方格。【任务要求】 编制非递归程序，求出马的行走路线 ，并按求出的行走路线，将数字1，2，

17、64依次填入一个8* 8的方阵，输出之。测试数据：由读者指定,可自行指定一个马的初始位置。实现提示：每次在多个可走位置中选择一个进行试探，其余未曾试探过的可走位置必须用适当结构妥善管理，以备试探失败时的“回溯”(悔棋)使用。【测试数据】自行设定，注意边界等特殊情况。选题13：迷宫与栈问题【问题描述】以一个mXn的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。【任务要求】1) 首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i，j，d）的形式输出。其中：（i，j）指示

18、迷宫中的一个坐标，d表示走到下一坐标的方向。如，对于下列数据的迷宫，输出一条通路为：（1，1，1），（1，2，2），（2，2，2），（3，2，3），（3，1，2），。2) 编写递归形式的算法，求得迷宫中所有可能的通路。3) 以方阵形式输出迷宫及其通路。【测试数据】迷宫的测试数据如下：左上角（0，1）为入口，右下角（8，9）为出口。树型结构选题1：哈夫曼(Huffman)编/译码器【问题描述】利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的

19、信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。【任务要求】一个完整的系统应具有以下功能：I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。E：编码（Encoding）。利用以建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。D：译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。P：印代码文件（Print）。将

20、文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。T：印哈夫曼树（Tree Printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。【测试数据】利用教科书例6-2（严蔚敏数据结构P148）中的数据调试程序。用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”。字符空格ABCDEFGHIJKLM频度1866413223210321154757153220字符NOP

21、QRSTUVWXYZ频度5763151485180238181161选题2：算术表达式与二叉树【问题描述】一个表达式和一棵二叉树之间，存在着自然的对应关系。写一个程序，实现基于二叉树表示的算术表达式的操作。【任务要求】假设算术表达式Expression内可以含有变量（az）、常量（09）和二元运算符（+，-，*，/，(乘幂)）。实现以下操作：1) ReadExpre(E)以字符序列的形式输入语法正确的前缀表达式并构造表达式E。2) WriteExpre(E)用带括弧的中缀表达式输出表达式E。3) Assign(V,c)实现对变量V的赋值（V=c），变量的初值为0。4) Value(E)对算术表

22、达式E求值。5) CompoundExpr（P，E1，E2）-构造一个新的复合表达式（E1）P（E2）【测试数据】1) 分别输入0；a；-91；+a*bc；+*5x2*8x；+*3x3*2x2x6并输出。2) 每当输入一个表达式后，对其中的变量赋值，然后对表达式求值。选题3：动态查找表【问题描述】 利用二叉排序树完成动态查找表的建立、指定关键字的查找、插入与删除指定关键字结点。【任务要求】 算法输入：指定一组数据。算法输出：显示二叉排序树的中序遍历结果、查找成功与否的信息、插入和删除后的中序遍历结果(排序结果)。算法要点：二叉排序树建立方法、动态查找方法,对树进行中序遍历。【测试数据】自行设定

23、，注意边界等特殊情况。图型结构选题1： 最小生成树【问题描述】在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。对于图，其生成树中的边也带权，将生成树各边的权值总和称为生成树的权，并将权值最小的生成树称为最小生成树（Minimun Spanning Tree），简称为MST。有两种非常典型的算法：Prim算法和kruskal算法。【任务要求】 设计程序完成如下功能：对给定的网和起点，用PRIM算法和kruskal算法的基本思想求解出所有的最小生成树。存储结构可自行选择。【测试数据】自行设定，注意边界等特殊情况。选题2：哈希表应用【问题描述】 利用哈希表进行存储。【任务要求】 任务要求：针对