数据结构课程设计题目及说明

发布 2022-10-06 03:51:28 阅读 2495

目录。1 一元稀疏多项式计算器 2

2 迷宫问题 2

3 哈夫曼编/译码器 3

4 教学计划编制问题 4

5 成绩分析问题 5

6 二叉排序树与平衡二叉树的实现 6

7 图的基本操作与实现 6

8 全国交通咨询模拟 6

9 内部排序算法的性能分析 7

10 背包问题的求解 7

11 简单个人书管理系统的设计与实现 8

12 简易电子**的设计 8

13 停车厂模拟管理程序的设计与实现 9

14 农夫过河问题的求解 9

15 **号码查询系统 10

16 通讯录 11

17 24点游戏1 11

18 24点游戏2 11

问题描述]设计一个一元稀疏多项式简单计算器。

基本要求]一元稀疏多项式简单计算器的基本功能是:

1) 输入并建立多项式;

2) 输出多项式,输出形式为整数序列:n,c1,e1, c2,e2,,,cn,en,其中n是多项式的项数,ci,ei,分别是第i项的系数和指数,序列按指数降序排序;

3) 多项式a和b相加,建立多项式a+b;

4) 多项式a和b相减,建立多项式a-b;

5) 计算多项式在x处的值。

6) 计算器的**界面。(选做)

测试数据]1) (2x+5x8-3.1x11)+(7-5x8+11x9) =3.1x11+11x9+2x+7)

2) (6x-3-x+4.4x2-1.2x9)-(6x-3+5.4x2-x2+7.8x15)=(7.8x15-1.2x9-x+12x-3)

3) (1+x+x2+x3+x4+x5)+(x3-x4)=(x5+x2+x+1)

4) (x+x3)+(x-x3)=0

5) (x+x2+x3)+0=( x3+ x2+ x)

实现提示]用带表头结点的单链表存储多项式,多项式的项数存放在头结点中。

问题描述]以一个m*n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论。

基本要求]1) 实现一个以链表作存储结构的栈类型,然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i,j,d)的形式输出,其中:(i,j)指示迷宫中的一个坐标,d表示走到下一坐标的方向。

2) 编写递归形式的算法,求得迷宫中所有可能的通路;

3) 以方阵形式输出迷宫及其通路。(选做)

测试数据]迷宫的测试数据如下:左上角(1,1)为入口,右下角(9,8)为出口。

实现提示]计算机解迷宫通常用的是“穷举求解”方法,即从入口出发,顺着某一个方向进行探索,若能走通,则继续往前进;否则沿着原路退回,换一个方向继续探索,直至出口位置,求得一条通路。假如所有可能的通路都探索到而未能到达出口,则所设定的迷宫没有通路。

可以二维数组存储迷宫数据,通常设定入口点的下标为(1,1),出口点的下标为(m,n)。为处理方便起见,可在迷宫的四周加一圈障碍。对于迷宫中任一位置,均可约定有东、南、西、北四个方向可通。

问题描述]利用哈夫曼编码进行信息通讯可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码;在接收端将传来的数据进行译码(复原)。对于双工信道 (即可以双向传输信息的信道),每端都需要一个完整的编/译码系统。

试为这样的信息收发站写一个哈夫曼码的编译码系统。

基本要求]一个完整的系统应具有以下功能:

l)i:初始化 (initialization)。从终端读入字符集大小n,及n个字符和m个权值,建立哈夫曼树,并将它存于文件hfmtree中。

2)c:编码 (coding)。利用已建好的哈夫曼树(如不在内存,则从文件hfmtree中读入),对文件tobetrans中的正文进行编码,然后将结果存入文件codefile中。

3)d:解码(decoding)。利用已建好的哈夫曼树将文件codefile中的**进行译码,结果存入文件textfile中。

4)p:打印**文件 (print)。将文件codefile以紧凑格式显示在终端上,每行50个**。同时将此字符形式的编码文件写入文件codeprint中。

5)t:打印哈夫曼树 (tree printing)。将已在内存中的哈夫曼树以直观的方式 (树或凹入表形式)显示在终端上,同时将此字符形式的哈夫曼树写入文件treeprint中。

实现提示]可以根据题目要求把程序划成5个模块,设计成菜单方式,每次执行一个模块后返回菜单。

除了初始化(i)过程外,在每次执行时都经过一次读取磁盘文件数据。这是因为如果在程序执行后一直没有进行初始化(i)过程,为了能使后面的操作顺利进行,可以通过读取旧的数据来进行工作。比如:

如果程序的工作需要的字符集和权值数据是固定的,只要在安装程序时进行一次初始(i)化操作就可以了。再次运行程序时,不管进行哪项操作都可以把需要的数据读入到内存。

算法分析]本程序主要用到了三个算法。

1)哈夫曼编码。

在初始化(i)的过程中间,要用输入的字符和权值建立哈夫曼树并求得哈夫曼编码。先将输入的字符和权值存放到一个结构体数组中,建立哈夫曼树,将计算所得的哈夫曼编码存储到另一个结构体数组中。

2)串的匹配。

在编码(d)的过程中间,要对已经编码过的**译码,可利用循环,将**中的与哈夫曼编码的长度相同的串与这个哈夫曼编码比较,如果相等就回显并存入文件。

3)二叉树的遍历。

在打印哈夫曼树(t)的过程中,因为哈夫曼树也是二叉树,所以就要利用二叉树的先序遍历将哈夫曼树输出。

测试数据]根据实验要求,在中输入"this program is my f**orite",字符集和其频度如表1所示。

表1字符集频度表。

问题描述]大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限,每学年含两学期,每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的,而且课程在开设时间的安排必须满足先修关系。

每门课程有哪些先修课程是确定的,可以有任意多门,也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。

基本要求]1) 输入参数包括:学期总数,一学期的学分上限,每门课的课程号(固定占3位的字母数字串)、学分和直接先修课的课程号。

2) 允许用户指定下列两种编排策略之一:一是使学生在各学期中的学习负担尽量均匀;二是使课程尽可能地集中在前几个学期中。

3) 若根据给定的条件问题无解,则报告适当的信息;否则将教学计划输出到用户指定的文件中。计划的**格式自行设计。

测试数据]学期总数:6;学分上限:10;该专业共开设12门课,课程号从c01到c12,学分顺序为2,3,4,3,2,3,4,4,7,5,2,3。先修关系见图1。

实现提示]可设学期总数不超过12,课程总数不超过100。如果输入的先修课程号不在该专业开设的课程序列中,则作为错误处理。应建立内部课程号与课程号之间的对应关系。

图1 课程先修关系。

问题描述]录入、保存一个班级学生多门课程的成绩,并对成绩进行分析。

基本要求]1)通过键盘输入各学生的多门课程的成绩,建立相应的文件。

2)对文件中的数据进行处理,要求具有如下功能:

1) 按各门课程成绩排序,并生成相应的文件输出。

2) 计算每人的平均成绩,按平均成绩排序,并生成文件。

3) 求出各门课程的平均成绩、最高分、最低分、不及格人数、60~69分人数、70~79分人数、80~89分人数、90分以上人数。

4) 根据姓名或学号查询某人的各门课成绩,重名情况也能处理。

3)界面美观。

测试数据]测试数据如表2所示。

表2 成绩表。

问题描述]分别采用二叉链表和顺序表作存储结构,实现对二叉排序树与平衡二叉树的操作。

基本要求]1)用二叉链表作存储结构:

1) 以回车('')为输入结束标志,输入数列l,生成一棵二叉排序树t;

2) 对二叉排序树t作中序遍历,输出结果;

3) 计算二叉排序树t查找成功的平均查找长度,输出结果;

4) 输入元素x,查找二叉排序树t,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2);否则输出信息“无x”;

5) 用数列l,生成平衡的二叉排序树bt:当插入新元素之后,发现当前的二叉排序树bt不是平衡的二叉排序树,则立即将它转换成新的平衡的二叉排序树bt;

6) 计算平衡的二叉排序树bt的平均查找长度,输出结果。

2)用顺序表(一维数组)作存储结构:

1) 以回车('')为输入结束标志,输入数列l,生成一棵二叉排序树t;

数据结构课程设计题目及要求

题目 学生信息管理系统的开发与设计。1.基本内容。学生简历 学生信息的添加 学生信息的删除 学生信息的查询 有关信息的输出2.设计要求。以链表为存储结构,利用菜单进行功能选择,测试数据设计者自定。每个学生的数据项包含 学号 姓名 性别 班级 住址等。要求用c完成。要求和安排。1 问题分析和任务定义 ...

《数据结构》课程设计题目及要求

1 每位同学限选1题,并到所在自然班的班长处登记,同一题不超过4人 一个班之内 2 课程设计成绩分为5级 优秀 5分 良好 4分 中等 3分 及格 2分 不及格 1分 3 题目有难易和工作量大小之分 具体见题目后的 星级 为体现公平,请参见下表,请同学们结合自身情况选择题目。4 课程设计报告和源 严...

数据结构课程设计题目及要求

实验一 实验四任选一题 实验五 实验九任选一题。实验一运动会分数统计。一 实验目的 1 熟练掌握线性表的两种存储方式。2 掌握链表的操作和应用。3 掌握指针 结构体的应用。4 按照不同的学校,不同项目和不同的名次要求,产生各学校的成绩单 团体总分报表。二 实验内容 问题描述 参加运动会的n个学校编号...