maxleaf（tonbridge）

赫夫曼树注：第一题 huffman 树以及 huffman编码我将第二题与第三题与用邻接矩阵存储图相关的操作放在了一起完成第三题则是利用邻接表1.第一题#include#include#include#include#define LEN 8 #define MAXLEAF 6 //最大叶子结点数目 #define MAXNODE (MAXLEAF*2)-1typedef float ElemType;typedef struct /* this structure stores the information of code */{ int start; /* 存放编码的起始位置右至左（高位至低位）*/ int bit[LEN]; /* 存放 huffman编码 */}HCode;typedef HCode HuffCode[MAXLEAF];typedef struct /* huffman tree结点的结构 */{ int parent; int LChild; int RChild; ElemType weight;}HNode;typedef HNode Huffman[MAXLEAF*2-1]; void createHuffmanTree(Huffman h,int leaves,ElemType *weight){ int i,j; for(i=0;iparent=-1; (h+i)->LChild=-1; (h+i)->RChild=-1; (h+i)->weight=0; } for(i=0;iweight=*(weight+i); } /* 上一个循环叶子已经带权,下面这个循环用来生成新根 * 新根数量为n-1 */ for(i=0;iweightparent==-1) { m2=m1; m1=(h+j)->weight; m2_pos=m1_pos; m1_pos=j; }else if((h+j)->weightparent==-1) { m2=(h+j)->weight; m2_pos=j; } } (h+leaves+i)->parent=-1; //生成新根，无双亲-1 (h+leaves+i)->LChild=m1_pos; //新根左孩子在数组中的下标 (h+leaves+i)->RChild=m2_pos; //新根右孩子在数组中的下标 (h+m1_pos)->parent=leaves+i; //原根的父亲位置 (h+m2_pos)->parent=leaves+i; //原根的父亲位置 (h+leaves+i)->weight=m2+m1; }}void huffmancode(Huffman h,HuffCode code,int leaves){ int i,j,p,c; HCode hf; /*从叶子结点开始向上回溯 从而计算出huffman code */ for(i=0;ib /\ | c首先输入顶点与弧的数目 3 2提示输入顶点abc输入弧（弧头弧尾）abca那些插入以及删除的操作已经放入主函数顾回车后可以看到进行相关操作后图的变化#include#include#define MAXVERT 10 //需要在图中进行插入操作所以设定一个最大值 #define INFINITE 32767#define ERROR -1#define FALSE 0#define OK 1typedef int ElemType;enum maritype{DG,UDG,DN,UDN};typedef struct{ char vertex[MAXVERT]; ElemType arc[MAXVERT][MAXVERT]; int ArcNum; int VertexNum;}adjacentMatrix;int locate(adjacentMatrix *G,char v){ int i, k=ERROR; for(i=0;iVertexNum;i++) { if(G->vertex[i]==v) { k=i; break; } } return(k);} void init(adjacentMatrix *G){ int i,j; for(i=0;iVertexNum;i++) { for(j=0;jVertexNum;j++) { G->arc[i][j]=0; } }}void createDN(adjacentMatrix *G){ int i,j,k; char v1,v2,blank; printf("请输入顶点与弧的数目 \n"); scanf("%d%d",&G-;>VertexNum,&G-;>ArcNum); init(G); printf("请输入顶点（用字母表示）:\n"); getchar(); for(i=0;iVertexNum;i++) { scanf("%c",&G-;>vertex[i]); } getchar(); for(i=0;iArcNum;i++) { printf("请输入弧%d的弧头与弧尾",i+1); scanf("%c%c",&v1;,&v2;); getchar(); j=locate(G,v1); k=locate(G,v2); G->arc[j][k]=1; }}int InsertVex(adjacentMatrix *G,char v) /* insert vertex */{ int i; if(G->VertexNum>MAXVERT-1) { return(FALSE); } G->vertex[G->VertexNum++]=v; for(i=0;iVertexNum;i++) { G->arc[i][G->VertexNum-1]=G->arc[G->VertexNum-1][i]=0; } return(OK);}int InsertAar(adjacentMatrix *G,char v,char w) //插入边{ int i,j; i=locate(G,v); j=locate(G,w); if(i==-1||j==-1) { return(FALSE); } G->arc[i][j]=1; return(OK);}int DeleteVex(adjacentMatrix *G,char v) //（删除顶点）{ int i, k; k=locate(G,v); if(k==-1) { printf("The vertex has not found\n"); return(FALSE); } for(i=k;iVertexNum;i++) { G->vertex[i]=G->vertex[i+1]; } --G->VertexNum; return(OK);}int DeleteArc(adjacentMatrix *G,char v,char w){ int i,j; i=locate(G,v); j=locate(G,w); if(i==-1||j==-1) { return(ERROR); } G->arc[i][j]=0; return(OK);}void degree(adjacentMatrix *G){ int i, j, odsum, idsum, zero=0; for(i=0;iVertexNum;i++) { odsum=0; idsum=0; for(j=0;jVertexNum;j++) { odsum+=G->arc[i][j]; idsum+=G->arc[j][i]; } if(!odsum) { ++zero; } printf("顶点 %c 的出度与入度是",G->vertex[i]); printf("%3d%3d\n",odsum,idsum); } printf("度为0的顶点 %d\n",zero);}void print(adjacentMatrix *G){ int i,j; for(i=0;iVertexNum;i++) { printf("%8c",G->vertex[i]); } printf("\n"); for(i=0;iVertexNum;i++) { for(j=0;jVertexNum;j++) { if(!j) { printf("%c",G->vertex[i]); } printf("%8d",G->arc[i][j]); } printf("\n"); }}int main(void){ int k; char v, w; adjacentMatrix G; createDN(&G;); print(&G;); //邻接矩阵打印 degree(&G;); //求所有顶点出度入度 及度为0的点 InsertVex(&G;,"f"); //插入顶点f InsertAar(&G;,"f","c"); //插入边 fc degree(&G;); //观察插入边顶点后度的变化 print(&G;); //邻接矩阵打印 DeleteArc(&G;,"f","c"); //删除边 fc print(&G;); //邻接矩阵打印 观察变化 DeleteVex(&G;,"a"); //删除顶点a print(&G;); //邻接矩阵打印 观察删除顶点a后变化 system("pause"); return(0);}3.使用同上 示例图也如上所画 使用方式也基本一直按你的要求只输出 顶点的出度入度以及度为0的顶点#include#include#define MAX_VERTEX_NUM 10#define ERROR -1#define FALSE 0#define OK 1typedef char VertexType;typedef struct ArcNode //边表的结构 { int adjvex; //与顶点相邻接的顶点在表头结点表（图中）的位置 struct ArcNode *nextarc;}ArcNode;typedef struct VertexNode //表头结点表的结构 { VertexType data; ArcNode *firstarc;}VertexNode;typedef struct //存放图信息的结构 { int vexnum, arcnum; //顶点与弧的数目 VertexNode vertex[MAX_VERTEX_NUM];}Adjlist;int locate(Adjlist *G,char v){ int i, k=ERROR; for(i=0;ivexnum;i++) { if(G->vertex[i].data==v) { k=i; break; } } return(k);} void createDG(Adjlist *G){ int i, j, k; char v1, v2; ArcNode *s; printf("输入顶点与弧的数目 \n"); scanf("%d%d",&G-;>vexnum,&G-;>arcnum); getchar(); printf("请输入顶点（用字母表示）:"); for(i=0;ivexnum;i++) //生成表头结点表 { scanf("%c",&G-;>vertex[i].data); G->vertex[i].firstarc=NULL; } getchar(); for(i=0;iarcnum;i++) { printf("请输入第%d条边的信息 弧尾与弧头:",i+1); scanf("%c%c",&v1;,&v2;); getchar(); j=locate(G,v1); k=locate(G,v2); s=(ArcNode *)malloc(sizeof(ArcNode)); s->adjvex=k; s->nextarc=G->vertex[j].firstarc; G->vertex[j].firstarc=s; } }void od(Adjlist *G){ int odsum, i; ArcNode *p; for(i=0;ivexnum;i++) //生成表头结点表 { odsum=0; p=G->vertex[i].firstarc; while(p) { ++odsum; p=p->nextarc; } printf("\n%c的出度是:%d\n ",G->vertex[i].data,odsum); }}void ind(Adjlist *G){ int insum, i, j, k; ArcNode *p; for(i=0;ivexnum;i++) //生成表头结点表 { insum=0; for(j=0;jvexnum;j++) { if(i==j) { continue; } p=G->vertex[j].firstarc; while(p) { if(p->adjvex==i) { ++insum; } p=p->nextarc; } } printf("\n%c的入度是:%d\n ",G->vertex[i].data,insum); }}int main(void){ Adjlist G; int i; createDG(&G;); od(&G;); ind(&G;); system("pause"); return(0);}哈夫曼树及哈夫曼编码的C程序实现(数据结构题)去年做的课程设计，有什么不合要求的自己改改 #include #include #include int m,s1,s2; typedef struct { unsigned int weight; unsigned int parent,lchild,rchild; }HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树 typedef char *HuffmanCode; //动态分配数组存储哈夫曼编码表 void Select(HuffmanTree HT,int n) { int i,j; for(i = 1;i HT[i].weight)&&(!HT[i].parent)&&(s2!=i))s1=i; for(j = 1;j HT[j].weight)&&(!HT[j].parent)&&(s1!=j))s2=j; } void HuffmanCoding(HuffmanTree &HT;, HuffmanCode HC[], int *w, int n) { //算法6.13 //w存放n个字符的权值(均>0)，构造哈夫曼树HT， //并求出n个字符的哈夫曼编码HC int i, j; char *cd; int p; int cdlen; if (n