数据结构课程设计题目及要求样本.doc

资料内容仅供您学习参考，如有不当之处，请联系改正或者删除。
《数据结构》课程设计
目录
一、课程设计要求 2
1. 分组设计 2
2. 题目选择 2
3. 考核标准 2
4. 提交材料 2
5. 考核等级 2
二、课程设计报告（见附件2） 2
三、课程设计题目： 2
（一）课程设计1 2
1. joseph环 2
2. 文章编辑 3
3. 学生成绩管理系统 3
4. 一元稀疏多项式计算器 4
5. 表达式求值 4
6.运动会分数统计 4
7.宿舍管理查询软件 5
8.校园导游咨询 5
9.哈夫曼编/译码器 6
10.建立通信网络 7
11. 考试报名管理 7
12. 停车场管理 7
项目简介 7
13.图书管理信息系统的设计与实现。 7
附件1：分组登记表 9
附件2：实训报告

一、 课程设计要求
1. 分组设计
按小组方式进行组织设计, 小组成员为3~4人, 班级内自由组合, 并确定小组组长, 分组名单汇总到曹钿鹏和韩滨龙, 最后交给老师。
2. 题目选择
每个小组选择1个题目设计完成, 组与组之间题目能够相同可是方法不同, 并完成实训报告。
3. 考核标准
总的要求: 组内每位同学, 一起协商承担的任务, 每人都要参与设计和编程工作。
评分组成:
1) 组长对组内成员学习态度和承担设计任务的评价;
2) 课程设计完成的效果, 必要时会采用现场演示和答辩的方式;
3) 课程设计实训报告的撰写质量;
4. 提交材料
每位同学依据所在小组选择的课程设计题, 独立撰写课程设计实训报告, 不允许相互间抄袭, 否则均以零分计算。
提交材料: 课程设计报告, 程序代码: ( 建议按如下形式打包)
文件夹以”组号.rar”提交, 里面每位同学包含两个文件夹: ”实训报告”和”源代码”。”实训报告”文件夹中是本组成员的实训报告。
备注: 小组长将本组得设计报告收齐, 以组为单位打包交给曹钿鹏和韩滨龙, 两人最后汇总提交到邮箱: 。
5. 考核等级
评分标准: 等级制( 优秀、 良好、 中等、 及格、 不及格)
二、 课程设计报告( 见附件2)
三、 课程设计题目:
( 一) 课程设计1
1. joseph环
【问题描述】
编号是1, 2, ……,n的n个人按照顺时针方向围坐一圈, 每个人只有一个密码( 正整数) 。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数, 报到m时停止报数。报m的人出列, 将她的密码作为新的m值, 从她在顺时针方向的下一个人开始重新从1报数, 如此下去, 直到所有人全部出列为止。设计一个程序来求出出列顺序。
【要求】
利用单向循环链表存储结构模拟此过程, 按照出列的顺序输出各个人的编号。
【测试数据】
m的初值为20, n=7 ,7个人的密码依次为3, 1, 7, 2, 4, 7, 4, 首先m=6,( 正确的出列顺序应为6,1,4,7,2,3,5) 。
【实现提示】
程序运行后, 首先要求用户指定初始报数上限值, 然后读取各人的密码。可设n≤30。此题所用的循环链表中不需要”头结点”, 请注意空表和非空表的界限。
2. 文章编辑
【问题描述】
输入一页文字, 程序能够统计出文字、 数字、 空格的个数。静态存储一页文章, 每行最多不超过80个字符, 共N行。
【要求】
( 1) 分别统计出其中英文字母数和空格数及整篇文章总字数;
( 2) 统计某一字符串在文章中出现的次数, 并输出该次数;
( 3) 删除某一子串, 并将后面的字符前移。
【存储结构】
使用线性表, 分别用几个子函数实现相应的功能;
【输入数据的形式和范围】
能够输入大写、 小写的英文字母、 任何数字及标点符号。
【输出形式】
( 1) 分行输出用户输入的各行字符;
( 2) 分4行输出"全部字母数"、 "数字个数"、 "空格个数"、 "文章总字数"
( 3) 输出删除某一字符串后的文章。
3. 学生成绩管理系统
【问题描述】
学生信息包括: 学号、 姓名、 性别、 四门课成绩,
主要功能如下:
主菜单= = = = = = = = = = = = = = = =
1. 输入学生信息
2. 按姓名查询学生信息
3. 按学号查找学生信息
4. 按姓名排序
5. 按学号排序
6. 按总成绩排序
7. 打印学生信息
= = = = = = = = = = = = = = = =
请选择( 0~4)
如果选择1, 则显示”请输入学生姓名、 学号、 成绩”, 并能输入; 选择2, 能够按照姓名查找该学生的各科成绩和平均分; 选择3, 能够按照学号查找该学生的各科成绩和平均分, 选择4, 能够显示按姓名排序结果; 选择5, 能够显示按学号排序结果; 选择6, 能够显示按成绩排序结果; 选择7, 能够按照学号输出学生姓名, 学号, 成绩; 选择0, 显示”谢谢使用”; 选择其它则显示”输入错误, 请重新输入) 。
4. 一元稀疏多项式计算器
【问题描述】
设计一个一元稀疏多项式简单计算器。
【基本要求】
一元多项式简单计算器的基本功能是:
( 1) 输入并建立多项式;
( 2) 输出多项式, 输出形式为整数序列n,c1,e1,c2,e2,…,cn,en, 其中n是多项式的项数, ci和ei分别是第i项的系数和指数, 序列指指数降序排列;
( 3) 多项式a和b相加, 建立多项式a+b;
( 4) 多项式a和b相减, 建立多项式a-b。
【实现提示】
用带头结点的单链表存储多项式, 多项式的项数存在头结点。

5. 表示式求值
【问题描述】
表示式求值是实现程序设计语言的基本问题之一, 也是栈的应用的一个典型例子。设计一个程序, 演示用算符优先法对算术表示式求值的过程。
【基本要求】
以字符序列的形式从终端上输入语法正确的、 不含变量的整数表示式。利用教材中给出的算符优先关系, 实现对算术四则混合运算表示式的求值, 并仿照教材例3-1演示在求值中运算符栈、 运算数栈、 输入字符和主要操作的变化过程。
【实现提示】
( 1) 设置运算栈和运算数栈辅助分析算符优先关系。
( 2) 在输入表示式的字符序列的同时, 完成运算符和运算数( 整数) 的识别处理, 以及相应的运算。
（3） 在识别出运算数的同时, 要将其字符序列形式转换成整数形式。

6.运动会分数统计
【问题描述】参加运动会有n个学校, 学校编号为1~n。比赛分成m个男子项目和w个女子项目。项目编号为男子1~m和女子m+1~m+w。不同的项目取前五名或前三名积分; 取前五名的积分分别为: 7、 5、 3、 2、 1, 前三名的积分分别为: 5、 3、 2; 哪些取前五名或前三名由学生自己设定。( m<=20,n<=20)
【功能要求】
( 1) 能够输入各个项目的前三名或前五名的成绩;
( 2) 能统计各学校总分,
( 3) 能够按学校编号、 学校总分、 男女团体总分排序输出;
( 4) 能够按学校编号查询学校某个项目的情况; 能够按项目编号查询取得前三或前五名的学校。
【规定】
输入数据形式和范围: 20以内的整数( 如果做得更好能够输入学校的名称, 运动项目的名称)
【输出形式】
有中文提示, 各学校分数为整形
【界面要求】
有合理的提示, 每个功能能够设立菜单, 根据提示, 能够完成相关的功能要求。
【存储结构】
学生自己根据系统功能要求自己设计, 可是要求运动会的相关数据要存储在数据文件中。( 数据文件的数据读写方法等相关内容在c语言程序设计的书上, 请自学解决) 请在最后的上交资料中指明你用到的存储结构;
【测试数据】
要求使用1、 全部合法数据; 2、 整体非法数据; 3、 局部非法数据。进行程序测试, 以保证程序的稳定。测试数据及测试结果请在上交的资料中写明。
7.宿舍管理查询软件
【问题描述】
为宿舍管理人员编写一个宿舍管理查询软件。
【基本要求】
( 1) 采用交互工作方式;
( 2) 建立数据文件 , 数据文件按关键字( 姓名、 学号、 房号) 进行排序(冒泡、 选择、 插入排序等任选一种)。
( 3) 建立查询菜单: (用二分查找实现以下操作)
按姓名查询
按学号查询
按房号查询
打印任一查询结果( 能够连续操作)
8.校园导游咨询
【问题描述】
设计一个校园导游程序, 为来访的客人提供各种信息查询服务。
【基本要求】
( 1) 设计你的学校的校园平面图, 所含景点不少于10个。以图中顶点表示学校各景点, 存放景点名称、 代号、 简介等信息; 以边表示路径, 存放路径长度等相关信息。
( 2) 为来访客人提供图中任意景点的问路查询, 即查询任意两个景点之间的一条最短的简单路径。
( 3) 为来访客人提供图中任意景点相关信息的查询。
【测试数据】
由读者根据实际情况指定。
【实现提示】
一般情况下, 校园的道路是双向通行的, 可设校园平面图是一个无向网。顶点和边均含有相关信息。
9.哈夫曼编/译码器
【问题描述】
用哈夫曼编码进行通信能够大大提高信道利用率, 缩短信息传输时间, 降低传输成本。可是, 这要求在发送端经过一个编码系统对待传数据预先编码, 在接收端将传 来的数据进行译码( 复原) 。对于双工信道( 即能够双向传输信息的信道) , 每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。
【基本要求】
一个完整的系统应具有以下功能:
( 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: 印哈夫曼树( Tree printing) 。将已在内存中的哈夫曼树以直观的方式( 树或凹入表形式) 显示出, 同时将此字符形式的哈夫曼树写入文件TreePrint中。
【测试数据】
（1） 利用教科书例6-2中的数据调试程序。
（2） 用下表给出的字符集和频度的实际统计数据建立哈夫曼树, 并实现以下报文的编码和译码: ”THIS PROGRAM IS MY FAVORITE”。
字符
A
B
C
D
E
F
G
H
I
J
K
L
M
频度
64
13
22
32
103
21
15
47
57
1
5
32
20
字符
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
频度
57
63
15
1
48
51
80
23
8
18
1
16
1

【实现提示】
( 1) 编码结果以文本方式存储在文件CodeFile中。
( 2) 用户界面能够设计为”菜单”方式: 显示上述功能符号, 再加上”Q”表示退出运行Quit。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单, 直至某次用户选择了”Q”为止。
( 3) 在程序的一次执行过程中, 第一次执行I、 D或C命令之后, 哈夫曼树已经在内存了, 不必再读入。每次执行中不一定执行I命令, 因为文件hfmTree可能早已建好。
10.建立通信网络
【问题描述】
在n个城市建设通信网络, 只需架设n-1条线路即可。设计一个程序, 求出如何以最低的经济代价建设这个通信网。( 该问题为最小生成树问题)
【基本要求】
( 1) 利用图作为存储结构;
( 2) 键盘输入问题规模n和各条线路的权值;
( 3) 输出生成树中各条边以及她们的权值。
11. 考试报名管理
【问题描述】
考试报名工作给各高校报名工作带来了新的挑战, 给教务管理部门增加了很大的工作量, 报名数据手工录入既费时又会不可避免地出现错误, 同时也给不少学生以可乘之机。本项目是对考试报名管理的简单模拟, 用菜单选择方式完成下列功能: 输入考生信息; 输出考生信息; 查询考生信息; 添加考生信息; 修改考生信息; 删除考生信息。
12. 停车场管理
项目简介
设停车场是一个能够停放n辆汽车的南北方向的狭长通道, 且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序, 依次由北向南排列( 大门在最南端, 最先到达的第一辆车停放在车场的最北端) , 若车场内已停满n辆车, 那么后来的车只能在门外的便道上等候, 一旦有车开走, 则排在便道上的第一辆车即可开入; 当停车场内某辆车要离开时, 在它之后进入的车辆必须先退出车场为它让路, 待该辆车开出大门外, 其它车辆再按原次序进入车场, 每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。要求程序输出每辆车到达后的停车位置( 停车场或便道上) , 以及某辆车离开停车场时应缴纳的费用和它在停车场内停留的时间。
13.图书管理信息系统的设计与实现。
图书管理一般包括: 图书采编、 图书编目、 图书查询及图书流通( 借、 还书) 等, 请编程实现上述功能。具体设计要求:  ( 1) 设计图书管理的存储结构, 输入若干种书的记录。 ( 2) 实现关于书号、 书名、 作者及出版社的图书查询;  
( 3) 实现图书的借还子系统, 包括建立读者文件、 借还书文件、 读者管理及图书借还等相关处理。

附件1: 分组登记表
组号
组长
组长联系电话
组员学号
组员姓名
分工
1

2

3

4

5

6

7

8

附件2:

山东协和学院
课 程 设 计

课程名称

题 目

专 业

班 级

姓 名

指导教师

年

月

日

一、 课程设计目的

二、 课程设计内容与要求、 环境

三、 课程设计基本思想
( 包括选择什么数据结构? 数据结构采用哪种存储方式? 选择的原因? 设计哪些操作? 这些操作之间的调用关系等等)

四、 详细设计
( 包括数据结构的类型定义, 每个操作的算法描述)

五、 源程序

六、 运行结果

七、 设计心得

八、 参考资料

本科生课程设计成绩评定表
班级: 姓名: 学号:
序号
评分项目
满分
实得分
1
学习态度认真、 遵守纪律
10

2
设计分析合理性
10

3
设计方案正确性、 可行性、 创造性
20

4
设计结果正确性
40

5
设计报告的规范性
10

6
设计验收
10

总得分/等级

评语:

注: 最终成绩以五级分制记。优( 90-100分) 、 良( 80-89分) 、 中( 70-79分) 、
及格( 60-69分) 、 60分以下为不及格

指导教师签名:
年 月 日