数据结构专业课程设计题目及要求.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，……,nn个人按照顺时针方向围坐一圈，每个人只有一种密码（正整数）。一开始任选一种正整数作为报数上限值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分如下为不及格

指引教师签名：
年 月 日