第一篇：数据结构huffman编码作业报告
哈夫曼编码与解码
一、设计思想
在设计本程序时，主要用到的算法有如下三个：
一、创建哈夫曼树算法；
二、求哈夫曼编码算法；
三、求哈夫曼解码算法。 创建哈夫曼树算法如下：
1)存储结构：构造由信息元素与对应的权值组成的信息元素结构体来存储已给定的字母与其权重信息；构造由信息元素、权值、当前结点的父结点、左结点、右结点组成的哈夫曼树结点结构体来存储树结点的信息，还会很方便地帮助创建哈夫曼树；构造由信息元素与对应的哈夫曼编码结构体来存储哈夫曼编码信息；方便进行对数据的编码。2)结构体数组处理：哈夫曼树没有度为 1 的结点，若一个哈夫曼树由 n 个叶子结点，则该哈夫曼树共有2n-1个结点。应用以上的原理，根据用户输入的信息元素的个数n开辟大小为2n-1的哈夫曼树数组来满足创建哈夫曼树的需要，并对此数组进行初始化，叶子结点的信息元素与权值即给定的的信息元素与权值；非叶子结点的信息元素与权值设置为空值；所有哈夫曼树结点的父结点、左结点、右结点设置为 0。
3)选择权值最小与次小：在进行比较的过程中循环取出权值进行比较，设置两个s1，s2分别记录本次循环最小与次小的权值，进行下一次的比较选择。返回权值最小与次小的哈夫曼树结点信息。
4)生成小树：应用3)中想法，在用户输入的信息元素中选择权值中最小与次小的元素分别赋值给右叶子结点与左叶子结点，并把这两个权值之和赋值给这两个结点的父结点，记录父结点位置。
5)生成哈夫曼树：再应用3)4)把这些小树的父结点的权值进行比较选择，选择权值比较大的设置为新的右结点的权值，权值比较小的设置为左结点，把这两个权值的和赋值给新的父结点；以此重复进行，最终生成哈夫曼树。 求哈夫曼编码算法如下
1)采用无栈非递归遍历哈夫曼树：每次站在根结点遍历哈夫曼树，直至到达某一个叶子结点为止，并临时用一个数组记录遍历过程中每个结点的状态。编码完成后再复制给哈夫曼编码结构体中的编码数组。
2)遍历与编码：在逻辑上，遍历时向左子时，编码为0，向右子为1，将每次的结点状态记录连接即哈夫曼编码；站在根结点上，若到左子上记录此时的结点状态为0，并把指针指向左子，进行下一次的遍历，若到右结点上记录此时的结点状态1，并把指针指向右子，进行下一次的判断遍历；重复进行，到达某一个叶子结点为止，完毕后，将每次
哈夫曼编码与解码
下面是哈夫曼编码过程的大致过程（如图2）：
图2 为huffman树的各节点进行编码
下面是对指定文件内信息编码的大致过程（如图3）：
图3 信息的编码
哈夫曼编码与解码
{
int j,k;/*找出第一个单节点树*/
for(k=1;k<=i;k++)
{
if(ht[k].parent!=0)
{ } continue;
s1=k;
break;
} /*找出其中权重最小的树*/
for(j=1;j<=i;j++)
{
if(ht[j].parent!=0)
{ } { }
continue;
if(ht[j].weight s1=j; } /*找出第二个单节点树*/ for(k=1;k<=i;k++) { if(ht[k].parent!=0||k==s1){ } continue; s2=k; break; } /*找出其中权重次小的树*/ for(j=1;j<=i;j++) { if(ht[j].parent!=0) { } { continue; if(ht[j].weight s2=j; 哈夫曼编码与解码 cd[--Istart]='0'; } { } else/*右1*/ cd[--Istart]='1'; hc[i]=(char *)malloc((n-Istart)*sizeof(char)); strcpy(hc[i], &cd[Istart]);/*将临时储存的code拷贝至hc中*/ } } free(cd);/*释放cd*/ } void main(){ char text[300];/*声明储存源码或Huffman码的临时数组*/ int i,j,count,choice;/*储存字母数组*/ /*储存字母对应权重的数组*/ char zi[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'}; int w[26]={64,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,18,1,16,1}; huffmantree ht; huffmancode hc; HuffmanTree(ht,w,zi,26);/*生成huffman树*/ huffmancoding(ht,hc,26);/*根据huffman树生成huffman码*/ FILE *fp; printf(“[1]Encoding...n”);printf(“[2]Decoding...n”);scanf(“%d”,&choice);if(choice==1)/*1为编码*/ { char file[20];printf(“Please choice the file:”);/*输入需要编码的文件名*/ scanf(“%s”,file);printf(“******************从%s文件读取字符串******************n”,file);if((fp=fopen(file,“r”))==NULL){ } fgets(text,300,fp);/*从文件中读取字符串*/ fclose(fp);printf(“Source code is:”);/*输出读取的字符串*/ puts(text);printf(“cannot open this filen”); printf(“Please choice function:”);/*选择编码还是译码*/ 哈夫曼编码与解码 } } } printf(“n”);} /*显示由部分电码译码得到的字符，并准备对后面的电码进行译码*/ printf(“%c”,ht[count].letter);count=51; 四、运行结果 下图是对SourceCode.txt文件信息进行编码，所得到的效果图（如图5所示）： 图5 对SourceCode.txt文件进行编码 下图是对CodeFile.txt文件中Huffman码进行译码，所得到的效果图（如图6所示）： 图6 对CodeFile.txt文件中Huffman码进行译码 《数据结构》课程设计报告 题目：HuffMan编码器 数据结构设计报告 计科0403 041106308 雷娜 目 录 一．问题描述 二．基本要求(需求分析) 三．•概要设计(设计思想、实现方法、模块设计) 四．•详细设计(数据结构设计、算法设计、算法分析) 五．测试数据及测试结果 六．课程设计小结(心得体会、存在问题、改进措施) 一． 问题描述 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。 第 1 页 数据结构设计报告 计科0403 041106308 雷娜 但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。二． 基本要求(需求分析) 一个完整的系统应具有以下功能： （1）I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。 （2）E：编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。 （3）D：译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。 （4）P：印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。 （5）T：印哈夫曼树（Tree printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。[测试数据] 用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”。 字符 空格 A B C D E F G H I J K L M 频度 186 13 22 32 103 21 15 47 57 1 20 字符 N O P Q R S T U V W X Y Z 频度 57 15 1 51 80 23 8 1 1[实现提示] （1）编码结果以文本方式存储在文件CodeFile中。 （2）用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示退出运行Quit。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了“Q”为止。 （3）在程序的一次执行过程中，第一次执行I，D或C命令之后，哈夫曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。 三． 概要设计(设计思想、实现方法、模块设计)哈夫曼编码是一种效率比较高的变长无失真信源编码方法，它的平均码长 第 2 页 数据结构设计报告 计科0403 041106308 雷娜 最短，因此是最佳编码。我采用二进制哈夫曼编码。 1． 设计思想 a、原理：构造一个码树。 b、编码步骤： (1)将信源符号按概率从大到小的顺序排列，为方便起见，令p(x1)≥p(x2)≥„≥p(xn)。 (2)对概率最小的两个信源符号求其概率之和，同时给两个符号分别赋予码元“0 ”和“1”。将“概率之和”当作一个新符号的概率，与剩下符号的概率一起，形成一个缩减信源，结果得到一个只包含（n－1）个信源符号的新信源，称为信源的第一次缩减信源,用S1表示。 (3)将缩减信源S1的符号仍按概率从大到小的顺序排列，重复步骤2，得到只含（n－2）个符号的缩减信源S2。 (4)重复上述步骤，直至缩减信源只剩下两个符号为止，此时所剩两个符号的概率之和必为1。 (5)按上述步骤实际上构造了一个码树，从树根到端点经过的树枝即为码字。 2． 实现方法 第一，哈夫曼编码实际上构造了一个码树，码树从最上层的端点开始构造，直到树根束，最后得到一个横放的码树，因此，编出的码是即时码。 第二，哈夫曼编码采用概率匹配方法来决定各码字的码长，概率大的符号对应于短码，概率小的符号对应于长码，从而使平均码长最小。 第三，每次对概率最小的两个符号求概率之和形成缩减信源时，就构造出两个树枝，由于给两个树枝赋码元时是任意的，因此编出的码字并不惟一。 3． 模块设计 第 3 页 数据结构设计报告 计科0403 041106308 雷娜 1．进入的操作界面： （图一） 2．输入字符串，及编码结果 （图二） 3．统计不同字符数及带权路径长度 （图三） 4．各字符编码明细 第 4 页 数据结构设计报告 计科0403 041106308 雷娜 （图四） 四．详细设计(数据结构设计、算法设计、算法分析) （一）数据结构设计 1)结点类型： //huffcode.cpp typedef struct HaffmanTreeNode { char ch, code[15]; int weight; int parent, lchild, rchild;} HTNode, *HaTree; typedef struct { HTNode arr[MAX_NODE]; int total;} HTree; 2)基本操作： 第 5 页 数据结构设计报告 计科0403 041106308 雷娜 int statistic_char(char *text, HTree *t);int create_htree(HTree *t);void coding(HTree *t, int head_i, char *code);void print_htree_ldr(HTree *t, int head_i, int deep, int* path);void code_string(char *text, HTree *t,char *codes); （二）算法设计 在哈夫曼编码过程中，对缩减信源符号按概率由大到小的顺序重新排列时，应使合并后的新符号尽可能排在靠前的位置，这样可使合并后的新符号重复编码次数减少，使短码得到充分利用。 （三）算法分析 (1)有效的信源编码可取得较好的冗余压缩效果。(2)有效的信源编码可使输出码元概率均匀化。 4． 测试数据及测试结果 1．输入简短英文字符串： （图五） 2．输入数字英文混合串： 第 6 页 数据结构设计报告 计科0403 041106308 雷娜 （图六） 3．混合串： （图七） 4．输入复杂无规则长串： （图八） 第 7 页 数据结构设计报告 计科0403 041106308 雷娜 六．课程设计小结(心得体会、存在问题、改进措施) 本次程序设计使我不仅深化理解了教学内容，进一步提高灵活运用数据结构、算法和程序设计技术的能力，而且在总体分析、总体结构设计、算法设计、程序设计、上机操作及程序调试等基本技能方面受到了综合训练。 本次实验我选择Huffman编译码器的课题。帮助我深入研究树的各种存储结构的特性及其应用。由于课程设计着眼于原理与应用的结合，使我学会把书本上和课堂上学到的知识用于解决实际问题，从而培养了一部分计算机软件工作所需要的动手能力。 我通过对Huffman编译码原理的学习，再通过分析、设计、编码、调试等各环节，实现了Huffman编译码器的数据实现和界面实现。在Huffman编译码器数据结构的算法设计中我同时用到了多种技术和方法，如算法设计的构思方法，算法的编码，递归技术，与二叉树和树相关的技术等。从而帮助我深入学习研究了树的各种存储结构的特性及其应用。 为了实现界面友好的要求，我决定采用MFC的界面操作，所以必须以C++为基本语言，但是由于学习数据结构课程是基于PASCAL，实验数据结构部分设计遇到一些语法冲突。但是通过课程实践学习，我又开始熟悉C++的编程环境，从而实现了在不同语言上数据结构思想的统一。 此次课程设计并没有划定具体题目，包括算法需求都由我们度量，思路开阔。我始终和同学探讨并独立研究新的功能的实现。通过尝试来学习，通过实践去理解。 当然，通过多天来的上机实践，我获取了一些心得： 一．充分准备。由于课题宽泛，很多同学去网上下了界面优良的源程序。相对而言在DOS下编程的我开始时很焦急，不知如何实现界面友好。准备充分是很重要的，为了实现MFC，我重新学习了C++语言。 二．冷静，耐心投入。集中精力地编程，不被外界影响，使自己的思路始终连贯不被打断。对待每一个错误，都要仔细分析，太过焦急，不仅不能及时的改正错误，还对后面的编程造成影响。 三．要有一种坚持不懈的毅力，不管自己的程序多么复杂，多么冗长，要坚持不懈的去完成。冷静思考。 四．要对自己有信心，出错是必然的。“屡战屡败，屡败屡战”，不怕受挫的心理承受能力和从零开始的决心是走向成功的必要条件。 五．学会与别人学习讨论，但不依赖别人，可以通过借鉴思路从而创新，但决不照搬别人的东西。 第 8 页 数据结构设计报告 计科0403 041106308 雷娜 通过查找资料，我发现我们做Huffman编码和解码时，一般都要在内存通过指针生成Huffman树，这是一个比较费时间、费空间的过程。实际上，真正的Huffman编码程序经常使用其他更快的数据结构来完成树的生成，如散列等。所以我的课题有待继续学习研究。 •用户手册/使用说明 （图九） 1．在此处输入要编码的字符串，点击进行编码。 2．再次输入时再点击可成功使用，不会受之前结果影响。 •附录(源程序清单)//huffcode.cpp //C编写的源代码，原来含有writef()以及printf(),但由于最终用MFC界面实现，故删去，只作为一 //些功能子函数被MFC的对话框类调用。//另外，对于类型申明等已包含于头文件。#include “stdafx.h” #include “huffcode.h” /* 统计字符出现的频率 */ int statistic_char(char *text, HTree *t){ int i, j; int text_len = strlen(text); t->total = 0; for(i=0;i for(j=0;j if(t->arr[j].ch == text[i]) { 第 9 页 数据结构设计报告 计科0403 041106308 雷娜 t->arr[j].weight ++; break; } if(j==t->total){ t->arr[t->total].ch = text[i]; t->arr[t->total].weight = 1; t->total ++; } } return t->total;} int create_htree(HTree *t){ int i; int total_node = t->total * 2-1;int min1, min2;/* 权最小的两个结点 */ int min1_i, min2_i;/* 权最小结点对应的编号 */ int leaves = t->total; for(i=0;i t->arr[i].parent =-1; t->arr[i].rchild =-1; t->arr[i].lchild =-1; } while(t->total < total_node){ min1 = min2 = MAX_WEIGHT; for(i=0;i 对每一个结点 */ if(t->arr[i].parent ==-1 /* 结点没有被合并 */ && t->arr[i].weight < min2){ /* 结点的权比最小权小 */ if(t->arr[i].weight < min1){ /* 如果它比最小的结点还小 */ min2_i = min1_i;min2 = min1; min1_i = i; min1 = t->arr[i].weight; } else { min2_i = i; min2 = t->arr[i].weight; } } } t->arr[t->total].weight = min1 + min2; t->arr[t->total].parent =-1; t->arr[min1_i].parent = t->total; t->arr[min2_i].parent = t->total; t->arr[t->total].ch = ' '; 第10 页 数据结构设计报告 计科0403 041106308 雷娜 t->total ++; } return 0;} /* 对哈夫曼树进行编码 */ void coding(HTree *t, int head_i, char *code){ if(head_i ==-1)return; if(t->arr[head_i].lchild ==-1 && t->arr[head_i].rchild ==-1){ strcpy(t->arr[head_i].code, code);/ } else { int len = strlen(code); strcat(code, “0”); coding(t, t->arr[head_i].lchild, code); code[len] = '1'; coding(t, t->arr[head_i].rchild, code); code[len] = ' '; } } /* 对字符进行编码 */ void code_string(char *text, HTree *t,char *codes){ int i, j, text_len = strlen(text); int n = 0; for(i=0;i char ch = text[i]; for(j=0;j strcat(codes, t->arr[j].code); break; } } } // DlgString.cpp //作为执行文件，通过MFC的可视化界面实现HuffMan编译码器 #include “stdafx.h” #include “iostream.h” #include “string.h” #include “math.h” #include “HUFFMANTREE.h” #include “DlgString.h” #include “huffcode.h” #ifdef _DEBUG 第11 页 数据结构设计报告 计科0403 041106308 雷娜 #define new DEBUG_NEW #undef THIS_FILE static char THIS_FILE[] = __FILE__;#endif CDlgString::CDlgString(CWnd* pParent /*=NULL*/): CDialog(CDlgString::IDD, pParent){ //{{AFX_DATA_INIT(CDlgString)m_inStr = _T(“");m_outstr = _T(”“);m_wpl = _T(”“);m_number = _T(”“);//}}AFX_DATA_INIT } void CDlgString::DoDataExchange(CDataExchange* pDX){ CDialog::DoDataExchange(pDX);//{{AFX_DATA_MAP(CDlgString)DDX_Control(pDX, IDC_LIST1, m_chars);DDX_Text(pDX, IDC_EDIT_STR, m_inStr);DDX_Text(pDX, IDC_STATIC_OUT, m_outstr);DDX_Text(pDX, IDC_STATIC_WPL, m_wpl);DDX_Text(pDX, IDC_STATIC_NUM, m_number);//}}AFX_DATA_MAP } BEGIN_MESSAGE_MAP(CDlgString, CDialog)//{{AFX_MSG_MAP(CDlgString)ON_NOTIFY(NM_CLICK, IDC_LIST1, OnClickList1)//}}AFX_MSG_MAP END_MESSAGE_MAP() // CDlgString message handlers void CDlgString::OnOK(){ UpdateData(true);// TODO: Add extra validation here m_chars.DeleteAllItems();CBrush brush(RGB(225,30,100)); CClientDC dc(this); dc.FillRect(CRect(630,10,1050,280),&brush);// 清屏 int i,ci,n,nn,wpl,len; 第12 页 数据结构设计报告 计科0403 041106308 雷娜 int x,y,h; HTree t; m_outstr= _T(”“); int path[16]={0}; char code[128] = ”“; char codes[128] = ”“; CString str; char text[128]; strcpy(text,m_inStr); n=statistic_char(text, &t);//n用于存储叶子个数 h=(int)(log(n)/log(2)+1); create_htree(&t);//建树 coding(&t, t.total-1, code);//编码 UpdateData(TRUE); wpl=0; for(ci=1;ci<=n;ci++){ CClientDC *pdc = new CClientDC(this); CPen pen;pen.CreatePen(PS_SOLID,1,RGB(225,250,250));CPen *oldpen =(CPen *)pdc->SelectObject(&pen);//建笔 x=800;y=20;// 原始坐标设定 pdc->MoveTo(x,y);//每次路径都从同一源点开始 str.Format(_T(”%c“),t.arr[ci-1].ch);/*对n个叶子的明细输入列表*/ nn=m_chars.InsertItem(m_chars.GetItemCount(),str); str.Format(_T(”%s“),t.arr[ci-1].code);m_chars.SetItemText(nn,1,str); str.Format(_T(”%d“),t.arr[ci-1].weight);m_chars.SetItemText(nn,2,str); len=strlen(t.arr[ci-1].code);str.Format(_T(”%d“),len);m_chars.SetItemText(nn,3,str); 第13 页 数据结构设计报告 计科0403 041106308 雷娜 wpl+=t.arr[ci-1].weight*len; for(i=0;i { y=y+50; if(t.arr[ci-1].code[i]=='0') //向左 { x=x-8*(h-i+1); pdc->LineTo(x,y); pdc->MoveTo(x,y); if(i==len-1){ str.Format(_T(”%c“),t.arr[ci-1].ch); pdc->TextOut(x,y+10,str);} } else if(t.arr[ci-1].code[i]=='1') { //向右 x=x+8*(h-i+1); pdc->LineTo(x,y); pdc->MoveTo(x,y); if(i==len-1){ str.Format(_T(”%c“),t.arr[ci-1].ch); pdc->TextOut(x,y+10,str);} } } } str.Format(_T(”%d“),wpl); m_wpl=str; //在对话框上显示最短带权路径 str.Format(_T(”%d“),n); m_number=str; //在对话框上显示不同的编码字符总数 UpdateData(false); code_string(text, &t,codes); str.Format(_T(”%s“),codes); m_outstr=str; //在对话框上输出对应于输入字符串的编码结果 UpdateData(false); } void CDlgString::OnClickList1(NMHDR* pNMHDR, LRESULT* pResult){ // TODO: Add your control notification handler code here *pResult = 0;} 第14 页 数据结构设计报告 计科0403 041106308 雷娜 BOOL CDlgString::OnInitDialog()//列表初始化 { CDialog::OnInitDialog(); m_font.CreateFont(17,0,0,0,FW_BLACK, 0,0,0，DEFAULT_CHARSET, OUT_CHARACTER_PRECIS, CLIP_CHARACTER_PRECIS，DEFAULT_QUALITY, DEFAULT_PITCH | FF_DONTCARE, ”Courier New“); m_chars.SetFont(&m_font); m_chars.SetExtendedStyle(LVS_EX_FULLROWSELECT |LVS_EX_GRIDLINES); m_chars.SetBkColor(RGB(100,000,100));m_chars.SetTextColor(RGB(255,255,255));m_chars.SetTextBkColor(RGB(150,010,200));m_chars.InsertColumn(0, ”字符“, LVCFMT_CENTER, 50);m_chars.InsertColumn(1, ”编码“, LVCFMT_CENTER, 100);m_chars.InsertColumn(2, ”频度(权)“, LVCFMT_LEFT, 95); m_chars.InsertColumn(3, ”路径长度", LVCFMT_LEFT, 95); return TRUE;// return TRUE unless you set the focus to a control // EXCEPTION: OCX Property Pages should return FALSE } 第15 页 1.(1)问题的描述：设计一个程序exp1-1.cpp,输出所有小于等于n(n为一个大于二的正整数)的素数。要求：（1）每行输出10个素数;(2)尽可能采用较优的算法。 (2)解决思想：判断一个整数n是否为素数，只需要用2~n-1之间的每一个整数去除，如果都不能被整除，那么m就是一个素数。其实可以简化，n不被被2~n-1之间的每一个整数去除，只需被2~根号n之间的每个数去除就可以了。因为如果n能被2~n-1之间任意整数整除，如果这个数大于根号m，那这个数必定对应的还有一个比根号m小的因子(3)源代码： #include cin>>n;if(n<=2) cout<<“输入错误”; else for(int i=2;i<=n;i++) { flag=0; for(int j=2;j<=(int)sqrt(i);j++) { if(i%j==0) { flag=1; break; } } if(flag==0) { cout< count++; if(count%10==0) cout< } } cout< } return 0;(4)运行结果截图 (5)心得体会:按照素数定义来判断素数时，可以进行一个较为明显的优化，即只需从2枚举到根n即可。 2.(1)问题的描述：编写一个程序exp1-2.cpp,计算任一输入的正整数的各位数字之和，并分析算法的时间复杂度。 (2)解决思想:采用递归的算法，对输入的正整数进行不断的取模运算和取商运算，即可得到该正整数的各位数字之和。时间复杂度为O(1)(3)源代码 exp1-2.cpp #include return 0;} else return n%10 + fun(n/10);} int main(){ int n; cout<<”请输入一个正整数:“; cin>>n; cout<<”各位数字之和是:“< (5)心得体会：当遇到一个复杂问题时，可以从最简单的地方着手，刚开始不知道n是几位数，感觉这个问题有点棘手，心想如果是二位数就好办了，因此脑海中浮现了“递归”的思想，把一个复杂问题转变成简单问题。即把一个正整数n边分解边累加，直到分解完毕。 3.(1)问题的描述：编写一个程序exp1-3.cpp,判断一个字符串是否为“回文”(顺读和倒读都一样的字符串称为“回文”)，并分析算法的时间复杂度。 (2)解决思想：依次将字符串两端的字符进行比较，若都相同，则为回文字符串。时间复杂度为O(n)。(3)源代码： exp1-3.cpp #include int fun(char s[]){ int flag=1;int i,j,n=strlen(s); for(i=0,j=n-1;i if(s[i]!=s[j]) { flag=0; break; } return(flag);} int main(){ char s[MAX];cout<<”输入一串字符串:“;cin>>s;if(fun(s)==1) cout<<”字符串是回文“< cout<<”字符串不是回文"< (5)心得体会：如果将这题进行扩展，判断一个正整数是否为回文数，也可以采用类似的算法。将正整数的各位存到数组里，用i从左到右扫描s，用j从右到左扫描s,若s[i]与s[j]不相等，则退出循环，否则继续比较，直到i 数据结构实验报告二 题目： 用先序递归过程监理二叉树（存储结构：二叉链表） 输入数据按先序遍历输入，当某节点左子树或者右子树为空时，输入‘*’号，如输入abc**d**e**时，得到的二叉树为： 并用如下实力测试： 算法思路： 显然，建立一个二叉链表存储的二叉树，如果不考虑效率要求，考虑到程序的简介性，递归建立和递归遍历是一种很好的办法。 利用C++的类模板的方法实现建立，遍历，输出等二叉树操作。首先利用构造函数实现先序遍历建立二叉树，然后调用类模板中已经声明好的四种遍历函数，将遍历结果输出，检验建立好的二叉树是否为要求的二叉树。 初始化：利用构造函数建立二叉树。采用先序递归的调用方法，构造函数主体如下： template template root = new BiNode //生成一个结点 root->data=aa; root->lchild = Creat(); //递归建立左子树 root->rchild = Creat(); //递归建立右子树 } return root;} 构造这样的函数，可以在输入时，按先序遍历顺序每次输入一个节点的数据，可以实现任意二叉树的构造。 为了检验构造的二叉树是否为预先设想的二叉树，需要遍历二叉树并进行输出。考虑到单一的输出并不能确定唯一的二叉树，因此对遍历二叉树的四种常用发方法，即先序遍历，中序遍历，后续遍历，层次遍历分别实现，通过遍历结果检验构造的二叉树是否为预先设计好的二叉树。 先序遍历：采用递归的方法建立。template xianxu(root->lchild);//先序遍历树的左子树 xianxu(root->rchild);//先序遍历树的右子树 } 中序遍历：递归方法建立： template if(root==NULL)return; //如果节点为空，则返回空 else{ zhongxu(root->lchild); //中序递归遍历root的左子树 cout< //访问根结点 zhongxu(root->rchild); //中序递归遍历root的右子树 } } 后序遍历：递归方法建立： template if(root==NULL) return; //如果节点为空，返回空 else{ houxu(root->lchild); //后序递归遍历root的左子树 houxu(root->rchild); //后序递归遍历root的右子树 cout< //访问根节点 } } 层序遍历：采用非递归方法。利用队列的方法层序遍历二叉树。建立一个队列，在访问一个节点的时候，把它的左孩子和右孩子入队，并且将这个节点出队。当队列为空时，就完成了对二叉树的层序遍历。 template Q[rear++] = root;// 若节点不为空，则该节点入队 while(front!= rear) { q = Q[front++];//只要队列不为空，则节点依次出队 cout< if(q->lchild!= NULL) Q[rear++] = q->lchild; if(q->rchild!= NULL) Q[rear++] = q->rchild;// 同时，该节点的双子入队 } } } 函数主体部分：声明一个类中的对象，调用构造函数，建立二叉树，并输出四种遍历结果，检验输出结果。 int main(){ BiTree BiNode cout<<“前序遍历序列为 ”< 程序结构： 主函数建立一个类模板定义构造函数，析构函数，以及成员函数声明类中的一个对象调用构造函数，构造一颗二叉树层序遍历二叉树后序遍历二叉树中序遍历二叉树前序遍历二叉树获取该二叉树的根节点将结果输出，人工检验 源代码： #include template { T data; BiNode template { public: BiTree(); //构造函数，初始化一棵二叉树 ~BiTree(void); //析构函数，释放二叉链表中各结点的存储空间 BiNode //获得指向根结点的指针 void xianxu(BiNode //前序遍历二叉树 void zhongxu(BiNode //中序遍历二叉树 void houxu(BiNode //后序遍历二叉树 void cengxu(BiNode //层序遍历二叉树 private: BiNode BiNode void Release(BiNode };template template if(aa==“*”)root = NULL; else{ root = new BiNode //生成一个结点 root->data=aa; root->lchild = Creat(); //递归建立左子树 root->rchild = Creat(); //递归建立右子树 } return root;} template template template else{ cout< xianxu(root->lchild);//先序遍历树的左子树 xianxu(root->rchild);//先序遍历树的右子树 } } template if(root==NULL)return; //如果节点为空，则返回空 else{ zhongxu(root->lchild); //中序递归遍历root的左子树 cout< //访问根结点 zhongxu(root->rchild); //中序递归遍历root的右子树 } } template if(root==NULL) return; //如果节点为空，返回空 else{ houxu(root->lchild); //后序递归遍历root的左子树 houxu(root->rchild); //后序递归遍历root的右子树 cout< //访问根节点 } } template const int MaxSize = 100;int front = 0;int rear = 0;//利用队列的方法对树进行层序遍历 BiNode BiNode else{ Q[rear++] = root;// 若节点不为空，则该节点入队 while(front!= rear) { q = Q[front++];//只要队列不为空，则节点依次出队 cout< if(q->lchild!= NULL) Q[rear++] = q->lchild; if(q->rchild!= NULL) Q[rear++] = q->rchild;// 同时，该节点的双子入队 } } } template if(root!= NULL){ Release(root->lchild); //释放左子树 Release(root->rchild); //释放右子树 delete root; } } int main(){ BiTree BiNode cout<<“前序遍历序列为 ”< cout<<“层序遍历序列为”< 通过对结果的分析，发现输出结果与建立二叉树时的输入完全符合，说明程序的运行结果是正确的。 心得体会： 1)函数递归的方法可以在相当程度上使程序简洁，避免代码的冗长复杂。2)构造函数如果带参数，在声明对象的时候应该将实参指出来。但是本题中构造函数位递归调用，初始的根节点的数据值由键盘输入，因此无法在声明对象时引入实参。所以最后选择了无参但是引用了this指针的构造函数。可见，对于构造函数的含参调用应该小心谨慎。 3)编程时，要不停得检验自己的输入与输出，必要的时候需要人工进行计算，以保证程序的运行按照预先的设想。 哈夫曼编码与解码的实现 一、设计思想 (一)哈夫曼树的设计思想 对于一组具有确定权值的叶子结点可以构造出多个具有不同带权路径长度的二叉树，其中具有最小带权路径长度的二叉树称作哈夫曼树或最优二叉树。 首先给定n个权值制造n个只含根结点的二叉树，得到一个二叉树林；再在这二叉树林里面找根结点的权值最小和次小的两棵树作成新的二叉树，其中新的二叉树的根结点的权值为左右子根结点权值之和；最后在二叉树林中把组合过的二叉树删除，再重复第二步，直到最后就剩一颗二叉树的时候得到的这棵二叉树就是哈夫曼树。 （二）哈夫曼编码与解码的设计思想 在数据通讯中，经常要将传送的文字转换为二进制字符0和1组成的二进制串，称这个过程为编码。与子相对的是解码或是译码，就是用与编码相同的方式将二进制串转换称编码前的文字的过程称作解码。在这里是通过哈夫曼树实现编码与解码的，所以称作是哈夫曼编码与解码。 首先输入一个字符串，还有相应的在哈夫曼树里的权值，这样用哈夫曼树把字符串用二进制串代替它，这个过程要注意树和编码问题，其中树的问题在上面已经解决，主要看编码的问题，就是根据我们输入的字符串和权值建立相应的树模型，这一步完成那编码就已经完成了，最后打印就行了；然后就是解码，完成编码相应的解码就相对简单了，就是先找到在编码的时候建的那个模型树，将编码中的二进制串再根据权值转换为相应的字符串，这样一步步解码就行了。 以上就是通过用哈夫曼树进行哈夫曼编码与解码如何实现的主要设计思想。 哈夫曼编码与解码的实现 for(i=n+1;i<=2*n-1;i++) { s1=s2=10000; x1=x2=0; for(j=1;j<=i-1;j++) { if(myHaffTree[j].parent==0&&myHaffTree[j].weight { s2=s1;x2=x1; s1=myHaffTree[j].weight;x1=j; } else if(myHaffTree[j].parent==0&&myHaffTree[j].weight { s2=myHaffTree[j].weight;x2=j; } } myHaffTree[x1].parent=i; myHaffTree[x2].parent=i; myHaffTree[i].weight=s1+s2; myHaffTree[i].lchild=x1; myHaffTree[i].rchild=x2; } } void HaffmanCode(int n){ int start,c,f,i,j,k;char *cd;cd=(char *)malloc(n*sizeof(char));myHaffCode=(struct Coding *)malloc((n+1)*sizeof(struct Coding));cd[n-1]=' ';for(i=1;i<=n;++i){ start=n-1; for(c=i,f=myHaffTree[i].parent;f!=0;c=f,f=myHaffTree[f].parent) if(myHaffTree[f].lchild==c)cd[--start]='0'; else cd[--start]='1'; for(j=start,k=0;j { myHaffCode[i].bit[k]=cd[j]; k++; } myHaffCode[i].ch=myHaffTree[i].ch; myHaffCode[i].weight=myHaffTree[i].weight;} /*取编码对应的权值*/ /*n个叶子结点的哈夫曼编码*/ /*构造n个结点哈夫曼编码*/ /*左右子组合为新树*/ /*分配左右结点*/ /*构造哈夫曼树的非叶子结点*/ /*树的初始化*/ 哈夫曼编码与解码的实现 { for(j=1;j<=m;j++) if(myHaffCode[j].ch==*p) printf(“%sn”,myHaffCode[j].bit);} } void Caozuo_D(int n){ int i,c;char code[1000],*p;printf(“please input the coding：”);scanf(“%s”,code);for(p=code,c=2*n-1;*p!=' ';p++) { if(*p=='0') { c=myHaffTree[c].lchild; { printf(“%c”,myHaffTree[c].ch); c=2*n-1; continue; } } else if(*p=='1') { c=myHaffTree[c].rchild; if(myHaffTree[c].lchild==0) { printf(“%c”,myHaffTree[c].ch); c=2*n-1; continue; } } } printf(“n”);} void main(){ int n; char char1; n=Init(); /*定义字符*/ /*函数的调用*/ /*赋值*/ /*结束*/ /*赋值*/ /* 扫描*/ if(myHaffTree[c].lchild==0) /*结束条件*/ /*进行解码*/ /*输入二进制编码*/ /*解码函数*/ 哈夫曼编码与解码的实现 五、遇到的问题及解决 这部分我主要遇到了如下三个问题，其内容与解决方法如下所列： 问题1: 刚开始不知道如何建一个好树，因为我开始试着建了几个二叉树，不知道什么原因运行的时候那编码总是不对，跟在草稿纸上自己画的那个二叉树总是不相符，就找原因。解决方法: 开始时总是编码出错，就试着找错，树的初始化不可能出错，所以首先看那叶子结点的for函数，没什么错误，接着看非叶子结点的for函数，非叶子结点不好弄，找起来麻烦一些，就是费时间，盘查到最后也没什么错，最后就是左右子结点重生结点的一块了，这也比较好查，可是结果却是错处在这儿了，没想到最放心的一块第二篇：数据结构课程设计报告(HuffMan编码器)
第三篇：数据结构作业
第四篇：数据结构作业——二叉树
第五篇：数据结构__课程设计之哈夫曼编码
点击咨询 