网站导航免费论文 原创论文 论文搜索 定作论文 网学软件 学术大家 资料中心 会员中心 问题解答 定作论文 大学论文导航 设计下载 最新论文 下载排行 原创论文 设计图标 Ppt模板 Flash素材 PSD素材 JS代码
返回网学首页
网学联系
最新论文 推荐专题 热门论文 素材专题
当前位置: 网学 > 论文模板 > 调查报告 > 正文

数据结构实验报告

来源:http://myeducs.cn 联系QQ:点击这里给我发消息 作者: 佚名 来源: 网络 发布时间: 15/07/28

网学网为需要调查报告的朋友们搜集整理了数据结构实验报告相关资料,希望对各位网友有所帮助!

转载请注明来源:毕业论文  需要其他论文可去论文范文查找。免费毕业论文下载数据结构实验报告

 

题目与内容
 哈夫曼(Huffman)树与哈夫曼码
 1.输入一个文本,统计各字符出现的频度,输出结果;
 2.使用二叉链表或三叉链表作存储结构,构造哈夫曼(Huffman)树;
 3.确定和输出各字符的哈夫曼码;
       4.输入一个由0和1组成的代码序列,翻译并输出与之对应的文本;
       
二、  数据结构及存储结构
在这个程序中我用了三叉链表tree作为哈夫曼树的结构:左、右儿子和父亲
节点;并且在开始,我还用此结构生成了单链表,用来存储读取的字符。编码的时候,我把编码放在栈结构stack中,然后逆序输出即为哈夫曼编码。存放叶节点时用到了指针数组。
struct tree(){
 char data;
 int m,sign;
 struct tree *lchild,*rchild,*parent;
}
struct stack{
 int data;
 struct stack *next;
}

算法设计思想
先调用frequency函数读取字符,创建链表来存储字符及其相关信息;同时把字符放进数组中进行备份,因为后面编码时要用到这些字符(它们就是叶节点)。然后遍历这个链表输出个字符的频度。接着调用ctree函数来生成哈夫曼树。在ctree函数中,首先对刚才那个链表按照频度排序,变成频度递增链表;然后取其前两个节点作为新建哈夫曼树的左右儿子(注:左儿子的频度<=右儿子的频度),再把它们从链表中删除,并且把新建的哈夫曼树的根结点插入到链表中。这样重复操作,就生成了哈夫曼树。然后调用ccode函数编码。我采用的是从叶到根的编码方式。先从数组中取出数据(即为一个叶节点),看其m的值(0/1),放进stack栈中,然后向根遍历,接着把栈中的数据取出输出,即为编码。最后调用translate函数进行译码。先读取01序列放进新创建的一个链表(队列形式)中,然后从根到叶进行遍历:从链表中取出一个数据,是0则到左子树,1则到右子树,如果其左右子树为空,则输出字符data,再取下一个数据从根重新遍历。这样就得到译码了。


心得体会
这次编程,从开始编到测试成功,我一共花了四天。这主要是因为之前我花了不少时间看书,把数据结构和存储结构都想好了,还看了大量程序,不管是相关还是不相关的。例如,有一个困扰我很久的问题:当询问是否继续时,输入y就继续,否则跳出;以前用getchar要等按了回车才进行判断,如果按了好几个y,则后面几个y被当成以后的输入处理了,这样就会出错。然而我在一个程序中看到了getche这个指令解决了这个问题,它不需等回车就进行处理。另外在定义哈夫曼树结构时,我加了个sign变量来标志它是左子树还是右子树,这样后面编码时就很方便。这次编程使我认识到:要重视细节,虽然很小,但是它会使程序不能运行或出错。这个程序中我由于把‘y’写成y,结果浪费了我半天的时间去查错。

五、  程序清单
#include <stdio.h>
#include <conio.h>
struct tree{         /*定义哈夫曼树的结构*/
 char data;            /*存放字符*/
 int m,sign; /*m存放字符出现的频率 sign是左(0)或右(1)儿子的标志*/
 struct tree *lchild,*rchild,*parent;    /*左儿子 右儿子 父节点*/
};
struct stack{           /*定义栈的结构*/
 int data;
 struct stack *next;
};
struct tree * ps[50],*root,*head;
 /*数组存放字符 root为二叉树的根结点 head为链表的头节点*/
int size;            /*标志字符个数*/
/*************************统计各字符出现的频度***********************/
void frequency(){
 struct tree *r,*p,*q;  
 int n,l,j=1;
 /*录入第一个字符并创建链表*/
 clrscr();             /*清屏*/
 head=NULL;
 printf("Input the text end of ENTER:\n");
 n=getchar();
 if(n!=''''\n''''){
  p=(struct tree*)malloc(sizeof(struct tree));
  p->data=n;
  p->m=1;
  p->sign=-1;
  p->lchild=NULL;
  p->rchild=NULL;
  p->parent=NULL;
  head=p;
  ps[0]=p;     /*把字符(后面的叶节点)放进数组备份*/
  n=getchar();

 }
 /*录入其它字符*/
 while(n!=''''\n''''){
  l=0;r=p;
  for(q=head;q!=NULL&&l==0;q=q->parent){
   if(q->data==n) {    /*检查是否和已经录入的字符相同*/
    q->m++;    /*如果相同则此字符的频度变量加1*/
    l=1;
   }
   r=p;
  }
  if(l==0){      /*如果不同则录入并加入链表*/
   p=(struct tree*)malloc(sizeof(struct tree));
   p->data=n;
   p->m=1;
   p->sign=-1;
   p->lchild=NULL;
   p->rchild=NULL;
   p->parent=NULL;
   r->parent=p;
   ps[j]=p;     /*把字符(后面的叶节点)放进数组备份*/
   j++;
  }
  n=getchar();
 }
 /*输出字符的频度*/
 p=head;
 size=0;
 printf("\nFrequency as follows:\ncharacters frequency\n");
 while(p!=NULL){
  printf("%c  %d\n",p->data,p->m);
  p=p->parent;
  size++;         /*统计字符的个数*/
 }
}
/****************************生成树**********************************/
void ctree(){ 
 struct tree *t,*r,*p,*e,*q;
 int n;
 /****给链表排序生成频度递增链表*****/
   for(p=head;p->parent!=NULL;p=p->parent){
      for(q=p->parent;q!=NULL;q=q->parent){
            if(p->m>q->m){
             n=q->m;       /*交换信息*/

     q->m=p->m;
              p->m=n;
    n=q->data;
    q->data=p->data;
    p->data=n;
         }
   }
 }
 /***********生成哈夫曼树***********/
 p=head;
 while(p!=NULL&&p->parent!=NULL){
 /*取递增链表前两个为左右儿子生成哈夫曼树*/
  q=p->parent->parent;    /*然后把它们从链表中删掉*/
  t=(struct tree*)malloc(sizeof(struct tree));
  t->lchild=p;       /*频度:左儿子<=右儿子*/
  t->rchild=p->parent;
  t->m=p->m+p->parent->m;
  t->rchild->parent=t;
  t->rchild->sign=1;
  t->lchild->parent=t;
  t->lchild->sign=0;
  t->sign=-1;
  root=t;          /*root为根结点*/
  root->parent=NULL;
  if(q!=NULL){        /*判断链表是否为空*/
   head=q;  
   r=head;
   e=head;     /*把新生成的根结点插入到链表中去*/
   if(head->m>t->m){      /*判断是否为头节点*/
    t->parent=q;
    head=t;
   }
   else{
    r=r->parent;
    while(r!=NULL&&r->m<t->m){
     e=r;
     r=r->parent;
    }
    t->parent=r;
    e->parent=t;
   }
   p=head;
   root=t;
  }

  else break;        /*如果链表为空则结束*/
 }
}
/******************************编码******************************/
void ccode(){      
 struct tree *p,*q;
 int j; 
 printf("\ncodes as follows:\ncharacters code\n");
 for(j=0;j<size;j++){      /*做size(叶节点个数)次循环*/
  head=NULL;
  p=ps[j];          /*从叶到根求编码*/
  printf("%c  ",p->data);
  while(p->parent!=NULL){       /*把编码存入栈中*/
   q=(struct stack *)malloc(sizeof(struct stack));
   q->data=p->sign;
   q->next=head;
   head=q;
   p=p->parent;
  }
  q=head;           /*输出编码*/
  while(q!=NULL){
   printf("%d",q->data);
   q=q->next;
  }
  printf("\n");
 }
}
/******************************译码******************************/
char translate(){
 struct tree *r,*p,*q;
 int n;
 char c;
 /*读取01序列*/
Error: printf("\nInput codes consist of 0 and 1 (end of ENTER):\n");
 n=getchar();
 if(n!=''''\n''''){          /*读取第一个字符*/
  p=(struct tree*)malloc(sizeof(struct tree));
  p->data=n;
  p->next=NULL;
  head=p;
  r=head;
  n=getchar();
 }
 while(n!=''''\n''''){          /*读取其它字符*/

  p=(struct tree*)malloc(sizeof(struct tree));
  p->data=n;
  p->next=NULL;
  r->next=p;
  r=p;
  n=getchar();
 }
 p=head;
 while(p!=NULL){        /*判断是否右非法字符*/
  if(p->data!=''''0''''&&p->data!=''''1''''){
   printf("There are illeage characters in your codes!\n");
   goto Error;
  }
  p=p->next;
 }
 printf("\nThe text of the codes is:");
 p=head;
 q=root;
 while(p!=NULL){         /*由根到叶遍历*/
  if(q->lchild==NULL&&q->rchild==NULL){  /*判断是否叶节点*/
   putchar(q->data);
   q=root;
  }
  else {           /*往下遍历*/
   if(p->data==''''0'''') q=q->lchild;
   else q=q->rchild;
   if(q->lchild==NULL&&q->rchild==NULL){
    putchar(q->data);
    q=root;
   }
  }
  p=p->next;
 }
 printf("\n\nInput codes again(y/n)?");     /*询问是否继续译码*/
 c=getche();
 printf("\n\n");
 return(c);          /*返回是否继续的标志*/
}
/******************************主程序******************************/
void main(){
 char c,a;
 
 do{
  frequency();

  ctree();
  ccode();
  c=translate();      /*translate子函数返回值赋给c*/
  for(;c==''''y''''||c==''''Y'''';){      /*判断是否继续译码*/
   c=translate();
  }
  printf("\nInput text again(y/n)?");
  a=getche();
 }
 while(a==''''y''''||a==''''Y'''');        /*判断是否循环*/
 clrscr();
 getchar();
}

数据结构实验报告......
  • 上一篇资讯: [调查报告]
  • 下一篇资讯: 软件测试实验报告
  • 版权所有 QQ:3710167 邮箱:3710167@qq.com 网学网 [Myeducs.cn] 您电脑的分辨率是 像素
    Copyright 2008-2015 myeducs.Cn www.myeducs.Cn All Rights Reserved 湘ICP备09003080号