数据结构图的操作课程设计资料

#include<stdio.h> #include <stdlib.h> #include "CSTree.h" #include "NewQueue.h" #include "MatrixGraph.h" #include "ALGraph.h" #define MAX_DEMGREE 40; //创建图 MGraph CreateMGraph(){ MGraph MG; char v1,v2; int i,j; printf("请输入定点数(vexnum)和弧数(arcnum)："); scanf("%d,%d",&MG.vexnum,&MG.arcnum); //初始化权值 for(i=0;i<MG.vexnum;i++){ for(j=0;j<MG.vexnum;j++){ MG.arcs[i][j].adj=0; } } printf("输入顶点向量的值："); for(i=0;i<MG.vexnum;i++) scanf("%c",&MG.vexs[i]); printf("输入两个顶点(v1,v2)的确定关系："); for(i=0;i<MG.arcnum;i++){//逐个输入弧即将两个有关的点的adj设为1 scanf("%c,%c,",&v1,&v2); i=Location(MG,v1);//查找v1&v2所在位置 j=Location(MG,v2); if (i==-1||j==-1)//没有找到结点v1或v2 结束本次循环跳到下次循环 { printf("没有结点(v1或v2)，重新输入：\n"); continue; } MG.arcs[i][j].adj=1;//设置权值 MG.arcs[i][j]=MG.arcs[j][i];//本图为无向图 } return MG; } //1、 对无向图求每个顶点的度，或对有向图求每个顶点的入度和出度（5分） void CaculateDeMGree(MGraph MG){ int i,j; int indegree[MAX_DEMGREE],outdegree[MAX_DEMGREE]; //初始化出入度 for (i=0;i<MAX_DEMGREE;i++) { indegree[i]=0; outdegree[i]=0; } for(i=0;i<MG.vexnum;i++){//查找各个结点的出入度的权值 如果权值为1 则出度增加1 与它相关的结点的入度增加1 由于这是一个无向图，所以该节点入度+1 与它相关的结点出度+1 for (j=0;j<MG.arcnum;j++) { if(MG.arcs[i][j].adj==1){ indegree[i]++; outdegree[i]++; indegree[j]++; outdegree[j]++; } } } for (i=0;i<MG.vexnum;i++)//输出各个节点的出入度 { printf("第个%d结点的入度%d是出度是%d\n",i+1,indegree[i],outdegree[i]); } } //2、 完成插入顶点和边（或弧）的功能（5分） MGraph InsertVex(MGraph MG,char v){ int i; MG.vexs[MG.vexnum]=v;//将结点v插入到结点数组的最后 for(i=0;i<MG.vexnum;i++){//初始化与v相关的结点的权值 MG.arcs[MG.vexnum][i]=0; } MG.vexnum++;//节点数增加1 return MG; } MGraph InsertArc(MGraph MG,char v1,char v2){ //printf("输入要插入的两个") int m,n; m=Location(MG,v1);//找到v1v2的位置 n=Location(MG,v2); if(m=-1){ MG=InsertVex(MG,v1);//如果没有找到v1则将v1插入到图中 }else if{ MG=InsertVex(MG,v2);//如果没有找到v2则将v2插入到图中 }else{//如果v1v2都存在，设置关系为1 MG.arcs[m][n].adj=1; MG.arcs[m][n]=MG.arcs[n][m]; } return MG; } //3、 完成删除顶点和边（或弧）的功能（5分） MGraph DeleteVex(MGraph MG,char v){ int i,j; j=Location(MG,v); //跟v有关的结点有几个减少几条弧 for (i=0;i<MG.vexnum;i++) { if (MG.arcs[j][i].adj==1) { MG.arcnum--; } } //删去v点的所有信息 for(i=0;i<MG.vexnum;i++){ for(;j<MG.vexnum;j++){ MG.arcs[i][j]=MG.arcs[i][j+1]; MG.arcs[j][i]=MG.arcs[j+1][i]; } } //删去v结点 for (;j<MG.vexnum;j++) { MG.vexs[j]=MG.vexs[j+1]; } MG.vexnum--;//结点数减少1 return MG; } MGraph DeleteArc(MGraph MG,char v1,char v2){ int m,n; m=Location(MG,v1);//查找结点v1v2所在的位置 n=Location(MG,v2); if (m==-1||n==-1)//如果没有找到其中一个 就返回MG { printf("没有找到结点v1或v2!\n"); return MG; }else{//如果都能找到 将两者之间的权值设为0， MG.arcs[m][n].adj=0; MG.arcs[n][m].adj=0; } MG.arcnum--;//弧数减少1 return MG; } //4、 两种存储结构的转换（5分），如果其中一种存储结构为十字链表或邻接多重表则增加5分。 ALGraph ToALGraph(MGraph MG){ ALGraph ALG; ArcNode *p,*q; int i,j; for (i=0;i<MG.vexnum;i++)//把邻接矩阵的顶点转化为邻接表的顶点 { ALG.vertices[i].data=MG.vexs[i]; ALG.vexnum++;//邻接表的顶点数加1 } for (i=0;i<MG.vexnum;i++)//逐个查找邻接矩阵 { for (j=0;j<MG.vexnum;j++) { if(MG.arcs[i][j].adj=1){ p=(ArcNode*)malloc(sizeof(ArcNode)); q=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=i; p->nextarc=ALG.vertices[j].firstarc; ALG.vertices[i].firstarc=q; q->adjvex=j; q->nextarc=ALG.vertices[i].firstarc; ALG.vertices[j].firstarc=q; ALG.arcnum++;//邻接表的弧数加1 } } } return ALG; } //5、 输出图的深度优先遍历序列或广度优先遍历序列（5分） void DFS(MGraph MG){ int i; int wasVisited[MAX_VERTEX_NUM]; printf("深度优先遍历："); for (i=0;i<MG.vexnum;i++){//初始化标志位 wasVisited[i]=0; } for(i=0;i<MG.vexnum-1;i++){//遍历整个矩阵 只要此节点未访问就调用dethfs()函数 if(wasVisited[i]==0){ depthfs(wasVisited[i],i,MG); } } } void depthfs(int[] wasVisited,int i,MGraph MG){ int j; wasVisited[i]=1;//将标志位设置为访问过 printf("%c->",MG.vexs[i]);//输出该节点 for(j=0;j<MG.vexnum;j++){//遍历整个矩阵 遍历与i相邻切没有访问到的 进行访问 if(MG.arcs[i][j].adj==1&&wasVisited[j]==0) depthfs(wasVisited[j],j,MG); } } void BFS(MGraph MG){ int wasVisited[MAX_VERTEX_NUM]; int i,j,e; LinkQueue Q; printf("\n广度优先遍历："); for(i=0;i<MG.vexnum;i++){//初始化标志位 wasVisited[i]=0; } Q=InitQueue();//初始化队列 for(i=0;i<MG.vexnum;i++){ if(wasVisited[i]==0){ wasVisited[i]=1; printf("%c->",MG.vexs[i]); Q=EnQueue(Q,MG.vexs[i]); while(!QueueEmpty()){ Q=DeQueue(Q); for(j=0;j<MG.vexnum;j++){ if(MG.arcs[i][j].adj==1&&wasVisited[j]!=1){ printf("%c->",MG.vexs[j]); wasVisited[j]=1; Q=EnQueue(Q,MG.vexs[j]); } }//while }//if }//for } } //6、 求图的深度优先或广度优先的生成树（或生成森林）（存储结构为孩子-兄弟链表），并对生成树进行遍历（15分） void DFSTree(MGraph MG,int v,CSTree T,int[] wasVisited){ int first=1,j; CSTree p,q; wasVisited[v]=1;//设置v位置的标志位为1 for(j=0;j<MG.vexnum;j++){ if(MG.arcs[v][j].adj==1&&wasVisited[j]!=1){//找到与p相邻的结点 p=(CSTree)malloc(sizeof(CSNode)); p->data=MG.vexs[j]; if(first){ T->firstchild=p;//j是v的第一个未被访问的邻接点 w是树的左孩子 first=0; }else{ q->nextsibling=p;//w是上一个邻接点的右兄弟 }//else q=p; DFSTree(MG,j,CSTree T,wasVisited[j]); }//for } } CSTree DFSForest(MGraph MG){ int v,wasVisited[MAX_VERTEX_NUM]; CSTree p,q,T; T=NULL;//建立空树 for(v=0;v<MG.vexnum;v++){//初始化标志位 wasVisited[v]=0; } for(v=0;v<MG.vexnum;v++){//遍历结点 if(wasVisited[v]){//第一次肯定执行 p=(CSTree)malloc(sizeof(CSNode)); if(!p) exit(0); p->data=MG.vexs[v];//给p赋值 p->firstchild=NULL; p->nextsibling=NULL; if(!T)//初始化每颗生成树的根 T=p; else q->nextsibling=p;//p是前一个树q的兄弟 q=p;//记录当前生成树的根 DFSTree(MG,v,p,wasVisited[v]);//遍历与q相邻的结点 }//if }//for return T; } //7、 判断图的连通性，输出连通分量的个数（5分） int IsConnect(MGraph MG){ int i,j,wasVisited[MAX_VERTEX_NUM],count=1; for(i=0;i<MG.vexnum;i++) wasVisited[i]=0; for(i=0;i<MG.vexnum;i++){ for(j=0;j<MG.vexnum;j++){ if(MG.arcs[i][j]==1&&wasVisited[j]==0){ wasVisited[i]=0; wasVisited[j]=0; count++; }//if }//for } if(count==MG.vexnum) return 1; return 0; } //8、 判断图中是否存在环，无向图5分，有向图10分 ///9、 给出顶点u和v，判断u到v是否存在路径（5分） //10、求顶点u到v的一条简单路径（10分） //11、求顶点u到v的所有简单路径（15分） //12、求顶点u到v的最短路径（10分） //13、求顶点u到其余各顶点的最短路径（15分） //14、求任两个顶点之间的最短路径（15分） //15、求最小生成树（15分） //16、对于有一个源点和一个汇点的有向网，求关键路径（20分）