数据结构 二维码文件第4章主要算法的C++代码

第4章主要算法的C++代码实验1：图的存储1．图的邻接矩阵存储及输出。#include<iostream>usingnamespacestd;typedefcharVertexType;//顶点类型应由用户定义typedefintEdgeType;//边上的权值类型应由用户定义#defineMAXVEX10//最大顶点数，应由用户定义typedefstruct{VertexTypevexs[MAXVEX];//顶点表EdgeTypearc[MAXVEX][MAXVEX];//邻接矩阵，可看作边intnumVertexes,numEdges;//图中当前的顶点数和边数}Graph;intlocates(Graph*g,charch){//定位inti=0;for(i=0;i<g->numVertexes;i++){if(g->vexs[i]==ch){break;}}if(i>=g->numVertexes){return-1;}returni;}//建立一个无向网图的邻接矩阵表示voidCreateGraph(Graph*g){inti,j,k,w;cout<<"输入顶点数和边数:"<<endl;cin>>g->numVertexes>>g->numEdges;cout<<"请输入顶点名称，每个顶点用单个字母或单个数字表示，并以回车键结束："<<endl;for(i=0;i<g->numVertexes;i++){g->vexs[i]=getchar();while(g->vexs[i]=='\n'){g->vexs[i]=getchar();}}cout<<"你输入的顶点是：";for(i=0;i<g->numVertexes;i++){cout<<g->vexs[i];}cout<<endl;for(i=0;i<g->numEdges;i++){for(j=0;j<g->numEdges;j++){g->arc[i][j]=0;//邻接矩阵初始化}}for(k=0;k<g->numEdges;k++){charp,q;cout<<"输入边(vi,vj)上的顶点i名称，顶点j名称和权值,每个输入后面以回键结束:"<<endl;p=getchar();while(p=='\n'){p=getchar();}q=getchar();while(q=='\n'){q=getchar();}cin>>w;intm=-1;intn=-1;m=locates(g,p);n=locates(g,q);if(n==-1||m==-1){fprintf(stderr,"thereisnothisvertex.\n");return;}g->arc[m][n]=w;g->arc[n][m]=g->arc[m][n];//因为是无向图，矩阵对称}}//打印图voidprintGraph(Graphg){inti,j; cout<<"这个邻接矩阵为："<<endl;for(i=0;i<g.numVertexes;i++){for(j=0;j<g.numVertexes;j++){cout<<""<<g.arc[i][j];}cout<<endl;}}intmain(intargc,char**argv){Graphg;CreateGraph(&g);//邻接矩阵创建图printGraph(g);return0;}2．图的邻接表存储及输出。/*邻接表表示的图结构*/#include<iostream>usingnamespacestd;#defineDEBUG#defineMAXVEX1000//最大顶点数typedefcharVertexType;//顶点类型应由用户定义typedefintEdgeType;//边上的权值类型应由用户定义typedefstructEdgeNode{//边表结点intadjvex;//邻接点域，存储该顶点对应的下标EdgeTypeweigth;//用于存储权值，对于非网图可以不需要structEdgeNode*next;//链域，指向下一个邻接点}EdgeNode;typedefstructVertexNode{//顶点表结构VertexTypedata;//顶点域，存储顶点信息EdgeNode*firstedge;//边表头指针}VertexNode,AdjList[MAXVEX];typedefstruct{AdjListadjList;intnumVertexes,numEdges;//图中当前顶点数和边数}GraphList;intLocate(GraphList*g,charch){inti;for(i=0;i<MAXVEX;i++){if(ch==g->adjList[i].data){break;}}if(i>=MAXVEX){fprintf(stderr,"thereisnovertex.\n");return-1;}returni;}//建立图的邻接表结构voidCreateGraph(GraphList*g){inti,j,k;EdgeNode*e;EdgeNode*f;cout<<"输入顶点数和边数:\n";cin>>g->numVertexes>>g->numEdges;cout<<"请输入少于10个顶点,每个顶点用单个字母或单个数字表示，并以回车键结束:"<<endl;for(i=0;i<g->numVertexes;i++){g->adjList[i].data=getchar();//输入顶点信息g->adjList[i].firstedge=NULL;//将边表置为空表while(g->adjList[i].data=='\n'){g->adjList[i].data=getchar();}}for(k=0;k<g->numEdges;k++){//建立边表cout<<"输入边(vi,vj)上的顶点序号及权值:"<<endl;charp,q; intw;p=getchar();while(p=='\n'){p=getchar();}q=getchar();while(q=='\n'){q=getchar();} cin>>w;intm,n;m=Locate(g,p);n=Locate(g,q);if(m==-1||n==-1){return;}//向内存申请空间，生成边表结点e=(EdgeNode*)malloc(sizeof(EdgeNode));if(e==NULL){fprintf(stderr,"malloc()error.\n");return;}e->adjvex=n;//邻接序号为n//将e指针指向当前顶点指向的结构 e->weigth=w;//权值为we->next=g->adjList[m].firstedge;//将当前顶点的指针指向eg->adjList[m].firstedge=e;f=(EdgeNode*)malloc(sizeof(EdgeNode));if(f==NULL){fprintf(stderr,"malloc()error.\n");return;}f->adjvex=m; f->weigth=w;f->next=g->adjList[n].firstedge;g->adjList[n].firstedge=f;}}voidprintGraph(GraphList*g){inti=0;while(g->adjList[i].firstedge!=NULL&&i<g->numVertexes){cout<<"顶点:"<<g->adjList[i].data;EdgeNode*e=NULL;e=g->adjList[i].firstedge;while(e!=NULL){cout<<"->";cout<<"("<<e->adjvex; cout<<","<<e->weigth<<")"; e=e->next; }i++;cout<<endl;}}intmain(intargc,char**argv){GraphListg;CreateGraph(&g);printGraph(&g);return0;}实验2：图的遍历#include<queue>#include<iostream>usingnamespacestd;#defineMAXVEX100//最大顶点数typedefintBoolean;//Boolean是布尔类型，其值是TRUE或FALSEBooleanvisited[MAXVEX];//访问标志数组#defineTRUE1#defineFALSE0typedefcharVertexType;//顶点类型应由用户定义typedefintEdgeType;//边上的权值类型应由用户定义typedefstruct{VertexTypevexs[MAXVEX];//顶点表EdgeTypearc[MAXVEX][MAXVEX];//邻接矩阵，可看作边intnumVertexes,numEdges;//图中当前的顶点数和边数}Graph;intlocates(Graph*g,charch){//定位inti=0;for(i=0;i<g->numVertexes;i++){if(g->vexs[i]==ch){break;}}if(i>=g->numVertexes){return-1;}returni;}//建立一个无向网图的邻接矩阵表示voidCreateGraph(Graph*g){inti,j,k;cout<<"输入顶点数和边数:"<<endl;cin>>g->numVertexes>>g->numEdges;cout<<"请输入顶点名称，每个顶点用单个字母或单个数字表示，并以回车键结束："<<endl;for(i=0;i<g->numVertexes;i++){g->vexs[i]=getchar();while(g->vexs[i]=='\n'){g->vexs[i]=getchar();}}cout<<"你输入的顶点是：";for(i=0;i<g->numVertexes;i++){cout<<g->vexs[i];}cout<<endl;for(i=0;i<g->numEdges;i++){for(j=0;j<g->numEdges;j++){g->arc[i][j]=0;//邻接矩阵初始化}}for(k=0;k<g->numEdges;k++){charp,q;cout<<"输入边(vi,vj)上的顶点i名称，顶点j名称,每个输入后面以回键结束:"<<endl;p=getchar();while(p=='\n'){p=getchar();}q=getchar();while(q=='\n'){q=getchar();}intm=-1;intn=-1;m=locates(g,p);n=locates(g,q);if(n==-1||m==-1){fprintf(stderr,"thereisnothisvertex.\n");return;}//getchar();g->arc[m][n]=1;g->arc[n][m]=g->arc[m][n];//因为是无向图，矩阵对称}}voidDFS(Graphg,inti){//邻接矩阵的深度优先递归算法intj;visited[i]=TRUE;cout<<g.vexs[i];//打印顶点，也可以其他操作for(j=0;j<g.numVertexes;j++){if(g.arc[i][j]==1&&!visited[j]){DFS(g,j);//对为访问的邻接顶点递归调用}}}//邻接矩阵的深度遍历操作voidDFSTraverse(Graphg){inti;for(i=0;i<g.numVertexes;i++){visited[i]=FALSE;//初始化所有顶点状态都是未访问过状态}cout<<"深度优先遍历次序为："; for(i=0;i<g.numVertexes;i++){if(!visited[i]){//对未访问的顶点调用DFS，若是连通图，只会执行一次DFS(g,i);}} cout<<endl;}//邻接矩阵的广度遍历算法voidBFSTraverse(Graphg){inti,j;queue<int>q; for(i=0;i<g.numVertexes;i++){visited[i]=FALSE;} cout<<"广度优先遍历次序为：";for(i=0;i<g.numVertexes;i++){//对每个顶点做循环if(!visited[i]){//若是未访问过visited[i]=TRUE;cout<<g.vexs[i];//打印结点q.push(i);//将此结点入队列while(!q.empty()){//将队中元素出队列，赋值给intm; m=q.front(); q.pop();for(j=0;j<g.numVertexes;j++){//判断其他顶点若与当前顶点存在边且未访问过if(g.arc[m][j]==1&&!visited[j]){visited[j]=TRUE;cout<<g.vexs[j]; q.push(j);}}}}}}intmain(intargc,char**argv){Graphg;CreateGraph(&g);//邻接矩阵创建图DFSTraverse(g); BFSTraverse(g);return0;}Prim算法实现：#include<iostream>usingnamespacestd;typedefcharVertexType;//顶点类型应由用户定义typedefintEdgeType;//边上的权值类型应由用户定义#defineMAXVEX100//最大顶点数，应由用户定义#defineMAX65535//以65535代表无穷大typedefstruct{VertexTypevexs[MAXVEX];//顶点表EdgeTypearc[MAXVEX][MAXVEX];//邻接矩阵，可看作边intnumVertexes,numEdges;//图中当前的顶点数和边数}Graph;typedefstruct{ inttop,tail;//用于存储选中边的两个顶点下标 EdgeTypelowcost;//最小边值}Edges;//边结构三元组//定位intlocates(Graph*g,charch){inti=0;for(i=0;i<g->numVertexes;i++){if(g->vexs[i]==ch){break;}}if(i>=g->numVertexes){return-1;}returni;}//建立一个无向网图的邻接矩阵表示voidCreateGraph(Graph*g){inti,j,k,w;cout<<"输入顶点数和边数:"<<endl;cin>>g->numVertexes>>g->numEdges;cout<<"请输入顶点名称，每个顶点用单个字母或单个数字表示，并以回车键结束："<<endl;for(i=0;i<g->numVertexes;i++){g->vexs[i]=getchar();while(g->vexs[i]=='\n'){g->vexs[i]=getchar();}}cout<<"你输入的顶点是：";for(i=0;i<g->numVertexes;i++){cout<<g->vexs[i];}cout<<endl;for(i=0;i<g->numEdges;i++){for(j=0;j<g->numEdges;j++){g->arc[i][j]=MAX;//邻接矩阵初始化}}for(k=0;k<g->numEdges;k++){charp,q;cout<<"输入边(vi,vj)上的顶点i名称，顶点j名称和权值,每个输入后面以回键结束:"<<endl;p=getchar();while(p=='\n'){p=getchar();}q=getchar();while(q=='\n'){q=getchar();}cin>>w;intm=-1;intn=-1;m=locates(g,p);n=locates(g,q);if(n==-1||m==-1){fprintf(stderr,"thereisnothisvertex.\n");return;}g->arc[m][n]=w;g->arc[n][m]=g->arc[m][n];//因为是无向图，矩阵对称}}voidPrim(Graphg){Edgesedges[MAXVEX];bools[MAXVEX];//bool型变量的S数组表示i是否已经包括在S中inti,k;s[0]=true;//从第一个结点开始寻找,扩展for(i=1;i<g.numVertexes;i++){//简单初始化edges[i].lowcost=g.arc[0][i]; edges[i].top=0; edges[i].tail=i;s[i]=false;}for(i=0;i<g.numVertexes;i++){intmin=1000;//最小值,设大一点的值intj=1;for(k=1;k<g.numVertexes;k++){//寻找最小值if((edges[k].lowcost<min)&&(!s[k])){min=edges[k].lowcost;j=k;}}s[j]=true;//添加点j到集合S中for(k=1;k<g.numVertexes;k++){//因为新加入了j点,所以要查找新加入的j点到未在S中的点K中的权值是不是可以因此更小if((g.arc[j][k]<edges[k].lowcost)&&(!s[k])){edges[k].lowcost=g.arc[j][k];edges[k].top=j;}}} cout<<"最小生成树为："<<endl; for(i=1;i<g.numVertexes;i++) cout<<g.vexs[edges[i].top]<<"->"<<g.vexs[edges[i].tail]<<"边值为："<<edges[i].lowcost<<endl;}intmain(){ Graphg;CreateGraph(&g);//邻接矩阵创建图Prim(g);return0;}【运行结果】Prim算法运行结果Kruskal算法实现（采用邻接矩阵存储）#include<iostream>usingnamespacestd;typedefcharVertexType;//顶点类型应由用户定义typedefintEdgeType;//边上的权值类型应由用户定义#defineMAXVEX100//最大顶点数，应由用户定义#defineMAX65535//以65535代表无穷大typedefstruct{VertexTypevexs[MAXVEX];//顶点表EdgeTypearc[MAXVEX][MAXVEX];//邻接矩阵，可看作边intnumVertexes,numEdges;//图中当前的顶点数和边数}Graph;typedefstruct{ inttop,tail;//用于存储选中边的两个顶点下标 EdgeTypecost;//边值 intflg;}Edges;//边结构三元组Edgese[MAXVEX];intlocates(Graph*g,charch){//定位inti=0;for(i=0;i<g->numVertexes;i++){if(g->vexs[i]==ch){break;}}if(i>=g->numVertexes){return-1;}returni;}//建立一个无向网图的邻接矩阵表示voidCreateGraph(Graph*g){inti,j,k,w; cout<<"输入顶点数和边数:"<<endl;cin>>g->numVertexes>>g->numEdges;cout<<"请输入顶点名称，每个顶点用单个字母或单个数字表示，并以回车键结束："<<endl;for(i=0;i<g->numVertexes;i++){g->vexs[i]=getchar();while(g->vexs[i]=='\n'){g->vexs[i]=getchar();}}cout<<"你输入的顶点是：";for(i=0;i<g->numVertexes;i++){cout<<g->vexs[i];}cout<<endl;for(i=0;i<g->numEdges;i++){for(j=0;j<g->numEdges;j++){g->arc[i][j]=MAX;//邻接矩阵初始化}}cout<<"输入边(vi,vj)上的顶点i名称，顶点j名称和权值,每个输入后面以回键结束:"<<endl;for(k=0;k<g->numEdges;k++){charp,q;p=getchar();while(p=='\n'){p=getchar();}q=getchar();while(q=='\n'){q=getchar();}cin>>w;intm=-1;intn=-1;m=locates(g,p);n=locates(g,q);if(n==-1||m==-1){fprintf(stderr,"thereisnothisvertex.\n");return;}g->arc[m][n]=w;g->arc[n][m]=g->arc[m][n];//因为是无向图，矩阵对称 e[k].top=n;e[k].tail=m;e[k].cost=w;e[k].flg=0;}}voidsorte(Graph*g,Edgese[MAXVEX]){ inti,j; Edgesf; for(i=0;i<g->numEdges;i++) for(j=1;j<g->numEdges-i;j++) if(e[j-1].cost>e[j].cost){ f.cost=e[j].cost;e[j].cost=e[j-1].cost;e[j-1].cost=f.cost; f.top=e[j].top;e[j].top=e[j-1].top;e[j-1].top=f.top; f.tail=e[j].tail;e[j].tail=e[j-1].tail;e[j-1].tail=f.tail; }}voidKruskal(Graph*g,Edgese[MAXVEX]){ inti,j,f1=0,f2=0; sorte(g,e); e[0].flg=1; for(i=1;i<g->numEdges;i++){for(j=0;j<g->numEdges;j++){ if((e[i].top==e[j].top||e[i].top==e[j].tail)&&e[j].flg) f1=1; if((e[i].tail==e[j].tail||e[i].tail==e[j].top)&&e[j].flg) f2=1; } if(!(f1==f2&&f1==1)) e[i].flg=1; f1=0;f2=0;} cout<<"最小生成树为："<<endl; for(i=0;i<g->numEdges;i++) { if(e[i].flg==1) cout<<g->vexs[e[i].top]<<"->"<<g->vexs[e[i].tail]<<"边值为："<<e[i].cost<<endl; }}intmain(){Graphg;CreateGraph(&g);//邻接矩阵创建图Kruskal(&g,e);return0;}【运行结果】Kruskal算法运行结果拓扑排序算法实现：#include<iostream>#include