信息学院2013年《数据结构》课程设计题目及要求

1、2013年数据结构课程设计题目及基本要求如下：上交相关内容要求交的成果的内容必须由以下四个部分组成，缺一不可1 上交源程序：学生按照课程设计的具体要求所开发的所有源程序（应该放到一个文件夹中）；2 上交程序的说明文件：（保存在.txt中）在说明文档中应该写明上交程序所在的目录，上交程序的主程序文件名，如果需要安装，要有程序的安装使用说明；3 课程设计报告：（要求 按照"姓名-学号-数据结构课程设计报告"起名，如为"张三-001-数据结构课程设计报告" ）按照课程设计的具体要求建立的功能模块，每个模块要求按照如下几个内容认真完成；其中包括:a)需求分析：在

2、该部分中叙述，每个模块的功能要求b)概要设计在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义。c）详细设计各个算法实现的主要源程序，对每个题目要有相应的源程序（可以是一组源程序，每个功能模块采用不同的函数实现）源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。d）调试分析测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是哪些？问题如何解决？），算法的改进设想。 4. 课设总结：总结可以包括 : 课程设计 过程的收获、遇到问题、遇到

3、问题解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程设计过程中对数据结构课程的认识等内容数据结构课程设计题目一、 试设计一个航空客运订票系统。基本要求如下：1、 每条航线所涉及的信息有：终点站名、航班号、飞机号、飞机周日（星期几）、乘员定额、余票量、订定票的客户名单（包括姓名、订票量、舱位等级1，2或3）以及等候替补的客户名单（包括姓名、所需数量）。2、 系统能实现的操作和功能如下：1） 查询航线：根据客户提出的终点站名输出如下信息：航班号、飞机号、星期几飞行，最近一天航班的日期和余票额；2） 承办订票业务：根据客户提出的要求（航班号、订票数额）查询该航班票额情况，若有

4、余票，则为客户办理订票手续，输出座位号；若已满员或余票少余订票额，则需重新询问客户要求。若需要，可登记排队候补；3） 承办退票业务：根据客户提出的情况（日期、航班号），为客户办理退票手续，然后查询该航班是否有人排队候补，首先询问排在第一的客户，若所退票额能满足他的要求，则为他办理订票手续，否则依次询问其它排队候补的客户。3、 实现提示：两个客户名单可分别由线性表和队列实现。为查找方便，已订票客户的线性表应按客户姓名有序，并且，为了插入和删除方便，应以链表作为存储结构。由于预约人数无法预计，队列也应以链表作为存储结构。二、 校园导游咨询（为来访的客人提供各种信息服务）1、 基本要求：1） 设计中

5、南大学校园平面图，有三个校区和三所附属医院，在这些校区和医院内选10个以上的建筑物、办公室、宿舍等地名。以图中顶点表示校园内各地名，存放地名名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。2） 为来访客人提供图中任意地名相关信息的查询。3） 为来访客人提供任意地名的问路查询，即查询任意两个地名之间的一条最短路径。2、 实现提示：一般情况下，校园的道路是双向通行的，可设计校园平面图是一个无向网。顶点和边均含有相关信息。三、停车场管理问题问题描述 设有一个可以停放n辆汽车的狭长停车场，它只有一个大门可以供车辆进出。车辆按到达停车场时间的早晚依次从停车场最里面向大门口处停放(最先到达的

6、第一辆车放在停车场的最里面)。如果停车场已放满n辆车，则后来的车辆只能在停车场大门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车就进入停车场。停车场内如有某辆车要开走，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车未进停车场就要离去，允许其离去，不收停车费，并且仍然保持在便道上等待的车辆的次序。编制一程序模拟该停车场的管理。实现要求 要求程序输出每辆车到达后的停车位置(停车场或便道上)，以及某辆车离开停车场时应交纳的费用和它在停车场内停留的时间。实现

7、提示 汽车的模拟输入信息格式可以是：(到达离去，汽车牌照号码，到达离去的时刻)。例如，(A，1，5)表示1号牌照车在5这个时刻到达，而(D，5，20)表示5号牌照车在20这个时刻离去。整个程序可以在输入信息为(E，0，0)时结束。本题可用栈和队列来实现。四、 全国交通咨询模拟【问题描述】处于对不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的时间尽可能短，出门旅游的游客则希望旅费尽可能省，而老年旅客则要求中转次数最少。编制一个全国城市间的交通咨询程序，为旅客提供两种或三种最优决策的交通咨询。【基本要求】（1）提供对城市信息进行编辑（如：添加或删除）的功能。 （2）城市之间

8、有两种交通工具：火车和飞机。提供对列车时刻表和飞机航班进行编辑（增设或删除）的功能。 （3）提供两种最优决策：最快到达或最省钱到达。全程只考虑一种交通工具。 （4）旅途中耗费的总时间应该包括中转站的等候时间。 （5）咨询以用户和计算机的对话方式进行。由用户输入起始站、终点站、最优决策原则和交通工具，输出信息：最快需要多长时间才能到达或者最少需要多少旅费才能到达，并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。徐州397乌鲁木齐哈尔滨长春沈阳天津郑州西安兰州成都上海昆明贵阳株州福州柳州广州深圳南宁18922161145668110096763990734967651124230570465

9、1622367409255607675140【测试数据】呼和浩特北京137674西宁大连534842武汉825南昌672【实现提示】（1）对全国城市交通图和班车时刻表及飞机航班表的编辑，应该提供文件形式输入和键盘输入两种方式。飞机航班表的信息应包括：起始站的出发时间、终点站的到达时间和票价；列车时刻表则需根据交通图给出各个路段的详细信息，例如：对于从北京到上海的火车，需给出北京至天津、天津至徐州及徐州至各段的出发时间、到达时间和票价信息。 （2）以邻接表作交通图的存储结构，表示边的结点内除含有邻接点的信息外，包括交通工具、路程中消耗的时间和花费以及出发和到达的时间等多项属性。五、压缩器/解压器

10、【问题描述】为了节省存储空间，常常需要把文本文件采用压缩编码的方式储存。例如：一个包含1000个x的字符串和2000个y的字符串的文本文件在不压缩时占用的空间为3002字节（每个x或每个y占用一个字节，两个字节用来表示串的结尾）。同样是这个文件，采用游程长度编码（run-length coding），可以存储为字符串1000x2000y，仅为10个字母，占用12个字节。若采用二进制表示游程长度（1000和2000）可以进一步节约空间。如果每个游程长度占用2个字节，则可以表示的最大游程长度为2*pow(16)，这样，上例中的字符串只需要用8个字节来存储。当要读取编码文件时，需要对其进行解码。由压

11、缩器（compressor）对文件进行编码，由解压器（decompressor）进行解码。（1）长度-游程编码的压缩/解压；+（2）LZW压缩/解压（散列）；（1）长度-游程编码的压缩/解压；+（3）霍夫曼编码压缩/解压 (霍夫曼树) 【基本要求】要求选用二种压缩/解压策略实现压缩/解压器（1）为必选。输入的为本文文件（.txt），输出的为一种自定义的文件（.nz）。考虑当构成文本的字符集合为a,b,c,z,0,1,2,9时，请用实例测试你的压缩/解压器。你的压缩器会不会出现抖动？（压缩后的文本比原来的还要大）。扩充构成文本的字符集合以便使它适应更一般的情况。【实现提示】LZW：由Lempel

12、、Ziv和Welch这三位科学家所开发的技术。该方法把文本的字符串映射为编码，首先，为该文本中所有可能出现的字母分别分配一个代码。例如：要压缩的对象是aaabbbbbbbaabaaba，由a和b组成。为a分配代码0,为b分配代码1。字符串和编码的关系被存储在字典中。字典如下：Key 01234567CodeAbAaaabbbbbbbbbaaaba LZW压缩器不断的在输入文件中寻找在字典中出现的最长的前缀p,并输出其相应的代码。若输入文件的下一个字符为c，则为pc分配下一个代码，并插入字典，这种策略称为LZW规则。相反，在解压时，编码表由压缩文件重新构造，LZW原则使这种重建成为可能。 如上例

13、子，压缩时，文件中第一个在字典中出现的最长前缀是a, 输出其编码0,然后为字符串aa分配代码2，并插入到字典中。余下的字符串在字典中出现的最长前缀是aa,输出aa的对应代码2，同时为字符串aab分配代码3并将其插入到字典中。依次类推，由此，输出0214537 解压时，要输入代码，然后用代码所表示的文本来替换这些代码。代码到文本的映射可按下面的方法重建：首先把分配给单一字母的代码插入到字典中。象前面一样，字典的入口为key-code对。然而此时是根据给定的代码（key）去寻找相应的入口（而不是根据文本Code）。压缩文件中的第一个代码对应于单一的字母，因此可以由该字母代替。对于压缩文件中的其他代

14、码p,要考虑两种情况：1）在字典中；2）不在字典中。在1）情况下，找到p对应的文本text(p)输出。并且，根据压缩原理可知，若在压缩文件中代码q写在p之前且text(q)是与q对应的文本，则压缩器会为文本text(q)（其后紧跟fc(p)，text(p)的第一个字符）分配一新代码。因此在字典中插入序偶（下一个代码，text(q)fc(p)）。 情况2）时，只有在当前文本段形如text(q)text(q)fc(q)且text(p)=text(q)fc(q)时才会发生。相应的压缩文件段是qp。在压缩过程中，为text(q)fc(q)分配的代码为p。在解压过程中，在用text(q)代替q后，又遇到

15、代码p。然而，此时字典中没有与p对应的文本。因为这种情况只在解压文本段为text(p)text(q)fc(q)时才发生，因此可以对p解码。当遇到一个没有定义代码文本对的代码p时，p对应的文本为text(q)fc(q)，其中q为p前面的代码。如上例子：首先，初始化字典，在其中插入(0,a),(1,b)。压缩的第一个代码为0,则用a代替之。下一个代码2未定义，因为前一个代码为0，且text(0)=a,fc(0)=a,则text(2)=text(0)fc(0)=aa。因此用aa代替2,并把(2,aa)插入字典中。下个代码1由b来替换，并把(3,text(2)fc(1)=(3,aab)插入字典中。依次

16、类推，得解压结果。霍夫曼编码：根据不同符号在文本中出现的不同的频率来进行压缩编码。假设文本是由a,u,x,z组成的字符串，若这个字符串的长度为1000，每个字符用一个字节来存储，共需1000个字节（即8000位）的空间。如果每个字符用2位二进制来编码（00=a,01=x,10=u,11=z），则用2000位二进制即可以表示1000个字符。此外，还需要一定的空间来存放编码表，可以采用如下格式来存储：符号个数：代码1，符号1，代码2，符号2，符号个数及每个符号分别用8位二进制来表示，每个代码需要占用log2(符号个数)位二进制。因此，上例中，代码表需占用5*8+4*2=48位，压缩比为8000/2

17、048=3.9 。利用这种编码方法，字符串aaxuaxz的压缩码为二进制串00000110000111，每个字符的编码具有相同的位数（两位）。从左到右依次从位串中取出两位，通过查编码表边可以获得原字符串，这是解压缩过程。我们利用霍夫曼编码来实现压缩，必须：1） 必须获得不同字符的频率。2） 建立具有最小加权外部路径的二叉数（即霍夫曼树），树的外部结点用字符串中的字符表示，外部结点的权重（weight）即为该字符出现的频率。3） 遍历从根到外部结点的路径得到每个字符的编码。4） 使用字符的编码来代替字符串中的字符。为了方便解码，需要保存字符代码映射表或每个字符的频率表（在保存信息为频率表的情况下

18、，解码需要重构霍夫曼数以获得相应的编码表）。构造霍夫曼树：首先从仅含一个外部结点的二叉树集合开始，每个外部结点代表字符串的一个不同的字符，其权重等于该字符的频率。此后不断的从集合中选择两棵具有最小权重的二叉树，并把它们合并成一棵新的二叉树，合并方法是把这两棵二叉树分别作为左右子树，然后增加一个新的根结点。新二叉树的权重为两棵子树的权重之和。这个过程一直可以持续到仅剩下一棵树为止。二叉树的集合可以使用有序表 /优先队列（基于队列/基于堆）实现。编码：构造完毕霍夫曼树后，可以对从根开始到外部结点（叶子）的路径进行编码，方法是向左孩子移动时取0，向右孩子移动时取1。【选作内容】对于策略2）我们用这种

19、方法修改它：每当压缩/解压1024*x个字节后，重新初始化代码表。取文本长度为100K到200K之间，x=10，20，30，40和50。测试修改后的程序，请给出你的结论：采用那种x值比较好？对于霍夫曼编码：当文本中的字符出现的频率差别很大时，我们可以通过使用变长的编码来降低每个位串的长度。但是，怎样对使用变长编码的位串解码呢？我们可以发现：在得到的霍夫曼编码中，没有任何一个代码是另一个代码的前缀。因此与编码向匹配的实际的字符是唯一的。请用实现这样的变长策略，并验证它。六、民航航班信息查询与客票发售服务系统。1.问题描述设民航售票处的计算机系统可以为客户提供下列各项服务：（1）查询航线：根据旅客

20、提出的终点站名输出下列信息：航班号、飞机号、星期几飞行，最近一天航班的日期和余票额；（2）承办订票业务：根据客户提出的要求（航班号、订票数额）查询该航班票额情况，若尚有余票，则为客户办理订票手续，输出座位号；若已满员或余票额少于订票额，则需重新询问客户要求。若需要，可预约登记排队等候；（3）承办退票业务：根据客户提供的情况（日期、航班），为客户办理退票手续，然后查询该航班是否有人预约登记，首先询问排在第一的客户，若所退票额能满足他的要求，则为他办理订票手续，否则依次询问其他排队预约的客户。2.要求编制便于人机对话的程序，实现上述服务项目。测试数据自定3.实现提示每条航线应包括的信息有：终点站名

21、、航班号、飞机号、飞行日期（星期几）、乘员定额、余票额、已订票的客户名单（包括姓名、订票额、座位号）和预约登记的客户名单（包括姓名、所需票额）。这最后两项显然是一个线性表和一个队列。为查找方便、已订票客户的线性表应按客户姓名有序，并且，为插入和删除方便，应以链表作存储结构。由于预约人数无法预计，队列也应以链表作存储结构。整个系统需汇总各条航线的情况登录在一张线性表上，由于航线基本不变，可采用顺序存储结构，并按航班有序或按终点站名有序。每条航线是这张表上的一个记录、包含上述八个域、其中乘员名单域为指向乘员名单链表的头指针，预约登记客户名单域为分别指向队头和队尾的指针。4.选做内容当客户订票要求不

22、能满足时，系统可向客户提供到达同一目的地的其他航线情况。七、简单的职工管理系统1.问题描述对单位的职工进行管理，包括插入、删除、查找、排序等功能。2.要求职工对象包括姓名、性别、出生年月、工作年月、学历、职务、住址、电话等信息。（1）新增一名职工：将新增职工对象按姓名以字典方式职工管理文件中。（2）删除一名职工：从职工管理文件中删除一名职工对象。（3）查询：从职工管理文件中查询符合某些条件的职工。（4）修改：检索某个职工对象，对其某些属性进行修改。（5）排序：按某种需要对职工对象文件进行排序。3.实现提示职工对象数不必很多，便于一次读入内存，所有操作不经过内外存交换。（1）由键盘输入职工对象，

23、以文件方式保存。程序执行时先将文件读入内存。（2）对职工对象中的"姓名"按字典顺序进行排序。（3）对排序后的职工对象进行增、删、查询、修改、排序等操作。4.选做内容将职工对象按散列法存储，并设计解决冲突的方法。在此基础上实现增、删、查询、修改、排序等操作。八、全国铁路运输网最佳经由问题1.问题描述该题目采用我国铁路运输网的数据进行编程和运行验证。图如下(详细可参见铁路运输网络中由铁路线和火车站的两个主要概念，譬如：1号铁路线表示京广线，2号铁路线表示京沪线等。铁路线对象包括铁路线编号,铁路线名称，起始站编号,终点站编号,该铁路线长度，通行标志(00B客货运禁行,01B货运通

24、行专线，10B客运通行专线，11B客货运通行)。火车站对象包括所属铁路线编号，车站代码，车站名，车站简称，离该铁路线起点站路程及终点站路程。2.要求（1） 查询某站所属的铁路线（2） 要求具备新增铁路线的管理功能（3） 要求具备新增车站的管理功能（4） 针对客运，货运情况能计算任何一个起始车站到任何一个终点站之间的最短路径。并且要求能够显示出该最短路径的各个火车站的经由顺序3.实现提示该题的解题思路可以参考第六大题。九、教学计划编制问题问题描述 大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等，每个专业开设的课程都是确定的，而且

25、课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。基本要求 （1）输入参数包括：学期总数，一学期的学分上限，每门课的课程号(固定占3位的字母数字串)、学分和直接先修课的课程号。（2）允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。（3）若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。计划的表格格式自行设计。测试数据学期总数：6；学分上限：10；该专业共开设12门课，课程号从C01到C12

26、，学分顺序为2,3,4,3,2,3,4,4,7,5,2,3。先修关系如下：课程编号课程名称先决条件C1程序设计基础无C2离散数学C1C3数据结构C1，C2C4汇编语言C1C5语言的设计和分析C3，C4C6计算机原理C11C7编译原理C5，C3C8操作系统C3，C6C9高等数学无C10线性代数C9C11普通物理C9C12数值分析C9，C10，C1实现提示可设学期总数不超过12，课程总数不超过100。如果输入的先修课程号不在该专业开设的课程序列中，则作为错误处理。应建立内部课程序号与课程号之间的对应关系。十、哈夫曼编/译码器问题描述利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间

27、，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼编/译码系统。基本要求一个完整的系统应具有以下功能：（1）I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。（2）E：编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。（3）

28、D：译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。（4）P：印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码写入文件CodePrint中。（5）T：印哈夫曼树（Tree Printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。测试数据（1）数据一：已知某系统在通信联络中只可能出现8种字符，其概率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11

29、,以此设计哈夫曼编码。利用此数据对程序进行调试。（2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THISPROGRAMISMYFAVORITE”。字符ABCDEFGHIJKLM频度1866413223210321154757153220字符NOPQRSTUVWXYZ频度5763151485180238181161实现提示（1）文件CodeFile的基类型可以设为子界型bit = 0.1。（2）用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示运行Quit。请用户键入一个先把功能符，些功能执行完毕后再经菜单，直至某次用户先把了“E”为止。

30、（3）在程序的一次执行过程中，第一次执行I、D或C命令之后，哈夫曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。十一、哈希表设计问题描述针对自己的班集体中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。基本要求假设人名为中国姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构照，用链表法处理冲突。测试数据读取熟悉的30个人的姓名。十二. 文章编辑功能：输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过80个字符，共N行；要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出"全部字母数"、"数字个数"、"空格