数据结构课程设计

dispno(emptype emp,int n):按pdepno指针输出。

sortsalary(emptype emp,int n):采用直接插入法对emp[1..n]按salary递增有序排序。

dispsalary(emptype emp,int n):按psalary指针链输出。

实验二电文的编码和译码。

一、内容和要求。

从键盘接收一串电文字符，输出对应的huffman编码。同时，能翻译由huffman编码生成的**串，输出对应的电文字符串。要求构造一颗huffman树，实现huffman编码，并用huffman编码生成的**串进行译码，程序中字符和权值是可变的，实现程序的灵活性。

本课程设计使用结构体数组作为数据结构来存储哈夫曼树及其编码。

二、实现提示。

在电报通信中，电文是以二进制**传送的。在发送中，需要将电文中的字符转换成二进制**串，即编码；在接受时，要将收到的二进制**串转化为对应的字符序列，即译码。我们知道，字符集中的字符被使用的频率是非均匀的。

在传送电文时，要想使电文总长尽可能短，就需要让使用频率高的字符编码长度尽可能短。因此，若对某字符集进行不等长编码的设计，则要求任意一个字符的编码都不是其他字符编码的前缀，这种编码称做前缀编码。

由huffman树求得的编码是最优前缀码，也叫huffman编码。给出字符集合各个字符的概率分布，构造huffman树，将huffman树中每个分支结点的左分支标0，右分支标1，将根到每个叶子路径上的标号连起来，就是该叶子所代表字符的编码。

引入头文件和定义huffman树结构：

#include”

typedef char datetype;

#define maxnum 50

typedef struct哈夫曼树结点的结构*/

datatype data;

int weight;

int parent;

int left;

int right;

huffnode;

typedef struct哈夫曼编码的存储结构*/

datatype cd[maxnum];

int start;

huffcode;

本函数由三个模块组成，构造哈夫曼树，编码和译码。

实验三停车场管理模拟系统。

一、内容和要求。

设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。

设计时还可以考虑以下因素：

1）汽车可有不同种类，则它们的占地面积不同，收费标准也不同，如1辆客车和1.5辆小汽车的占地面积相同，1辆十轮卡车占地面积相当于3辆小汽车的占地面积。

2）汽车可以直接从便道上开走，此时排在它前面的汽车要先开走让路，然后再依次排到队尾。

二、实现提示。

以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：

若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去；则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表实现。

需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：

汽车的牌照号码和进入停车场的时刻。

本程序可以分为四大模块：程序功能介绍和操作提示模块；汽车进入停车位的管理模块、汽车离开停车位的管理模块、查看停车场停车状态的查询模块。要求界面简洁、友好，容错性好。

实验四北京市城市轨道交通咨询模拟系统。

一、内容和要求。

问题描述。以无向图的形式可以描述城市轨道交通的状况，现请参考北京地铁运营图，给出从甲地到乙地最优的换乘方案。

基本要求。可提供对城市交通信息进行编辑（如添加或删除）的功能。线路交叉的换乘站和重合的线路车站使用相同的站名，当输入合法的上、下车站名时，输出换乘线路、乘车方向、路径车站和换乘车站。

真实的实际图形比较复杂，可对其进行某种简化，但线路条数要达到5条以上，且线路数据用文本文件的形式进行存储。

二、实现提示。

无向图的顶点表示站名，可先对车站进行编号，作为基本测试数据，再逐步过渡到真实站名。顶点之间的边表示可换乘线路，其上的权值可代表运行时间或运行长度等信息，为简化操作可以省略，即忽略每站的运行时间和平均停靠时间，以路经的站数来作为最优路径的计算依据。该题目的主要数据结构包括图和一组线性表，以及准备输出数据用的辅助数据结构，路径的搜索可用dfs或bfs算法实现，搜索到的每一条路径需要使用临时空间缓存。

乘车方向能够从车站与换乘站的位置关系来设法确定。

数据结构课程设计

数据结构课程设计

数据结构课程设计

数据结构课程设计

其他用户还读了