中北大学 算法与数据结构实验报告(8)

else

{ if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) { cout<<\//no alloction return (ERROR); }

T->data=ch;

CreateBiTree(T->lchild); //构造左孩子 CreateBiTree(T->rchild); //构造右孩子 }

return (OK);

} //CreateBiTree() end

int PostOrderTraverse(BiTree T) {//后序遍历二叉树 if(T)

{ if (PostOrderTraverse(T->lchild)) //访问左孩子 if(PostOrderTraverse(T->rchild)) //访问右孩子 { cout<data<<\ //访问根 return (OK); } return (ERROR); } else

return (OK);

} //PostOrderTraverse() end

void main() //main() function { BiTree T;

cout<

cout<

cout<

cout<<\ getch(); } //main()

35

4、建立二叉树算法

# include # include # include

# define OK 1 # define ERROR 0

typedef char TElemType;

typedef struct BiTNode //定义二叉树结点 { TElemType data;

struct BiTNode *lchild,*rchild; }BiTNode, *BiTree;

int CreateBiTree(BiTree &T) //构造二叉树 { TElemType ch;

cout<<\请输入数据(/for NULL node!):\ cin>>ch;

if(ch=='/') T=NULL; else

{ if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) { cout<<\//no alloction return (ERROR); }

T->data=ch;

CreateBiTree(T->lchild); //构造左孩子 CreateBiTree(T->rchild); //构造右孩子 }

return (OK);

} //CreateBiTree() end

36

void main() //main() function { BiTree T;

cout<

cout<

cout<

5、求哈夫曼树及哈夫曼编码算法

# include # include # include # include # include

# define MAX_LENGTH 100 typedef char **HuffmanCode;

typedef struct //定义哈夫曼树的结点 { unsigned int weight;

unsigned int parent,lchild,rchild; }HTNode,*HuffmanTree;

void Select(HuffmanTree HT,int i,int &s1,int &s2) //Select sub-function { int j,k=1; //s1 is the least of HT[].weight while(HT[k].parent!=0) //s2 is the second least of HT[].weight k++; s1=k;

37

for(j=1;j<=i;++j)

if(HT[j].parent==0&&HT[j].weight

while((HT[k].parent!=0||k==s1)) k++; s2=k;

for(j=1;j<=i;++j)

if(HT[j].parent==0&&HT[j].weight

void HuffmanCoding(HuffmanTree &HT,HuffmanCode&HC,int *w,int n)

{//w存放n个字符的权值，构造哈夫曼数HT，并求出n个字符的哈夫曼编码HC int m,i,s1,s2,start,c,f; HuffmanTree p; if(n<=1) return; m=2*n-1;

HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));

//分配m+1个哈夫曼树结点的存储空间，0号单元未用

for(p=HT+1,i=1;i<=n;++i,++p,++w) //初始化HT的前n个分量 { p->weight=*w; cout<parent=0; p->lchild=0; p->rchild=0; }

for(;i<=m;++i,++p) //初始化HT的后m-n个分量 { p->weight=0; p->parent=0; p->lchild=0; p->rchild=0; }

cout<

{ Select(HT,i-1,s1,s2); //s1是最小, s2是第二小 HT[s1].parent=i; HT[s2].parent=i; HT[i].lchild=s1; HT[i].rchild=s2;

HT[i].weight=HT[s1].weight+HT[s2].weight;

cout<

38

}

//线面从叶子结点到根结点逆向求每个字符的哈夫曼编码 HC=(HuffmanCode)malloc((n+1)*sizeof(char *)); char *cd;

cd=(char *)malloc(n*sizeof(char));//分配求编码的工作空间 cd[n-1]='\\0';//编码结束符

cout<

{ start=n-1;//编码结束符位置

for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) //从叶子到根逆向求编码 if(HT[f].lchild==c) cd[--start]='0'; else cd[--start]='1';

HC[i]=(char*)malloc((n-start)*sizeof(char)); //为第i个字符编码分配空间，n-start为第i个字符的编码长 strcpy(HC[i],&cd[start]);//从cd复制编码到HC printf(\的哈夫曼编码是: %s\ }

free(cd);

} //HuffmanCoding() end

void main() //main() function { HuffmanTree HT; HuffmanCode HC; int n,i;

int *w,W[MAX_LENGTH];;

cout<

cout<>n;

for(i=0;i

{ cout<<\请输入\个元素的权重(eg,8): \ cin>>W[i]; } w=W;

HuffmanCoding(HT,HC,w,n); //构造哈夫曼树 cout<

39