数据结构实验指导书(2016)(6)

void CrtHuffmanTree(HuffmanTree *ht , int n) { /* w存放已知的n个权值，构造哈夫曼树ht */ int m,i,w;

int s1,s2;char c; m=2*n-1;

*ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /*0号单元未使用*/ printf(\输入字符及权重:\\n\ for(i=1;i<=n;i++)

{/*1-n号放叶子结点，初始化*/ fflush(stdin);

scanf(\ (*ht)[i].data = c; (*ht)[i].weight = w; (*ht)[i].LChild = 0; (*ht)[i].parent = 0; (*ht)[i].RChild = 0; }

for(i=n+1;i<=m;i++) {

(*ht)[i].weight = 0; (*ht)[i].LChild = 0; (*ht)[i].parent = 0; (*ht)[i].RChild = 0;

} /*非叶子结点初始化*/ /*创建非叶子结点,建哈夫曼树*/ for(i=n+1;i<=m;i++)

{ /*在(*ht)[1]~(*ht)[i-1]的范围内选择两个parent为0且weight最小的结点，其序号分别赋值给s1、s2返回*/ select(ht,i-1,&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; } }

//中序输出哈夫曼树叶子节点//

void outputHuffman(HuffmanTree HT, int m) { if(m!=0) {

outputHuffman(HT,HT[m].LChild);

第23页 /共58页

if(!HT[m].LChild&&!HT[m].RChild)printf(\ outputHuffman(HT,HT[m].RChild); } }

/*从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码*/ void CrtHuffmanCode(HuffmanTree *ht, HuffmanCode *hc, int n) {

char *cd; int i;

unsigned int c; int start; int p;

hc=(HuffmanCode *)malloc((n+1)*sizeof(char *)); /*分配n个编码的头指针*/ cd=(char * )malloc(n * sizeof(char )); /*分配求当前编码的工作空间*/ cd[n-1]='\\0'; /*从右向左逐位存放编码，首先存放编码结束符*/ for(i=1;i<=n;i++) /*求n个叶子结点对应的哈夫曼编码*/ {

start=n-1; /*初始化编码起始指针*/

for(c=i,p=(*ht)[i].parent; p!=0; c=p,p=(*ht)[p].parent) /*从叶子到根结点求编码*/ if( (*ht)[p].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]); }

free(cd);

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

printf(\编码为%s\\n\}

// 主函数// void main() {

HuffmanTree HT; HuffmanCode HC; int n; int m;

printf(\输入叶子节点的个数:\ scanf(\

CrtHuffmanTree(&HT,n);

m = 2*n-1;printf(\中序输出哈夫曼树叶子节点：\\n\ outputHuffman(HT,m); printf(\

第24页 /共58页

CrtHuffmanCode(&HT,&HC,n); }

实验八图的建立及遍历操作

实验预备知识：

1．掌握图的存储结构和访问。 2．掌握图的遍历及相关操作原理。

一、实验目的

1．掌握图的存储结构和相关操作。

2．能够熟练用计算机来表示图和进行图处理。

二、实验环境

⒈ 硬件：每个学生需配备计算机一台。操作系统：DOS或Windows； ⒉ 软件：DOS或Windows操作系统+Turbo C；

三、实验要求

1．要求对于给定的图分别用邻接矩阵和邻接表来存储。 2．对于存储好的图进行深度和广度优先遍历。 3．完成图的各种操作。

四、实验内容

1．在自己的U盘的“姓名+学号”文件夹中创建“实验8”文件夹，本次实验的所有程序和数据都要求存储到本文件夹中。

2．现在某网络公司的光纤连接结点如下图所示，请分别用邻接矩阵和邻接表将图存储到计算机中方便进行处理。

3．现在公司想知道共有哪些结点及其名称，现在请你用深度优先和广度优先进行遍历。 4．完成如下图中没有实现的操作函数：

第25页 /共58页

#include \#include \#include \#define INFINITY 32767 #define MAX_VERTEX_NUM 20

typedef enum{FALSE,TRUE}visited_hc; typedef enum{DG,DN,UDG,UDN}graphkind_hc;

typedef struct arccell_hc {int adj; int *info;

}arccell_hc,adjmatrix_hc[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct

{char vexs[MAX_VERTEX_NUM]; adjmatrix_hc arcs; int vexnum,arcnum; graphkind_hc kind; }mgraph_hc;

第26页 /共58页

typedef struct arcnode_hc {int adjvex;

struct arcnode_hc *nextarc; int *info; }arcnode_hc;

typedef struct vnode_hc {char data;

arcnode_hc *firstarc;

}vnode_hc,adjlist_hc[MAX_VERTEX_NUM];

typedef struct {adjlist_hc vertices; int vexnum,arcnum; graphkind_hc kind; }algraph_hc;

int locatevex_hc(mgraph_hc*g,char v) {int i,k=0;

for(i=0;ivexnum;i++)

if(g->vexs[i]==v){k=i;i=g->vexnum;} return(k);}

mgraph_hc*createudg_hc() {mgraph_hc*g; char v1,v2; int i,j,incinfo;

g=(mgraph_hc*)malloc(sizeof(mgraph_hc)); g->kind=UDG;

printf(\请输入图顶点数、边数及该边相关信息:\scanf(\printf(\请输入顶点信息:\

for(i=0;ivexnum;++i)scanf(\for(i=0;ivexnum;++i) for(j=0;jvexnum;++j) g->arcs[i][j].adj=0;

printf(\输入一条边依附的顶点:\\n\flushall();scanf(\while(v1!='#'&&v2!='#')

{i=locatevex_hc(g,v1);j=locatevex_hc(g,v2); g->arcs[i][j].adj=1;

if(incinfo)g->arcs[i][j].info=&incinfo; g->arcs[j][i].adj=g->arcs[i][j].adj; g->arcs[j][i].info=g->arcs[i][j].info;

第27页 /共58页