数据结构实验六报告
第一篇：数据结构实验六报告
实验六报告
课程名称： 数据结构 实验名称：二叉树的应用
实验日期
2011/11/23
一、实验目的：
掌握赫夫曼二叉树的建立及赫夫曼编码的生成。
二、实验内容与要求：
根据给定的n个权值生成赫夫曼二叉树，输出赫夫曼编码。
三、数据结构设计
顺序表的存储结构，建立了二叉树的关系
Struct HTNode{
int weight;
unsigned int parent,lchild,rchild;};
四、算法设计
1、从数据中选择较小的两个数据元素
void Select(HTNode *HT, const int n, int &a, int &b){ //选择较小的两个元素
} int x,y;
x=y=0x7fff;for(int j=0;j
if(HT[j].parent==0)
if(HT[j].weight
2、建立赫夫曼树
void CreatHuff(HTNode *HT,int *p,const int n){
} int m=2*n-1;int i,a,b;for(i=0;i
Select(HT ,i,a,b);HT[a].parent=HT[b].parent=i;HT[i].weight=HT[a].weight+HT[b].weight;HT[i].lchild=a;HT[i].rchild=b;}
3、生成赫夫曼编码
void HuffCoding(HTNode *HT, Huffcode &HC, const int n){
//
}HC=new
char*[n+1];
char *code=new char[n];code[n-1]='';int i,j,p,k;for(i=0;i
} delete[] code;j=n-1;k=i;while(HT[k].parent){
p=HT[k].parent;if(HT[p].lchild==k)code[--j]='0';else code[--j]='1';k=p;} HC[i]=(char*)malloc((n-j)*sizeof(char));HC[i]=new char[n-j];strcpy(HC[i],&code[j]);
五、测试结果
测试数据一：
测试数据二：
六、心得体会
这次实验是在前面的实验基础之上，加上只用了顺序表的存储结构，所以比较简单。尽管实验内容少，但还是学到一些知识。首先学会了赫夫曼编码的简单实现，认识到其应用的实际价值。然后，学会了用指针数组，前面几次试验有过尝试，但没写成。这次实验最初也是用C++写的，但错误“无法解析的外部符号“public: void __thiscall HuffmanTree::HuffCoding(struct HTNode *,char * * &,int)”(?HuffCoding@HuffmanTree@@
QAEXPAUHTNode@@AAPAPADH@Z)，该符号在函数_main 中被引用”改不过来，所以迫于无奈，只得稍微改成像C的代码。
第二篇：数据结构实验五报告
实验五报告
课程名称： 数据结构 实验名称：二叉树的创建与遍历
实验日期
2011/11/16
一、实验目的：
通过上机实验进一步掌握栈、队列、二叉树的存储结构及基本操作的实现方法。
二、实验内容与要求：
基于二叉链表存储结构实现二叉树的基本运算，要求：
⑴能建立非空二叉树；
⑵实现二叉树的先、中、后序递归遍历算法；
⑶实现二叉树的非递归的先（或中、或后）序遍历算法及层序遍历算法；
⑷记录运行结果并对递归算法和非递归算法的效率加以分析。
三、算法设计 结构体的定义：
typedef struct BiTNote{
struct Node{
};类的定义： class CStack{
//栈 private:
};
class LinkQueue{ //队列 public: BiTree base;BiTree top;int stacksize;//当前空间分配量 static const int STACK_INIT_SIZE=100;static const int STACKINCREMENT=10;CStack();
void Push(BiTree T);//入栈 void Pop(BiTree &T);//出栈 bool StackEmpty();//判断是否是空栈 friend class CBiTree;Node(BiTree &d):num(d),next(NULL){} BiTree num;Node *next;char data;struct BiTNote *lchild,*rchild;}BiTNote,*BiTree;public:
二叉树的遍历及应用实验报告};LinkQueue();bool QueueEmpty();void EnQueue(BiTree &T);void DeQueue(BiTree &T);friend class CBiTree;int length;//队列元素的个数 Node *front;
//队列的头指针 Node *rear;
//队列的尾指针 private: class CBiTree{ public:
};CStack::CStack():stacksize(STACK_INIT_SIZE){ //构造函数，初始化
} void CStack::Push(BiTree T){...} //入栈 void CStack::Pop(BiTree &T){...} //出栈 bool CStack::StackEmpty(){} int i=0;//全局变量
int CBiTree::CreatBiTree(BiTree &T){}//构造二叉树 //LinkQueue类函数的实现 LinkQueue::LinkQueue(){} bool LinkQueue::QueueEmpty(){} void LinkQueue::EnQueue(BiTree &T){} void LinkQueue::DeQueue(BiTree &T){} int CBiTree::PreOrderTraverse1(BiTree T, int(*Visit)(char)){...} //前序遍历（递归）int CBiTree::InOrderTraverse(BiTree T, int(*Visit)(char)){...} //中序遍历（递归）int CBiTree::PostOrderTraverse(BiTree T, int(*Visit)(char)){...}//后序遍历（递归）int CBiTree::PreOrderTraverse2(BiTree T, int(*Visit)(char)){ //前序遍历（非递归）
BiTree p=T;while(p!=NULL||!s.StackEmpty()){ BiTree p=(BiTree)malloc(STACK_INIT_SIZE*sizeof(BiTNote));base=p;top=base;int CreatBiTree(BiTree &T);//建立二叉树
int PreOrderTraverse1(BiTree T,int(*Visit)(char e));
//前序遍历（递归）int PreOrderTraverse2(BiTree T,int(*Visit)(char e));
//前序遍历（非递归）
int InOrderTraverse(BiTree T,int(*Visit)(char e));
//中序遍历（递归）int PostOrderTraverse(BiTree T,int(*Visit)(char e));//后序遍历（递归）int LevelOrderTraverse(BiTree T,int(*Visit)(char e));//层序遍历（非递归）CStack s;LinkQueue link;private:
}
} while(p!=NULL){
} if(!s.StackEmpty()){
} s.Pop(p);p=p->rchild;Visit(p->data);s.Push(p);p=p->lchild;return 1;int CBiTree::LevelOrderTraverse(BiTree T, int(*Visit)(char))//层序遍历（非递归）{
} //main.cpp #include“BiTree.h” #include“Function.h” #include int PrintData(char e){
}
int main(){
CBiTree Tree;BiTree T;T=(BiTree)malloc(sizeof(BiTNote));cout<

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。