数据结构之线性表的应用

数据结构之线性表的应用

1．实验题目

利用哈夫曼编码进行通信可以大大提高信道利用率，这要求在发送端通过一个编码系统对待传输预先编码，在接收端将传来的数据进行译码。对于双工通道，每端都需要一个完整的编/译码系统。

2．需求分析

本演示程序用TC编写，完成单链表的生成，任意位置的插入、删除，以及确定某一元素在单链表中的位置。

① 输入的形式和输入值的范围：根据程序所给的提示输入字符的种类数、想要编码的字符串、想译码的哈夫曼码。输入的字符串中字符的种类一定要和输入的种类数对应，否则会造成程序的错误。

② 输出的形式：首先会输出第一次输入字符串中各字符出现的次数，并给出每个字符的哈夫曼码；之后再输出的就是对应于用户输入的哈夫曼码的译码字符以及再次输入一串字符串后编码得到的哈夫曼码。

③ 程序所能达到的功能：哈夫曼树的初始化，用已构造的哈夫曼树实现哈夫曼码的编/译码及输出。

④ 测试数据：字符数为4，第一次字符串为qweqqqrtyeruiy。需要译码的哈夫曼码为100001001001111010101110001，进行编码的字符串为yretweqt。

3．概要设计

1）为了实现上述程序功能，需要定义哈夫曼树的抽象数据类型：

ADT Tree{

数据对象：D是具有相同特性的数据元素的集合。

数据关系：R={H},（Di，{Hi}）。

HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int n)

操作结果：构造赫夫曼树HT,n个字符编码HC

select(HuffmanTree t,int i,int &s1,int &s2)

初始条件：哈夫曼树HT已存在

操作结果：使s1为较小的值

min(HuffmanTree t,int i)

初始条件：哈夫曼树HT已存在

操作结果：被函数void select()调用取小。

Creatree(BT &p,char c)

操作结果：采用递归方式构造一棵二叉排序树。

InOrderTraverse(BT p)

初始条件：二叉排序树BT已存在。

操作结果：中序遍历。

DispHCode(HuffmanTree HT,HuffmanCode HC,int n)

初始条件：哈夫曼树HT已存在。

操作结果：显示哈弗曼码。

Tran(HuffmanTree HT,int n)

初始条件：哈夫曼树HT已存在。

操作结果：将哈夫曼码译码为字符串。

TTranChar(HuffmanTree HT,HuffmanCode HC,int n)

初始条件：哈夫曼树HT已存在。

操作结果：将字符串整体编码成哈夫曼码。

}

2）本程序包含9个函数：

①主函数main（）

②哈夫曼树构造HuffmanCoding（）

③取小排序select（）

④遍历取小min（）

⑤构造二叉排序树Creatree（）

⑥中序遍历排序树InOrderTraverse（）

⑦输出哈夫曼编码DispHCode（）

⑧将哈夫曼码译码成字符Tran（）

⑨将字符串编码成哈夫曼码TTranChar（）

4．详细设计

实现概要设计中定义的所有的数据类型，对每个操作给出伪码算法。对主程序和其他模块也都需要写出伪码算法。

1）结点类型和指针类型

 1       typedef struct
 2 
 3         { unsigned int weight;char data;
 4 
 5          unsigned int parent,llchild,rrchild;
 6 
 7         }HTNode,*HuffmanTree;
 8 
 9       typedef char * *HuffmanCode;
10 
11 typedef struct tnode
12 
13 { char ch;     
14 
15          int count;   
16 
17          struct tnode *lchild,*rchild;
18 
19 }BTree,*BT;

2）二叉树的基本操作

  1  void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int n)
  2 
  3 {构造赫夫曼树HT,n个字符编码HC；
  4 
  5 在HT[1~i-1]中选择parent为0且weight最小的两个,分别s1、s2；
  6 
  7 strcpy(HC[i],&cd[start])函数进行复制；
  8 
  9 }
 10 
 11  void select(HuffmanTree t,int i,int &s1,int &s2)
 12 
 13 { if(s1>s2)
 14 
 15    {j=s1;
 16 
 17     s1=s2;
 18 
 19     s2=j;
 20 
 21    }
 22 
 23 }
 24 
 25       int min(HuffmanTree t,int i)
 26 
 27          { unsigned int k=100;取k比任何权值都大
 28 
 29             for(j=1;j<=i;j++)
 30 
 31             if(t[j].weight<k&&t[j].parent==0)
 32 
 33                k=t[j].weight,flag=j;
 34 
 35             t[flag].parent=1;}
 36 
 37       void Creatree(BT &p,char c)
 38 
 39        { 采用递归方式构造一棵二叉排序树
 40 
 41          if(p==NULL)                 
 42 
 43 {  p=(BTree * )malloc(sizeof(BTree));
 44 
 45 p->ch=c;
 46 
 47 p->count=1;
 48 
 49 p->lchild=p->rchild=NULL;
 50 
 51 }
 52 
 53 else
 54 
 55           if(c==p->ch) p->count++;
 56 
 57 else
 58 
 59   if(c<p->ch) Creatree(p->lchild,c);
 60 
 61              else  Creatree(p->rchild,c);}
 62 
 63       void InOrderTraverse(BT p)
 64 
 65        {中序遍历
 66 
 67 InOrderTraverse(p->lchild);
 68 
 69             {printf("%c的个数为:%d
",p->ch,p->count);
 70 
 71          s[b]=p->count;b++;
 72 
 73             str[a]=p->ch;a++;}
 74 
 75  InOrderTraverse(p->rchild)}
 76 
 77 void DispHCode(HuffmanTree HT,HuffmanCode HC,int n)
 78 
 79 {显示哈夫曼编码
 80 
 81 printf("%c:	",HT[i].data)
 82 
 83 }
 84 
 85       void Tran(HuffmanTree HT,int n)
 86 
 87         { while(cc[j]!='#')
 88 
 89  {
 90 
 91                if(cc[j]=='0')
 92 
 93                   i=HT[i].llchild;  
 94 
 95               else
 96 
 97                   i=HT[i].rrchild;  
 98 
 99                 if(HT[i].llchild==0)    
100 
101                  { 
102 
103                  printf("%c",HT[i].data);i=2*n-1; }
104 
105              j++;}
106 
107 }
108 
109       void TTranChar(HuffmanTree HT,HuffmanCode HC,int n)
110 
111 { while(ss[i]!='')
112 
113              {
114 
115              j=1;
116 
117               while((HT[j].data!=ss[i])&&(j<=n))
118 
119               {j++;}
120 
121            printf("%s",HC[j]);
122 
123              i++;}
124 
125 }

5．调试分析

在实现哈夫曼树编码的过程中，首先构建哈夫曼树，并用动态分配数组存储，也用动态分配数组存储哈夫曼编码表。开始统计字符串中出现的各种字符及其次数时，将字母存放数组中，但是考虑到字母出现的不同，完全初始化再统计其出现的个数，不仅占用空间并且时间复杂度高。后来采用二叉树统计出现的字母及个数，实现了输入字母种类的灵活性。

6．使用说明

根据想编码的字符串的字符种类数输入“请输入要用几种字符”；

根据输入的字符数输入字符串，注意字符串中字符数一定要与定义的字符数相同；

输入完毕后程序会统计输出字符串中各字符出现的次数（即权值）并输出每个字符的哈夫曼码；

输入想进行译码的哈夫曼码，注意一定要以“#”为结束标志；

程序输出译码的字符；

再次输入想进行编码的字符串；

程序输出编码后的哈夫曼码。

7．测试结果

8．附代码

  1 // 实验三.cpp : 定义控制台应用程序的入口点。
  2 //
  3 
  4 #include "stdafx.h"
  5 
  6 #include<stdio.h>
  7 #include<stdlib.h>
  8 #include<string.h>
  9 #include<malloc.h>
 10 #define MAXWORD 100
 11 typedef struct
 12  { unsigned int weight;char data;
 13    unsigned int parent,llchild,rrchild;
 14  }HTNode,*HuffmanTree;                //动态分配数组存储哈夫曼树
 15 
 16 typedef char * *HuffmanCode;        //动态分配数组存储哈夫曼编码表
 17 
 18 typedef struct tnode
 19 { char ch;          //字符
 20   int count;        //出现次数 
 21  struct tnode *lchild,*rchild;
 22 }BTree,*BT;
 23 
 24 int a=0,b=0;int s[MAXWORD];char str[MAXWORD];
 25 
 26 void main()
 27 { int n;int i=0;
 28   HuffmanTree HT;HuffmanCode HC;
 29  void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int n);
 30  void DispHCode(HuffmanTree HT,HuffmanCode HC,int n);
 31  void Creatree(BT &p,char c);            //Creatree()和InOrderTraverse()
 32  void InOrderTraverse(BT p);           //利用二叉树统计出现的字符及个数
 33  void TTranChar(HuffmanTree HT,HuffmanCode HC,int n);
 34  void Tran(HuffmanTree HT,int n);
 35  printf("请输入要用几种字符：");
 36  scanf("%d",&n);
 37  BT root=NULL;
 38  printf("
");
 39  printf("请输入字符串:
");
 40  scanf("%s",str);
 41  while(str[i]!='')
 42   {Creatree(root,str[i]);i++;}
 43  printf("字符及出现次数:
");
 44  InOrderTraverse(root);
 45  printf("
");
 46  HuffmanCoding(HT,HC,n);
 47  DispHCode(HT,HC,n);
 48  Tran(HT,n);
 49 TTranChar(HT,HC,n);
 50 system("pause");
 51 }
 52 
 53 void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int n) 
 54 {              // w放n个权值,构造赫夫曼树HT,n个字符编码HC
 55   void select(HuffmanTree t,int i,int &s1,int &s2);
 56   int m,i,s1,s2,start;char *cd;unsigned c,f;
 57   HuffmanTree p;
 58   if(n<=1) return;
 59   m=2*n-1;
 60   HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); 
 61   for(p=HT+1,i=1;i<=n;++i,++p)
 62    { (*p).parent=0;
 63      (*p).llchild=0;
 64      (*p).rrchild=0;
 65    }
 66 for(p=HT+1,i=0;i<n;++i,++p)
 67  { (*p).data=str[i];
 68    (*p).weight=s[i];
 69 }
 70 for(;i<=m;++i,++p)
 71      (*p).parent=0;
 72    for(i=n+1;i<=m;++i)            // 建赫夫曼树
 73    {     // 在HT[1~i-1]中选择parent为0且weight最小的两个,分别s1、s2
 74      select(HT,i-1,s1,s2);
 75      HT[s1].parent=HT[s2].parent=i;
 76      HT[i].llchild=s1;
 77      HT[i].rrchild=s2;
 78      HT[i].weight=HT[s1].weight+HT[s2].weight;
 79    }
 80    HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//([0]不用)
 81    cd=(char*)malloc(n*sizeof(char)); 
 82    cd[n-1]='';                                 // 编码结束符
 83    for(i=1;i<=n;i++)
 84    { start=n-1;                                  // 编码结束符位置
 85      for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
 86      if(HT[f].llchild==c)
 87      cd[--start]='0';
 88      else
 89      cd[--start]='1';
 90      HC[i]=(char*)malloc((n-start)*sizeof(char));
 91      strcpy(HC[i],&cd[start]);                    // 复制
 92    }
 93    free(cd); 
 94  }
 95 
 96 void select(HuffmanTree t,int i,int &s1,int &s2)     // s1为较小
 97  { int min(HuffmanTree t,int i);
 98    int j;
 99    s1=min(t,i);
100    s2=min(t,i);
101    if(s1>s2)
102    {j=s1;
103     s1=s2;
104     s2=j;
105    }
106  }
107 
108 int min(HuffmanTree t,int i)         // 函数void select()调用
109  { 
110    int j,flag;
111   unsigned int k=100;              // 取k比任何权值都大
112    for(j=1;j<=i;j++)
113      if(t[j].weight<k&&t[j].parent==0)
114        k=t[j].weight,flag=j;
115    t[flag].parent=1;
116    return flag;
117  }
118 
119 void Creatree(BT &p,char c)       //采用递归方式构造一棵二叉排序树
120 {if(p==NULL)                   //p为NULL，则建立一个新结点
121 {p=(BTree * )malloc(sizeof(BTree));
122 p->ch=c;
123 p->count=1;
124 p->lchild=p->rchild=NULL;
125 }
126 else 
127  if(c==p->ch) p->count++;
128 else 
129  if(c<p->ch) Creatree(p->lchild,c);
130  else  Creatree(p->rchild,c);
131 }
132 
133 void InOrderTraverse(BT p)      //中序遍历
134 {
135     if(p!=NULL)
136 { InOrderTraverse(p->lchild);
137     {printf("%c的个数为:%d
",p->ch,p->count);
138      s[b]=p->count;b++;
139     str[a]=p->ch;a++;}
140  InOrderTraverse(p->rchild);}
141 }
142 
143 void DispHCode(HuffmanTree HT,HuffmanCode HC,int n)  //显示0、1编码
144 {int i;
145  printf("输出哈夫曼编码:
");
146  for(i=1;i<=n;i++)
147   { printf("%c:	",HT[i].data);
148     puts(HC[i]);}
149 }
150 
151 void Tran(HuffmanTree HT,int n)         //将含0、1的编码翻译成字符
152 {
153  int i,j=0;
154  char cc[MAXWORD];
155  i=2*n-1;           
156  printf("输入发送的(0、1)编码(以'#'为结束标志)：");
157  scanf("%s",cc);
158  printf("译码后的字符为");
159  while(cc[j]!='#')
160  {
161   if(cc[j]=='0')
162    i=HT[i].llchild;   
163   else
164    i=HT[i].rrchild;   
165   if(HT[i].llchild==0)     
166   {  
167      printf("%c",HT[i].data);i=2*n-1; }
168      j++;
169  }
170  printf("
");
171 }
172  
173 void TTranChar(HuffmanTree HT,HuffmanCode HC,int n)
174 { 
175  char ss[50];int i,j;                 //将字符串翻译成0、1代码
176  printf("输入字符串:");
177     scanf("%s",ss);
178     i=0;
179     printf("编码后的代码为");
180     while(ss[i]!='')
181     {
182      j=1;
183      while((HT[j].data!=ss[i])&&(j<=n))
184      {j++;}
185      printf("%s",HC[j]);
186       i++;
187     }
188      printf("
");}

View Code