devbox
寸_铁
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

头歌实践教学平台——数据结构_基于邻接表的新顶点的增加头歌

作者：寸_铁 | 2024-06-19 20:58:44

赞

踩

基于邻接表的新顶点的增加头歌

目录

一、迷宫问题

任务描述

编程要求

输入

输出

测试说明

二、基于Dijsktra算法的最短路径求解

三、六度空间理论

四、基于邻接表的新顶点的增加

五、基于邻接矩阵的新顶点的增加

一、迷宫问题

任务描述

密密被困在一个迷宫里，迷宫有n个路口，编号为1-n。密密现在站在第一个路口，出口编号为m。先给出每个路口通向何处，问密密能否逃出迷宫。

编程要求

输入

多组数据，每组数据n+2行。第一行为一个正整数n代表路口的个数，之后n行，这n行中的第i行为第i个路口的向左路口、向前路口、向右路口。最后一行为一个正整数m代表迷宫的终点。当n=0时输入结束。

输出

每组数据输出一行，若密密能走出迷宫，输出“YES”，否则输出“NO”。

测试说明

平台会对你编写的代码进行测试：

测试输入：

6

0 2 0

3 5 6

0 0 4

0 0 0

0 0 0

7 0 0

7

3

2 0 0

0 0 0

0 0 0

3

0

预期输出：

YES

NO

  1. #include <iostream>
  2. using namespace std;
  3. int m,n;//m:出口编号  n:入口
  4. int tag;//输出标记
  5. int DFS(int k,int (*a)[3])
  6. {//深度搜索第k层，k:当前路口
  7. /**************begin************/
  8. 	int i,j;
  9. 	if(k==m)//到达出口
  10. 	{
  11. 		tag=1;
  12. 		return 0;
  13. 	}
  14. 	for(i=0;i<3;i++)//遍历三个路口
  15. 	{
  16. 		if(0!=a[k][i]&&tag!=1)//如果当前路口有通路，并且没有走过
  17. 		{
  18. 			DFS(a[k][i],a);//进入下一个路口 ，递归
  19. 		}
  20. 	}
  21. 	return 0;
  22.     /**************end************/
  23. }
  24. int main()
  25. {
  26. 	while(cin>>n)
  27. 	{
  28. 	if(n==0)break;
  29. 	int i,j;
  30. 	tag=0;
  31. 	int a[n+1][3];//迷宫
  32. 	for(i=1;i<=n;i++)
  33. 		for(j=0;j<3;j++)
  34. 			cin>> a[i][j];
  35. 	cin>>m;
  36. 	DFS(1,a);//从第一层开始搜索
  37. 	if(tag==1)
  38. 		cout<<"YES"<<endl;
  39. 	else if(tag==0)
  40. 		cout<<"NO"<<endl;
  41. 	}
  42. 	return 0;
  43. }

二、基于Dijsktra算法的最短路径求解

  1. #include <iostream>
  2. #include <cstring>
  3. #define MVNum 100
  4. #define MaxInt 999
  5. using namespace std;
  6.  
  7. typedef struct
  8. {
  9. 	char vexs[MVNum];//点集 
  10. 	int arcs[MVNum][MVNum];//边的邻接矩阵 
  11. 	int vexnum,arcnum;//点数&边数 
  12. }AMGraph;
  13.  
  14. int LocateVex(AMGraph G,char u)
  15.  {//存在则返回u在顶点表中的下标;否则返回-1
  16.    int i;
  17.    for(i=0;i<G.vexnum;++i)
  18.      if(u==G.vexs[i])
  19.        return i;
  20.    return -1;
  21.  }
  22.  
  23. void InitAM(AMGraph &G)
  24. {//初始化图 
  25.  	memset(G.vexs,0,sizeof(G.vexs));//初始化顶点集 
  26. 	for(int i=0;i<MVNum;i++)
  27. 		for(int j=0;j<MVNum;j++)
  28. 			G.arcs[i][j]=MaxInt;
  29. 	return;
  30. }
  31.  
  32. int CreateUDN(AMGraph &G)
  33. {
  34. 	int i,j,k;  
  35. 	//G.vexnum++;
  36. 	for(i=0;i<G.vexnum;i++)
  37. 		cin>>G.vexs[i];
  38. 	for(k=0;k<G.arcnum;k++)//将边录入邻接矩阵，顺便将顶点录入 
  39. 	{
  40. 		char v1,v2;int w;
  41. 		cin>>v1>>v2>>w;//边的端点
  42. 		i=LocateVex(G,v1);
  43. 		j=LocateVex(G,v2);
  44. 		G.arcs[i][j]=w;
  45. 		G.arcs[j][i]=G.arcs[i][j];
  46. 		G.arcs[i][j]=w;
  47. 		G.arcs[k][k]=0;
  48. 	}
  49. 	return 1;
  50. }
  51.  
  52. void ShortestPath_DIJ(AMGraph G){ 
  53.     //用Dijkstra算法求有向网G的v0顶点到其余顶点的最短路径 
  54.     char v0,v1;
  55.     int S[MVNum];
  56.     int D[MVNum];
  57.     int Path[MVNum];
  58.     cin>>v0>>v1;
  59.     int v00=LocateVex(G,v0);
  60.     int n=G.vexnum; int v;                  		//n为G中顶点的个数 
  61.     for( v = 0; v<n; ++v){             	//n个顶点依次初始化 
  62.        S[v] = false;                  	//S初始为空集 
  63.        D[v] = G.arcs[v00][v];           	//将v0到各个终点的最短路径长度初始化 
  64.        if(D[v]< MaxInt)  Path [v]=v00; //v0和v之间有弧，将v的前驱置为v0 
  65.        else Path [v]=-1;               	//如果v0和v之间无弧，则将v的前驱置为-1 
  66.       }//for 
  67.       S[v00]=true;                    	//将v0加入S 
  68.       D[v00]=0;     
  69. 	  int w;  int i;               		//源点到源点的距离为0 	
  70. /*―开始主循环，每次求得v0到某个顶点v的最短路径，将v加到S集―*/ 
  71.       for(i=1;i<n; ++i){               	//对其余n?1个顶点，依次进行计算 
  72.         int min= MaxInt;  
  73.         for(w=0;w<n; ++w) 
  74.           if(!S[w]&&D[w]<min)  
  75.               {v=w; min=D[w];}         	//选择一条当前的最短路径，终点为v 
  76.         S[v]=true;                   		//将v加入S 
  77.         for(w=0;w<n; ++w) 	//更新从v0出发到集合V?S上所有顶点的最短路径长度 
  78.         if(!S[w]&&(D[v]+G.arcs[v][w]<D[w])){ 
  79.              D[w]=D[v]+G.arcs[v][w];   	//更新D[w] 
  80.              Path [w]=v;              		//更改w的前驱为v 
  81.         }//if 
  82.     }//for   
  83. 	w=LocateVex(G,v1);
  84. 	cout<<D[w]<<endl; 
  85. 	char road[G.vexnum];
  86. 	road[0]=G.vexs[w];
  87. 	int t=w;i=0;
  88. 	while(1)
  89. 	{  
  90. 		i++;
  91. 		if(t==-1||t==v00)break;
  92. 		//cout<<G.vexs[Path[t]];//<<"#"<<Path[t]<<"#"<<Path[Path[t]]
  93. 		road[i]=G.vexs[Path[t]];
  94. 		//if(t!=-1||t!=v00)cout<<" ";
  95. 		t=Path[t];	
  96. 	}
  97. 	while(i)
  98. 	{
  99. 		if(road[i])cout<<road[i]<<" ";
  100. 		i--;
  101. 	} 
  102. 	cout<<road[0];
  103. 	cout<<endl;
  104. }//ShortestPath_DIJ 
  105.  
  106. void CA(AMGraph &G)
  107. {//输出矩阵 
  108. 	int i;int j;
  109. 	//输出表头 
  110. 	cout<<0<<" ";
  111. 	for(int i=0,j;i<G.vexnum;i++)
  112. 	{
  113. 			cout<<G.vexs[i];
  114. 			if(i!=G.vexnum-1)cout<<" ";
  115. 	}
  116. 	cout<<endl;
  117. 	for(i=0;i<G.vexnum;i++)
  118. 	{
  119. 		//输出表头 
  120. 		cout<<G.vexs[i];
  121. 		if(i!=G.vexnum)cout<<" ";
  122. 		//输出内容 
  123. 		for(j=0;j<G.vexnum;j++)
  124. 		{
  125. 			cout<<G.arcs[i][j];
  126. 			if(j!=G.vexnum-1)cout<<" "; 
  127. 		}
  128. 		cout<<endl;
  129. 	}
  130.  } 
  131.  
  132. int main()
  133. {	
  134. 	while(1)
  135. 	{
  136. 		AMGraph G;
  137. 		InitAM(G);
  138. 		cin>>G.vexnum>>G.arcnum;
  139. 		if(G.vexnum==0&&G.arcnum==0)break;
  140. 		CreateUDN(G);
  141. 		//CA(G);
  142. 		ShortestPath_DIJ(G);
  143. 		//cout<<"--------------"<<endl;
  144. 	}
  145. }

三、六度空间理论

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<string.h>
  4. #define MAXN 10005
  5.  
  6. typedef struct VNode* Vertex;
  7. struct VNode {
  8. 	Vertex Next;
  9. 	int V;
  10. };
  11.  
  12. typedef struct LNode {
  13. 	Vertex FirstEdge;
  14. 	
  15. }List[MAXN];
  16.  
  17. typedef struct GNode* Graph;
  18. struct GNode {
  19. 	int Nv,Ne;
  20. 	List Head;
  21. };
  22.  
  23. Graph G;
  24.  
  25.  
  26. void Insert(int v,int w) {
  27. 	Vertex NewNode = (Vertex)malloc(sizeof(struct VNode));
  28. 	NewNode->V = v;
  29. 	NewNode->Next = G->Head[w].FirstEdge;
  30. 	G->Head[w].FirstEdge = NewNode;
  31. 	
  32. 	NewNode = (Vertex) malloc(sizeof(struct VNode));
  33. 	NewNode->V = w;
  34. 	NewNode->Next = G->Head[v].FirstEdge;
  35. 	G->Head[v].FirstEdge = NewNode;
  36. }
  37.  
  38. int visit[MAXN];
  39.  
  40. void BFS(int s) {
  41. 	int Q[MAXN],front = 0,rear = 0,v,i;
  42. 	int tail,last = s,cnt = 0,level = 0,kase = s;
  43. 	Vertex p;
  44. 	double perc;
  45. 	Q[++rear] = s;
  46. 	visit[s] = 1;
  47. 	cnt ++;
  48. 	while(rear!=front) {
  49. 		v = Q[++front];
  50. 		for(p = G->Head[v].FirstEdge;p;p = p->Next) {
  51. 			if(!visit[p->V]) {
  52. 				Q[++rear] = p->V;
  53. 				visit[p->V] =1;
  54. 				cnt ++;
  55. 				tail = p->V;
  56. 			}
  57. 		}
  58. 		if(v==last) {
  59. 			level ++;
  60. 			last = tail;
  61. 		}
  62. 		if(level == 6) break;
  63. 	}
  64. 	perc = ((double)cnt)/((double)G->Nv) * 100;
  65. 	printf("%d: %.2lf%%\n",kase,perc);
  66. }
  67. int main()
  68. {
  69. 	int i;
  70. 	int v,w;
  71. 	G = (Graph)malloc(sizeof(struct GNode));
  72. 	while(1){
  73. 	scanf("%d%d",&G->Nv,&G->Ne);
  74. 	if(!G->Nv||!G->Ne)
  75. 		return 0;
  76. 	for(i=1;i<=G->Nv;i++)
  77. 		G->Head[i].FirstEdge = NULL;
  78. 	for(i=1;i<=G->Ne;i++) {
  79. 		scanf("%d%d",&v,&w);
  80. 		Insert(v,w);
  81. 	}
  82. 	for(i=1;i<=G->Nv;i++) {
  83. 		memset(visit,0,sizeof(visit));
  84. 		BFS(i);
  85. 	}
  86. 	}
  87. 	return 0;
  88. 	
  89. }

四、基于邻接表的新顶点的增加

  1. #include<iostream>
  2. #define OK 1
  3. #define ERROR 0
  4. #define OVERFLOW -2
  5. #define MVNum 100
  6. using namespace std;
  7.  
  8. typedef struct VNode{
  9. 	int data;
  10. 	struct VNode *next;
  11. }VNode,*NodeList;
  12.  
  13. typedef struct{
  14. 	NodeList V[MVNum];
  15. 	int vexnum,arcnum;
  16. }ALGragh ;
  17.  
  18. int CreateUDG(ALGragh  &G,int vexnum,int arcnum){
  19. 	G.vexnum = vexnum;
  20. 	G.arcnum = arcnum;
  21. 	for(int i=1;i<=vexnum; i ++){
  22. 		G.V[i] = new VNode;
  23. 		G.V[i]->next = NULL;
  24. 		G.V[i]->data = i;
  25. 	}
  26.     for(int i=0;i<arcnum;i++){
  27. 		int v1,v2;
  28. 		cin>>v1>>v2;
  29. 		NodeList p1 =new VNode;
  30. 		p1->data =v2;
  31. 		p1->next =G.V[v1]->next;
  32. 		G.V[v1]->next = p1;
  33. 		NodeList p2 =new VNode;
  34. 		p2->data = v1;
  35. 		p2->next = G.V[v2]->next;
  36. 		G.V[v2]->next = p2;
  37. 	}
  38. 	return OK;
  39. }
  40.  
  41. int InsertVex(ALGragh  &G){
  42. 	int data;
  43. 	cin>>data;
  44. 	G.vexnum++;
  45. 	G.V[G.vexnum] = new VNode;
  46.     G.V[G.vexnum]->data = data;
  47.     G.V[G.vexnum]->next = NULL;
  48.     return OK;
  49. }
  50.  
  51. int PrintGraph(ALGragh  G){
  52. 	for(int i=1;i<=G.vexnum;i++){
  53. 		NodeList p =G.V[i];
  54. 		while(p->next){
  55. 			cout<<p->data<<" ";
  56. 			p = p->next;
  57. 		}
  58. 		cout<<p->data<<endl;
  59. 	}
  60. 	return OK;
  61. }
  62.  
  63.  
  64.  
  65. int main()
  66. {
  67. 	int n,m;
  68. 	while(cin>>n>>m)
  69. 	{
  70.       	if(n==0&&m==0) break;     //输入结束标志
  71.       	ALGragh G;
  72.        	CreateUDG(G,n,m);      //采用邻接表表示法，创建无向图G
  73.      	InsertVex(G);        //在图G中增添新顶点
  74. 	   	PrintGraph(G);      //输出图G
  75. 	}
  76. 	return 0;
  77. }
  78.

五、基于邻接矩阵的新顶点的增加

  1. #include <iostream>
  2. #define MaxInt 32767 
  3. #define MVNum 100
  4. #define OK 1
  5. #define ERROR -1
  6. using namespace std;
  7.  
  8. typedef struct{
  9. 	char vexs[MVNum];
  10. 	int arcs[MVNum][MVNum];
  11. 	int vexnum,arcnum;
  12. }AMGraph;
  13.  
  14. int InitAM(AMGraph &G){
  15.     for(int i =0;i<MVNum; i++)
  16.       G.vexs[i] = 0;
  17.     for(int i =0;i<MVNum; i++)
  18.      for(int j =0 ; j<MVNum;j++){
  19. 	 	G.arcs[i][j]= 0;
  20. 	}
  21. 	return OK;
  22. }
  23.  
  24. int LocateVex(AMGraph G,char v){
  25. 	for(int i=0;i<G.vexnum;i++)
  26. 	 if(v==G.vexs[i])
  27. 	   return i;
  28. 	return ERROR;
  29. }
  30.  
  31. int CreateUDN(AMGraph &G){
  32. 	int n;
  33. 	int vex = 0;
  34. 	for(n=0;n<G.arcnum;n++){
  35. 		char v1,v2;
  36. 		cin>>v1>>v2;
  37. 		int tag = 0;
  38. 		for(int i =0;i<G.vexnum;i++){
  39. 			if(v1==G.vexs[i]) tag = 1;
  40. 		}
  41. 		if(tag == 0){
  42. 			G.vexs[vex] = v1;
  43. 			vex++;
  44. 		}
  45. 		tag = 0;
  46. 		for(int i =0;i<G.vexnum;i++){
  47. 			if(v2==G.vexs[i]) tag = 1;
  48. 		}
  49. 		if(tag == 0){
  50. 			G.vexs[vex] = v2;
  51. 			vex++;
  52. 		}
  53. 		int i = LocateVex(G,v1);
  54. 		int j = LocateVex(G,v2);
  55. 		G.arcs[i][j] = 1;
  56. 		G.arcs[j][i] = G.arcs[i][j]; 
  57. 	}
  58. 	cin>>G.vexs[vex];
  59.     G.vexnum++;
  60. 	return OK; 
  61. }
  62. void PrintAM(AMGraph &G){
  63. 	int i,j;
  64. 	cout<<0<<" ";
  65. 	for(i=0;i<G.vexnum;i++)
  66. 	{
  67. 			cout<<G.vexs[i];
  68. 			if(i!=G.vexnum-1)
  69. 			  cout<<" ";
  70. 	}
  71. 	cout<<endl;
  72. 	for(i=0;i<G.vexnum;i++)
  73. 	{
  74. 		cout<<G.vexs[i]; //输出表头 
  75. 		if(i!=G.vexnum)
  76. 		   cout<<" ";
  77. 		//输出内容 
  78. 		for(j=0;j<G.vexnum;j++)
  79. 		{
  80. 			cout<<G.arcs[i][j];
  81. 			if(j!=G.vexnum-1)
  82. 			  cout<<" "; 
  83. 		}
  84. 		cout<<endl;
  85. 	}
  86.  } 
  87.  int main()
  88. {	
  89.     AMGraph G;
  90. 	while(cin>>G.vexnum>>G.arcnum&&G.vexnum!=0&&G.arcnum!=0)
  91. 	{	InitAM(G);
  92. 		CreateUDN(G);
  93. 		PrintAM(G); 	
  94. 	}
  95. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/寸_铁/article/detail/737656
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号