数据结构综合实践课程设计任务书
课程设计名称
中文：数据结构综合实践
英文：Datastructure Comprehensive Practice
一、课程设计目的与要求
课程设计目的
1、训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题。
2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；
3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；
4.训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。
课程设计要求
通过课程设计，在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用。
学生自选课程设计题目，设计题目从任务书所列选题表中选取，每个班每题不得超过3人。提醒：比较容易的题目自觉留给基础比较差的学生。难度高的题目才有可能得优秀。
学生原则上可以结合个人爱好自选课题，要求课题有一定的深度与难度，有一定的算法复杂性，能够巩固数据结构课程所学的知识。学生自选课题需先报课程设计指导教师批准方可生效。
1、编码要求：
（1）使用多文件完成系统，以项目文件提交。要求：
1、优：按要求完成题目，有完整的符合标准的文档，文档有条理、文笔通顺，格式正确，其中有总体设计思想的论述，有正确的流程图，程序完全实现设计方案，设计方案先进，软件可靠性好。 答辩回答问题正确，对系统的演示流畅，源代码解释清晰。
2、良：完成设计题目，有完整的符合标准的文档，文档有条理、文笔通顺，格式正确；有完全实现设计方案的软件，设计方案较先进。答辩回答问题较好，对系统的演示较流畅，源代码解释较清晰。
3、中：基本完成题目，有完整的符合标准的文档，有基本实现设计方案的软件，设计方案正确。答辩回答问题基本正确，对系统的演示基本完成，源代码解释较清楚。
4、及格：基本完成题目，有完整的符合标准的文档，有基本实现设计方案的软件，设计方案基本正确。答辩回答问题基本正确，系统演示能够完成。源代码解释基本清楚。
5、不及格：没有完成题目的要求，没有完整的符合标准的文档，软件没有基本实现设计方案，设计方案不正确。答辩回答问题不正确，系统演示不能够完成，源代码解释不清楚。
附录1:
源码联系UP主 -> https://space.bilibili.com/329101171
1.景区评论文本的热度调查（难度3）
图1 景区评论数据格式
【功能】
图1所示为“景区评论.csv”数据。现在要求统计50个景区的热度词。词的热度主要以词出现的频率表示。要求设计数据结构为：基于词汇的哈希链，然后基于哈希链统计每个词出现的频率。实现功能：
2、三国人物关系图谱 （难度2）
基于三国人物关系数据，构建三国人物关系图。图的顶点为三国人物。边为人物关系（如儿子、义弟、主公）。本题需要实现在图结构上做的各种人物关系查询。人物的属性包括：人名、所属国。
如刘备（刘备，蜀国）
【功能】
1.基于邻接表构建三国人物关系图，并能输出展示邻接表，保存在文件”TRKGraph.txt”中。文件格式如下：
刘备–>张飞—>关羽—>赵云
注意：图的构建，应该先整理图中的顶点数据，即要整理所有三国人物数据作为图顶点。
2.统计人物关系数量最多的前10个三国人物及其所属国。
3.输入2个人物，查找2个人物之间所有关系。基于图的深度遍历，展示关系路径。并能说明最短路径是哪条。答辩时候展示：有关系的人物。无关系的人物。
4.智能问答。输入荀彧的主公的儿子是谁？能输出关系路径，并给出答案。
3．航空客运订票系统（难度2）
【问题描述】
航空客运订票的业务活动包括：查询航线、客票预订和办理退票等。试设计一个航空客运订票系统，以使上述业务可以借助计算机来完成。
【基本要求】
(1)每条航线所涉及的信息有：起点站名，终点站名、航班号、飞机号、飞行日期、乘员定额、余票量、已订票的客户名单(包括姓名、订票量及所订的座位号)以及等候替补的客户名单(包括姓名、所需票量)；
(2)系统能实现的操作和功能如下：
（1）录入：可以录入航班情况，录入的航班数据可存于内存中，每天结束工作时内存中的数据可通过“保存录入航班数据”添加存入文件中；
提示：使用合适的结构组织，使它方便按“起点站名”与“终点站名”被查找。设一般航班记录数据文件中将保存近10000条记录。
（2）加载：将文件中保存的航班数据至内存中。
（3）清除：将日期超过当前日期的航班记录清除。
（4）查询航线：根据旅客提出的“起点站名”与“终点站名”输出下列信息：航班号、飞机号、星期几飞行，最近一天航班的日期和余票额；
（5）承办订票业务：根据客户提出的要求(航班号、订票数额)查询该航班票额情况，若尚有余票，则为客户办理订票手续，输出座位号，并将订票结果保存文件中。若已满员或余票额少于订票额，则需重新询问客户要求。若需要，可登记排队候补，候补名单将保存于内存中，选择合适的数据结构以方便候补业务的处理；
④承办退票业务：根据客户提供的情况(日期、航班)，为客户办理退票手续，然后查询该航班是否有人排队候补，首先询问排在第一的客户，若所退票额能满足他的要求，则为他办理订票手续，否则依次询问其他排队候补的客户。
（6）保存航班信息至文件中。
（7）保存订票名单。
（8）保存候补名单。
【测试数据】
由读者自行指定。
【进一步完成内容】
当客户订票要求不能满足时，系统可向客户提供到达同一目的地的其他航线情况。
4．迷宫问题（难度1）
【问题描述】
以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。
（1）以递归方式输出一条从入口至出口的通路。
（2）使用栈方式输出一条从入口至出口的通路。
（3）输出迷宫所有的可能路径，以及所有最短路径。
（4）可任意指定一个起点和终点，输出其间的最短路径。
【基本要求】
编写一个求解迷宫的非递归程序。求得的通路以三元组(i，j，d)的形式输出，其中：(i，j)指示迷宫中的一个坐标，d表示走到下一坐标的方向。如：对于下列数据的迷宫，输出的一条通路为z(1，1，1)，(1，2，2)，(2，2，2)，(3，2，3)，(3，1，2)，··。
【测试数据】
（1）可随机生成一组迷宫的数据，如左上角(1，1)为入口，右下角(8，9)为出口。（先计算是否存在路径，如果不存在则重新生成。）
1 2 3 4 5 6 7 8
0
0 1 0 0 0 1 0
0 0 1 0 0 0 1 0
0 0 0 0 1 1 0 1
0 1 1 1 0 0 1 0
0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 1
0 1 1 1 1 0 0 1
1 1 0 0 0 1 0 1
1 1 0 0 0 0 0 0
(2) 以方阵形式输出迷宫及其通路。（通路上用特殊符号标记）
（3）可指定任意起点和终点，如（6，3）–》（5，8）
5．简单行编辑程序（难度2）
【问题描述】
文本编辑程序是利用计算机进行文字加工的基本软件工具，实现对文本文件的插入、删除等修改操作。限制这些操作以行为单位进行的编辑程序称为行编辑程序。
被编辑的文本文件可能很大，全部读入编辑程序的数据空间(内存)的作法既不经济，也不总能实现。一种解决方法是逐段地编辑。任何时刻只把待编辑文件的一段放在内存，称为活区。试按照这种方法实现一个简单的行编辑程序。设文件每行不超过320个字符，很少超过80个字符。
【基本要求】
实现以下4条基本编辑命令:
(1) 行插入。格式:i<行号><回车><文本>.<回车>
将<文本>插入活区中第<行号>行之后。
(2) 行删除。格式:d<行号l>[<空格><行号2>]<回车>
删除活区中第<行号l>行(到第<行号2>行)。例如:“d10"和"d1014”。
(3) 活区切换。格式n<回车>
将活区写入输出文件，并从输入文件中读入下一段，作为新的活区。
(4) 活区显示。格式:p<回车>
逐页地(每页20行)显示活区内容，每显示一页之后请用户决定是否继续显示以后备页(如果存在)。印出的每一行要前置行号和一个空格符，行号固定占4位，增量为1。
各条命令中的行号均须在活区中各行行号范围之内，只有插入命令的行号可以等于活区第一行行号减1，表示插入当前屏幕中第一行之前，否则命令参数非法。
【测试数据】
自行设定，注意测试将活区删空等特殊情况。
【实现提示】
(1)设活区的大小用行数ActiveMULen(可设为100)来描述。考虑到文本文件行长通常为正态分布，且峰值在60到70之间，用320×ActiveMULen大小的字符数组实现存储将造成大量浪费。可以以标准行块为单位为各行分配存储，每个标准行块可含81个字符。这些行块可以组成一个数组，也可以利用动态链表连接起来。一行文字可能占多个行块。行尾可用一个特殊的ASCII字符(如(012)8)标识。此外，还应记住活区起始行号。行插入将引起随后各行行号的顺序下推。
(2)初始化函数包括:请用户提供输入文件名(空串表示无输入文件)和输出文件名，两者不能相同。然后尽可能多地从输入文件中读入各行，但不超过ActiveMULen-LX的值可以自定，例如20。
(3)在执行行插入命令的过程中，每接收到一行时都要检查活区大小是否已达ActiveMaxLen。如果是，则为了在插入这一行之后仍保持活区大小不超过ActiveMaxLen应将插入点之前的活区部分中第一行输出到输出文件中;若插入点为第一行之前，则只得将新插入的这一行输出。
(4)若输入文件尚未读完，活区切换命令可将原活区中最后几行留在活区顶部，以保持阅读连续性;否则，它意味着结束编辑或开始编辑另一个文件。
(5)可令前三条命令执行后自动调用活区显示。
【进一步完成内容】
(1)对于命令格式非法等一切错误作严格检查和适当处理。
(2)加入更复杂的编辑操作，如对某行进行串替换；在活区内进行模式匹配等，格式可以为S<行号>@<串1>@<串2><回车>和m<串><回车>。
6．校园导游咨询（难度2）
【问题描述】
设计一个校园导游程序，为来访的客人提供各种信息查询服务。用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。
【基本要求】
(1) 设计你所在学校的校园平面图，所含景点不少于20个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息;以边表示路径，存放路径长度等相关信息。
(2)为来访客人提供图中任意景点相关信息的查询。
(3)为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。
(4)区分机动车道和人行道。可提供步行或驾车的路径导航 。
【实现提示】
一般情况下，校园的道路是双向通行的，可设校园平面图是一个无向网。顶点和边均含有相关信息。
【进一步完成内容】
(1) 求校园图的关节点。
(2) 提供图中任意景点问路查询，即求任意两个景点之间的所有路径。
(3) 提供校园图中多个景点的最佳访问路线查询 , 即求途经这多个景点的最佳 ( 短 )路径。
(4) 校园导游图的景点和道路的修改扩充功能。
(5) 扩充道路信息 , 如道路类别 ( 车道、人行道等 ) 、沿途景色等级 , 以至可按客人所需分别查询人行路径或车行路径或观景路径等。
(6) 扩充每个景点的邻接景点的方向等信息 , 使得路径查询结果能提供详尽的导向信息。
(7) 实现校园导游图的仿真界面。
7．资源调配管理（难度2）
【问题描述】
建立资源调配管理系统，模拟对资源的管理和调配。我们可以通过一个队列/栈来存储空闲的资源，当需要用到资源的时候，可以从队列/栈中取出一个资源，同时还需要一个数据结构用于存储被占用的资源。当资源使用完时，将其归还至队列/栈中。
对于资源，每个资源有唯一的ID编号，任意两个资源的ID不重复。可以定义一个结构体（或类）来表示资源，或者直接使用ID（int或者string类型）表示资源。
资源在使用完后需要归还，所以必须用一个数据结构存储被调用的资源，可以通过ID来指定归还的资源，所以这个数据结构必须满足这样的要求，给出一个资源ID，可以找到对应的资源。可以使用哈希散列（哈希表）实现。
【基本要求】
（1）创建队列/栈存储空闲资源；
（2）实现满足需求可以存储被占用的资源的数据结构（哈希散列）；
（3）实现占用和归还资源的功能；
（4）实现一个简易的UI（命令行）；
【实现提示】
本课程设计使用的数据结构有 队列 或 栈 和 哈希散列。
【测试数据】
自行生成每个资源的ID编号，要求不存在重复的ID编号。数量至少为100
8．家族关系查询系统（难度3） 家族层数限定至少5层
【问题描述】
建立家族关系数据库，实现对家族成员关系的相关查询。
【基本要求】
（5）建立家族关系并能存储到文件中；
（6）读文件并以树形结构显示家族关系。
（3）实现家族成员及其相互关系的添加，修改与删除；添加家庭成员结点时可以是添加某人的儿子、女儿、妻子、丈夫。每个成员的孩子可以有多个，不限于2个，孩子的姓氏也可以与母亲相同。可删除家族树中某成员结点，一般用于在输入家庭成员时出现错误情形时进行家族树的修正。
（4）实现查询家族成员的双亲、祖先、兄弟、孩子和后代等信息。注意：在3代以内应能区分爷爷/外公，父/母、兄/弟、姐/妹、女/媳、儿/婿、孙子/外孙、伯父/叔父/姑/舅/姨。
如下图显示的家族树中，姚媛媛的父亲是姚冠冠，母亲是周纯全，爷爷是姚家祖。姚缓缓的妹妹是姚密密。姚家祖的孙女是姚媛媛。姚丝璇的母亲是姚北北，父亲是夏雨田，外公是姚家祖。姚丝璇的弟弟是姚丝皇。姚家祖的外孙女是姚丝璇，外孙是姚丝皇。另外，姚缓缓的姑姑是姚北北。姚缓缓的叔叔是姚南南，姚丝天的伯父是姚冠冠。
注意：该家族树仅记录某姓家族中的直系成员，如果查询非直系成员的亲属关系，如查询姚丝璇的爷爷时，可显示“未在本家族树中显示”。如果查询不存在的亲属关系，如查询姚丝璇的姨妈，则显示“不存在”。
【实现提示】
本课程设计使用的数据结构有树状结构和队列。树状结构采用三叉链表表示，三叉链可以采用孩子/兄弟/父链的结构。队列采用链式队列实现。
【测试数据】
以自已家族做为测试，注意测试边界数据。
9．哈希应用(难度2)
【问题描述】
建立一个包括电话号码及姓名的通迅录，可以通过电话号码和姓名进行快速查询，要求设计合理的哈希函数和解决冲突策略，建立以电话号码为关键字的哈希表和关键字为姓名的哈希表以便快速查询电话号码。HASH表长设为N/4,对于冲突的数据可以将提供（N－N/4）个空间，装填因子要求不低于0.8；每个电话号码的查找的比较次数不超过4次。
【基本要求】
根据电话号码和姓名为关键字分别建立哈希表：
（1）显示所有电话号码的查找次数以及最大查找次数。
（2）任意输入一个电话号码，显示可能的查找次数。
（3）可以任意删除一个电话号码，再重计算所有电话号码的查找次数
（4）可以添加一个电话号码，显示它添加位置的冲突电话。
【测试数据】
1）要求通过编写程序生成10000条电话号码记录进行测试，测试数据的生成要有一定的合理性和随机分布性。
提示：
我国使用的手机号码为11位，其中各段有不同的编码方式，其构成如下：
前3位—网络识别号；
第4-7位—地区编码；
第8-11位—用户号码。
如：
有关手机号码的编码规则请自行查询相关资料。
2）自行生成姓名的测试数据。要求自动生成的姓名有一定的合理性。
如姓氏应是常用姓氏。请自行查询相关资料。
10、北京地铁关系网 （难度3）
基于北京21条地铁路线建一个地铁关系图。图节点信息在station.csv中。节点关系在line1,line2…lineyz中的文件。无向图。2个站的距离值为边的权值。注意：1个站点属于多条线。
【功能】
11基于AVL树表示的集合(难度3)
设计目的：
平衡二叉树（AVL）作为一种重要的查找表结构，能有效地支持数据的并行处理，本设计使学生牢固掌握AVL树及其实现的方法，并应用该结构实现集合抽象数据类型，提升学生对数据结构与数据抽象的人士，提高学生的综合实践与应用能力。
设计内容：
本设计分为三个层次：（1）以二叉链表作为存储结构，设计与实现AVL树-动态查找表的6中基本运算；（2）以AVL树表示集合，实现集合抽象数据类型；（3）以集合表示个人微博或社交网络中好友集、粉丝集、关注人集、实现共同关注、共同爱好、二度好友等查询功能
算法分析
算法实现应具备较好的时间复杂度与空间复杂度，并对算法实现的时间复杂度和空间复杂度作出详细分析。
12 、字典树 （难度3）
大家熟悉的英文分词（python的jieba分词库），如果只是用空格作为单词的标志，这是不合理。因为单词可能书写不对。所以合理的自然语言处理（NLP）分词，需要一个有效字典维护。现有的英文字典包含单词量高达10万多条，在这样一个庞大的字典中查找数据，基于线性查找，效率非常低。现在基于单词有很多共同字符（共同前缀字母）特点，构造一棵字典树，可大大提高单词的查询效率。并能快速对单词排序、词频统计、单词拼写检查及全文搜索。
本次课设只要实现基于英文文章建一棵字典树。并能统计相关单词出现的词频。
英文字典树的结构图是这样的。按照树型结构存储字符串，每个结点存一个字符，自顶向下做标记的就是词的词尾，比如，app,apple,application,abstract,absorb,block,black,blake… 等等