数据结构实验题目

一、 多项式相加

【问题描述】一元多项式相加是通过键盘输入两个形如P0+P1X+P2X+…+PnX的多项式，经过程序运算后在屏幕上输出他们的相加和。

1

2

n

二、 约瑟夫(Josephus)环

【问题描述】设编号为1、2、……n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。

三、 背包问题

【问题描述】设有n件物品，其重量分别为W1,W2,...,Wn，有一背包容量为T，求从n件物品取若干件，他们的重量和恰好等于背包容量T的所有解。

四、 停车场管理

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

1

实验二 二叉树

一、别求二叉树中度为0、1、2的结点数，交换每个结点的左右子女

【问题描述】参照二叉树遍历递归算法完成求解。输入一组数据，选择一种方法生成二叉树的二叉链表存储结构，输出中序遍历序列，度为0、1、2的结点数，交换每个结点的左右子女后中序遍历序列。

二、简单哈夫曼编/译码系统的设计

【问题描述】利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码，此实验即设计这样的一个简单编/码系统。系统应该具有如下的几个功能：

1、接收原始数据。 输入n个字符和n个权值，建立哈夫曼树，并将n个字符和n个权值及n个字符的哈夫曼编码存于文件hfmdata.dat中，哈夫曼树hfmtree.dat中。

#define HFMCODELEN 20 //字符的哈夫曼编码长度 typedef strcut { char ch; //字符 int weight； //权值

char bm[CODELEN +1]； //字符的哈夫曼编码 }ELEM；元素数据类型

文件hfmdata.dat中存放n个ELEM类型元素

typedef strcut { int weight； /*结点权值*/

int pat,lc,rc；

}HNode；哈夫曼树结点类型

文件hfmtree.dat中存放2n-1个HNode类型元素

2

2、编码发报。 利用已生成的哈夫曼编码(不在内存，则从文件hfmdata.dat中读入)，对输入的正文进行编码，将编码追加存入文件codefile.dat中。 #define TEXTCODELEN 1024 //一个正文编码长度 char bm[TEXTCODELEN]; //存放一个正文编码 文件codefile.dat中存放所有正文编码 3、译码。

利用已建好的哈夫曼树（如不在内存，则从文件hfmtree.dat中读入），将文件codefile.dat中的编码读入列表，选择并同步进行译码。

3