《数据结构》课程设计
目录
一、课程设计要求 ........................................................................................................................... 2
1. 分组设计 ........................................................................................................................... 2 2. 题目选择 ........................................................................................................................... 2 3. 考核标准 ........................................................................................................................... 2 4. 提交材料 ........................................................................................................................... 2 5. 考核等级 ........................................................................................................................... 2 6. 时间安排 ........................................................................................................................... 2 二、课程设计报告的书写内容（仅供参考） ............................................................................... 3 三、课程设计题目： ....................................................................................................................... 3
（一）课程设计1 .................................................................................................................... 3
1. joseph环 ................................................................................................................... 3 2. 文章编辑 ................................................................................................................... 3 3. 学生搭配问题 ........................................................................................................... 4 4. 一元稀疏多项式计算器 ........................................................................................... 4 5. 表达式求值 ............................................................................................................... 4 （二）课程设计2 .................................................................................................................... 5
1. 集合基本运算 ........................................................................................................... 5 2. 运动会分数统计 ....................................................................................................... 5 3. 内部排序算法比较 ................................................................................................... 6 4. 宿舍管理查询软件 ................................................................................................... 6 （三）课程设计3 .................................................................................................................... 7
1. 校园导游咨询 ........................................................................................................... 7 2. 哈夫曼编/译码器 ..................................................................................................... 7 3. 散列法的实验研究 ................................................................................................... 8 4. 建立通信网络 ........................................................................................................... 8
附件1：封面格式 ............................................................................................................................ 9 附件2：分组登记表 ...................................................................................................................... 10
1
一、课程设计要求
1. 分组设计
按小组方式进行组织设计，小组成员为4~5人，班级内自由组合，并确定小组组长，分组名单汇总到各班班长，最后交给老师。 2. 题目选择
每个小组至少选择3个题目，其中：在课程设计1中任选1道题，在课程设计2选1道题，在课程设计3中选1道题。 3. 考核标准 总的要求：组内每位同学，一起协商承担的任务，每人都要参与设计和编程工作，不能只负责撰写论文。 评分组成： 1）组长对组内成员学习态度和承担设计任务的评价；
2）课程设计完成的效果，必要时会采用现场演示和答辩的方式； 3）课程设计报告的撰写质量； 4. 提交材料 每位同学依据所在小组选择的课程设计题，独立撰写课程设计报告，分题目依次撰写。不允许相互间抄袭，否则均以零分计算。
备注：如果是合作完成一个题目的，除了选择的数据结构一样以为，算法部分每个人只写自己完成的那部分，绝对不允许交上来的论文一模一样！。
提交材料：纸质的课程设计报告，程序代码：（建议按如下形式打包）
备注：以组为单位打包提交。
5. 考核等级
评分标准：等级制（优秀、良好、中等、及格、不及格） 6. 时间安排 1) 布置设计任务：11月13号，发到公共邮箱pspublicmail@163.com，密码：ggyx2013 2) 提交分组名单：布置设计任务后一周内，班长汇总后将分组结果及分组任务表交给老师； 3）设计与撰写：上机时间为课内的上机时间和课外自己找时间完成。 4）提交截止日期：第16周周三
2
二、课程设计报告的书写内容（仅供参考）
1、题目的内容及要求 2、需求分析
3、概要设计（包括选择什么数据结构？数据结构采用哪种存储方式？选择的原因？设计哪些操作？这些操作之间的调用关系等等）
4、详细设计（包括数据结构的类型定义，每个操作的算法描述） 5、源代码
6、运行结果及分析 7、收获及体会
三、课程设计题目：
（一）课程设计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）分别统计出其中英文字母数和空格数及整篇文章总字数；
3
（2）统计某一字符串在文章中出现的次数，并输出该次数； （3）删除某一子串，并将后面的字符前移。 【存储结构】
使用线性表，分别用几个子函数实现相应的功能； 【输入数据的形式和范围】
可以输入大写、小写的英文字母、任何数字及标点符号。 【输出形式】
（1）分行输出用户输入的各行字符；
（2）分4行输出\全部字母数\、\数字个数\、\空格个数\、\文章总字数\（3）输出删除某一字符串后的文章。
3. 学生搭配问题
【问题描述】
一班有m个女生，有n个男生(m不等于n)，现要开一个舞会。男女生分别编号坐在舞池的两边的椅子上，每曲开始时，依次从男生和女生中各出一人配对跳舞，本曲没成功配对者坐着等待下一曲找舞伴。请设计一系统模拟动态地显示出上述过程。 【基本要求】
（1）输出每曲配对情况 （2）计算出任何一个男生(编号为X)和任意女生(编号为Y)，在第K曲配对跳舞的情况。至少求出K的两个值。 【提示】
用队列来解决比较方便.
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. 表达式求值
【问题描述】
表达式求值是实现程序设计语言的基本问题之一，也是栈的应用的一个典型例子。设
4
计一个程序，演示用算符优先法对算术表达式求值的过程。 【基本要求】
以字符序列的形式从终端上输入语法正确的、不含变量的整数表达式。利用教材中给出的算符优先关系，实现对算术四则混合运算表达式的求值，并仿照教材例3-1演示在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。 【实现提示】
（1）设置运算栈和运算数栈辅助分析算符优先关系。
（2）在输入表达式的字符序列的同时，完成运算符和运算数（整数）的识别处理，以及相应的运算。
（3）在识别出运算数的同时，要将其字符序列形式转换成整数形式。
（二）课程设计2
1. 集合基本运算
【问题描述】
编制一个能演示执行集合的并、交和差运算的程序。允许采用顺序存储或链式存储来实现。
【基本要求】
（1） 集合的元素限定为小写字符[‘a’. .’z’]。 （2） 演示程序以用户和计算机的对话方式执行。 【测试数据】
（1） Set1=”magazine”,Set2=”paper”.
Set1∪Set2=”aegimnprz”,Set1∩Set2=”ae”,Set1-Set2=”gimnz”. (2) Set1=”012oper4a6tion89”,Set2=”error data”,
Set1∪Set2=”adeinoprt”, Set1∩Set2=”aeort”, Set1-Set2=”inp”. 【实现提示】
以有序链表表示集合。
2. 运动会分数统计
【问题描述】参加运动会有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）可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。 【规定】
5