数据结构实验报告

数据结构实验报告题目与 内容 财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容 哈夫曼(Huffman)树与哈夫曼码输入一个文本，统计各字符出现的频度，输出结果使用二叉链 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 或三叉链表作存储结构，构造哈夫曼(Huffman)树;确定和输出各字符的哈夫曼码;输入一个由0和1组成的代码序列，翻译并输出与之对应的文本;二、数据结构及存储结构在这个程序中我用了三叉链表tree作为哈夫曼树的结构：左、右儿子和父亲节点;并且在开始，我还用此结构生成了单链表，用来存储读取的字符。编码的时候，我把编码放在栈结构stack中，然后逆序输出即为哈夫曼编码。存放叶节点时用到了指针数组。structtree(){chardata;intm,sign;structtree*lchild,*rchild,*parent;}structstack{intdata;structstack*next;}算法设计思想先调用frequency函数读取字符，创建链表来存储字符及其相关信息;同时把字符放进数组中进行备份，因为后面编码时要用到这些字符（它们就是叶节点）。然后遍历这个链表输出个字符的频度。接着调用ctree函数来生成哈夫曼树。在ctree函数中，首先对刚才那个链表按照频度排序，变成频度递增链表;然后取其前两个节点作为新建哈夫曼树的左右儿子（注：左儿子的频度心得体会这次编程，从开始编到测试成功，我一共花了四天。这主要是因为之前我花了不少时间看书，把数据结构和存储结构都想好了，还看了大量程序，不管是相关还是不相关的。例如，有一个困扰我很久的问题：当询问是否继续时，输入y就继续，否则跳出;以前用getchar要等按了回车才进行判断，如果按了好几个y,则后面几个y被当成以后的输入处理了，这样就会出错。然而我在一个程序中看到了getche这个指令解决了这个问题，它不需等回车就进行处理。另外在定义哈夫曼树结构时，我加了个sign变量来标志它是左子树还是右子树，这样后面编码时就很方便。这次编程使我认识到：要重视细节，虽然很小，但是它会使程序不能运行或出错。这个程序中我由于把‘y'写成y，结果浪费了我半天的时间去查错。五、程序 清单 安全隐患排查清单下载最新工程量清单计量规则下载程序清单下载家私清单下载送货清单下载 #include#includestructtree{/*定义哈夫曼树的结构*/chardata;/*存放字符*/intm,sign;/*m存放字符出现的频率sign是左(0)或右(1)儿子的标志*/structtree*lchild,*rchild,*parent;/*左儿子右儿子父节点*/};structstack{/*定义栈的结构*/intdata;structstack*next;};structtree*ps,*root,*head;/*数组存放字符root为二叉树的根结点head为链表的头节点*/统计各字符出现的频度intsize;/*标志字符个数*//************************************************voidfrequency(){structtree*r,*p,*q;intn,l,j=1;/*录入第一个字符并创建链表*/clrscr();/*清屏*/head=NULL;printf("InputthetextendofENTER:");n=get);if(n!=''){p=(structtree*)malloc(sizeof(structtree));p->data=n;p->m=1;p->sign=-1;p->lchild=NULL;p->rchild=NULL;p->parent=NULL;head=p;ps=p;/*把字符(后面的叶节点)放进数组备份*/n=get);}/*录入其它字符*/while(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=(structtree*)malloc(sizeof(structtree));p->data=n;p->m=1;p->sign=-1;p->lchild=NULL;p->rchild=NULL;p->parent=NULL;r->parent=p;ps=p;/*把字符(后面的叶节点)放进数组备份*/j++;}n=get);}/*输出字符的频度*/p=head;size=0;printf("Frequencyasfollows:frequency");while(p!=NULL){printf("%c%d",p->data,p->m);p=p->parent;size++;/*统计字符的个数*/}}/**************************************************************/voidctree(){structtree*t,*r,*p,*e,*q;intn;/****给链表排序生成频度递增链表*****for(p=head;p->parent!=NULL;p=p->parent){for(q=p->parent;q!=NULL;q=q->parent){if(p->m>q->m){characters生成树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=(structtree*)malloc(sizeof(structtree));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->mm){e=r;r=r->parent;}t->parent=r;e->parent=t;}p=head;root=t;}elsebreak;/*如果链表为空则结束*/}}/******************************编******************************/voidccode(){structtree*p,*q;intj;printf("codesasfollows:characterscode");for(j=0;jhead=NULL;p=ps;/*从叶到根求编码*/printf("%c",p->data);while(p->parent!=NULL){/*把编码存入栈中*/q=(structstack*)malloc(sizeof(structstack));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("");}}/************************************************************/chartranslate(){structtree*r,*p,*q;intn;charc;/*读取01序列*/Error:printf("InputcodesconsistofENTER):");n=get);if(n!=''){/*读取第一个字符*/p=(structtree*)malloc(sizeof(structtree));p->data=n;p->next=NULL;head=p;译码0and1(endr=head;n=get);}while(n!=''){/*读取其它字符*/p=(structtree*)malloc(sizeof(structtree));p->data=n;p->next=NULL;r->next=p;r=p;n=get);}p=head;while(p!=NULL){/*判断是否右非法字符*/if(p->data!='0'&&p->data!='1'){inyourprintf("Thereareilleagecharacterscodes!");gotoError;}p=p->next;}printf("Thetextofthecodesis:");p=head;q=root;while(p!=NULL){/*由根到叶遍历*/if(q->lchild==NULL&&q->rchild==NULL){/*否叶节点*/putq->data);q=root;}else{/*往下遍历*/if(p->data=='0')q=q->lchild;elseq=q->rchild;if(q->lchild==NULL&&q->rchild==NULL){putq->data);q=root;}}p=p->next;}printf("Inputcodesagain(y/n)?");/*继续译码*/c=getche();printf("");return(c);/*返回是否继续的标志*/判断是询问是否}******************************/voidmain(){charc,a;do{frequency();ctree();ccode();c=translate();/*translate子函数返回值赋给c*/for(;c=='y'||c=='Y';){/*判断是否继续译码*/c=translate();}printf("Inputtextagain(y/n)?");a=getche();}while(a=='y'||a=='Y');/*判断是否循环*/clrscr();get);}