《算法与数据结构》实验指导书

for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) //从叶子到根逆向求编码 if(HT[f].lchild==c) cd[--start]='0'; //若是左孩子编为'0' else cd[--start]='1'; //若是右孩子编为'1' HC[i]=(char *)malloc((n-start)*sizeof(char)); //为第i个编码分配空间 strcpy(HC[i],&cd[start]); //将编码从cd复制到HC中 }

free(cd); //释放工作空间 }

void PrintHuffmanCode(HuffmanCode HC,unsigned int *w,int n) {//显示有n个叶子结点的哈夫曼树的编码表 int i;

printf("HuffmanCode is :\n"); for(i=1;i<=n;i++)

{printf(" %3d---",w[i-1]); puts(HC[i]); }

printf("\n"); }

void Select(HuffmanTree HT,int t,int&s1,int&s2)

{//在HT[1...t]中选择parent不为0且权值最小的两个结点，其序号分别为s1和s2 int i,m,n;

m=n=10000; for(i=1;i<=t;i++)

{if(HT[i].parent==0&&(HT[i].weight<m||HT[i].weight<n)) if(m<n) {n=HT[i].weight;s2=i;} else {m=HT[i].weight;s1=i;} }

if(s1>s2) //s1放较小的序号 {i=s1;s1=s2;s2=i;} }

六、选作实验

给定权值5,29,7,8,14,23,3,11，建立哈夫曼树，输出哈夫曼编码。

实验七 图的遍历操作

一、实验目的：

掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储结构；掌握DFS、BFS的基本思想及对图的遍历操作；了解图结构在人工智能、工程等领域的广泛应用。

二、实验内容：

设计一个有向图和一个无向图，任选一种存储结构，完成有向图和无向图的DFS（深