《数据结构》课程设计任务书
一、 设计题目
1、约瑟夫环
2、集合的并、交和差运算 3、一元稀疏多项式计算器 4、停车场管理 5、车厢调度 6、文学研究助手 7、哈夫曼编/译码器 8、图遍历的演示 9、最小生成树问题 10、哈希表设计
二、 设计目的
数据结构课程设计是计算机专业的集中实践性环节之一，是学习完《数据结构》课程后进行的一次全面的综合练习。其目的在于加深对数据结构的理解和掌握，使学生更好地掌握数据结构的特点、存储表示、运算方法及其应用，训练学生选用合适的数据结构编写质量高、风格好的应用程序的能力。
三、 设计任务
每班每人按照学号的顺序依次选择1-10号设计题目，独立完成课题。（即1、11、21号学生完成1号课题，2、12、22号学生完成2号题，以此类推）
四、时间安排
课程名称 班级 周次 星期 节次 1 1 1 1 时间 实验室 数据结构课设 计算机类1103 数据结构课设 计算机类1104 数据结构课设 计算机类1105 数据结构课设 计算机类1106
全周 上午 2012.9.3-2012.9.7 全周 上午 2012.9.3-2012.9.7 全周 下午 2012.9.3-2012.9.7 全周 下午 2012.9.3-2012.9.7 五、 设计内容
1. 约瑟夫环
【问题描述】
约瑟夫 (Joseph) 问题的一种描述是：编号为 1，2，… ，n 的n个人按顺时针方向围坐一 圈，每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 【基本要求】 利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 【测试数据】 m 的初值为 20；n=7，7 个人的密码依次为：3，1，7，2，4，8，4， 首先 m 值为 6( 正确的出列顺序应为 6，1，4，7，2，3，5) 。 【实现提示】
程序运行后，首先要求用户指定初始报数上限值，然后读取各人的密码。可设n≤30。 此题所用的循环链表中不需要 “头结点”，请注意空表和非空表的界限。
【选作内容】
向上述程序中添加在顺序结构上实现的部分。
2. 集合的并、交和差运算 【问题描述】 编制一个能演示执行集合的并、交和差运算的程序。 【基本要求】 (1) 集合的元素限定为小写字母字符 [?a?..?z?] 。 (2) 演示程序以用户和计算机的对话方式执行。 【测试数据】 (1)Set1=\，Set2=\， Set1∪Set2=\，Setl ∩Set2=\，Set1-Set2=\。
(2)Set1= \，Set2=\， Set1∪Set2=\，Setl ∩Set2=\，Set1-Set2=\。 【实现提示】 以有序链表表示集合。 【选作内容】
(1) 集合的元素判定和子集判定运算。 (2) 求集合的补集。
3. 一元稀疏多项式计算器
【问题描述】
设计一个一元稀疏多项式简单计算器。 【基本要求】
一元稀疏多项式简单计算器的基本功能是： (1) 输入并建立多项式 ；
(2) 输出多项式，输出形式为整数序列：n，cl，el，c2，e2，…，cn，en，其中n是多项式的项数，ci 和ei，分别是第 i 项的系数和指数，序列按指数降序排列；
(3) 多项式a和b相加，建立多项式a +b； (4) 多项式a和b相减，建立多项式a -b 。 【测试数据】
(1)(2x+5x8－3.1x11) + (7－5x8+11x9)=(－3.lx11+11x9+2x+7)
(2)(6x-3－x+4.4x2－1.2x9) －(-6x-3+5.4x2－x2+7.8x15)=(-7.8x15-1.2x9+12x-3-x) (3)(1 +x + x2+x3+x4+x5)+(-x3－x4)=(1+x+x2+x5) (4)(x+x3)+(-x－x3)=0
(5)(x+x100)+(x100 +x200)=(x+2x100+x200) (6)(x+x2+x3)+0=x+x2+x3
(7) 互换上述测试数据中的前后两个多项式 【实现提示】
用带表头结点的单链表存储多项式。 【选作内容】
(1) 计算多项式在x处的值。 (2) 求多项式 a 的导函数a? 。
(3) 多项式a和b相乘，建立乘积多项式ab。 (4) 多项式的输出形式为类数学表达式。例如,多项式 -3x8+6x3－18 的输出
????形式为?3x8?6x3?18，x15+(－8)x7－14的输出形式为x15?8x7?14。注意，数值为1的非零次项的输出形式中略去系数1，如项1x8的输出形式为x8，项 －1x3的输出形式为－x3。
4. 停车场管理 【问题描述】
设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列(大门在最南端，最先到达的第一辆车停放在车场的最北端)，若车场内己停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开人；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让
路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。 【基本要求】
以桟模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用(在便道上停留的时间不收费)。钱以顺序结构实现，队列以链表结构实现。 【测试】
设n=2,输入数据为：(?A?,1,5), (?A?,2,10), (?D?,1,15), (?A?,3,20), (?A?,4,25), (?A?,5,30), (?D?,2,35), (?D?,4,40), (?E?,0,0)。其中，?A?表示到达(Arrival)；?D?表示离去(Departure)；?E?表示输入结束(End)。 【实现提示】
需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。
5. 车厢调度 【问题描述】
假设停在铁路调度站入口处的车厢序列编号依次为1，2，3，??，n。设计一个程序求出所有可能由此输出的长度为n的车厢序列。 【基本要求】
首先在教科书3.1.2节中提供的栈的顺序存储结构SqStack之上实现栈的基本操作，即实现栈类型。程序对栈的任何存取（即更改，读取和状态判别等操作）必须借助于基本操作进行。 【测试数据】
分别取n=1,2,3,4 【实现提示】
一般的说，在操作过程的任何状态下都有两种可能的操作：“入”和“出”。每个状态下处理问题的方法都是相同的，这说明问题本身具有天然的递归特性，可以考虑用递归算法实现。输入序列可以仅由一对整型变量表示，即给出序列头/尾编号。输出序列用栈实现是方便的。
6. 文学研究助手 【问题描述】
文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。试写一个实现这一目标的文字统计系统,称为\文学研究助手\。 【基本要求】
英文小说存于一个文本文件中。待统计的词汇集合要一次输入完毕,即统计工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和出现位置所在行的行号,格式自行设计。 【测试数据】
以你的C源程序模拟英文小说,C语言的保留字集作为待统计的词汇集。 【实现提示】
约定小说中的词汇一律不跨行。这样,每读入一行,就统计每个词在这行中的出现次数。出现位置所在行的行号可以用链表存储。若某行中出现了不止一次,不必存多个相同的行号。
如果读者希望达到选做部分(1)和(2)所提出的要求,则首先应把KMP算法改写成如下的等价形式,再将它推广到多个模式的情形。
i=1;j=1;
while(i!=s.curlen+1&&j!=t.curlerl十1) {
while(j!=0&&s.ch[i]!=t.ch[j])
j=next[j]; //j==O或s.ch[i]==t.ch[j] j++;i++;//每次进入循环体,i只增加一次 }
【选作内容】
(1)模式匹配要基于KMP算法。
(2)整个统计过程中只对小说文字扫描一遍以提高效率。
7. 哈夫曼编/译码器 【问题描述】
利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息的信道)，每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。 【基本要求】
该系统应具有以下功能：
(1)I：初始化(Initialization)。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树。
(2)E：编码(Encoding)。利用已建好的哈夫曼树，对输入的报文（字符串）进行编码，然后输出编码结果。
(3)D：译码(Decoding)。利用已建好的哈夫曼树对输入的密文进行译码，输出结果。
(4)T：打印哈夫曼树(Tree printing)。将已在内存中的哈夫曼树以直观的方式(树或凹入表形式)显示在终端上。 【测试数据】
可以选用下表给出的字符集和频度的实际统计数据建立哈夫曼树 , 并实现报文的编码和译码。如，对报文\进行编码。 字符 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) 将各字符的哈夫曼编码写入文件Code中；