首页 考试资料幻灯片工程技术公务员考试小学教学中学教学大学教学外语资料
数据结构实验书


main(){ BiThrTree T=NULL,Thrt=NULL; printf("nCreate CreateBiTree(&T); InorderThreading(&Thrt,T);/* InorderTraverse(Thrt); } a Thread Binary Treen");

/*建立二叉树 T*/ 将 T 进行中序线索化*/ /*中序遍历线索二叉树 Thrt*/

【测试数据】 1. 输入:A↙ 输出:A 2. 输入:ABC##DE#G##F###↙, 输出:C B E G D F A

3. 输入:ABD#GJ##K##E##C#FH##IL###↙, 输出:D J G K B E A C H F L I

4. 读者可自行指定测试数据(注意建立二叉树时的输入序列) 【说明】 1. 此处只是写出中序线索二叉树的建立和遍历算法的实现,读者需要注意类 C 语言描述的算法在转变为 C 源程序时关于函数参数的处理以及其它变量的定义与使用方法; 2. 读者可参考此程序,实现先序线索二叉树和后序线索二叉树的算法,并进行相应的遍历。

第四节 赫夫曼树与赫夫曼编码

【问题描述】 利用 Huffman 编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是, 这要求在发送端通过一个编码系统对待传数据预先编码,在接受端将传来的数据编码进行译码(复原)。 对于有些信道,每端都需要一个完整的编/译码系统。试为这样的信息收发站编写一个 Huffman 的编/译 码系统。给定一组权值{7,9,5,6,10,1,13,15,4,8},构造一棵赫夫曼树,并计算带权路径长度 WPL。 【数据描述】 //- - 赫夫曼树的存储表示 - -

typedef struct { unsigned unsigned }HTNode; int weight; int parent,lchild,rchild; //用顺序存储结构表示赫夫曼树的结点结构定义

//动态分配数组存储 Huffman 编码表 【算法描述】 1. 初始化:从键盘读入 n 个字符,以及它们的权值,建立 Huffman 树。(具体算法可参见教材 P147 的算 法 6.12) 2. 编码:根据建立的 Huffman 树,求每个字符的 Huffman 编码。对给定的待编码字符序列进行编码。 3. 译码:利用已经建立好的 Huffman 树,对上面的编码结果译码。译码的过程是分解电文中的字符串,从 根结点出发,按字符’0’和’1’确定找左孩子或右孩子,直至叶结点,便求得该子串相应的字符。具体 算法留给读者完成。 4. 打印 Huffman 树。 【C 源程序】 /*实现初始化,建立 Huffman 树,并完成字符的编码*/ #include #define N #define M <stdio.h> 10 2*N-1 /*待编码字符的个数,即树中叶结点的最大个数*/ /*树中总的结点数目*/

typedef struct{ unsigned int weight;

unsigned }HTNode;

int parent,lchild,rchild; /*树中结点的结构*/

typedef struct { char data; /*待编码的字符*/ /*字符的权值 /*字符的编码 */ */

int weight; char } HTCode; code[N];

void

Init(HTCode hc[],int

*n){

/*初始化,读入待编码字符的个数 n,从键盘输入 n 个字符和 n 个权值*/ int i; printf("ninput n="); scanf("%d",&(*n)); printf("ninput %d charactern",*n); for (i=1;i<=*n;i++) hc[i].data=getch();

printf("ninput %d weightn",*n); for (i=1;i<=*n;i++) } void Select(HTNode ht[],int k,int *s1,int *s2){ scanf("%d",&(hc[i].weight));

/*ht[1?k]中选择 parent 为 0,并且 weight 最小的两个结点 其序号由指针变量 s1,s2 指向*/ int i; for (i=1;i<=k *s1=i; for (i=1;i<=k;i++) if (ht[i].parent==0 i<=k ; i++) && i!=*s1) break; && ht[i].weight<ht[*s1].weight) *s1=i; && ht[i].parent!=0 ;i++);

for (i=1; if *s2=i;

(ht[i].parent==0

for (i=1;i<=k;i++) if ( ht[i].parent==0 && i!=*s1 && ht[i].weight<ht[*s2].weight) *s2=i;

} void HuffmanCoding(HTNode ht[],HTCode hc[],int n){

/*构造 Huffman 树 ht,并求出 n 个字符的编码*/ char cd[N];

int i,j,m,c,f,s1,s2,start; m=2*n-1; for (i=1;i<=m;i++){ if else (i<=n) ht[i].weight=hc[i].weight;

ht[i].weight=0;

ht[i].parent=ht[i].lchild=ht[i].rchild=0; } for (i=n+1;i<=m;i++){ Select(ht,i-1,&s1,&s2); ht[s1].parent=i; ht[i].lchild=s1; ht[s2].parent=i; ht[i].rchild=s2;

ht[i].weight=ht[s1].weight+ht[s2].weight; } cd[n-1]='\0'; for (i=1;i<=n;i++) start=n-1; for (c=i,f=ht[i].parent;f;c=f,f=ht[f].parent) if else (ht[f].lchild==c) cd[--start]='1'; cd[--start]='0'; {

strcpy(hc[i].code,&cd[start]); } } main(){ int i,m,n,w[N+1]; HTNode HTCode ht[M+1]; hc[N+1];

Init(hc,&n);

/*初始化*/

HuffmanCoding(ht,hc,n);/*构造 Huffman 树,并形成字符的编码*/ /*输出字符的编码*/ for (i=1;i<=n;i++)printf("n%c } --- %s",hc[i].data,hc[i].code);

【测试数据】 1. 根据运行提示,依次输入待编码的字符个数和这些字符,以及每个字符的权值: input n=4↙ input abcd↙ input4 weight 7 5 2 4↙ 输出: a b c d --------0 10 110 111 4character

2. 读者可根据运行提示,自行指定数据,观察程序的运行结果。

【说明】 1. 此处只是 Huffman 树的建立和编码算法的实现,一个完整的 Huffman 编/译码系统应进一步完善,实现 以上算法描述的四个基本要求,并可考虑将 Hufmman 树和 Huffman 编码存在磁盘文件中。提出这些要求, 是给读者一定的思考空间和提高自己的编程能力的机会。读者需要注意类 C 语言描述的算法在转变为 C 源 程序时关于函数参数的处理以及其它变量的定义与使用方法; 2. 读者可参考此程序,实现 Huffman 编/译码系统的其他算法,以进一步加深理解和学习体会。

第五节

思考题

1. 二叉树的遍历 二叉树的遍历算法是二叉树各种操作的基础,前面讲过二叉树前序/中序/后序遍历的递归算法,本节想在 此基础上实现二叉树遍历的非递归算法,并利用遍历算法实现二叉树的其它操作。

(1) 仿照二叉树遍历的递归算法执行过程中递归工作栈的状态变化状况写出相应的非递归算法,将遍历 和栈的应用相结合; (2) 在遍历的基础上实现对给定二叉树统计总结点数目/双孩子结点数目/单孩子结点数目/叶结点数目的 算法; (3) 编写算法计算一棵二叉树的高度的算法,并能判断任意结点所在的层次; (4) 判断两棵二叉树是否相似,所谓两棵二叉树 s 和 t 相似,要么它们都为空或都只有一个根结点,要 么它们的左右子树均相似; (5) 编写算法(递归/非递归)完成交换二叉树中所有结点的左右子树。 【简要分析】 以上算法主要是为了加深读者关于各种遍历算法的实现和基本应用的理解,可有选择地实现,最好能编写 完整的程序上机实现。 2. 线索二叉树的建立和遍历 二叉树的遍历是以一定规则将二叉树中的结点排列成一个线性序列。当二叉树以二叉链表做存储结构 时,只能找到结点的左右孩子信息,而不能直接得到结点在任意序列中的前驱和后继信息,这种信息只有 在遍历的动态过程中才能得到。由于在有 n 个结点的二叉链表中一定存在 n+1 个空链域,可以利用这些空 链域来存放结点的前驱和后继信息。对二叉树以某种次序遍历使其变成线索二叉树的过程就是线索化。 读者可仿照本章第二节所实现的中序线索二叉树的建立和遍历实现二叉树的前序和后序线索二叉树的建立 和遍历; 3. 二叉树的先序、中序和后序遍历序列的关系 对一棵给定的二叉树进行某种次序的遍历,将得到唯一的遍历序列。但是如果对一个已知的遍历序列,则 可对应多种二叉树的形态。例如对前序遍历序列 ABC,有 5 棵不同二叉树的先序遍历序列与其一致。但是 如果同时知道一棵二叉树的前序和中序遍历序列,则可唯一确定一棵二叉树。 请设计一个算法对已知一棵二叉树的前序和中序遍历序列,由此构造这棵二叉树。 4. 二叉树遍历应用 已知二叉树用下面的顺序结构存储,写出中序遍历该二叉树的算法及 C 语言源程序。 Type Array [1..maxn] Record Data:Char; Lc,Rc:Integer //存结点值 //左、右孩子下标,0 表示无左、右孩子 of

123456789101112131415161718192021222324252627282930

 


 

  【Top

最新搜索

 


 

热点推荐