《数据结构》课程设计任务书
一、设计目的
《数据结构》是一门实践性较强的软件基础课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。 二、设计要求
1．通过这次设计，要求在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。 2．学生必须仔细研读《数据结构》课程设计要求，以学生自学为主、指导教师指导为辅，认真、独立地完成课程设计的任务，有问题及时主动与指导教师沟通。
3．本次课程设计按照教学要求需要在一周时间内独立完成，学生要发挥自主学习的能力，充分利用时间，安排好课程设计的时间计划，并在课程设计过程中不断检测自己的计划完成情况，及时地向指导教师汇报。
4．编程语言任选。 三、设计选题
选题说明：前面6个为基础题（必选一题，可达60分），后面题目*越多难度越大，根据实际选做题目的难度和数量以及实现程序的完善性可以适当加减分；同学们在选题时，要结合个人实际情况，确保及格，力争多做。 1．集合的并、交和差运算
任务：编制一个能演示执行集合的并、交和差运算的程序。 要求：
(1) 集合的元素限定为小写字母字符 [‘a’..’z’] 。 (2) 演示程序以用户和计算机的对话方式执行。 实现提示：以链表表示集合。 选作内容：
(1) 集合的元素判定和子集判定运算。 (2) 求集合的补集。
(3) 集合的混合运算表达式求值。
(4) 集合的元素类型推广到其他类型 ， 甚至任意类型。 2.停车场管理
任务：设停车场是一个可以停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次有北向南排列（大门在最南端，最先到达的第一车停放在车场的最北端），若车场内已停满n辆车，那么后来的车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。
要求：以栈模拟停车场，以队列模拟车场外的便道。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停车不收费）。栈以顺序存储结构实现，队列以链表结构实现。
3.哈夫曼码的编/译码系统
【问题描述】利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。
【基本要求】一个完整的系统应具有以下功能：
(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)利用下面这道题中的数据调试程序。某系统在通信联络中只可能出现八种字符，其概率分别为0.25，0.29，0.07，0.08，0.14，0.23，0.03，0.11，试设计哈夫曼编码。
(2)用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”。 字符 空格 A B C D E F G H I J K L M
频度 186 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或E命令之后，哈夫曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。 4.校园导游咨询
任务：设计一个校园导游程序，为来访的客人提供各种信息查询服务。 要求：
(1)设计学校的校园平面图，所含景点不少于10个，以图中顶点表示校内各
景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。
(2)为来访客人提供图中任意景点相关信息的查询。
(3)为来访客人提供景点的问路查询，即已知一个景点，查询到某景点之间的一条最短路径及长度。 5.散列表的设计与实现
任务：设计散列表实现电话号码查找系统。 要求：
(1) 设每个记录有下列数据项：用户名、电话号码、地址；
(2) 从键盘输入各记录，以用户名（汉语拼音形式）为关键字建立散列表； (3) 采用一定的方法解决冲突； (4) 查找并显示给定电话号码的记录； 选作内容：
(1) 系统功能的完善；
(2) 设计不同的散列函数，比较冲突率；
(3) 在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。 6.排序综合
利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。
要求：
(1)至少采用三种方法（希尔排序、快速排序、堆排序）实现上述问题求解； (2)统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法；
(3)统计每种算法所用的比较次数和交换次数，最后列表显示； (4)如果采用4种或4种以上的方法者，可适当加分。 7.一元稀疏多项式的计算（*）
任务：能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减，并将结果输出；
要求：以链式存储结构实现多项式。 8. 文章编辑（*）
功能：输入一页文字，程序可以统计出文字、数字、空格的个数。 静态存储一页文章，每行最多不超过80个字符，共N行； 要求:
(1)分别统计出其中英文字母数和空格数及整篇文章总字数； (2)统计某一字符串在文章中出现的次数，并输出该次数； (3)删除某一子串，并将后面的字符前移。
存储结构使用线性表，分别用几个子函数实现相应的功能；
输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。
输出形式：
(1)分行输出用户输入的各行字符；
(2)分4行输出\全部字母数\、\数字个数\、\空格个数\、\文章总字数\(3)输出删除某一字符串后的文章； 9.迷宫求解（*）
任务：以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
要求：首先实现一个栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i,j,d)的形式输出，其中(i,j)指示迷宫中的一个坐标，d表示走到下一坐标的方向。 10. 猴子选大王（*）
任务：一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1--m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。
要求：
输入数据：输入m,n。 m,n 为整数，n 输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子