数据结构课程设计

实验一工资管理系统内容和要求设有一个职工文件，其结构为：职工号（no）、姓名（name）、部门号（depno）、工资数（salary）、职工号指针（pno）、部门号指针（pdepno）和工资数指针（psalary）。设计一个程序，从该文件中读取记录到一个单链表中，并完成如下功能。输入：添加一个职工记录。输出：输出全部职工记录。按no排序：通过pno指针将职工记录no从小到大链接起来。按no输出：沿pno链输出全部职工记录。按depno排序：通过pdepno指针将职工记录按depno从小到链接起来。按depno输出：沿pdepno链输出全部职工记录。按salary排序：通过psalary指针将职工记录按salary从小到大链接起来。按salary输出：沿psalary链输出全部职工记录。全清：删除职工文件中的全部记录。存储退出：将单链表中的全部结点存储到职工文件中，然后退出程序运行过程。实现提示由于这里的排序是通过指针链来实现的，不涉及记录的移动，而且还需要将排序后的结果保存到文件中，而一般的指针是绝对地址，不适合这种情况，为此采用静态链表。设计一个emp[]数组，其元素的类型为EmpType,其中含有三个指针即指向下一个元素的下标，分别用于no、depno和salary的排序。文件包含如下函数：DelAll(EmpTypeemp[],int&n):清除职工文件全部记录。ReadFile(EmpTypeemp[],int&n):读数据文件并存入emp数组中。SaveFile(EmpTypeemp[]intn):将emp数组存入数据文件。InputEmp(EmpTypeemp[],int&n):添加一个职工记录。OutpputFile(EmpTypeemp[],intn):输出职工文件全部记录。Sortno(EmpTypeemp[],intn):采用直接插入法对emp[1..n]按no递增有序排序。Dispno(EmpTypeemp[],intn):按pdepno指针输出。Sortsalary(EmpTypeemp[],intn):采用直接插入法对emp[1..n]按salary递增有序排序。Dispsalary(EmpTypeemp[],intn):按psalary指针链输出。实验二电文的编码和译码一、内容和要求从键盘接收一串电文字符，输出对应的Huffman编码。同时，能翻译由Huffman编码生成的代码串，输出对应的电文字符串。要求构造一颗Huffman树，实现Huffman编码，并用Huffman编码生成的代码串进行译码，程序中字符和权值是可变的，实现程序的灵活性。本课程设计使用结构体数组作为数据结构来存储哈夫曼树及其编码。二、实现提示在电报通信中，电文是以二进制代码传送的。在发送中，需要将电文中的字符转换成二进制代码串，即编码；在接受时，要将收到的二进制代码串转化为对应的字符序列，即译码。我们知道，字符集中的字符被使用的频率是非均匀的。在传送电文时，要想使电文总长尽可能短，就需要让使用频率高的字符编码长度尽可能短。因此，若对某字符集进行不等长编码的设计，则要求任意一个字符的编码都不是其他字符编码的前缀，这种编码称做前缀编码。由Huffman树求得的编码是最优前缀码，也叫Huffman编码。给出字符集合各个字符的概率分布，构造Huffman树，将Huffman树中每个分支结点的左分支标0，右分支标1，将根到每个叶子路径上的标号连起来，就是该叶子所代表字符的编码。引入头文件和定义Huffman树结构：#include”consts.h”typedefcharDateType;#defineMAXNUM50typedefstruct/*哈夫曼树结点的结构*/{DataTypedata;intweight;intparent;intleft;intright;}HuffNode;typedefstruct/*哈夫曼编码的存储结构*/{DataTypecd[MAXNUM];intstart;}HuffCode;本函数由三个模块组成，构造哈夫曼树，编码和译码。实验三停车场管理模拟系统一、内容和要求设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。设计时还可以考虑以下因素：（1）汽车可有不同种类，则它们的占地面积不同，收费标准也不同，如1辆客车和1.5辆小汽车的占地面积相同，1辆十轮卡车占地面积相当于3辆小汽车的占地面积。（2）汽车可以直接从便道上开走，此时排在它前面的汽车要先开走让路，然后再依次排到队尾。二、实现提示以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去；则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表实现。需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。本程序可以分为四大模块：程序功能介绍和操作提示模块；汽车进入停车位的管理模块、汽车离开停车位的管理模块、查看停车场停车状态的查询模块。要求界面简洁、友好，容错性好。实验四北京市城市轨道交通咨询模拟系统一、内容和要求问题描述以无向图的形式可以描述城市轨道交通的状况，现请参考北京地铁运营图，给出从甲地到乙地最优的换乘方案。基本要求可提供对城市交通信息进行编辑（如添加或删除）的功能。线路交叉的换乘站和重合的线路车站使用相同的站名，当输入合法的上、下车站名时，输出换乘线路、乘车方向、路径车站和换乘车站。真实的实际图形比较复杂，可对其进行某种简化，但线路条数要达到5条以上，且线路数据用文本文件的形式进行存储。二、实现提示无向图的顶点表示站名，可先对车站进行编号，作为基本测试数据，再逐步过渡到真实站名。顶点之间的边表示可换乘线路，其上的权值可代表运行时间或运行长