数据结构课程设计(赫夫曼树的建立).doc

吉首大学信息科学与工程学院课程设计报告书课 程 数据结构课程设计 课 题： 赫夫曼树的建立 专 业： 计算机科学与技术 年 级： 2012级 指导教师： 基地指导教师： 2014年 6 月一、项目介绍与设计目的 任务：按给定的数据建立赫夫曼树要求：可以建立函数输入二叉树，并输出其赫夫曼树目的：了解和认识赫夫曼树，进一步学习数据结构，提高编程能力二、设计方案1项目环境要求电脑、 Visual C+ 6.02项目功能模块3 设计内容HuffmanTree.h文件：#include #include #include using namespace std;class HTNode friend class MyHuffmanTree;public: char charater;/元素值(字符) int weight;/权值(频率) string code;/Huffman编码 HTNode *left;/左孩子 HTNode *right;/右孩子 HTNode (char c=0, int w=0) charater=c; weight=w; left=right=NULL; bool operator (HTNode & target) if( weight target.weight ) return true; else return false; /operator bool operator (HTNode * target) if( weight target-weight ) return true; else return false; friend ostream & operator (ostream &cout, HTNode * target) coutchar: charatertweight: weight coderight & NULL=target-left) coutcharater weight codecode=;/root的Huffman编码 stack aStack;/存储未访问元素的栈 HTNode * temp =root; aStack.push(NULL);/栈底监视哨 while(temp) if(NULL != temp-right ) temp-right-code=temp-code + 1; aStack.push(temp-right); if( NULL != temp-left ) temp-left-code=temp-code + 0; temp=temp-left; else/左子树访问完毕，转向访问右子树 temp=aStack.top(); aStack.pop(); /while /Huffman编码函数public: MyHuffmanTree(HTNode * r) root=r; HuffmanCode(root); /构造函数 MyHuffmanTree()DeleteTree(root); /析构函数 void DeleteTree(HTNode *root) if(NULL!=root) DeleteTree(root-left); DeleteTree(root-right); delete root; /销毁树函数 void InOrder(HTNode * root) if(NULL!=root) InOrder(root-left); visit(root); InOrder(root-right); /中序周游 HTNode * Root() return root;/返回跟结点函数main文件：#include HuffmanTree.h#include MinHeap.h#include #include #include using namespace std;int main () int f128=0;/频率表 char c;/读入字符 /打开文件 ifstream fin(input.txt); if(!fin) coutc; fc+; MinHeap heap(128); HTNode * p;/建堆用指针 HTNode *first , * second , *pa; for(int i=0;iweight+second-weight); pa-left=first; pa-right=second; heap.insert(pa); pa=heap.min(); heap.remove(0); MyHuffmanTree mht(pa); mht.InOrder(mht.Root(); return 0;最小堆MinHeap.h文件：#include using namespace std;template class MinHeapprivate: T * heapArray ; /存放堆数据的数组 int CurrentSize ; /当前堆中的元素数目 int MaxSize ; /最大元素数目 void swap( int pos_x, int pos_y ) /交换位置xy的元素的函数 if( pos_x0 | pos_y0 ) return ; T temp ; temp=heapArraypos_x; heapArraypos_x=heapArraypos_y; heapArraypos_y=temp; public: MinHeap( const int size ) /构造函数，size为堆的最大元素数目 if( size= CurrentSize/2) & ( pos CurrentSize ); int leftchild( int pos ) /返回左孩子位置的函数 return ( 2 * pos + 1 ); int rightchild( int pos )/返回右孩子位置的函数 return ( 2 * pos + 2 ); int Parent( int pos ) /返回父结点位置的函数 return ( (pos-1) / 2 ); int Pos( T value ) /找出值为value的元素在堆中位置的函数 for(int i=0; iMaxSize; i+) if( heapArrayi = value ) return i ; return -1 ;/pos bool insert( const T & newNode )/向堆中插入新元素newNode /判断堆是否已满 if ( CurrentSize = MaxSize )/堆已满 cout堆已满endl; return false; /堆未满 heapArrayCurrentSize= newNode ;/新元素newNode放到堆的末尾 SiftUp( CurrentSize ); /向上调整 CurrentSize + ; /堆的当前元素数加1 return true ; /insert bool remove( int pos)/删除给定下标的元素 /判断下标是否越界 if ( (pos = CurrentSize) ) return false ; /下标未越界 heapArraypos=heapArray-CurrentSize;/用最后的元素值代替被删除的元素 if( pos = 0 ) SiftDown(pos); if ( heapArrayParent(pos) heapArraypos ) SiftUp(pos); else SiftDown(pos); return true ; /remove T & min() /返回最小值元素 return heapArray0 ; void SiftUp( int pos ) /从pos开始向上调整 int temppos=pos; T temp = heapArraytemppos; while( (temppos0) & (heapArrayParent(temppos) temp) ) heapArraytemppos=heapArrayParent(temppos); temppos=Parent(temppos); heapArraytemppos=temp ; /SiftUp void SiftDown ( int pos )/从pos开始向下调整 int i = pos ; /标识父结点 int j = leftchild(i);/用于记录关键值较小的子结点 T temp = heapArrayi;/记录父结点元素值 while( j CurrentSize) if( (j heapArrayj+1) )/若有右子结点且小于左子结点 j+; /j指向小的右子结点 if ( temp heapArrayj )/若父结点的值大于子结点的值则交换 heapArrayi=heapArrayj; i=j; j=leftchild(j); /if else break ; /父结点=子结点满足堆序跳出 /while heapArrayi=temp; /SiftDown void display()/显示堆中内容 int i ; for(i=0; iCurrentSize; i+) coutheapArrayi; /display T & RemoveMin() if(CurrentSize=0) cout 1) SiftDown(0); return heapArrayCurrentSize; /else /RemoveMin int GetCurrentSize() return CurrentSize ;程序运行结果： 输入：2 4 6 8 10 权：1 3 5 7 9输出：三、总结和分析 经过这次程序设计，我深刻的认识到，编写的程序不但要拿来使用，还要给别人查看，以便代码的维护。所以代码编写的风格尽量规范，清晰。代码较为冗余，可读性较差，可以多添加一些提示语句以及注释。 在这次课程设计中我又进一步地了解了