第五次上机报告

1、一、调试成功程序及说明1、题目：树创建；算法：源程序：#include#include#include#include#define LEN sizeof(structHTnode)typedef char *Huffmancode;i,l,n,w=0,c,start,a1,a2,f;struct HTnodeunsignedweight;unsignedparent,lchild,rchild;*p,*HT;select()k=1,j,flag=0;while(HT+k)-parent!=0) k+;for(j=k+1;jparent!=0) flag=1;if(HT+j)-weight=0

2、) flag=1;if(!flag)if(HT+j)-weightweight)k=j;return(k);void main()Huffmancode HC;char*cd;prf(n 赫夫曼树的建立:n);prf(请输入权值(叶子)数目:);scanf(%d,&l);while(l1)prf(输入错误,请重新输入权值数目:);scanf(%d,&l);if(l=1)prf(n 只有一个权值,无须建立赫夫曼树!);elsen=2*l-1;HT=(struct HTnode*)malloc(n+1)*LEN);prf(请按对应顺序输入权值(输入一权值,键入一回车):n);for(i=1,p=H

3、T+1;i=l;+i,+p)scanf(%d,&w);while(wweight=w; p-parent=0;p-lchild=0; p-rchild=0;for(i=l+1;iweight=0;p-parent=0;p-lchild=0;for(i=l+1;iparent=i;a2=select();(HT+a2)-parent=i;(HT+i)-lchild=a1;(HT+i)-rchild=a2;(HT+i)-weight=(HT+a1)-weight+(HT+a2)-weight;HC=(Huffmancode)malloc(l+1)*sizeof(char *);cd=(char *

4、)malloc(l*sizeof(char);*(cd+(l-1)=0;for(i=1;iparent;f!=0;c=f,f=(HT+f)-parent)if(HT+f)-lchild=c)*(cd+(-start)=0;else*(cd+(-start)=1;*(HC+i)=(char *)malloc(l-start)*sizeof(char);strcpy(*(HC+i),(cd+start);prf(n 对应的二进制赫夫曼编码为:n);for(i=1;i=l;+i)prf(%s,*(HC+i);prf();运行结果：赫夫曼树的建立:请输入权值(叶子)数目:4请按对应顺序输入权值(输入一

5、权值,键入一回车):531728对应的二进制赫夫曼编码为:001000011Press any key to continue二、未调试成功程序及说明1、题目：用邻接矩阵结构实现图的基本操作；算法：递归源程序：#include#include#include#include#defineTRUE 1#defineFALSE 0#defineERROR 0#defineOK 1#defineINFINITY10000 /最大值#defineMAX_VERTEX_NUM 20/最大顶点个数#defineMAX_NAME 5/顶点标示最多 5 个字符#defineMAX_INFO 20typedef

6、Sus;typedefVRType;typedefcharInfoType;typedefcharVertexTypeMAX_NAME;typedefenumGraphKindDG,DN,UDG,UDN; /有向图，有向网，无向图，无向网typedefstruct ArcCellVRType adj;/VRType 是顶点关系类型。对无权图，用 1 或 0/表示相邻否；对带权图，则为权值类型。InfoType *info;/该弧相关信息的指针ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef structVertexType vexsMA

7、X_VERTEX_NUM;/顶点向量AdjMatrix arcs;/邻接矩阵um;/图的当前顶点数和弧数GraphKind kind;/图的种类标志MGraph;/寻找图中顶点 u 的位置Sus LocateVex (MGraph G,VertexType u)i;for(i=0;iG.vexnum;+i)if(strcmp(u,G.vexsi)=0)return i;elsereturn -1;/构造图 GSus CreateDG(MGraph &G)/构造有向图 Gi,j,k,l,IncInfo; /IncInfo 为 0 则弧不包括相关信息char sMAX_INFO,*info;Ver

8、texType va,vb;prf(请输入有向图 G 的顶点数，弧数，弧是否有相关信息（是：1，否：0）：);scanf(%d,%d,%d,um,&IncInfo);prf(请输入%d 个顶点的值（%d 个字符）n,&G.vexnum,MAX_NAME);for(i=0;iG.vexnum;+i)/构造顶点向量scanf(%s,G.vexsi);for(i=0;iG.vexnum;+i)for(j=0;jG.vexnum;+j)G.arcsij.adj=0; /图，不相邻G.=NULL; /无相关信息prf(请输入%d 条弧的弧尾，弧头（以空格为间隔）：num);for(

9、k=0;kum;+k)scanf(%s%s%*c,va,vb,&l); /用%*c回车符i=LocateVex(G,va);j=LocateVex(G,vb);G.arcsij.adj=l;/有向图if(IncInfo)prf(请输入关于该弧的相关信息（%d 个字符）：,MAX_INFO);gets(s);l=strlen(s);if(l)info=(char*)malloc(l+1)*sizeof(char);strcpy(info,s);G.=info;/有向G.kind=DG;return OK;Sus CreateDN(MGraph &G)/构造有向网 Gi,j,

10、k,w,IncInfo; /IncInfo 为 0 则弧不包括相关信息char sMAX_INFO,*info;VertexType va,vb;prf(请输入有向网 G 的顶点数，弧数，弧是否有相关信息（是：1，否：0）：);scanf(%d,%d,%d,um,&IncInfo);prf(请输入%d 个顶点的值（%d 个字符）n,&G.vexnum,MAX_NAME);for(i=0;iG.vexnum;+i)/构造顶点向量scanf(%s,G.vexsi);for(i=0;iG.vexnum;+i)for(j=0;jG.vexnum;+j)G.arcsij.adj=INFINITY;/网，

11、不相邻G.=NULL;prf(请输入%d 条弧的弧尾，弧头（以空格为间隔）：num);for(k=0;kum;+k)scanf(%s%s%*c,va,vb,&w); /用%*c回车符i=LocateVex(G,va);j=LocateVex(G,vb);G.arcsij.adj=w;/有向图if(IncInfo)prf(请输入关于该弧的相关信息（%d 个字符）：,MAX_INFO);gets(s);w=strlen(s);if(w)info=(char*)malloc(w+1)*sizeof(char);strcpy(info,s);G.=info;

12、/有向G.kind=DN;return OK;Sus CreateUDG(MGraph &G)/构造无向图 Gi,j,k,l,IncInfo;char sMAX_INFO,*info;VertexType va,vb;prf(请输入无向图 G 的顶点数，边数，边是否含其他信息（是：1 否：0）：);scanf(%d,%d,%d,um,&IncInfo);prf(请输入%d 个顶点的值（%d 个字符）：n,G.vexnum,MAX_NAME);for(i=0;iG.vexnum;+i)scanf(%s,G.vexsi);for(i=0;iG.vexnum;+i)for(j=0;jG.vexnum

13、;+j)G.arcsij.adj=INFINITY;/网，不相邻G.=NULL;prf(请输入%d 条边的顶点 1 顶点 2(以空格为间隔)：num);for(k=0;kum;+k)scanf(%s%s%*c,va,vb,&l);i=LocateVex(G,va);j=LocateVex(G,vb);G.arcsij.adj=G.arcsji.adj=l;/无向图if(IncInfo)prf(请输入该边的相关信息(%d 个字符）,MAX_INFO);gets(s);l=strlen(s);if(l)info=(char*)malloc(l+1)*sizeof(char);

14、strcpy(info,s);G.=G.=info;/无向G.kind=UDG;return OK;Sus CreateUDN(MGraph &G)/构造无向网i,j,k,w,IncInfo;char sMAX_INFO,*info;VertexType va,vb;prf(请输入无向图 G 的顶点数，边数，边是否含其他信息（是：1 否：0）：);scanf(%d,%d,%d,um,&IncInfo);prf(请输入%d 个顶点的值（%d 个字符）：n,G.vexnum,MAX_NAME);for(i=0;iG.vexnum;+i)scanf(%s,

15、G.vexsi);for(i=0;iG.vexnum;+i)for(j=0;jG.vexnum;+j)G.arcsij.adj=0;/G.=NULL;prf(请输入%d 条边的顶点 1 顶点 2(以空格为间隔)：num);for(k=0;kum;+k)scanf(%s%s%*c,va,vb,&w);i=LocateVex(G,va);j=LocateVex(G,vb);G.arcsij.adj=G.arcsji.adj=w;/无向图if(IncInfo)prf(请输入该边的相关信息(%d 个字符）,MAX_INFO);gets(s);w=strlen(s);if(w)in

16、fo=(char*)malloc(w+1)*sizeof(char);strcpy(info,s);G.=G.=info;/无向G.kind=UDG;return OK;Sus CreateGraph(MGraph &G)prf(请输入图 G 的类型(有向图：0，有向网：1，无向图：2，无向网：3):);scanf(%d,&G.kind);switch(G.kind)caseDG:return CreateDG(G); /构造有向图 GcaseDN:return CreateDN(G);/构造有向网 GcaseUDG:return CreateUDG

17、(G);/构造无向网 Gcase UDN:return CreateUDN(G);/构造有向网 Gdefault:return ERROR;/销毁图 GSus DestroyGraph(MGraph &G)i,j;if(G.kind2)/有向for(i=0;ium;i+)/该弧的相关信息（如果有的话）for(j=0;jG.vexnum;j+)if(G.arcsij.adj=1&G.kind=0)|(G.arcsij.adj!=INFINITY&G.kind=1) /有向图的弧或有向网的弧if(G.)/有相关信息free(G.);G.arcsij.in

18、fo=NULL;else/无向for(i=0;iG.vexnum;i+) /该边的相关信息（如果有的话）for(j=i+1;j=G.vexnum|v0)exit(ERROR);elsereturn G.vexsv;/对图中某个顶点赋值Sus PutVex(MGraph&G,VertexType v,VertexTypevalue)k;k=LocateVex(G,v);/k 为顶点v 在图G 中的序号if(k0)return ERROR;strcpy(G.vexsk,value);return OK;/返回第一个邻接点SusAdjVex(MGraph G,VertexTypev)i,j=0,k;

19、k=LocateVex(G,v);if(G.kind=DN|G.kind=UDN)j=INFINITY;for(i=0;iG.vexnum;i+)if(G.arcski.adj!=j)return i;elsereturn NULL;/返回相对于 w 的下一个邻接点Sus NextAdjVex(MGraph G,VertexTypev,VertexTypew)i,j=0,k1,k2;k1=LocateVex(G,v);k2=LocateVex(G,w);if(G.kind=DN|G.kind=UDN)j=INFINITY;for(i=k2+1;iG.vexnum;i+)if(G.arcsk1i

20、.adj!=j)return i;elsereturn -1;/增添新顶点void InsertVex(MGraph &G,VertexTypev)i;strcpy(G.vexsG.vexnum,v); /构造新顶点向量for(i=0;i=G.vexnum;i+)if(G.kind%2)/网G.arcsG.vexnumi.adj=INFINITY;/初始化行邻接矩阵的值（无边或无弧）G.arcsiG.vexnum.adj=INFINITY;/初始化列邻接矩阵的值（无边或无弧）else /图G.arcsG.vexnumi.adj=G.arcsiG.vexnum.adj=0;/初始化行、列邻接矩阵

21、的值（无边或无弧）G.arcsG.=G.arcsiG.=NULL;G.vexnum+;/顶点数增一/删除 G 中顶点 v 和相关的弧Sus DeleteVex(MGraph &G,VertexType v)i,j,k;VRType m=0;k=LocateVex(G,v);/k 为待删除顶点v 的序号if(k0)return ERROR;if(G.kind=DN|G.kind=UDN)/网m=INFINITY;for(j=0;jG.vexnum;j+)if(G.arcsjk.adj!=m) /有入弧或边if(G.) / 有相关

22、信息free(G.);/相关信息um-; /修改弧数if(G.kind=DG|G.kind=DN)/有向for(j=0;jG.vexnum;j+)if(G.arcsjk.adj!=m) /有入弧或边if(G.) / 有相关信息free(G.);/相关信息um-; /修改弧数for(j=k+1;jG.vexnum;j+)strcpy(G.vexsj-1,G.vexsj);for(i=0;iG.vexnum;i+)for(j=k+1;jG.vexnum;j+)G.arcsij-1=G.arcsij;/移动待删除顶点之右的矩阵元素fo

23、r(i=0;iG.vexnum;i+)for(j=k+1;jG.vexnum;j+)G.arcsj-1i=G.arcsji;/移动待删除顶点之下的矩阵元素G.vexnum-;return OK;/增添弧Sus InsertAraph &G,VertexTypev,VertexTypew)i,l,v1,w1;char *info,sMAX_INFO;v1=LocateVex(G,v);/尾w1=LocateVex(G,v);/头if(v10|w11)/无向G.arcsw1v1.adj=G.arcsv1w1.adj;G.=G.;return OK

24、;/删除弧Sus DeleteAraph &G,VertexType v,VertexTypew)v1,w1;v1=LocateVex(G,v);/尾w1=LocateVex(G,v);/头if(v10|w1=2)/无向G.arcsw1v1.adj=G.arcsv1w1.adj;G.=NULL;return OK;Sus visit(VertexType i)prf(%s,i);return OK;bool visitedMAX_VERTEX_NUM ;/标志数组（全局变量）Sus(*VisitFunc)(VertexType);/函数变量/深度优先遍历返回图的信息v

25、oid DFS(MGraph G,v)VertexType w1,v1;w;visitedv=TRUE;/设置标志为 TRUE（已）VisitFunc(G.vexsv);/第v 个结点strcpy(v1,GetVex(G,v);for(w=AdjVex(G,v1);w=0;w=NextAdjVex(G,v1,strcpy(w1,GetVex(G,w)if(!visitedw)DFS(G,w);Sus DFSTraverse(MGraph G,Sus(*Visit)(VertexType)v;VisitFunc=Visit;for(v=0;vG.vexnum;v+)visitedv=FALSE;

26、for(v=0;vnext=NULL;return OK;/元素e 为新的队尾元素Sus EnQueue(LinkQueue &ElemTypee)QueuePtr p;if(!Q.front)prf(队列不存在n);return ERROR;elsep=(QueuePtr)malloc(sizeof(QNode); /动态生成新结点p-data=e;/将 e 的值赋给新结点p-next=NULL; /新结点的指针为空Q.rear-next=p;/原队尾结点的指针域为指向新结点Q.rear=p;/尾指针指向新结点return OK;/判断队列是否为空Sus QueueEmpty(LinkQue

27、ueQ)if(!Q.front)exit(ERROR);elseif(Q.front=NULL)return TRUE;elsereturn FALSE;/删除队头元素，用 e 返回其值Sus DeQueue(LinkQueue &ElemType e)QueuePtr p;if(!Q.front)prf(队列不存在n);return ERROR;elseif(Q.front=Q.rear)/队列为空return ERROR;elsep=Q.front-next; /p 指向队头结点e=p-data;/队头元素赋给 eQ.front-next=p-next;/头结点指向下一个结点if(p=Q.

28、rear)/如果删除的队尾结点Q.rear=Q.front;/修改队尾指针指向头结点free(p);return OK;/广度优先遍历返回图的信息Sus BFSTraverse(MGraph G,Sus(*Visit)(VertexType)v,u,w;VertexType w1,u1;LinkQueue Q;for(v=0;vG.vexnum;v+)visitedv=FALSE; /置初值InitQueue(Q);/置空的辅助队列 Qfor(v=0;v=0;w=NextAdjVex(G,u1,strcpy(w1,GetVex(G,w)if(!visitedw)visitedw=TRUE;Visit(G.vexsw);EnQueue(Q,w);prf(n);/输出邻接矩阵void Display(MGraph G)i,j;char s7,s13;switch(G.kind)case DG: strcpy(s,有向图0);strcpy(s1,弧0);break;case DN: strcpy(s,有向网0);strcpy(s1,弧0);break;case UDG: strcpy(s,无向图0);strcpy(s1,弧0);break;case