《数据结构课程设计》指导书级Word文件下载.docx
《《数据结构课程设计》指导书级Word文件下载.docx》由会员分享，可在线阅读，更多相关《《数据结构课程设计》指导书级Word文件下载.docx（26页珍藏版）》请在冰点文库上搜索。
},{9,"
一号教学楼，主要以阶梯教室为主\n"
},{10,"
二号教学楼，小教室为多\n"
}};
/*景点名称和简介*/
操作：
/*给景点之间的路径赋最大值*/
/*最短路径的C语言函数*/
/*输出最短路径和最短距离函数*/
/*输入景点代码查景点名称和简介*/
/*输入景点代码查到其它景点的最短距离*/
2【员工管理系统】
每个员工的信息包括：
编号、姓名、性别、出生年月、学历、职务、电话、住址等。
系统能够完成员工信息的查询、更新、插入、删除、排序等功能。
排序：
按不同关键字，对所有员工的信息进行排序；
查询：
按特定条件查找员工；
更新，按编号对某个员工的某项信息进行修改；
插入，加入新员工的信息；
删除，按编号删除已离职的员工的信息。
实现图形用户界面。
通过链表实现
structworkers
charname[15];
//姓名
chardepartment[18];
//单位
chargender;
//性别
unsignedintage;
//年龄
unsignedlongtelephone;
//电话
unsignedlongwage;
//工资
unsignedlongnum;
//职工号
structworkers*next;
};
操作实现：
/*插入职工信息，通过链表实现*/
/*具体实现职工信息的插入*/
/*对职工信息的删除操作*/
/*修改操作*/
/*实现对员工信息的查找*/
/*排序*/
/*输出员工信息*/
/*显示职工工资情况计算平均工资*/
3【算术表达式求值】
一个算术表达式是由操作数（operand）、运算符（operator）和界限符（delimiter）组成的。
假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：
#（7+15）*（23-28/4）#。
引入表达式起始、结束符是为了方便。
编程利用“算符优先法”求算术表达式的值。
从键盘读入一个合法的算术表达式，输出正确的结果；
显示输入序列和栈的变化过程，操作数类型扩充到实数。
"
（3.14159/2+sqrt（1/3^2+4）+1/2^2*ln（1/1.1*（2+sqrt（1/3^2+4））））*23.45@"
;
扩充运算符集合；
引入变量操作数；
4【运动会分数统计】
任务：
参加运动会有n个学校，学校编号为1……n。
比赛分成m个男子项目，和w个女子项目。
项目编号为男子1……m，女子m+1……m+w。
不同的项目取前五名或前三名积分；
取前五名的积分分别为：
7、5、3、2、1，前三名的积分分别为：
5、3、2；
哪些取前五名或前三名由学生自己设定。
（m<
=20，n<
=20）
功能要求：
可以输入各个项目的前三名或前五名的成绩；
能统计各学校总分；
可以按学校编号、学校总分、男女团体总分排序输出；
可以按学校编号查询学校某个项目的情况；
可以按项目编号查询取得前三或前五名的学校。
规定：
输入数据形式和范围为20以内的整数（如果做得更好可以输入学校的名称，运动项目的名称）；
输出形式，有中文提示，各学校分数为整形；
界面要求，有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。
存储结构：
学生自己根据系统功能要求自己设计，请在最后的上交资料中指明你用到的存储结构。
参考的数据结构：
（1）项目信息表结构
typedefstructxm_table{
intitem;
//项目编号
charname[20];
//项目名称
intcount;
//该项目得分人的数量
}XM_TABLE;
（2）学生信息表结构
structSTUDENT{
//姓名
intscore;
//得分成绩
intrange;
//得分名次
//得分项目
intsex;
//性别
（3）参赛学校信息结构
//参赛学校
typedefstructSchoolStruct
//计算实际运动员个数
intserial;
//学校编号
charName[20];
//学校名称
intmenscore;
//男子团体总分
intwomenscore;
//女子团体总分
inttotalscore;
//团体总分
intjifeng;
//学校积分
struct
STUDENTstudents[10];
//参赛运动员
structSchoolStruct*next;
//下一个参赛学校
}SCHOOLSTRUCT;
操作需求：
//建立参赛学校链表
//添加获奖学生
//成绩统计
//按项目编号查询取得前三或前五名的学校。
//按学校编号查询学校某个项目
//在幕输出数据
//参数设置
（设置参赛学校数n>
=2，请输男生项目总数<
m<
=20，请输女生项目总数<
k<
//项目资料:
请输入男生项目信息：
项目名称;
项目编号;
该项目的参与人数
请输入女生项目信息：
//添加学生数据
intSchoolCount=0;
//学校总数
intboyCount=0;
//男生项目总数
intgirlCount=0;
//女生项目总数
intxm_Count=0;
//项目总数
XM_TABLExm_T[41];
//项目表
主要实现：
参数设置"
、"
添加学生"
统计"
、"
学校查询"
项目查询"
等功能。
5一元多项式计算
能够按照指数降序排列建立并输出多项式；
能够完成两个多项式的相加、相减和相乘，并将结果输出；
在上交资料中请写明：
存储结构、多项式相加的基本过程的算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；
设有一元多项式Am（x）和Bn（x）.
Am（x）=A0+A1x1+A2x2+A3x3+…+Amxm
Bn（x）=B0+B1x1+B2x2+B3x3+…+Bnxn
请实现求M（x）=Am（x）+Bn（x）、M（x）=Am（x）-Bn（x）和M（x）=Am（x）×
Bn（x）。
要求：
1）
首先判定多项式是否稀疏
2）
分别采用顺序和动态存储结构实现；
3）
结果M（x）中无重复阶项和无零系数项；
4）
要求输出结果的升幂和降幂两种排列情况
6订票系统
通过此系统可以实现如下功能：
录入：
可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）
可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）
可以输入起飞抵达城市，查询飞机航班情况；
订票：
（订票情况可以存在一个数据文件中，结构自己设定）
可以订票，如果该航班已经无票，可以提供相关可选择航班；
退票：
可退票，退票后修改相关数据文件；
客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。
修改航班信息：
当航班信息改变可以修改航班数据文件
根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能；
航班信息数据结构
typedefcharkeytype;
//航班信息结构
typedefstruct
{
charstart[6];
//起点站
charend[6];
//终点站
charsche[10];
//航班期
chartime1[5];
//起飞时间
chartime2[5];
//到达时间
charmodel[4];
//机型
intprice;
//票价
}infotype;
//定义航班节点
typedefstruct
keytypekeys[keylen];
//航班号
infotypeothers;
//航班信息
intnext;
//下一航班
}slnode;
//航班表
slnodesl[maxspace];
intkeynum;
intlength;
}sllist;
（1）录入航班信息：
（2）查询航班信息：
可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；
航班信息查询系统：
可以按：
1.航班号;
2.起点站；
3.终点站；
4.起飞时间;
5.到达时间;
以下选作：
（3）航班订票：
可以订票，如果该航班已经无票，可以提供相关可选择航班；
（4）航班退票：
客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。
（5）修改航班信息：
当航班信息改变可以修改航班数据文件
注：
因为航班号为两位字母后跟数字，所以在排序时应该使用多关键字的基数排序对航班号进行排序。
7迷宫问题求解
可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；
存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；
8文章编辑（不算数）
功能：
输入一页文字，程序可以统计出文字、数字、空格的个数。
静态存储一页文章，每行最多不超过80个字符，共N行；
要求
分别统计出其中英文字母数和空格数及整篇文章总字数；
统计某一字符串在文章中出现的次数，并输出该次数；
删除某一子串，并将后面的字符前移。
存储结构使用线性表，分别用几个子函数实现相应的功能；
输入数据的形式和范围：
可以输入大写、小写的英文字母、任何数字及标点符号。
输出形式：
分行输出用户输入的各行字符；
分4行输出"
全部字母数"
数字个数"
空格个数"
文章总字数"
；
输出删除某一字符串后的文章；
9joseph环（不算数）
编号是1，2，……，n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。
一开始任选一个正整数作为报数上限值m，从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。
报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。
设计一个程序来求出出列顺序。
利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。
测试数据：
m的初值为20，n=7，7个人的密码依次为3，1，7，2，4，7，4，首先m=6，则正确的输出是什么？
输入数据：
建立输入处理输入数据，输入m的初值，n，输入每个人的密码，建立单循环链表。
建立一个输出函数，将正确的输出序列
typedefstructNode
intdata;
intpassword;
structNode*next;
}Node,*LinkList;
基本操作：
//初始化单链表
//给每个人赋密码
//确定需要处理的人数
//确定开始的上限值
//得到正确的顺序
//输出结果
10猴子选大王（不算数）
一堆猴子都有编号，编号是1，2，3，...，m，这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。
输入m，nm，n为整数，n<
m
中文提示按照m个猴子，数n个数的方法，输出为大王的猴子是几号，建立一个函数来实现此功能。
（10、11二者任选其一）
11已知二叉树的层序和中序遍历序列，或已知二叉树的先序序列、中序序列，是编写算法建立该二叉树（用递归或非递归的方法都可以）
要求能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列；
分别建立建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数；
12【哈夫曼编/译码器】
建立最优二叉树函数
可以建立函数输入二叉树，并输出其赫夫曼树。
存储结构、基本算法（可以使用程序流程图）、输入输出、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；
利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。
但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。
对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。
试为这样的信息收发站写一个哈夫曼码的编/译码系统。
[基本要求]
一个完整的系统应具有以下功能：
（1）I：
初始化（Initialization）。
从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。
（2）E：
编码（Encoding）。
利用已建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。
（3）D：
译码（Decoding）。
利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。
（4）P：
印代码文件（Print）。
将文件CodeFile以紧凑格式显示在终端上，每行50个代码。
同时将此字符形式的编码文件写入文件CodePrin中。
（5）T：
印哈夫曼树（Treeprinting）。
将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。
[测试数据]
（1）利用下面这道题中的数据调试程序。
某系统在通信联络中只可能出现八种字符，其概率分别为0.25，0.29，0.07，0.08，0.14，0.23，0.03，0.11，试设计哈夫曼编码。
（2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：
“THISPROGRAMISMYFAVORITE”。
字符空格
A
B
C
D
E
F
G
H
I
J
K
L
M
频度186
64
13
22
32103
21
15
47
57
1
5
32
20
字符
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
频度
63
48
51
80
23
8
18
16
1
[实现提示]
（1）编码结果以文本方式存储在文件CodeFile中。
（2）用户界面可以设计为“菜单”方式：
显示上述功能符号，再加上“Q”，表示退出运行Quit。
请用户键入一个选择功能符。
此功能执行完毕后再显示此菜单，直至某次用户选择了“Q”为止。
（3）在程序的一次执行过程中，第一次执行I，D或C命令之后，哈夫曼树已经在内存了，不必再读入。
每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。
13纸牌游戏（不算数）
编号为1-52张牌，正面向上，从第2张开始，以2为基数，是2的倍数的牌翻一次，直到最后一张牌；
然后，从第3张开始，以3为基数，是3的倍数的牌翻一次，直到最后一张牌；
然后从第4张开始，以4为基数，是4的倍数的牌翻一次，直到最后一张牌；
再依次5的倍数的牌翻一次，的，7的直到以52为基数的翻过，输出这时正面向上的牌有哪些？
14【拓扑排序】
编写函数实现图的拓扑排序。
15【学生成绩管理】
实现功能：
输入、输出、插入、删除、查找、追加、读入、显示、保存、拷贝、排序、索引、分类合计、退出。
能实现对学生信息的简单管理。
具体要求：
建立一个4个学生的信息登记表，每个学生的信息包括：
学号，姓名，和3门课程的成绩（FOX,C,ENGLISH）。
程序运行时显示一个简单的菜单，例如：
（1）：
信息输入（INPUT）
（2）：
总分统计（COUNT）
（3）：
总分排序（SORT）
（4）：
查询（QUERY）
其中：
对4个学生的信息进行输入；
对每个学生的3门课程统计总分；
对4个学生的总分按降序排序并显示出来；
查询输入一个学号后，显示出该学生的有关信息；
structstudent
//学号
charname[20];
intfoxscore;
//fox成绩
intcscore;
//C语言
intenglishscore;
//英语成绩
structstudent*next;
1.成绩信息输入;
2.统计总分;
3.排序;
4.查询
16【停车场管理】
设停车场（如下图所示）内只有一个可停放几量汽车的狭长通道，且只有一个大门可供汽车进出。
汽车在停车场内按车辆到达时的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已经停满几量汽车，则后来的汽车只能在门外的便道上等候，一旦停车场内有车开走，则排在便道上的第一辆汽车即可开入；
当停车场内某车辆要离开时，由于停车场是狭长的通道，在它之后开入车场的车辆必须先退出车场为它让路，待该车辆开出大门外后，为它让路的车辆再按原次序进入车场。
在这里假设汽车不能从便道上开走。
试设计一个停车场管理程序（这里只是一个假想的停车场管理，并不代表实际的停车场管理）。
停
车
场
大门
北
图停车场示意图
分析：
汽车在停车场内进出是按照栈的运算方式来实现的，先到的先进停车场；
停车场的汽车离开停车场时，汽车场内其它汽车为该辆汽车让路，也是按栈的方式进行；
汽车在便道上等候是按队列的方式进行的。
因此，将停车场设计成一个栈，汽车让路也需要另一个栈来协助完成，汽车进出便道用队列来实现。
本设计，栈采用顺序栈结构，队列用链式存储结构。
存储结构定义如下：
#definestacksize10
typedefstructsqstack
{
intdata[stacksize];
inttop;
}SqStackTp;
typedefstructlinked_queue
intdata;
structlinked_queue*next;
}LqueueTp;
LqueueTp*front,*rear;
}QueptrTp;
停车场管理的算法描述如下：
1）接受命令和车号，若是汽车要进停车场，先判断停车场栈是否满，若不满，则汽车入栈，否则汽车进入便道队列等候。
2）若是汽车要离开停车场，为给汽车让路，将停车场栈上若干辆汽车入临时栈，等这辆车出停车场后，临时栈中的汽车出栈，在回到停车场栈，然后看便道队列是否为空，若不空则说明有汽车等候，从队头取出汽车号，让该车进入停车场栈。
3）重复1），2）直到为退出命令（车号为0或负数）。
17【二叉排序树与文件操作】
（1）从键盘输入一组学生记录建立二叉排序树；
（2）二叉排序树存盘；
（3）由文件恢复内存的二叉排序树；
（4）中序遍历二叉排序树；
（5）求二叉排序树深度；
（6）求二叉排序树的所有节点数和叶子节点数；
（7）向二叉排序树插入一条学生记录；
（8）从二叉排序树中删除一条学生记录；
（9）从二叉排序树中查询一条学生记录；
（10）以广义表的形式输出二叉排序树
//定义学生记录类型
Structstudent{
Charnum[6];
Intgrade;
//成绩
//定义二叉排序树节点值的类型为学生记录类型
typedefstudentElemType;
升级会员 