2023年数据结构大作业题目

数据结构大作业

专业：_______________________________

班级：_______________________________

题目：_______________________________

学生姓名:_______________________________

（课程设计报告撰写的基本规定）

题目（三号，黑体，居中）

（空一行）

一、任务与目的（标题均为小三号，宋体）

（正文均为小四号，宋体，行距1.5倍）

（这一部分需简朴介绍题目内容，即该题目到底要做什么。假如涉及明确的算法，最佳

再简朴介绍一下算法产生的背景，还要列出各项本设计要达成的具体的目的。）

二、方案设计与论证

（对目的进行总体分析，说明要采用的基本思绪，说明碰到的问题和解决方法。说明

完毕本次课程设计的完整过程。要描述程序的设计思想，重点描述你自己提出的与己有工作

不同的程序设计思想。）

三、算法说明

（这一部分需具体描述解决问题所需要用到的算法和重要的数据结构，即该课程设计到

底应当怎么做。

基本规定：解决问题中所用到的关键筑法都要描述清楚，而不是仅描述主函数。算法和

数据结构可用伪码和图示描述，不耍只写源代码和注释。这一部分的目的是让读者在短时间

内清楚地理解作者解决问题的整体思绪，表达方式必须比源代码更通俗易懂，假如读者感

觉还不如直接读源代码来得明白，这一部分内容就失去了意义.）

四、所有源程序清单

（给出本次大作业所编写所有源程序已经调试好的可运营代码清单，字体可以用宋体五

号，页数可增长，每个程序开头用注释文字说明此程序的用途和大休工作过程，，程序中必

要部分也要加入足够多的注释行。）

五、程序运营的测试与分析

（这一部分内容需要紧扣课程设计的题目类型和规定，设计提供相应的测试方法和结

果。这部分涉及运营图。

对于需要比较不同算法性能优劣的题目，应设计并填写一张性能比较表格，列出不同算

法在同一指标卜的性能表现。仅仅罗列出一堆数据是不够的，还应将数字转化为图形、曲线

等方式，帮助读者更直观地理解测试结果。

对于需要运用某算法解决某问题的题目，应设计并填写一张测试用例表。每个测试用例

一般应涉及下列内容：

•测试输入：设计一组输入数据；

•测试目的：设计该输入的目的在于测试程序在哪方面也先存在漏洞；

•对的输出：相应当输入，若程序对的，应当输出的内容；

•实际输出：该数据输入后，实际测试得到的输出内容；

•错误因素：假如实际输出与对的输出不符，需分析产生错误的也许因素：

•当前状态：分为“通过”（实际输出与对的输出相符）、"已改正‘‘（实际输出与对的输

出不符，但现在已修改对的）、“待修改”（实际输出与对的输出不符，且尚未改正）三种状态。

需要注意的是，测试员的态度，不是提供几组简朴的数据让程序员容易通过，从而宣称

该程序是对的的；而应当是下方百计设计“刁难”的数据，想办法让所测试的程序暴露出问

题，这样才干真正帮助程序员完毕对的的程序，最后通过严格的裁判数据测试。）

六、结论与心得

（重要说明程序调试中发现的问题和解决办法，涉及你学到了什么，哪里碰到了困难，

解决的办法，也许但因时间关系没有来得及完毕的想法，此后的目的等。）

七、参考资料

（用五号，宋体，按照规范格式列出。）

（要列出在完毕设计中查看过并有所运用的所有参考资料，涉及各类技术书籍、期刊

论文和相关网页的网址。注意你看过但没有运用的资料不要列入,要可以回答你列出资料中

的相关问题。）

1.航空客运订票系统

通过此系统可以实现如下功能：

录入：可以录入航班情况（数据可以存储在一个数据文献中，数据结构、具体数据自

定）；

查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞到达城市，

航班票价，票价折扣，拟定航班是否满仓）：可以输入起飞到达城市，查询飞机航班情况：

订票：（订票情况可以存在一个数据文献中，结构自己设定）可以订票，假如该航班

已经无票，可以提供相关可选择航班：

退票：可退票，退票后修改相关数据文献；客户资料有姓名，证件号，订票数量及

航班情况，订单要有编号。

修改航班信息：当航班信息改变可以修改航班数据文献

规定：根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完毕功能;

2.散列法的实验研究

基本规定：

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

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

3、采用一定的方法解决冲突：

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

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

进一步完毕内容：

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

2、在散列函数拟定的前提下,尝试各种不同类型解决冲突的方法，考察平均查找长度的变

化。

3.学生搭配问题

一班有m个女生，有n个男生（m不等于n）,现要开一个舞会.男女生分别编号坐在舞池的

两边的椅子上.每曲开始时，依次从男生和女生中各出一人配对跳舞，本曲没成功配对者坐着

等待下一曲找舞伴.

请设计一系统模拟动态地显示出上述过程，规定如下：

1、输出每曲配对情况

2、计算出任何一个男生（编号为X）和任意女生（编号为Y）,在第K曲配对跳舞的情况.

至少求出K的两个值.

3、尽量设计出多种算法及程序

4、提醒:用队列来解决比较方便.

4.二叉排序树的实现

用顺序和二叉链表作存储结构

1）以回车（’山）为输入结束标志，输入数列L,生成一棵二叉排序树T：

2）对二叉排序树T作中序遍历，输出结果；

3）输入元素x,查找二叉排序树T,若存在含x的结点，则删除该结点,并作中序遍历（执行操作

2）；否则输出信息“无X”：

5.运用栈求表达式的值

编写程序实现表达式求值，即验证某算术表达式的对的性，若对的，则计算该算术表达式的

值。

重要功能描述如下：

1、从键盘上输入表达式。

2、分析该表达式是否合法：

（1）是数字，则判断该数字的合法性。若合法，则压入数据到堆栈中。

(2)是规定的运算符，则根据规则进行解决。在解决过程中，将计算该表达式的值。

(3)若是其它字符，则返回借误信息。

3、若上述解决过程中没有发现错误，则认为该表达式合法，并打印解决结果。

程序中应重要包含下面几个功能函数：

voidinitstack()：初始化堆栈

intMake_str()：语法检查并计算

intpush_opcratc(intoperate)：将操作码压入堆栈

intpush_num(doublenum)：将操作数压入堆栈

intprecede。ntoperate)：解决操作码

intchange_opnd(intoperate)：将字符型操作码转换成优先级

intpush_opnd(intoperate)：将操作码压入堆栈

intpop_opnd()：将操作鸟弹出堆栈

intcaculate(intcur_opnd)：简朴计算+,-»*>/

doublepop_num()：弹出操作数

6.走迷宫游戏

程序开始运营时显示一个迷宫地图，迷宫中央有一只老鼠，迷宫的右下方有一个粮仓。游戏

的任务是使用键盘上的方向键操纵老鼠在规定的时间内走到粮仓处。

规定：

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

迷宫的墙足够结实，老鼠不能穿墙而过；

对的检测结果，若老鼠在规定期间内走到粮仓处，提醒成功，否则提醒失败；

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

找出走出迷宫的所有途径，以及最短途径。

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

7.顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实

现。

设有一元多项式Am(X)和Bn(X).

Am(X)=Ao+A1X1+A2X2+A3X3+...+AmXm

Bn(X)=Bo+BlX1+B2X2+B3X3+...4-BnXn

请实现求M(x)=Am(x)+Bn(x)、M(x)=Am(x)-Bn(x)和M(x)=Am(x)xBn(x)o

8.线索二叉树的应用

规定：实现线索树建立、插入、删除、恢复线索的实现。

9.稀疏矩阵实现与应用

规定：实现三元组，十字链表下的稀疏矩阵的下列应用。

(1)稀疏矩阵的存储

(2)稀疏矩阵加法

(3)矩阵乘法

(4)矩阵转置

10.树的应用

规定：实现树与二叉树的转换的实现。以及树的前序、后序的递归、非递归算法，层顺序的

非递归算:法的实现，应包含建树的实现。

11.图的遍历和生成树求解实现

规定：

先任意创建一个图;

图的DFS,BFS的递归和非递归算法的实现

最小生成树（两个算法）的实现，求连通分量的实现

规定用邻接矩阵、邻接表、十字链表多种结构存储实现

12.排序综合

运用随机函数产生N个随机整数（20230以上），对这些数进行多种方法进行排序。

规定：

至少采用三种方法实现上述问题求解（提醒，可采用的方法有插入排序、希尔排序、起泡排

序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文献中。

记录每一种排序方法的性能（以上机运营程序所花费的时间为准进行对比），找出其中两种

较快的方法。

假如采用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）将权值数据存放在数据文献〔文献名为daia.txt,位于执行程序的当前目录中）

2）分别采用动态和静态存储结构

3）初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫星树：

4）编码：运用建好的哈夫显树生成哈夫曼编码：

5）输出编码:

6）设字符集及频度如下表：

字符空格ABCDEFGHIJKLM

频度1866413223210321154757153220

字符NOPQRSTUVWXYZ

频度5763151485180238181161

【进一步完毕内容】

1）译码功能；

2）显示哈夫曼树：

3）界面设计的优