北京交通大学数据结构上机实验4.docx
- 文档编号:14554590
- 上传时间:2023-06-24
- 格式:DOCX
- 页数:25
- 大小:21.81KB
北京交通大学数据结构上机实验4.docx
《北京交通大学数据结构上机实验4.docx》由会员分享,可在线阅读,更多相关《北京交通大学数据结构上机实验4.docx(25页珍藏版)》请在冰点文库上搜索。
北京交通大学数据结构上机实验4
一)建立一个无向图+遍历+插入
(1)以数组表示法作为存储结构,从键盘依次输入顶点数、弧数与各弧信息建立一个无向图;
(2)对
(1)中生成的无向图进行广度优先遍历并打印结果;
(3)向
(1)中生成的无向图插入一条新弧并打印结果;
#include
#include
#include
#include
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineOVERFLOW-2
#defineMAX_NAME5/*顶点字符串的最大长度+1*/
#defineMAX_INFO20/*相关信息字符串的最大长度+1*/
#defineINFINITYINT_MAX/*用整型最大值代替∞*/
#defineMAX_VERTEX_NUM20/*最大顶点个数*/
typedefintBoolean;
Booleanvisited[MAX_VERTEX_NUM];/*访问标志数组(全局量)*/
typedefintStatus;
typedefintVRType;
typedefcharInfoType;
typedefcharVertexType[MAX_NAME];
typedefenum{DG,DN,AG,AN}GraphKind;/*{有向图,有向网,无向图,无向网}*/
typedefstruct
{
VRTypeadj;/*顶点关系类型。
对无权图,用1(是)或0(否)表示相邻否;*/
/*对带权图,c则为权值类型*/
InfoType*info;/*该弧相关信息的指针(可无)*/
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedefstruct
{
VertexTypevexs[MAX_VERTEX_NUM];/*顶点向量*/
AdjMatrixarcs;/*邻接矩阵*/
intvexnum,arcnum;/*图的当前顶点数和弧数*/
GraphKindkind;/*图的种类标志*/
}MGraph;
intLocateVex(MGraphG,VertexTypeu)
{/*初始条件:
图G存在,u和G中顶点有相同特征*/
/*操作结果:
若G中存在顶点u,则返回该顶点在图中位置;否则返回-1*/
inti;
for(i=0;i if(strcmp(u,G.vexs[i])==0) returni; return-1; } StatusCreateAG(MGraph&G) {/*采用数组(邻接矩阵)表示法,构造无向图G*/ inti,j,k,l,IncInfo; charch,s[MAX_INFO],*info; VertexTypeva,vb; printf("请输入无向图G的顶点数,边数,边是否含其它信息(是: 1,否: 0): "); scanf("%d%d%d",&G.vexnum,&G.arcnum,&IncInfo); printf("请输入%d个顶点的值(<%d个字符): \n",G.vexnum,MAX_NAME); for(i=0;i scanf("%s",G.vexs[i]); for(i=0;i for(j=0;j { G.arcs[i][j].adj=0;/*图*/ G.arcs[i][j].info=NULL; } printf("请输入%d条边的顶点1顶点2(以空格作为间隔): \n",G.arcnum); for(k=0;k { scanf("%s",va); scanf("%s",vb); ch=getchar(); i=LocateVex(G,va); j=LocateVex(G,vb); G.arcs[i][j].adj=G.arcs[j][i].adj=1;/*无向图*/ if(IncInfo) { printf("请输入该边的相关信息(<%d个字符): ",MAX_INFO); scanf("%s",s); l=strlen(s); if(l) { info=(char*)malloc((l+1)*sizeof(char)); strcpy(info,s); G.arcs[i][j].info=G.arcs[j][i].info=info;/*无向*/ } } if(k printf("请输入下一条边的顶点1顶点2: \n"); } G.kind=AG; returnOK; } typedefVRTypeQElemType;/*队列类型*/ typedefstructQNode { QElemTypedata; structQNode*next; }QNode,*QueuePtr; typedefstruct { QueuePtrfront,rear;/*队头、队尾指针*/ }LinkQueue; StatusInitQueue(LinkQueue*Q) {/*构造一个空队列Q*/ (*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode)); if(! (*Q).front) exit(OVERFLOW); (*Q).front->next=NULL; returnOK; } StatusQueueEmpty(LinkQueueQ) {/*若Q为空队列,则返回TRUE,否则返回FALSE*/ if(Q.front==Q.rear) returnTRUE; else returnFALSE; } StatusEnQueue(LinkQueue*Q,QElemTypee) {/*插入元素e为Q的新的队尾元素*/ QueuePtrp=(QueuePtr)malloc(sizeof(QNode)); if(! p)/*存储分配失败*/ exit(OVERFLOW); p->data=e; p->next=NULL; (*Q).rear->next=p; (*Q).rear=p; returnOK; } StatusDeQueue(LinkQueue*Q,QElemType*e) {/*若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR*/ QueuePtrp; if((*Q).front==(*Q).rear) returnERROR; p=(*Q).front->next; *e=p->data; (*Q).front->next=p->next; if((*Q).rear==p) (*Q).rear=(*Q).front; free(p); returnOK; } voidVisit(VertexTypeV) { printf("%s",V); } intFirstAdjVex(MGraphG,VertexTypev) {/*初始条件: 图G存在,v是G中某个顶点*/ /*操作结果: 返回v的第一个邻接顶点的序号。 若顶点在G中没有邻接顶点,则返回-1*/ inti,j=0,k; k=LocateVex(G,v);/*k为顶点v在图G中的序号*/ for(i=0;i if(G.arcs[k][i].adj! =j) returni; return-1; } intNextAdjVex(MGraphG,VertexTypev,VertexTypew) {/*初始条件: 图G存在,v是G中某个顶点,w是v的邻接顶点*/ /*操作结果: 返回v的(相对于w的)下一个邻接顶点的序号,*/ /*若w是v的最后一个邻接顶点,则返回-1*/ inti,j=0,k1,k2; k1=LocateVex(G,v);/*k1为顶点v在图G中的序号*/ k2=LocateVex(G,w);/*k2为顶点w在图G中的序号*/ for(i=k2+1;i if(G.arcs[k1][i].adj! =j) returni; return-1; } VertexType*GetVex(MGraphG,intv) {/*初始条件: 图G存在,v是G中某个顶点的序号。 操作结果: 返回v的值*/ if(v>=G.vexnum||v<0) exit(ERROR); return&G.vexs[v]; } voidBFSTraverse(MGraphG) {/*初始条件: 图G存在,Visit是顶点的应用函数。 算法7.6*/ /*操作结果: 从第1个顶点起,按广度优先非递归遍历图G,并对每个顶点调用函数*/ /*Visit一次且仅一次。 一旦Visit()失败,则操作失败。 */ /*使用辅助队列Q和访问标志数组visited*/ intv,u,w; VertexTypew1,u1; LinkQueueQ; for(v=0;v visited[v]=FALSE;/*置初值*/ InitQueue(&Q);/*置空的辅助队列Q*/ printf("按广度优先遍历图: \n"); for(v=0;v if(! visited[v])/*v尚未访问*/ { visited[v]=TRUE;/*设置访问标志为TRUE(已访问)*/ Visit(G.vexs[v]); EnQueue(&Q,v);/*v入队列*/ while(! QueueEmpty(Q))/*队列不空*/ { DeQueue(&Q,&u);/*队头元素出队并置为u*/ strcpy(u1,*GetVex(G,u)); for(w=FirstAdjVex(G,u1);w>=0;w=NextAdjVex(G,u1,strcpy(w1,*GetVex(G,w)))) if(! visited[w])/*w为u的尚未访问的邻接顶点的序号*/ { visited[w]=TRUE; Visit(G.vexs[w]); EnQueue(&Q,w); } } } printf("\n"); } StatusInsertArc(MGraph&G,VertexTypev,VertexTypew) {/*初始条件: 图G存在,v和W是G中两个顶点*/ /*操作结果: 在G中增添弧 inti,l,v1,w1; char*info,s[MAX_INFO]; v1=LocateVex(G,v);/*尾*/ w1=LocateVex(G,w);/*头*/ if(v1<0||w1<0) returnERROR; G.arcnum++;/*弧或边数加1*/ G.arcs[v1][w1].adj=1; printf("是否有该弧或边的相关信息(0: 无1: 有): "); scanf("%d%*c",&i); if(i) { printf("请输入该弧或边的相关信息(<%d个字符): ",MAX_INFO); gets(s); l=strlen(s); if(l) { info=(char*)malloc((l+1)*sizeof(char)); strcpy(info,s); G.arcs[v1][w1].info=info; } } G.arcs[w1][v1].adj=G.arcs[v1][w1].adj; G.arcs[w1][v1].info=G.arcs[v1][w1].info;/*指向同一个相关信息*/ returnOK; } voidDisplay(MGraphG) {/*输出邻接矩阵G*/ inti,j; chars[7],s1[3]; switch(G.kind) { caseDG: strcpy(s,"有向图\0"); strcpy(s1,"弧\0"); break; caseDN: strcpy(s,"有向网\0"); strcpy(s1,"弧\0"); break; caseAG: strcpy(s,"无向图\0"); strcpy(s1,"边\0"); break; caseAN: strcpy(s,"无向网\0"); strcpy(s1,"边\0"); } printf("%d个顶点%d条%s的%s\n",G.vexnum,G.arcnum,s1,s); for(i=0;i printf("G.vexs[%d]=%s\n",i,G.vexs[i]); printf("G.arcs.adj: \n");/*输出G.arcs.adj*/ for(i=0;i { for(j=0;j printf("%6d",G.arcs[i][j].adj); printf("\n"); } printf("G.arcs.info: \n");/*输出G.arcs.info*/ printf("顶点1(弧尾)顶点2(弧头)该%s信息: \n",s1); for(i=0;i for(j=i+1;j if(G.arcs[i][j].info) printf("%5s%11s%s\n",G.vexs[i],G.vexs[j],G.arcs[i][j].info); } voidmain() { charch; VertexTypeva,vb; MGraphG; CreateAG(G); Display(G); printf("\n"); BFSTraverse(G); printf("\n"); printf("请输入要插入的弧所连接的顶点: "); scanf("%s",va); scanf("%s",vb); //ch=getchar(); InsertArc(G,va,vb); Display(G); printf("\n"); BFSTraverse(G); } 二)建立一个有向图+遍历+插入+删除 (1)以邻接表作为图的存储结构,从键盘输入图的顶点与弧的信息建立一个有向图; (2)对 (1)中生成的有向图进行深度优先遍历并打印结果; (3)在 (1)中生成的有向图中,分别插入与删除一条弧并打印其结果; (4)在 (1)中生成的有向图中,分别插入与删除一个顶点并打印结果; (5)在 (1)中生成的有向图中,各顶点的入度与出度并打印结果; #include #include #include #include #defineTRUE1 #defineFALSE0 #defineOK1 #defineERROR0 #defineOVERFLOW-2 #defineMAX_VERTEX_NUM20 #defineMAX_NAME5/*顶点字符串的最大长度+1*/ typedefintBoolean; Booleanvisited[MAX_VERTEX_NUM];/*访问标志数组(全局量)*/ typedefintStatus; typedefintVRType; typedefcharInfoType; typedefcharVertexType[MAX_NAME]; typedefenum{DG,DN,AG,AN}GraphKind;/*{有向图,有向网,无向图,无向网}*/ typedefstructArcNode { intadjvex;/*该弧所指向的顶点的位置*/ structArcNode*nextarc;/*指向下一条弧的指针*/ InfoType*info;/*网的权值指针)*/ }ArcNode; typedefstruct { VertexTypedata;/*顶点信息*/ ArcNode*firstarc;/*第一个表结点的地址,指向第一条依附该顶点的弧的指针*/ }VNode,AdjList[MAX_VERTEX_NUM];/*头结点*/ typedefstruct { AdjListvertices; intvexnum,arcnum;/*图的当前顶点数和弧数*/ intkind;/*图的种类标志*/ }ALGraph; intLocateVex(ALGraphG,VertexTypeu) {/*初始条件: 图G存在,u和G中顶点有相同特征*/ /*操作结果: 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1*/ inti; for(i=0;i if(strcmp(u,G.vertices[i].data)==0) returni; return-1; } StatusCreateGraph(ALGraph&G) {/*采用邻接表存储结构,构造没有相关信息的有向图G*/ inti,j,k; VertexTypeva,vb; ArcNode*p; G.kind=0; printf("请输入图的顶点数,边数: "); scanf("%d%d",&G.vexnum,&G.arcnum); printf("请输入%d个顶点的值(<%d个字符): \n",G.vexnum,MAX_NAME); for(i=0;i { scanf("%s",G.vertices[i].data); G.vertices[i].firstarc=NULL; } printf("请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔): \n"); for(k=0;k { scanf("%s%s",va,vb); i=LocateVex(G,va);/*弧尾*/ j=LocateVex(G,vb);/*弧头*/ p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=j; p->info=NULL; if(G.vertices[i].firstarc==NULL) { p->nextarc=G.vertices[i].firstarc;/*插在表头*/ G.vertices[i].firstarc=p; } else { p->nextarc=G.vertices[i].firstarc->nextarc; G.vertices[i].firstarc->nextarc=p; } if(k printf("请输入下一条弧的弧尾和弧头(以空格作为间隔): \n"); } returnOK; } VertexType*GetVex(ALGraphG,intv) {/*初始条件: 图G存在,v是G中某个顶点的序号。 操作结果: 返回v的值*/ if(v>=G.vexnum||v<0) exit(ERROR); return&G.vertices[v].data; } intFirstAdjVex(ALGraphG,VertexTypev) {/*初始条件: 图G存在,v是G中某个顶点*/ /*操作结果: 返回v的第一个邻接顶点的序号。 若顶点在G中没有邻接顶点,则返回-1*/ ArcNode*p; intv1; v1=LocateVex(G,v);/*v1为顶点v在图G中的序号*/ p=G.vertices[v1].firstarc; if(p) returnp->adjvex; else return-1; } intNextAdjVex(ALGraphG,VertexTypev,VertexTypew) {/*初始条件: 图G存在,v是G中某个顶点,w是v的邻接顶点*/ /*操作结果: 返回v的(相对于w的)下一个邻接顶点的序号。 */ /*若w是v的最后一个邻接点,则返回-1*/ ArcNode*p; intv1,w1; v1=LocateVex(G,v);/*v1为顶点v在图G中的序号*/ w1=LocateVex(G,w);/*w1为顶点w在图G中的序号*/ p=G.vertices[v1].firstarc; while(p&&p->adjvex! =w1)/*指针p不空且所指表结点不是w*/ p=p->nextarc; if(! p||! p->nextarc)/*没找到w或w是最后一个邻接点*/ return-1; else/*p->adjvex==w*/ returnp->nextarc->adjvex;/*返回v的(相对于w的)下一个邻接顶点的序号*/ } voidVisitFunc(VertexTypev) {
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 北京 交通大学 数据结构 上机 实验