《数据结构课程设计》指导书.doc

数据结构课程设计指导书一、实习目的数据结构课程设计是一项综合性设计活动，要求在教师的指导下，利用本课程内的以及到目前为止所学到的有关知识和技术解决一些不太复杂但却是综合性的问题。从规模来说，课程设计是在平时作业的基础上进一步扩大的大作业。在设计中，要求学生要全面考虑相互联系的各个方面及问题。通过课程设计，使学生对整个课程的知识体系有较深入的理解，在运用本课程的知识解决实际问题方面得到锻炼，对锻炼学生的实践能力以及运用本课程的知识、方法解决更为复杂的实际问题有较好的启发和指导作用，从而为后续课程的学习、毕业设计环节以及将来的实际工作打好坚实的基础。通过对给定问题的求解，使学生在运用数据结构、程序设计以及迄今为止所学课程中的各种基本技术和理论，在建立问题模型、构造求解算法、设计数据结构、编程及上机调试等方面得到全面的锻炼，从而能更深刻地理解数据结构的精髓，为后续软件课程的学习及软件设计能力的提高奠定良好的基础。二、数据结构课程设计要求1.学生必须仔细阅读数据结构课程设计方案，认真主动完成课设的要求。有问题及时主动通过各种方式与教师联系沟通。2.学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时向教师汇报。3.课程设计按照教学要求需要两周时间完成（2周共十天）。数据结构课程设计时间：17周周一下午5-8节，17周周二下午5-8节，17周周五下午5-8节，18周周一全天1-8节，18周周二上午1-4节，18周周四下午5-8节，18周周五上午1-4节三、实习基本内容本次课程设计完成如下模块（共20个模块，学生可以在其中至少挑选4-5个功能块完成）1 校园导游程序 问题描述：用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。基本要求：查询各景点的相关信息；查询图中任意两个景点间的最短路径；查询图中任意两个景点间的所有路径；增加、删除、更新有关景点和道路的信息。选作内容：求多个景点的最佳（最短）游览路径。区分机动车道和人行道。实现导游图的仿真界面。数据结构：typedef struct messageint num;/景点代码char name100;/景点名称char pro500;/简介Ciceroni;Ciceroni school10=1,行政楼n,2,食堂n,3,赛博楼,信息分院办公室所在地n,4,求是楼,实验楼计算机中心n,5,格致楼,法学管理学院,6,工程实习中心,金工实习n,7,仰仪楼,机电计测分院n,8,体育馆,旁边有篮球场足球场还有网球场n,9,一号教学楼，主要以阶梯教室为主n,10,二号教学楼，小教室为多n; /*景点名称和简介*/操作：/*给景点之间的路径赋最大值*/*最短路径的C语言函数*/*输出最短路径和最短距离函数*/*输入景点代码查景点名称和简介*/*输入景点代码查到其它景点的最短距离*/2 员工管理系统问题描述：每个员工的信息包括：编号、姓名、性别、出生年月、学历、职务、电话、住址等。系统能够完成员工信息的查询、更新、插入、删除、排序等功能。基本要求：排序：按不同关键字，对所有员工的信息进行排序；查询：按特定条件查找员工；更新，按编号对某个员工的某项信息进行修改；插入，加入新员工的信息；删除，按编号删除已离职的员工的信息。选作内容：实现图形用户界面。通过链表实现数据结构：struct workers char name15;/姓名char department18;/单位char gender;/性别 unsigned int age;/年龄 unsigned long telephone;/电话unsigned long wage;/工资unsigned long num;/职工号struct workers *next;操作实现：/*插入职工信息，通过链表实现 */*具体实现职工信息的插入*/*对职工信息的删除操作*/*修改操作*/*实现对员工信息的查找*/*排序*/* 输出员工信息 */* 显示职工工资情况 计算平均工资 */3 算术表达式求值问题描述：一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。基本要求：从键盘读入一个合法的算术表达式，输出正确的结果；显示输入序列和栈的变化过程。(3.14159/2+sqrt(1/32+4)+1/22*ln(1/1.1*(2+sqrt(1/32+4)*23.45;选作内容：扩充运算符集合；引入变量操作数；操作数类型扩充到实数。4 运动会分数统计任务：参加运动会有n个学校，学校编号为1n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1m，女子m+1m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m=20，n=2，请输男生项目总数m=20，请输女生项目总数k=20）/项目资料:请输入男生项目信息：项目名称;项目编号;该项目的参与人数请输入女生项目信息：项目名称;项目编号;该项目的参与人数/添加学生数据int SchoolCount=0;/学校总数int boyCount=0;/男生项目 总数int girlCount=0;/女生项目 总数int xm_Count=0; /项目 总数XM_TABLE xm_T41;/项目表主要实现： 参数设置; 添加学生; 统计 ; 学校查询; 项目查询;等功能。5 一元多项式计算任务：能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减，并将结果输入；在上交资料中请写明：存储结构、多项式相加的基本过程的算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；设有一元多项式Am(x)和Bn(x).Am(x)=A0+A1x1+A2x2+A3x3+ +Amxm Bn(x)=B0+B1x1+B2x2+B3x3+ +Bnxn请实现求M(x)= Am(x)+Bn(x)、M(x)= Am(x)-Bn(x)和M(x)= Am(x)Bn(x)。要求： 1)首先判定多项式是否稀疏2)分别采用顺序和动态存储结构实现；3)结果M(x)中无重复阶项和无零系数项；4)要求输出结果的升幂和降幂两种排列情况6 订票系统任务：通过此系统可以实现如下功能：录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）可以输入起飞抵达城市，查询飞机航班情况；订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；退票：可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。修改航班信息：当航班信息改变可以修改航班数据文件要求：根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能；航班信息数据结构typedef char keytype;/航班信息结构typedef struct char start6;/起点站char end6;/终点站char sche10;/航班期char time15;/起飞时间char time25;/到达时间char model4;/机型int price; /票价infotype;/定义航班节点typedef structkeytype keyskeylen;/航班号infotype others;/航班信息int next; /下一航班slnode;/航班表typedef structslnode slmaxspace;int keynum;int length; sllist;操作实现：（1）录入航班信息：（2）查询航班信息：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况；航班信息查询系统：可以按： 1.航班号; 2.起点站； 3.终点站； 4.起飞时间; 5.到达时间;以下选作：（3）航班订票：（订票情况可以存在一个数据文件中，结构自己设定） 可以订票，如果该航班已经无票，可以提供相关可选择航班；（4）航班退票：可退票，退票后修改相关数据文件； 客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。（5）修改航班信息： 当航班信息改变可以修改航班数据文件 注：因为航班号为两位字母后跟数字，所以在排序时应该使用多关键字的基数排序对航班号进行排序。7 迷宫问题求解任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；要求：在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；8 文章编辑功能：输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过80个字符，共N行；要求分别统计出其中英文字母数和空格数及整篇文章总字数；统计某一字符串在文章中出现的次数，并输出该次数；删除某一子串，并将后面的字符前移。存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式：分行输出用户输入的各行字符；分4行输出全部字母数、数字个数、空格个数、文章总字数；输出删除某一字符串后的文章；9 joseph环 任务：编号是1，2，n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。测试数据：m的初值为20，n=7 ，7个人的密码依次为3，1，7，2，4，7，5，首先m=6，则正确的输出是什么？要求：输入数据：建立输入处理输入数据，输入m的初值，n ，输入每个人的密码，建立单循环链表。输出形式：建立一个输出函数，将正确的输出序列输出。数据结构：typedef struct Nodeint data;int password;struct Node *next;Node, *LinkList;基本操作： /初始化单链表/给每个人赋密码/确定需要处理的人数/确定开始的上限值/得到正确的顺序/输出结果10 猴子选大王任务：一堆猴子都有编号，编号是1，2，3，.，m ，这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。要求：输入数据：输入m，n m，n 为整数，nm输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号，建立一个函数来实现此功能。(10、11二者任选其一)11 建立二叉树，层序、先序遍历（ 用递归或非递归的方法都可以）任务：要求能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列；分别建立建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数；12 哈夫曼编/译码器利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。基本要求一个完整的系统应具有以下功能：（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或C命令之后，哈夫曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。13 纸牌游戏任务：编号为1-52张牌，正面向上，从第2张开始，以2为基数，是2的倍数的牌翻一次，直到最后一张牌；然后，从第3张开始，以3为基数，是3的倍数的牌翻一次，直到最后一张牌；然后从第4张开始，以4为基数，是4的倍数的牌翻一次，直到最后一张牌；再依次5的倍数的牌翻一次，6的，7的直到以52为基数的翻过，输出这时正面向上的牌有哪些？14 拓扑排序任务：编写函数实现图的拓扑排序。15 学生成绩管理（限1 人完成） 实现功能：输入、输出、插入、删除、查找、追加、读入、显示、保存、拷贝、排序、索引、分类合计、退出。能实现对学生信息的简单管理。具体要求：建立一个4个学生的信息登记表，每个学生的信息包括：学号，姓名，和3门课程的成绩（FOX，C，ENGLISH）。程序运行时显示一个简单的菜单，例如： （1）：信息输入（INPUT） （2）：总分统计（COUNT） （3）：总分排序（SORT） （4）：查询(QUERY） 其中： （1）：对4个学生的信息进行输入； （2）：对每个学生的3门课程统计总分； (3)：对4个学生的总分按降序排序并显示出来； (4)：查询输入一个学号后，显示出该学生的有关信息；数据结构：struct student int num; /学号 char name20;/姓名 int foxscore;/fox成绩 int cscore; /C语言 int englishscore;/英语成绩 struct student *next;操作：1.成绩信息输入; 2.统计总分; 3.排序; 4.查询16 停车场管理设停车场（如下图所示）内只有一个可停放几量汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已经停满几量汽车，则后来的汽车只能在门外的便道上等候，一旦停车场内有车开走，则排在便道上的第一辆汽车即可开入；当停车场内某车辆要离开时，由于停车场是狭长的通道，在它之后开入车场的车辆必须先退出车场为它让路，待该车辆开出大门外后，为它让路的车辆再按原次序进入车场。在这里假设汽车不能从便道上开走。试设计一个停车场管理程序（这里只是一个假想的停车场管理，并不代表实际的停车场管理）。停车场 大门北入口 便道 出口 图 停车场示意图分析：汽车在停车场内进出是按照栈的运算方式来实现的，先到的先进停车场；停车场的汽车离开停车场时，汽车场内其它汽车为该辆汽车让路，也是按栈的方式进行；汽车在便道上等候是按队列的方式进行的。因此，将停车场设计成一个栈，汽车让路也需要另一个栈来协助完成，汽车进出便道用队列来实现。 本设计，栈采用顺序栈结构，队列用链式存储结构。 存储结构定义如下： #define stacksize 10 typedef struct sqstack int datastacksize; int top; SqStackTp;typedef struct linked_queue int data; struct linked_queue * next;LqueueTp;typedef struct LqueueTp *front , *rear ; QueptrTp;停车场管理的算法描述如下：1）接受命令和车号，若是汽车要进停车场，先判断停车场栈是否满，若不满，则汽车入栈，否则汽车进入便道队列等候。 2）若是汽车要离开停车场，为给汽车让路，将停车场栈上若干辆汽车入临时栈，等这辆车出停车场后，临时栈中的汽车出栈，在回到停车场栈，然后看便道队列是否为空，若不空则说明有汽车等候，从队头取出汽车号，让该车进入停车场栈。 3）重复1），2）直到为退出命令（车号为0或负数）。17 模拟旅馆管理系统中的床位分配和加收；18 银行业务活动的模拟；19 修道士野人问题；20 索引文件的插入、删除和查找操作假定一个以ElemType为记录类型的主文件MAINFILE.DAT存于当前目录中，他的索引文件IndexFile,idx也存于此目录中。索引文件中的每个索引项对应主文件中的一个记录，每个索引项包含两个域：一是索引值域，又称关键字域（KEY），用来存储对应记录的关键字；二是记录位置域（NEXT），用来存储对应记录在主文件中的位置编号。若主文件中包含有N个记录，则位置编号为0N-1。主文件中记录的排列次序可以任意安排，即不强求按关键字有序排列，而索引文件是按关键字从小到大排列的有序文件。在这种带有主文件和索引文件的整个文件系统中，当向主文件的末尾插入一条记录后，还要把他的索引项插入到索引文件中；当删除一条记录时，首先从索引文件中删除掉对应的索引项，然后把主文件中被删除记录的关键字域置为特定值作为删除标记即可，不需要真正从物理上删除他；当查找时，是先查找索引文件得到对应的索引项，然后根据索引项中所含的记录位置从主文件中取出记录。由此可知，对这种文件系统操作的时间主要花在对索引文件的操作上。四、上交相关内容要求上交成果的内容必须由以下四个部分组成，缺一不可1上交源程序：学生按照课程设计的具体要求所开发的所有源程序（应该放到一个文件夹中）；2上交程序的说明文件：（保存在.txt中）在说明文档中应该写明上交程序所在的目录，上交程序的主程序文件名，如果需要安装，要有程序的安装使用说明；3课程设计报告：（保存在word 文档中，文件名要求按照姓名-学号-课程设计报告起名，如文件名为张三-001-课程设计报告.doc ）按照课程设计的具体要求建立的功能模块，每个模块要求按照如下几个内容认真完成；其中包括:（1） 需求分析：（2）在该部分中叙述，每个模块的功能要求（3）概要设计在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义。详细设计各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组源程序，每个功能模块采用不同的函数实现）源程序要按照写程序的