精华内容
下载资源
问答
  • 此段代码有两个函数在用的时候得注意一下myswitch函数中的一些变量的定义应当随文件输入的地点的数量而改变creaud函数来创建一个图,里面调用到两个文件输入,自己得进行创建#include <iostream> #include<...
    此段代码有两个函数在用的时候得注意一下
    myswitch函数中的一些变量的定义应当随文件输入的地点的数量而改变
    creaud函数来创建一个图,里面调用到两个文件输入,自己得进行创建

    #include <iostream> #include<fstream> #include<stack> #include<iomanip> #define mvnum 50 #define maxint 32767 typedef int status; using namespace std; typedef struct { int point; //地点的索引 string number; //地点编码,可以再文件中随便设置后读入 string placename; //地点的名称 string introduction; //地点的相关介绍 }vex; typedef struct { int realweight; //图的权值,即地点之间的真实距离 int virtualize; //用来存放输出为0和距离的矩阵而已 }arc; typedef struct { vex vexs[mvnum]; //0下标不用 arc arcs[mvnum][mvnum]; int vexnum,arcnum; string title[4]; }Amgraph; status locatvex(Amgraph G,int place) { for(int i=1;i<=G.vexnum;i++) { if(G.vexs[i].point==place) { return i; } } } status creatudn(Amgraph &G) //创建图 这个函数是最重点的函数,要求自己建造一个图,并构建两个文件,分别存放地点和地点之间的联系距离
                      只要数据输入了,其他函数都能够通用。
    { fstream file; file.open("place.txt"); if(!file) { cout<<"open error"<<endl; } int i=1; file>>G.title[0]>>G.title[1]>>G.title[2]>>G.title[3]; while(!file.eof()) //此处在插入数据是一个重点,使用一个txt文件存放对应的数据,用空格隔开,分行存放数据,后通过文件流传值给
                  G.vexs[i].point (地点的索引,从1开始,有n个地点就一直到n) G.vexs[i].number(地点的一个代码编号)
                  G.vexs[i].placename(地点的名称) G.vexs[i].introduction(地点的相关介绍)

    //格式是这样子的

                  
              
    { file
    >>G.vexs[i].point>>G.vexs[i].number>>G.vexs[i].placename>>G.vexs[i].introduction; i++; } file.close(); file.open("path.txt"); if(!file) { cout<<"error open"<<endl; } for(int m=1;m<=G.vexnum;m++) //初始化,必须有 { for(int n=1;n<=G.vexnum;n++) { G.arcs[m][n].realweight=maxint; G.arcs[m][n].virtualize=0; } } int place1,place2,distance,pos1,pos2; while(!file.eof()) //读取输入另一个存放路劲和长度的文件,文件里面每一行放着三个数据 分别是 place1的索引,place2的索引,还有两地的距离
                    表示两地之间有连接并且距离为distance,此处也为一个重点。
     

     

               
    { file
    >>place1>>place2>>distance; pos1=locatvex(G,place1); pos2=locatvex(G,place2); G.arcs[pos1][pos2].realweight=G.arcs[pos1][pos2].virtualize=distance; G.arcs[pos2][pos1].realweight=G.arcs[pos1][pos2].virtualize=distance; } file.close(); } void updategraph(Amgraph &G) //更新图 ,增加你想加入的东西 { int addvex,addarc,i=G.vexnum+1; cout<<"请输入要增加的点数目:"; cin>>addvex; cout<<"请输入要增加的边的数目:"; cin>>addarc; int origanvexnum=G.vexnum; G.vexnum=G.vexnum+addvex; G.arcnum=G.arcnum+addarc; for(int m=origanvexnum+1;m<=G.vexnum;m++) //给扩展出来的两列初始化。 { for(int n=1;n<=G.vexnum;n++) { G.arcs[m][n].realweight=maxint; G.arcs[n][m].realweight=maxint; G.arcs[m][n].virtualize=0; G.arcs[n][m].virtualize=0; } } while(addvex!=0) //增加点 { cout<<"请输入要增加的点的下标,从"<<G.vexnum-addvex+1<<"开始输入下表,编码,地点名称,和介绍 :"; cin>>G.vexs[i].point>>G.vexs[i].number>>G.vexs[i].placename>>G.vexs[i].introduction; i++; addvex--; } int place1,place2,distance; int pos1,pos2; while(addarc!=0) //更新的时候用到 { cout<<"请输入要增加的边的连接的两个地点的下表以及距离:"; cin>>place1>>place2>>distance; pos1=locatvex(G,place1); pos2=locatvex(G,place2); G.arcs[pos1][pos2].realweight=G.arcs[pos1][pos2].virtualize=distance; G.arcs[pos2][pos1].realweight=G.arcs[pos1][pos2].virtualize=distance; addarc--; } } void outputgraph(Amgraph G) //输出图的所有的相关信息 { cout<<G.title[0]<<" "<<G.title[1]<<" "<<G.title[2]<<setw(40)<<G.title[3]<<endl; for(int i=1;i<=G.vexnum;i++) { cout<<G.vexs[i].point<<setw(10)<<G.vexs[i].number<<" "<<G.vexs[i].placename<<setw(40)<<G.vexs[i].introduction<<endl; } cout<<endl; } void outputgraphudn(Amgraph G) //输出邻接矩阵 { for(int i=1;i<=G.vexnum;i++) { for(int j=1;j<=G.vexnum;j++) { cout<<G.arcs[i][j].virtualize; if(j!=G.vexnum) { cout<<setw(4); } } cout<<endl; } cout<<endl; cout<<G.arcnum<<endl; } void searchplace(Amgraph G) //查找某一地点并且输出相关的信息 { string str; int tip=0; cout<<"输入地点的编号或者地点名称: "; cin>>str; if(str=="0") { return ; } for(int i=1;i<=G.vexnum;i++) { if(str==G.vexs[i].number||str==G.vexs[i].placename) { tip=1; cout<<G.vexs[i].point<<" "<<G.vexs[i].number<<" "<<G.vexs[i].placename<<" "<<G.vexs[i].introduction<<endl; break; } } if(!tip&&str!="0") { cout<<"没有找到此地点!!! 提示:按0可退出查询"<<endl; return searchplace(G); } } status searchplacepoint(Amgraph G) //找到一个地点的下表 { string place; cout<<"请输入起始的地点名称或者编号:"; cin>>place; int tip=0; if(place=="0") { return 0; } for(int i=1;i<=G.vexnum;i++) { if(G.vexs[i].number==place||G.vexs[i].placename==place) { tip=1; return i; } } if(!tip&&place!="0") { cout<<"未找到该地点!!! "<<endl; cout<<"提示输入0可结束搜索"<<endl; return searchplacepoint(G); } } bool S[mvnum+1]; int D[mvnum+1]; int Path[mvnum+1]; void shortpath(Amgraph G,int &point1,int tip,int ppoint1=0) //tip是一个标志点 tip为 的时候用于寻找以point1为起始的路径。 { //tip为0时,用于寻找以ppoint为起点的路径。 if(tip==1) { point1=searchplacepoint(G); } else if(tip==0) { point1=ppoint1; } if(point1==0) { return ; } int n=G.vexnum; for(int point2=1;point2<=n;point2++) { S[point2]=false; D[point2]=G.arcs[point1][point2].realweight; //初始化其他点point2到point1这一点的权值,没有路径则为无穷大。 if(D[point2]<maxint) { Path[point2]=point1; //将每一个与point1存在直接相连的店的Path设为point1 ,没有直接相连则设置-1. } else { Path[point2]=-1; } } S[point1]=true; D[point1]=0; //初始化完毕 int min,point3; for(int i=2;i<=n;i++) { min=maxint; for(int j=1;j<=n;j++) { if(D[j]<min&&!S[j]) { min=D[j]; point3=j; } //找出当前的路径中最小的一段终点是在 point3; } S[point3]=true; for(int j=1;j<=n;j++) { if(!S[j]&&G.arcs[point3][j].realweight+D[point3]<D[j]) //判断是否point3这一点到j这一点的距离和point3到远点point1的距离之和是否小于j到远点point1这一点的距离 { Path[j]=point3; //假设成立的话修改最短路径中j的一个点为point3 D[j]=G.arcs[point3][j].realweight+D[point3]; //修改j到原点point1的距离 } } } cout<<"路径搜索成功!"<<endl; } void allshortpath(Amgraph G) { int point1; shortpath(G,point1,1); cout<<G.vexs[point1].placename<<"到其他地点的路径的最短距离如下"<<endl; for(int point4=1;point4<=G.vexnum;point4++) { cout<<G.vexs[point1].placename<<"-->"<<G.vexs[point4].placename<<"的距离:"<<D[point4]<<endl; } cout<<G.vexs[point1].placename<<"到其他地点的最短路径如下"<<endl; for(int point4=1;point4<=G.vexnum;point4++) { int point5=point4; int count=0; string temp[50]; while(D[point5]!=0) //如果终点 { temp[count]=G.vexs[Path[point5]].placename; point5=Path[point5]; count++; } if(D[point4]==0) //如果终点是原点的话就直接输出一个原点 { cout<<G.vexs[point5].placename<<endl; } else { for(int i=count-1;i>=0;i--) { cout<<temp[i]<<"-->"; } cout<<G.vexs[point4].placename<<endl; //point4这个点为终点,它的地名没有存进数组里面,故需要将其输出,否则失去终点。 } //此时不能用point5,因为point5已经改变了。 } } status searchplacepoint(Amgraph G,string place) { for(int i=1;i<=G.vexnum;i++) { if(G.vexs[i].number==place||G.vexs[i].placename==place) { return i; } } } void errorexcept(Amgraph G,string &place) //排除异常的输入并且给出重新输入的机会。 { int tip=0; for(int i=1;i<=G.vexnum;i++) { if(G.vexs[i].number==place||G.vexs[i].placename==place) { tip=1; return ; } } if(!tip) { cout<<"输入错误,未找到该地点,请重新输入: "; cin>>place; return errorexcept(G,place); } } void twoplacepath(Amgraph G) //查询两个地点之间的联系 { string place1,place2; cout<<"请输入起始地点: " ; cin>>place1; errorexcept(G,place1); cout<<"请输入终点: "; cin>>place2; errorexcept(G,place2); int p1,p2,viturized; //viturized是无所谓的变量 p1=searchplacepoint(G,place1); p2=searchplacepoint(G,place2); shortpath(G,viturized,0,p1); //viturized是无所谓的变量。 cout<<G.vexs[p1].placename<<"-->"<<G.vexs[p2].placename<<"的距离:"<<D[p2]<<endl; int point5=p2; int count=0; string temp[50]; while(D[point5]!=0) //将路径的倒数第一个放进下标为1的数组中,一次放入 { temp[count]=G.vexs[Path[point5]].placename; point5=Path[point5]; count++; } for(int i=count-1;i>=0;i--) { cout<<temp[i]; cout<<"-->"; } cout<<G.vexs[p2].placename<<endl; //输出到达的目的地 } void creatmenu() //创建菜单 { cout<<endl; cout<<"---------------菜单---------------"<<endl; cout<<"1:创建导航地图"<<endl; cout<<"2:输出地图的各个地方信息"<<endl; cout<<"3:输出地图的邻接矩阵"<<endl; cout<<"4:查找地点的相关信息"<<endl; cout<<"5:查找某地点到其他所有地点的最短路径以及距离"<<endl; cout<<"6:查找两地点间的信息"<<endl; cout<<"7:增加地图地点"<<endl; cout<<"0:退出导航系统"<<endl; cout<<"----------------------------------"<<endl; cout<<endl; } void checkfunction(int &choice) //检查输入的功能有没有错误 这个函数也有一部分不能通用的,比如下面边的数目的定义和定点的数量的定义,53和30,如果上面文件输入的数目不够的话得做出适当的改变 { int tip=0; for(int i=0;i<=7;i++) { if(choice==i) { tip=1; return ; } } if(!tip) { cout<<"输入错误,请重新输入:"; cin>>choice; } } void myswitch() { Amgraph G; G.arcnum=53; G.vexnum=30; int choice=1; while(choice) { switch(choice) { case 1:creatudn(G);cout<<"创建导航地图成功"<<endl; break; case 2:outputgraph(G); break; case 3:outputgraphudn(G); break; case 4:searchplace(G); break; case 5:allshortpath(G); break; case 6:twoplacepath(G); break; case 7:updategraph(G); break; default :break; } creatmenu(); cout<<"请选择功能: "; cin>>choice; checkfunction(choice); if(choice==1) { cout<<"已经创建地图"<<endl; creatmenu(); cout<<"请重新选择功能: "; cin>>choice; } } if(choice==0) { return ; } } int main() { myswitch(); return 0; }

     

     

    G.vexs[i].point

    转载于:https://www.cnblogs.com/chenhanwu/p/9753860.html

    展开全文
  • 的邻接矩阵表示法是一个用一维数组存储顶点信息,用二维数组存储边(弧)的信息。实现这个算法首先要创建无向,对图进行初始化操作,其次设置三个函数,分别为打印邻接矩阵,判断是否为对称矩阵和打印顶点的...

    无向图邻接矩阵的创建代码实现

    根据图的定义,邻接矩阵的存储需要对顶点和边分别存储。而图的邻接矩阵表示法是一个用一维数组存储顶点信息,用二维数组存储边(弧)的信息。实现这个算法首先要创建无向图,对图进行初始化操作,其次设置三个函数,分别为打印邻接矩阵,判断是否为对称矩阵和打印顶点的出度和入度。具体实现如下所示。

    完整代码如下

    #include<stdio.h>
    #include<malloc.h>
    #define maxnumber 6//顶点数目最大值
    typedef  struct
    {
    	char vexs[maxnumber];//顶点表
    	int  edges[maxnumber][maxnumber];//邻接矩阵,边表 
    	int n,e;//图的顶点数和弧数
    }MGraph;
    
    //创建无向图
    void CreateMGraph(MGraph *G)
    {
    	int i,j,k,max=0;
    	printf("请输入顶点数和边数(格式:顶点数,边数):\n");
    	scanf("%d,%d",&(G->n),&(G->e));
    
    	//图的初始化
    	for(i=0;i<G->n;i++)
    	{
    		printf("请输入第%d个顶点的信息:",i+1);
    		scanf("\n%c",&(G->vexs[i]));
    	}
    	printf("\n");
    	for(i=0;i<G->n;i++)
    	{
    		for(j=0;j<G->n;j++)
    			G->edges[i][j]=0;
    	}
    	printf("请输入每条边对应的两个顶点的序号(格式为:i,j):\n");
    	printf("\n");
    
    	//顶点信息存入顶点表
    	for(k=0;k<G->e;k++)
    	{
    		printf("请输入第%d个顶点和边的信息:",k+1);
    		scanf("%d,%d",&i,&j);
    		G->edges[i][j]=1;
    	}
    }
    
    //打印邻接矩阵
    void print_Matrix(MGraph G)
    {
    	int i,j;
    	printf("\n输出的邻接矩阵为:\n");
    	printf("\n");
    	for(i=0;i<G.n;i++)      //输出对应的领接矩阵 
    	{
    		for(j=0;j<G.n;j++)
    		{
    			printf("%d   ",G.edges[i][j]); 
    			if(j==(G.n-1)) 
    				printf("\n");    //输出结束 
    		}
    	}
    }
    
    //判断是否为对称矩阵
    void check_Matrix(MGraph G)
    {
    	int i,j,a;
    	for(i=0;i<G.n;i++)    //用于判断是否为对称矩阵 
    		for(j=0;j<G.n;j++)
    		{
    			if(G.edges[i][j]==G.edges[j][i])
    				a=1;
    			else
    			{
    				a=0;
    				break;
    			}
    		}   
    	if(a==1)
    		printf("矩阵是为对称矩阵\n");
    	else
    		printf("矩阵不是为对称矩阵\n");  
    }
    
    //输出顶点的出入度
    void output_Matrix(MGraph G)
    {
    	int i,j,cnt,max1,max2,max=0;
    	for(i=0,cnt=0;i<G.n;i++)    //用于输出顶点的出度
    	{
    		for(j=0;j<G.n;j++)
    		{
    			if(G.edges[i][j]==1)
    				cnt++; 
    			if(j==(G.n-1))
    				printf("%8d的出度为%d\n",i,cnt);
    			if(max<cnt)
    			{
    				max=cnt;
    				max1=i;
    			}
    		}
    	}
    	printf("%3d的出度最大\n",max1);
    	for(j=0,cnt=0,max=0;j<G.n;j++)    //用于输出顶点的入度
    	{
    		for(i=0;i<G.n;i++)
    		{
    			if(G.edges[i][j]==1)
    				cnt++; 
    			if(i==(G.n-1))
    				printf("%8d的入度为%d\n",j,cnt);
    			if(max<cnt)
    			{
    				max=cnt;
    				max2=i;
    			}
    		}
    		
    
    	}printf("%d的入度最大\n",max2);
    }
    void main() 
    {
    	MGraph G;
    	CreateMGraph(&G);//创建无向图
    	print_Matrix(G);//打印邻接矩阵
    	check_Matrix(G);//判断是否为对称矩阵
    	output_Matrix(G);//输出顶点的出入度
    }
    

    程序结果

    无向图的邻接矩阵创建

    展开全文
  • 怎么按照要求创建一棵二叉树怎么创建下的二叉树? 我写过完全二叉树的创建【数据结构】-java 完全二叉树的创建以及递归遍历算法实现参考完全二叉树的结点的创建。对于这种普通的二叉树我们也可以用递归的方式去...

    怎么按照要求创建一棵二叉树

    怎么创建下图的二叉树?

    aca602b9c18fbcc8cd56cdaf9ff5fa72.png

    我写过完全二叉树的创建【数据结构】-java 完全二叉树的创建以及递归遍历算法实现

    参考完全二叉树的结点的创建。

    对于这种普通的二叉树我们也可以用递归的方式去创建。

    先上代码,朋友们应该就明白个大概了,文本末附总结

    树节点的创建

    //全部是私有属性,这里用set、get方法返回所需要的属性。

    public class BTNode {

    //定义一个二叉树的结点

    private int data;

    private BTNode lchild;

    private BTNode rchild;

    //构造函数

    public BTNode(){

    }

    //新的构造函数,其实也可以简写

    public BTNode(int data ,BTNode lchild ,BTNode rchild){

    this.data=data;

    this.lchild=lchild;

    this.rchild=rchild;

    }

    //以下就是data lchild rchild的set,get函数

    public void setdata(int data){

    this.data=data;

    }

    public int getdata(){

    return data;

    }

    public void setlchild(BTNode lchild ){

    this.lchild=lchild;

    }

    public BTNode getlchild(){

    return this.lchild;

    }

    public void setrchild(BTNode rchild ){

    this.rchild=rchild;

    }

    public BTNode getrchild(){

    return this.rchild;

    }

    }

    递归先序创建普通二叉树

    //以输入的值是否为0来确定其是不是有孩子结点。

    public static BTNode preCreat(BTNode btnode){

    Scanner in =new Scanner(System.in);

    System.out.println("输入结点的值");

    int value=in.nextInt();

    if(value!=0){

    btnode=new BTNode();

    btnode.setdata(value);

    //以下两行是核心代码

    btnode.setlchild(preCreat(btnode.getlchild()));

    btnode.setrchild(preCreat(btnode.getrchild()));

    }

    else

    //这个是一定要有的,确定最终的结束结点

    btnode=null;

    return btnode;

    }

    先序遍历以及访问处理

    public static void visit(BTNode btnode){

    if(btnode!=null)

    System.out.print(btnode.getdata() + " ,");

    }

    public static void preorder(BTNode btnode) {

    if(btnode!=null){

    visit(btnode);

    preorder(btnode.getlchild());

    preorder(btnode.getrchild());

    }

    }

    测试

    public static void main(String[] args){

    BTNode tree=new BTNode();

    tree=preCreat(tree);

    preorder(tree);

    }

    那么怎么输入呢?

    由于0是结束符号。上 面的那个图其实应该是这样的

    0d03df56b4096f32ecbdd556530e9489.png

    所以先序输入进控制台的是:

    1 回车

    2 回车

    0 回车

    4 回车

    0 回车

    0 回车

    3 回车

    0 回车

    0 回车

    输入一个数字回车一次。

    总结

    每个方法我都封装好了,如果你有需要,则可以直接复制在一个类中进行测试。

    我已经亲自测试,结果无误。

    核心思想:递归建立普通二叉树,什么时候是空结点。若要创建任意的二叉树注意应该怎么输入。

    展开全文
  • 要求用数据结构 代码后面要有注释 底下的要求一个也不能漏 图的DFS遍历 要求: 1) 先任意创建一个图; 2) 图的DFS的递归和非递归算法的实现 3) 要求用邻接矩阵、邻接表两种结构存储实现
  • 1.准备工作:创建一个visited数组,用来记录已被访问过的顶点;创建一个队列,用来存放每一层的顶点;初始化G。 2.从中的v0开始访问,将的visited[v0]数组的值设置为true,同时将v0入队。 3.只要队列不空,则...

    广度优先搜索

    1.准备工作:创建一个visited数组,用来记录已被访问过的顶点;创建一个队列,用来存放每一层的顶点;初始化图G。
    2.从图中的v0开始访问,将的visited[v0]数组的值设置为true,同时将v0入队。
    3.只要队列不空,则重复如下操作:
    (1)队头顶点u出队。
    (2)依次检查u的所有邻接顶点w,若visited[w]的值为false,则访问w,并将visited[w]置为true,同时将w入队。

    用邻接矩阵表示图的广度优先搜索

    /*一些量的定义*/
    queue<char> q;				//定义一个队列,使用库函数queue
    #define MVNum 100			//表示最大顶点个数
    bool visited[MVNum];		        //定义一个visited数组,记录已被访问的顶点
    /*邻接矩阵存储表示*/
    typedef struct AMGraph
    {
    	char vexs[MVNum];            //顶点表
    	int arcs[MVNum][MVNum];      //邻接矩阵
    	int vexnum, arcnum;          //当前的顶点数和边数
    }AMGraph;
    /*找到顶点v的对应下标*/
    int LocateVex(AMGraph &G, char v)
    {
    	int i;
    	for (i = 0; i < G.vexnum; i++)
    		if (G.vexs[i] == v)
    			return i;
    }
    /*采用邻接矩阵表示法,创建无向图G*/
    int CreateUDG_1(AMGraph &G)
    {
    	int i, j, k;
    	char v1, v2;
    	scanf("%d%d", &G.vexnum, &G.arcnum);	                //输入总顶点数,总边数
    	getchar();				   	        //获取'\n’,防止其对之后的字符输入造成影响
    	for (i = 0; i < G.vexnum; i++)			
    		scanf("%c", &G.vexs[i]);			//依次输入点的信息
    	for (i = 0; i < G.vexnum; i++)
    		for (j = 0; j < G.vexnum; j++)
    			G.arcs[i][j] = 0;			//初始化邻接矩阵边,0表示顶点i和j之间无边
    	for (k = 0; k < G.arcnum; k++)
    	{
    		getchar();
    		scanf("%c%c", &v1, &v2);			//输入一条边依附的顶点
    		i = LocateVex(G, v1);				//找到顶点i的下标
    		j = LocateVex(G, v2);				//找到顶点j的下标
    		G.arcs[i][j] = G.arcs[j][i] = 1;	        //1表示顶点i和j之间有边,无向图不区分方向
    	}
    	return 1;
    }
    /*采用邻接矩阵表示图的广度优先遍历*/
    void BFS_AM(AMGraph &G,char v0)
    {
    	/*从v0元素开始访问图*/
    	int u,i,v,w;
    	v = LocateVex(G,v0);                 //找到v0对应的下标
    	printf("%c ", v0);                   //打印v0
    	visited[v] = 1;		                 //顶点v0已被访问
    	q.push(v0);			                //将v0入队
    	while (!q.empty())
    	{
    		u = q.front();				//将队头元素u出队,开始访问u的所有邻接点
    		v = LocateVex(G, u);			//得到顶点u的对应下标
    		q.pop();				//将顶点u出队
    		for (i = 0; i < G.vexnum; i++)
    		{
    			w = G.vexs[i];
    			if (G.arcs[v][i] && !visited[i])//顶点u和w间有边,且顶点w未被访问
    			{
    				printf("%c ", w);	//打印顶点w
    				q.push(w);		//将顶点w入队
    				visited[i] = 1;		//顶点w已被访问
    			}
    		}
    	}
    }   
    

    用邻接表表示图的广度优先搜索

    /*找到顶点对应的下标*/
    int LocateVex(ALGraph &G, char v)
    {
    	int i;
    	for (i = 0; i < G.vexnum; i++)
    		if (v == G.vertices[i].data)
    			return i;
    }
    /*邻接表存储表示*/
    typedef struct ArcNode	        //边结点
    {
    	int adjvex;		//该边所指向的顶点的位置
    	ArcNode *nextarc;	//指向下一条边的指针
    	int info;		//和边相关的信息,如权值
    }ArcNode;
     
    typedef struct VexNode		//表头结点
    {
    	char data;				
    	ArcNode *firstarc;	//指向第一条依附该顶点的边的指针
    }VexNode,AdjList[MVNum];	//AbjList表示一个表头结点表
     
    typedef struct ALGraph
    {
    	AdjList vertices;
    	int vexnum, arcnum;
    }ALGraph;
    /*采用邻接表表示法,创建无向图G*/
    int CreateUDG_2(ALGraph &G)
    {
    	int i, j, k;
    	char v1, v2;
    	scanf("%d%d", &G.vexnum, &G.arcnum);	        //输入总顶点数,总边数
    	getchar();
    	for (i = 0; i < G.vexnum; i++)			//输入各顶点,构造表头结点表
    	{
    		scanf("%c", &G.vertices[i].data);	//输入顶点值
    		G.vertices[i].firstarc = NULL;		//初始化每个表头结点的指针域为NULL
    	}
    	for (k = 0; k < G.arcnum; k++)			//输入各边,构造邻接表
    	{
    		getchar();
    		scanf("%c%c", &v1, &v2);			//输入一条边依附的两个顶点
    		i = LocateVex(G, v1);				//找到顶点i的下标
    		j = LocateVex(G, v2);				//找到顶点j的下标
    		ArcNode *p1 = new ArcNode;			//创建一个边结点*p1
    		p1->adjvex = j;						//其邻接点域为j
    		p1->nextarc = G.vertices[i].firstarc; G.vertices[i].firstarc = p1; // 将新结点*p插入到顶点v1的边表头部
    		ArcNode *p2 = new ArcNode;			//生成另一个对称的新的表结点*p2
    		p2->adjvex = i;
    		p2->nextarc = G.vertices[j].firstarc;
    		G.vertices[j].firstarc = p1;
    	}
    	return 1;
    }
    /*采用邻接表表示图的广度优先遍历*/
    void BFS_AL(ALGraph &G, char v0)
    {
    	int u,w,v;
    	ArcNode *p;
    	printf("%c ", v0);		                                        //打印顶点v0
    	v = LocateVex(G, v0);	                                                //找到v0对应的下标
    	visited[v] = 1;			                                        //顶点v0已被访问
    	q.push(v0);				                                //将顶点v0入队
    	while (!q.empty())
    	{
    		u = q.front();		                                        //将顶点元素u出队,开始访问u的所有邻接点
    		v = LocateVex(G, u);                                            //得到顶点u的对应下标
    		q.pop();			//将顶点u出队
    		for (p = G.vertices[v].firstarc; p; p = p->nextarc)		//遍历顶点u的邻接点
    		{
    			w = p->adjvex;	
    			if (!visited[w])	//顶点p未被访问
    			{
    				printf("%c ", G.vertices[w].data);	        //打印顶点p
    				visited[w] = 1;				        //顶点p已被访问
    				q.push(G.vertices[w].data);			//将顶点p入队
    			}
    		}
    	}
    }
    

    深度优先搜索

    深度优先搜索类似于树的先序遍历,具体过程如下:
    创建一个visited数组,用于记录所有被访问过的顶点。
    1.从图中v0出发,访问v0。
    2.找出v0的第一个未被访问的邻接点,访问该顶点。以该顶点为新顶点,重复此步骤,直至刚访问过的顶点没有未被访问的邻接点为止。
    3.返回前一个访问过的仍有未被访问邻接点的顶点,继续访问该顶点的下一个未被访问领接点。
    4.重复2,3步骤,直至所有顶点均被访问,搜索结束。
    用邻接矩阵表示图的深度优先搜索

    void DFS_AM(AMGraph &G, int v)
    {
    	int w;
    	printf("%c ", G.vexs[v]);
    	visited[v] = 1;
    	for (w = 0; w < G.vexnum; w++)
    		if (G.arcs[v][w]&&!visited[w]) //递归调用
    			DFS_AM(G,w);
    }
    

    用邻接表表示图的深度优先搜素

    void DFS_AL(ALGraph &G, int v)
    {
    	int w;
    	printf("%c ", G.vertices[v].data);
    	visited[v] = 1;
    	ArcNode *p = new ArcNode;
    	p = G.vertices[v].firstarc;
    	while (p)
    	{
    		w = p->adjvex;
    		if (!visited[w]) DFS_AL(G, w);
    		p = p->nextarc;
    	}
    }
    
    展开全文
  • 彻底搞懂二叉树的创建与遍历二叉树基本概念二叉树的递归创建二叉链表的节点结构定义递归创建一图彻底搞懂递归创建二叉树的遍历前序遍历中序遍历后序遍历一彻底搞懂遍历顺序的前中后代码整合: 二叉树基本概念 ...
  • 一、示例要求 代码实现如下图结构 二、代码实现示例 1、创建图的类 ... ... * @description: 定义一个图 类 * @author: xiaozhi * @create: 2020-10-27 21:58 */ public class Graph { private
  • 双向链表是为了满足更加方便的查找前驱,而付出空间的代价的一个数据结构。双向链表的节点定义如下: typedef struct node { int x; struct node *prior,*next; }DLNode; 双向链表的空间结构如下所示: ...
  • 包含四文件的代码和一张测试效果: AdjacencyMatrix.h文件: 构建邻接矩阵的存储结构与邻接矩阵的创建函数 DBFSAdjacencyMatrix.h文件: 构建邻接矩阵的深度优先遍历与广度优先遍历函数 StackAndQueue.h文件: ...
  • JAVA数据结构基础–的两种创建方式 的邻接矩阵表示 如图示一个有向转为矩阵表示的例子(矩阵中空格表示无穷大,即无路径到达)。矩阵的行表示起始点,列表示终止点。对角线元素表示自己到自己,全为0。 ...
  • 数据结构二叉树代码

    2020-04-06 15:50:10
    数据结构--超全二叉树详细c版欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中...
  • 从键盘接收有向的顶点集,弧集,创建有向,并完成下列任务: (1)计算结点的出度、入度以及度; (2) 从第一个顶点出发,求一个深度优先遍历序列; (3) 从第一个顶点顶点出发,求一个广度优先遍历序列。 注意:以...
  • 2.网上数据结构和算法的课程不少,但存在两问题:1)授课方式单一,大多是照着代码遍,数据结构和算法本身就比较难理解,对基础好的学员来说,还好一点,对基础不好的学生来说,基本上就是听天书了2)说是讲数据...
  • 二叉树的二叉链表存储结构一个结点结构包含三个域:数据域、左、右指针域。如下所示。 二叉树的遍历知识参考:http://blog.csdn.net/fansongy/article/details/6798278/ 二叉树的二叉链表存储表示的代码...
  • 的存储结构 邻接矩阵 邻接表 邻接表是一种链式存储结构,对图中每个顶点 i 建立一个单链表,单链表的头节点存放顶点的...创建一个二维数组 G,每行表示一个花园,共 N 行,列表示与该花园邻接的花园。用一维数组
  • #include &lt;iostream&gt; #define MAXVEX 4 //起始顶点数默认为6,可在此直接修改 ...//注意点1:下标0的位置都不用,所以要多开辟一个空间 //注意点2:头结点信息既可以是字符A,B,C,D,...
  • 文章目录图图的基本介绍和存储形式的表示方式创建图解和代码实现的深度优先(DFS)算法图解与实现 的基本介绍和存储形式 基本介绍: 为什么要有? 前面我们学了线性表和树,线性表局限于一个直接前驱...
  • 标题 链表的插入操作: 创建链表: 修正:下解释,创建一个节点吧数组数据35存进来,然后把节点放到rear的下一项,再把指针rear给移动到node节点现在项,准备下一次插入。
  • 用图解决畅通工程案例 畅通工程-续 介绍 ...创建一个图无向图Undigraph对象 ,表示城市的图; 分别调用Undigraph对象的addEdge(0,1),addEdge(6,9),addEdge(3,8),addEdge(5,11),addEdge(2,12),addE...
  • 含义:用两个数组来表示一个一维数组存储顶点的信息,一个二维数组(邻接矩阵)存储边或弧的信息。 对于普通的(指没有权值的): 如果 或 则. 反之,. 求某个顶点的度,其实就是这个顶点 在矩阵中第 行...
  • 数据结构,其中节点可以具有零或多相邻元素。两节点之间的连接称为边。节点也可称为顶点。 表示多对多的关系时,就会用到概念 1、的名词解释 2、的表示方法 3、代码实现 创建...
  • 上节中我们已经知道有些问题,如果用递归解决变得非常容易。但是仍然很难在大脑里形成一种模型或可视化的方法,让我们直觉地明白函数递归过程到底发生了什么。这一节我们引入几个例子,用递归的...你可以创建一个t...
  • 这里写自定义目录`数据结构 线性表的顺序存储演示 C语言代码`标题新的改变功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格...
  • 本例中树结构、节点权如下所示顺序存储是指将二叉树存储在一个数组中,通过存储元素的下标反映元素之间的父子关系。任何一个二叉树都可以转换为数组,同理,任何一个数组都可以转换为二叉树。顺序存储的二叉树通常...
  • 数据结构——

    2019-03-10 19:27:18
    定义:一个图就是一些顶点的集合,这些顶点通过一系列边结对(连接)。 著名的图算法(比如广度优先搜索 或者 深度优先搜索) 如何描述: 有两种主要的方法:邻接列表和邻接矩阵。 邻接列表 邻接矩阵 往这个图中...
  • 怎么按照要求创建一棵二叉树 怎么创建下的二叉树? 我写过完全二叉树的创建【数据结构】-java 完全二叉树的创建以及递归遍历算法实现 参考完全二叉树的结点的创建。 对于这种普通的二叉树我们也可以用递归的方式...
  • 对于“破解代码模块”的每一章,我都创建一个对应的模块,其中包含每个数据结构的实现。 数据结构 第1章数组和字符串 哈希表 数组列表 字符串生成器 第2章链表 单链表 双链表 第3章堆栈和队列 堆 队列 第四章树和...
  • dsa网站 这是我的第一个项目。 创建该网站的目的是教授数据结构。 它包括对每种类型的结构的详细说明,旨在演示其工作方式的图像以及有助于学生加深理解的补充代码。 我正在使用HTML,CSS和JavaScript。
  • 前面我们学了线性表和树,它们都有一些局限性,线性表局限于一个直接前驱和一个直接后继的关系,树也只能有一个直接前驱也就是父节点,当我们需要表示多对多的关系时, 这里我们就要用到。 举例    ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,799
精华内容 1,119
关键字:

数据结构创建一个图代码

数据结构 订阅