数据结构课程设计独立题目

1/1数据结构课程设计独立题目题目2：运动会分数统计

1.问题描述

参与运动会有n个学校，学校编号为1……n。竞赛分成m个男子项目，和w个女子项目。项目编号为男子1……m，女子m+1……m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由同学自己设定。（m<=20,n<=20）

2.功能要求

1)可以输入各个项目的前三名或前五名的成果；

2)能统计各学校总分；

3)可以按学校编号、学校总分、男女团体总分排序输出；

4)可以按学校编号查询学校某个项目的状况；可以按项目编号查询取得前三或前五名的学校。

存储结构：同学自己依据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。

。

题目6：哈夫曼编/译码器

1.问题描述

利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼编/译码系统。

2.功能要求

I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。

E：编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。

D：译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。

P：印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码写入文件CodePrint中。

T：印哈夫曼树（TreePrinting）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。

题目9：构造可以使n个城市连接的最小生成树

1.问题描述

给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。

2.功能要求

城市间的距离网采纳邻接矩阵表示，邻接矩阵的存储结构定义采纳课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。

输入：表示城市间距离网的邻接矩阵（要求至少6个城市，10条边）

输出：最小生成树中包括的边及其权值，并显示得到的最小生成树的代价。

题目10：哈希表设计

1.问题描述

针对自己的班集体中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。

2.功能要求

假设人名为中国姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构照，用链表法处理冲突。测试数据读取熟识的30个人的姓名。

题目11：走迷宫嬉戏

1.问题描述

程序开头运行时显示一个迷宫地图，迷宫中心有一只老鼠，迷宫的右下方有一个粮仓。嬉戏的任务是使用键盘上的方向键操纵老鼠在规定的时间内走到粮仓处。

2.功能要求

1)老鼠形象可辨认，可用键盘操纵老鼠上下左右移动；

2)迷宫的墙足够牢固，老鼠不能穿墙而过；

3)正确检测结果，若老鼠在规定时间内走到粮仓处，提示胜利，否则提示失败；

4)添加编辑迷宫功能，可修改当前迷宫，修改内容：墙变路、路变墙；

5)找出走出迷宫的全部路径，以及最短路径。

利用序列化功能实现迷宫地图文件的存盘和读出等功能

题目12：任意长的整数加法

1.问题描述

设计一个程序实现两个任意长的整数的求和运算。

2.功能要求

利用双向循环链表，设计一个实现任意长的整数进行加法运算的演示程序。要求输入和输出每四位一组，组间用逗号隔开。如：1，0000，0000，0000，0000。

题目13：括号匹配问题

1.问题描述

假设一个算术表达式中可包含三种括号：圆括号，方括号和花括号且这三种括号可按任意次序嵌套使用。试利用栈的运算，编写判别给定表达式中所含括号是否正确配对消失的算法。

题目14：关键路径问题

1.问题描述

设计一个程序求出完成整项工程至少需要多少时间以及整项工程中的关键活动。

2.功能要求

1)对一个描述工程的AOE网，应推断其是否能够顺当进行。

2)若该工程能顺当进行，输出完成整项工程至少需要多少时间，以及每一个关键活动所依附的两个顶点、最早发生时间、最迟发生时间。

题目17：利用栈求表达式的值，可供学校生作业，并能给出分数。

功能要求

建立试题库文件，随机产生n个题目；题目涉及加减乘除，带括弧的混合运算；随时可以退出；保留历史分数，能回顾历史，给出与历史分数比较后的评价

题目18：约瑟夫环

1.问题描述

编号为1，2…n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开头任选一个正整数作为报数的上限值m，从第一个人开头按顺时针方向自1开头挨次报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个开头重新从1报数，如此下去，直至全部人全部出列为止，设计一个程序求出出列挨次。

2.功能要求

A利用单循环链表作为存储结构模拟此过程；

B键盘输入总人数、初始报数上限值m及各人密码；

C根据出列挨次输出各人的编号。

题目22：家谱管理

编写程序采纳一棵二叉树表示一个家谱关系，要求程序具有如下功能：

（1）文件操作功能：记录输入、记录输出、家谱记录存盘；

（2）家谱操作功能：用括号表示法和凹入表示法输出家谱二叉树，查找某人全部的儿子，查找某人的祖先。

题目23：哈夫曼编码应用

本设计要求对输入的一串电文字符实现哈夫曼编码，再对哈夫曼编码生成的代码串进行译码，输出电文字符串，要求程序实现以下几个方面的功能：

（1）哈夫曼树的建立（提示：还要设计一个实现统计输入电文字符串中各种字符消失的频率以及字符的种类的算法，假设电文中仅含有大写字母）；

（2）哈夫曼编码的生成；

（3）编码文件的译码

题目25：银行业务模拟

客户业务分两种：一是从银行借款或取款，二是向银行存款或还款。银行有两个窗口，相应的有两个队列。客户到达银行先排第一个队。若客户属第一种，且申请额超过银行现存资金总额而得不到满意时，则马上排入其次个队等候，直到满意时才离开银行；否则业务完成后马上离开银行。每接待完一个其次种业务的客户，则挨次检查和处理（假如可能）其次个队列中的客户，对能满意的申请者予以满意，不能满意者重新排到其次个队列的队尾。留意，在此检查过程中，一旦银行资金总额少于或等于刚才第一个队列中最终一个客户（其次种业务）被接待之前的数额，或者本次已将其次个队列检查或处理了一遍，就停止检查（由于此时已不行能还有能满意者）转而连续接待第一个队列的客户。任何时刻都只开一个窗口。假设检查不需要时间。营业时间结束时全部客户马上离开银行。

利用动态存储结构实现模拟写一个上述银行业务的大事驱动模拟系统，通过模拟方法求出客户在银行内逗留的平均时间。

题目26：文学讨论助手

文学讨论人员需要统计某篇英文小说中某些形容词的消失次数和位置。试写一个实现这一目标的文字统计系统，称为“文学讨论助手”

英文小说存于一个文本文件中。待统计的词汇合合要一次输入完毕，即统计工作必需在程序的一次运行之后就全部完成。程序的输出结果是每个词的消失次数和消失位置所在行的行号。

以您的C源程序模拟小说，C语言的保留字集作为待统计的词汇合。

题目27：散列表的设计与实现

设计散列表实现电话号码查找系统，把数据保存在文件中，充分利用挨次表和链表完成以下功能：

1)设每个记录有下列数据项：电话号码、用户名、地址；

2)从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；

3)采纳肯定的方法解决冲突；

4)查找并显示给定电话号码的记录；

5)查找并显示给定用户名的记录。

6)设计不同的散列函数，比较冲突率；

7)在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平

均查找长度的变化。

题目30：商店存货管理系统建立一商店存货管理系统，要求每次出货时取进货

时间最早且最接近保质期中止时间的货物。

分步实施：

（1）初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；（2）完成最低要求：建立一个文件，包括5个种类的货物状况，能对商品信息进行扩充（追加），修改和删除以及简洁的排序；

（3）进一步要求：扩充商品数量，以及完成系统查询功能。有爱好的同学可以自己扩充系统功能。

题目31：压缩器/解压器

为了节约存储空间，经常需要把文本文件采纳压缩编码的方式储存。例如：一个包含1000个x的字符串和2000个y的字符串的文本文件在不压缩时占用的空间为3002字节（每个x或每个y占用一个字节，两个字节用来表示串的结尾）。同样是这个文件，采纳游程长度编码（run-lengthcoding），可以存储为字符串1000x2000y，仅为10个字母，占用12个字节。若采纳二进制表示游程长度（1000和2000）可以进一步节省空间。假如每个游程长度占用2个字节，则可以表示的最大游程长度为2*pow(16)，这样，上例中的字符串只需要用8个字节来存储。当要读取编码文件时，需要对其进行解码。由压缩器（compressor）对文件进行编码，由解压器（decompressor）进行解码。

①（1）长度-游程编码的压缩/解压；+（2）L