头歌数据结构——图——课上课后练

这篇具有很好参考价值的文章主要介绍了头歌数据结构——图——课上课后练。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

第1关:图的邻接矩阵存储及图初始化

本关任务:根据下面的描述和要求,完成图的邻接矩阵数据结构定义,及图初始化函数。

#include <stdio.h>
#include <stdlib.h>
#define N  6
#define MAX 100
typedef struct {
	int vex;
	int shortweight;
}ShortWeight;
typedef struct QueueNode{
	int val;
	struct QueueNode* next;
}QueueNode;
 
typedef struct Queue{
	QueueNode *head;
	QueueNode *tail;
}Queue;
//邻接矩阵数据结构 
typedef  struct{
   int vcount;//顶点数
   int type ;//0 无向图,1 有向图
   char  vexs[N]  ;     // 顶点信息
   int  arcs[N][N]; //关系矩阵
} GraphMatrix;
 
//邻接表数据结构
struct EdgeNode { //边表中的结点
      int  endvex;    //相邻顶点在顶点表中下标
      int  weight;  //边的权
      struct EdgeNode  * nextedge;   //链字段
};   
typedef struct EdgeNode * EdgeList;
 
typedef struct
{
   char  vertex;  //记录顶点信息
   int degree;//用于记录顶点的入度,在拓扑排序时需使用
   EdgeList  edgelist;  //指向边表的指针
} VexNode; 
typedef struct{
   VexNode  *vexs[N];  //N个顶点
   int type ;//0 无向图,1 有向图
   int vcount;//顶点数
} GraphList; 

/*第一关 完成图初始化
*/
void printGraph(GraphMatrix *G)
{//本函数输出图的邻接矩阵
 int i,j;
 for(i=0;i<G->vcount;i++)
 {
//  printf("%c ",G->vexs[i]);
  for( j=0;j<G->vcount;j++)
     printf("%d ",G->arcs[i][j]);
  printf("\n");
 }
}

/*第一关 完成图初始化-邻接矩阵
*/
GraphMatrix *initGraphMatrix( )
{
  /*第一行输入图的类型、图的顶点数和边数,第二行输入各条边的两顶点的编号,按顶点编号从小到大的顺序输入。
输出邻接矩阵,不需要考虑输入的数字非法情况,不输入顶点的信息*/
   GraphMatrix *G;
   G=(GraphMatrix *)malloc(sizeof(GraphMatrix));
   int t,v,s;
   scanf("%d %d %d",&t,&v,&s);
   G->vcount=v;
   G->type=t;
   int i,j;
   for(i=0;i<N;i++){
      for(j=0;j<N;j++){
         G->arcs[i][j]=0;
      }
   }
   int head,tail;
   if(t==0)
      for(i=0;i<N;i++){
         scanf("%d %d",&head,&tail);
         G->arcs[head][tail]=1;
         G->arcs[tail][head]=1;
      }
   if(t==1){
      for(i=0;i<N;i++){
         scanf("%d %d",&head,&tail);
         G->arcs[head][tail]=1;
      }
   }
   return G;
}
/*第二关 完成图初始化-邻接表,并完成输出图的邻接表函数
*/
GraphList* initGraphList()
{
	/*第一行输入图的类型、图的顶点数和边数,第二行输入各条边的两顶点的编号,按顶点编号从小到大的顺序输入。
  输出邻接表。不需考虑输入的数字非法情况,输入顶点的信息*/
	GraphList* G = (GraphList*)malloc(sizeof(GraphList));
	int t, v, s;
	scanf("%d%d%d", &t, &v, &s);
	G->vcount = v;
	G->type = t;
	int i, j, k, l;
	char vex[N];
	char ch = getchar();
	for (i = 0; i < v; i++) {
		scanf("%c", &vex[i]);
	}
	for (i = 0; i < v; i++) {
		G->vexs[i] = (VexNode*)malloc(sizeof(VexNode));
		G->vexs[i]->vertex = vex[i];
		G->vexs[i]->edgelist = (EdgeList)malloc(sizeof(struct EdgeNode));
		G->vexs[i]->edgelist->nextedge = NULL;
	}
	for (i = 0; i < s; i++) {
		int head, tail,w;
		scanf("%d %d %d", &head, &tail,&w);
		if (t == 0) {
			for (k = 0; k < v; k++) {
				if (G->vexs[k]->vertex - '0' == head) {
					EdgeList node1 = (EdgeList)malloc(sizeof(struct EdgeNode));
					for (j = 0; j < v; j++) {
						if (vex[j] - '0' == tail) {
							node1->weight = w;
							node1->endvex = j;
							node1->nextedge = G->vexs[k]->edgelist->nextedge;
							G->vexs[k]->edgelist->nextedge = node1;
							break;
						}
					}
					for (j = 0; j < v; j++) {
						if (G->vexs[j]->vertex - '0' == tail) {
							EdgeList node2 = (EdgeList)malloc(sizeof(struct EdgeNode));
							for (l = 0; l < v; l++) {
								if (vex[l] - '0' == head) {
									node2->weight = w;
									node2->endvex = l;
									node2->nextedge = G->vexs[j]->edgelist->nextedge;
									G->vexs[j]->edgelist->nextedge = node2;
									break;
								}
							}
						}
					}
				}
 
 
			}
		}
	}
	return G;
}
void printGraphLit( GraphList *G)
{
 /*输出邻接表,输出格式:顶点->邻接顶点编号->...*/
    int i;
	for(i=0;i<G->vcount;i++){
		printf("%c->",G->vexs[i]->vertex);
		EdgeList tp=G->vexs[i]->edgelist->nextedge;
		while(tp->nextedge!=NULL){
			printf("%d->",tp->endvex);
			tp=tp->nextedge;
		}
		printf("%d\n",tp->endvex);
	}
}
/*第三关 完成图的广度遍历(周游),可根据需要添加自定义函数
*/
int visited[N]={0};
void BFS_list(GraphList *G)
{
	int i,j;
	printf("%c ",G->vexs[0]->vertex);
	visited[0]=1;
	EdgeList tp=G->vexs[i]->edgelist->nextedge;
	while(tp->nextedge!=NULL){
		printf("%d ",tp->endvex);
		visited[tp->endvex]=1;
		tp=tp->nextedge;
	}
	printf("%d ",tp->endvex);
	visited[tp->endvex]=1;
	for(i=N-1;i>=0;i--){
		if(visited[i]==1){
			EdgeList tp=G->vexs[i]->edgelist->nextedge;
			while(tp->nextedge!=NULL && visited[tp->endvex]==0){
			printf("%d ",tp->endvex);
			visited[tp->endvex]=1;
			tp=tp->nextedge;
			}
		}
	}
	
}
/*第四关 完成图的深度遍历(周游),可根据需要添加自定义函数
*/
int visited2[N];
void DFS_list(GraphList *G)
{
	int i,j,k;
	for(i=0;i<N;i++){
		visited2[i]=0;
	}
	printf("%c ",G->vexs[0]->vertex);
	visited2[0]=1;
	EdgeList tp=G->vexs[0]->edgelist->nextedge;
	printf("%d ",tp->endvex);
	visited2[tp->endvex]=1;
	int num=4;
	while(1){
		for(i=0;i<G->vcount;i++){
			if(G->vexs[i]->vertex-'0'==tp->endvex){
				EdgeList tp2=G->vexs[i]->edgelist->nextedge;
				if(visited2[tp2->endvex]==0){
					tp=tp2;
					printf("%d ",tp2->endvex);
					visited2[tp2->endvex]=1;
					break;
				}
				else if(visited2[tp2->endvex]==1){
					for(tp2=tp2->nextedge;tp2!=NULL;tp2=tp2->nextedge){
						if(visited2[tp2->endvex]==0){
							tp=tp2;
							printf("%d ",tp2->endvex);
							visited2[tp2->endvex]=1;
							break;
						}
					}
					
				}
				
			}
		}
		int count=0;
		for(i=0;i<N;i++){
			if(visited2[i]==1) count++;
		}
		if(count==G->vcount) break;
	}
	
}
/*第五关 生成图的拓扑排序,可根据需要添加自定义函数
*/
void QueueInit(Queue* pq) {
	pq->head = pq->tail = NULL;
}
void QueuePush(Queue* pq, int x) {
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	newnode->val = x;
	newnode->next = NULL;
	if (pq->tail == NULL) {
		pq->head = pq->tail = newnode;
	}
	else {
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}
void QueuePop(Queue* pq) {
	if (pq->head->next == NULL) {
		pq->head = pq->tail = NULL;
	}
	else {
		QueueNode* next = pq->head->next;
		pq->head = next;
	}
}
int QueueFront(Queue* pq) {
	return pq->head->val;
}
int QueueEmpty(Queue* pq) {
	return pq->head == NULL;
}
void Top_list(GraphList* G)
{
	Queue* Q=(Queue *)malloc(sizeof(Queue));
	QueueInit(Q);
	int i;
	int deg[N];
	for (i = 0; i < N; i++) {
		deg[i] = 0;
	}
	for (i = 0; i < N; i++) {
		deg[i] = G->vexs[i]->degree;
	}
 
	for (i = 0; i < N; i++) {
		if (deg[i] == 0) {
			QueuePush(Q, i);
		}
	}
	while (!QueueEmpty(Q)) {
		int j = QueueFront(Q);
		printf("%d ", j);
		QueuePop(Q);
		EdgeList p;
		p = G->vexs[j]->edgelist->nextedge;
		while (p != NULL) {
			deg[p->endvex]--;
			if (deg[p->endvex] == 0) {
				QueuePush(Q, p->endvex);
			}
			p = p->nextedge;
		}
	}
}
/*第六关 prim算法生成最小生成树
*/
int GetShortWeight(GraphList* G,ShortWeight *shortw) {
	int i;
	int min = MAX;
	int loc;
	for (i = 1; i < G->vcount; i++) {
		if (min > shortw[i].shortweight && shortw[i].shortweight != 0) {
			min = shortw[i].shortweight;
			loc = i;
		}
	}
	return loc;
}
 
void Prim_list(GraphList* G)
{
	int i, j, k;
	ShortWeight shortw[10];
	for (i = 0; i < 10; i++) {
		shortw[i].shortweight = MAX;
	}
	k = 0;
	EdgeList tp = G->vexs[k]->edgelist->nextedge;
	while (tp) {
		shortw[tp->endvex].shortweight= tp->weight;
		shortw[tp->endvex].vex = k;
		tp = tp->nextedge;
	}
	shortw[k].shortweight = 0;
	for (i = 0; i < G->vcount - 1; i++) {
		k = GetShortWeight(G, shortw);
		printf("%d %d\n", shortw[k].vex, k);
		shortw[k].shortweight = 0;
		EdgeList tp2 = G->vexs[k]->edgelist->nextedge;
			while (tp2) {
				if (tp2->weight < shortw[tp2->endvex].shortweight) {
					shortw[tp2->endvex].shortweight = tp2->weight;
					shortw[tp2->endvex].vex = k;
				}
				tp2 = tp2->nextedge;
			}
	}
}
/*第七关 Kruskal算法生成最小生成树
*/

void Kruskal_list(GraphList *G)
{


}

/*第八关 Dijistra算法求最短路径
*/

void Dijkstra_list(GraphList *G)
{


}

第2关:图的邻接表存储及图初始化

本关任务:编写一个能输入图的基本信息(含图的类型,图的顶点,边等),并用邻接表存储图的程序。

#include <stdio.h>
#include <stdlib.h>
#define N  6
#define MAX 100
typedef struct {
	int vex;
	int shortweight;
}ShortWeight;
typedef struct QueueNode{
	int val;
	struct QueueNode* next;
}QueueNode;
 
typedef struct Queue{
	QueueNode *head;
	QueueNode *tail;
}Queue;
//邻接矩阵数据结构 
typedef  struct{
   int vcount;//顶点数
   int type ;//0 无向图,1 有向图
   char  vexs[N]  ;     // 顶点信息
   int  arcs[N][N]; //关系矩阵
} GraphMatrix;
 
//邻接表数据结构
struct EdgeNode { //边表中的结点
      int  endvex;    //相邻顶点在顶点表中下标
      int  weight;  //边的权
      struct EdgeNode  * nextedge;   //链字段
};   
typedef struct EdgeNode * EdgeList;
 
typedef struct
{
   char  vertex;  //记录顶点信息
   int degree;//用于记录顶点的入度,在拓扑排序时需使用
   EdgeList  edgelist;  //指向边表的指针
} VexNode; 
typedef struct{
   VexNode  *vexs[N];  //N个顶点
   int type ;//0 无向图,1 有向图
   int vcount;//顶点数
} GraphList; 
/*第二关 完成图初始化-邻接表,并完成输出图的邻接表函数
*/
GraphList *initGraphList()
{
  /*第一行输入图的类型、图的顶点数和边数,第二行输入各条边的两顶点的编号,按顶点编号从小到大的顺序输入。
输出邻接表。不需考虑输入的数字非法情况,输入顶点的信息*/
 GraphList *G=(GraphList*)malloc(sizeof(GraphList));
 int t,v,s;
 scanf("%d%d%d",&t,&v,&s);
 G->vcount=v;
 G->type=t;
 int i,j,k,l;
 char vex[N];
 char ch=getchar();
 for(i=0;i<v;i++){
 	scanf("%c",&vex[i]);
 }
 for(i=0;i<v;i++){
 	G->vexs[i]=(VexNode *)malloc(sizeof(VexNode));
 	G->vexs[i]->vertex=vex[i];
 	G->vexs[i]->edgelist=(EdgeList)malloc(sizeof(struct EdgeNode));
 	G->vexs[i]->edgelist->nextedge=NULL;
 	G->vexs[i]->degree=0;
 }
 for(i=0;i<s;i++){
	int head,tail;
	scanf("%d %d",&head,&tail);
	if(t==0){
		for(k=0;k<v;k++){
			if(G->vexs[k]->vertex-'0'==head){
				EdgeList node1=(EdgeList)malloc(sizeof(struct EdgeNode));
				for(j=0;j<v;j++){
					if(vex[j]-'0'==tail){
						node1->endvex=j;
						node1->nextedge=G->vexs[k]->edgelist->nextedge;
						G->vexs[k]->edgelist->nextedge=node1;
						break;
					}
				}
				for(j=0;j<v;j++){
					if(G->vexs[j]->vertex-'0'==tail){
						EdgeList node2=(EdgeList)malloc(sizeof(struct EdgeNode));
						for(l=0;l<v;l++){
							if(vex[l]-'0'==head){
								node2->endvex=l;
								node2->nextedge=G->vexs[j]->edgelist->nextedge;
								G->vexs[j]->edgelist->nextedge=node2;
								break;
							}
						}
					}
				}
			}
			
		
		}
	} 
	else if(t==1){
		for(k=0;k<v;k++){
			if(G->vexs[k]->vertex-'0'==head){
				EdgeList node1=(EdgeList)malloc(sizeof(struct EdgeNode));
				for(j=0;j<v;j++){
					if(vex[j]-'0'==tail){
						for(l=0;l<G->vcount;l++){
							if(G->vexs[l]->vertex-'0'==tail){
								G->vexs[l]->degree++;
							}
						}
						node1->endvex=j;
						node1->nextedge=G->vexs[k]->edgelist->nextedge;
						G->vexs[k]->edgelist->nextedge=node1; 
						break;
					}
				}
			}
		}
	
 	}
 }
 return G;
}
void printGraphLit( GraphList *G)
{
 /*输出邻接表,输出格式:顶点->邻接顶点编号->...*/
    int i;
	for(i=0;i<G->vcount;i++){
		printf("%c->",G->vexs[i]->vertex);
		EdgeList tp=G->vexs[i]->edgelist->nextedge;
		while(tp->nextedge!=NULL){
			printf("%d->",tp->endvex);
			tp=tp->nextedge;
		}
		printf("%d\n",tp->endvex);
	}
}

第3关:图的广度遍历

本关任务:完成程序能实现图的广度遍历。

#include <stdio.h>
#include <stdlib.h>
#define N  6
#define MAX 100
typedef struct {
	int vex;
	int shortweight;
}ShortWeight;
typedef struct QueueNode{
	int val;
	struct QueueNode* next;
}QueueNode;
 
typedef struct Queue{
	QueueNode *head;
	QueueNode *tail;
}Queue;
//邻接矩阵数据结构 
typedef  struct{
   int vcount;//顶点数
   int type ;//0 无向图,1 有向图
   char  vexs[N]  ;     // 顶点信息
   int  arcs[N][N]; //关系矩阵
} GraphMatrix;
 
//邻接表数据结构
struct EdgeNode { //边表中的结点
      int  endvex;    //相邻顶点在顶点表中下标
      int  weight;  //边的权
      struct EdgeNode  * nextedge;   //链字段
};   
typedef struct EdgeNode * EdgeList;
 
typedef struct
{
   char  vertex;  //记录顶点信息
   int degree;//用于记录顶点的入度,在拓扑排序时需使用
   EdgeList  edgelist;  //指向边表的指针
} VexNode; 
typedef struct{
   VexNode  *vexs[N];  //N个顶点
   int type ;//0 无向图,1 有向图
   int vcount;//顶点数
} GraphList; 
/*第一关 完成图初始化-邻接矩阵
*/
GraphMatrix *initGraphMatrix( )
{
  /*第一行输入图的类型、图的顶点数和边数,第二行输入各条边的两顶点的编号,按顶点编号从小到大的顺序输入。
输出邻接矩阵,不需要考虑输入的数字非法情况,不输入顶点的信息*/
   GraphMatrix *G;
   G=(GraphMatrix *)malloc(sizeof(GraphMatrix));
   int t,v,s;
   scanf("%d %d %d",&t,&v,&s);
   G->vcount=v;
   G->type=t;
   int i,j;
   for(i=0;i<N;i++){
      for(j=0;j<N;j++){
         G->arcs[i][j]=0;
      }
   }
   int head,tail;
   if(t==0)
      for(i=0;i<N;i++){
         scanf("%d %d",&head,&tail);
         G->arcs[head][tail]=1;
         G->arcs[tail][head]=1;
      }
   if(t==1){
      for(i=0;i<N;i++){
         scanf("%d %d",&head,&tail);
         G->arcs[head][tail]=1;
      }
   }
   return G;
}
/*第二关 完成图初始化-邻接表,并完成输出图的邻接表函数
*/
GraphList *initGraphList()
{
  /*第一行输入图的类型、图的顶点数和边数,第二行输入各条边的两顶点的编号,按顶点编号从小到大的顺序输入。
输出邻接表。不需考虑输入的数字非法情况,输入顶点的信息*/
 GraphList *G=(GraphList*)malloc(sizeof(GraphList));
 int t,v,s;
 scanf("%d%d%d",&t,&v,&s);
 G->vcount=v;
 G->type=t;
 int i,j,k,l;
 char vex[N];
 char ch=getchar();
 for(i=0;i<v;i++){
 	scanf("%c",&vex[i]);
 }
 for(i=0;i<v;i++){
 	G->vexs[i]=(VexNode *)malloc(sizeof(VexNode));
 	G->vexs[i]->vertex=vex[i];
 	G->vexs[i]->edgelist=(EdgeList)malloc(sizeof(struct EdgeNode));
 	G->vexs[i]->edgelist->nextedge=NULL;
 	G->vexs[i]->degree=0;
 }
 for(i=0;i<s;i++){
	int head,tail;
	scanf("%d %d",&head,&tail);
	if(t==0){
		for(k=0;k<v;k++){
			if(G->vexs[k]->vertex-'0'==head){
				EdgeList node1=(EdgeList)malloc(sizeof(struct EdgeNode));
				for(j=0;j<v;j++){
					if(vex[j]-'0'==tail){
						node1->endvex=j;
						node1->nextedge=G->vexs[k]->edgelist->nextedge;
						G->vexs[k]->edgelist->nextedge=node1;
						break;
					}
				}
				for(j=0;j<v;j++){
					if(G->vexs[j]->vertex-'0'==tail){
						EdgeList node2=(EdgeList)malloc(sizeof(struct EdgeNode));
						for(l=0;l<v;l++){
							if(vex[l]-'0'==head){
								node2->endvex=l;
								node2->nextedge=G->vexs[j]->edgelist->nextedge;
								G->vexs[j]->edgelist->nextedge=node2;
								break;
							}
						}
					}
				}
			}
			
		
		}
	} 
	else if(t==1){
		for(k=0;k<v;k++){
			if(G->vexs[k]->vertex-'0'==head){
				EdgeList node1=(EdgeList)malloc(sizeof(struct EdgeNode));
				for(j=0;j<v;j++){
					if(vex[j]-'0'==tail){
						for(l=0;l<G->vcount;l++){
							if(G->vexs[l]->vertex-'0'==tail){
								G->vexs[l]->degree++;
							}
						}
						node1->endvex=j;
						node1->nextedge=G->vexs[k]->edgelist->nextedge;
						G->vexs[k]->edgelist->nextedge=node1; 
						break;
					}
				}
			}
		}
	
 	}
 }
 return G;
}
void printGraphLit( GraphList *G)
{
 /*输出邻接表,输出格式:顶点->邻接顶点编号->...*/
    int i;
	for(i=0;i<G->vcount;i++){
		printf("%c->",G->vexs[i]->vertex);
		EdgeList tp=G->vexs[i]->edgelist->nextedge;
		while(tp->nextedge!=NULL){
			printf("%d->",tp->endvex);
			tp=tp->nextedge;
		}
		printf("%d\n",tp->endvex);
	}
}
/*第三关 完成图的广度遍历(周游),可根据需要添加自定义函数
*/
int visited[N]={0};
void BFS_list(GraphList *G)
{
	int i,j;
	printf("%c ",G->vexs[0]->vertex);
	visited[0]=1;
	EdgeList tp=G->vexs[i]->edgelist->nextedge;
	while(tp->nextedge!=NULL){
		printf("%d ",tp->endvex);
		visited[tp->endvex]=1;
		tp=tp->nextedge;
	}
	printf("%d ",tp->endvex);
	visited[tp->endvex]=1;
	for(i=N-1;i>=0;i--){
		if(visited[i]==1){
			EdgeList tp=G->vexs[i]->edgelist->nextedge;
			while(tp->nextedge!=NULL && visited[tp->endvex]==0){
			printf("%d ",tp->endvex);
			visited[tp->endvex]=1;
			tp=tp->nextedge;
			}
		}
	}
	
}

第4关:图的深度遍历

本关任务:完成程序能实现图的深度遍历。

#include <stdio.h>
#include <stdlib.h>
#define N  6
#define MAX 100
typedef struct {
	int vex;
	int shortweight;
}ShortWeight;
typedef struct QueueNode{
	int val;
	struct QueueNode* next;
}QueueNode;
 
typedef struct Queue{
	QueueNode *head;
	QueueNode *tail;
}Queue;
//邻接矩阵数据结构 
typedef  struct{
   int vcount;//顶点数
   int type ;//0 无向图,1 有向图
   char  vexs[N]  ;     // 顶点信息
   int  arcs[N][N]; //关系矩阵
} GraphMatrix;
 
//邻接表数据结构
struct EdgeNode { //边表中的结点
      int  endvex;    //相邻顶点在顶点表中下标
      int  weight;  //边的权
      struct EdgeNode  * nextedge;   //链字段
};   
typedef struct EdgeNode * EdgeList;
 
typedef struct
{
   char  vertex;  //记录顶点信息
   int degree;//用于记录顶点的入度,在拓扑排序时需使用
   EdgeList  edgelist;  //指向边表的指针
} VexNode; 
typedef struct{
   VexNode  *vexs[N];  //N个顶点
   int type ;//0 无向图,1 有向图
   int vcount;//顶点数
} GraphList; 
/*第一关 完成图初始化-邻接矩阵
*/
GraphMatrix *initGraphMatrix( )
{
  /*第一行输入图的类型、图的顶点数和边数,第二行输入各条边的两顶点的编号,按顶点编号从小到大的顺序输入。
输出邻接矩阵,不需要考虑输入的数字非法情况,不输入顶点的信息*/
   GraphMatrix *G;
   G=(GraphMatrix *)malloc(sizeof(GraphMatrix));
   int t,v,s;
   scanf("%d %d %d",&t,&v,&s);
   G->vcount=v;
   G->type=t;
   int i,j;
   for(i=0;i<N;i++){
      for(j=0;j<N;j++){
         G->arcs[i][j]=0;
      }
   }
   int head,tail;
   if(t==0)
      for(i=0;i<N;i++){
         scanf("%d %d",&head,&tail);
         G->arcs[head][tail]=1;
         G->arcs[tail][head]=1;
      }
   if(t==1){
      for(i=0;i<N;i++){
         scanf("%d %d",&head,&tail);
         G->arcs[head][tail]=1;
      }
   }
   return G;
}
/*第二关 完成图初始化-邻接表,并完成输出图的邻接表函数
*/
GraphList *initGraphList()
{
  /*第一行输入图的类型、图的顶点数和边数,第二行输入各条边的两顶点的编号,按顶点编号从小到大的顺序输入。
输出邻接表。不需考虑输入的数字非法情况,输入顶点的信息*/
 GraphList *G=(GraphList*)malloc(sizeof(GraphList));
 int t,v,s;
 scanf("%d%d%d",&t,&v,&s);
 G->vcount=v;
 G->type=t;
 int i,j,k,l;
 char vex[N];
 char ch=getchar();
 for(i=0;i<v;i++){
 	scanf("%c",&vex[i]);
 }
 for(i=0;i<v;i++){
 	G->vexs[i]=(VexNode *)malloc(sizeof(VexNode));
 	G->vexs[i]->vertex=vex[i];
 	G->vexs[i]->edgelist=(EdgeList)malloc(sizeof(struct EdgeNode));
 	G->vexs[i]->edgelist->nextedge=NULL;
 	G->vexs[i]->degree=0;
 }
 for(i=0;i<s;i++){
	int head,tail;
	scanf("%d %d",&head,&tail);
	if(t==0){
		for(k=0;k<v;k++){
			if(G->vexs[k]->vertex-'0'==head){
				EdgeList node1=(EdgeList)malloc(sizeof(struct EdgeNode));
				for(j=0;j<v;j++){
					if(vex[j]-'0'==tail){
						node1->endvex=j;
						node1->nextedge=G->vexs[k]->edgelist->nextedge;
						G->vexs[k]->edgelist->nextedge=node1;
						break;
					}
				}
				for(j=0;j<v;j++){
					if(G->vexs[j]->vertex-'0'==tail){
						EdgeList node2=(EdgeList)malloc(sizeof(struct EdgeNode));
						for(l=0;l<v;l++){
							if(vex[l]-'0'==head){
								node2->endvex=l;
								node2->nextedge=G->vexs[j]->edgelist->nextedge;
								G->vexs[j]->edgelist->nextedge=node2;
								break;
							}
						}
					}
				}
			}
			
		
		}
	} 
	else if(t==1){
		for(k=0;k<v;k++){
			if(G->vexs[k]->vertex-'0'==head){
				EdgeList node1=(EdgeList)malloc(sizeof(struct EdgeNode));
				for(j=0;j<v;j++){
					if(vex[j]-'0'==tail){
						for(l=0;l<G->vcount;l++){
							if(G->vexs[l]->vertex-'0'==tail){
								G->vexs[l]->degree++;
							}
						}
						node1->endvex=j;
						node1->nextedge=G->vexs[k]->edgelist->nextedge;
						G->vexs[k]->edgelist->nextedge=node1; 
						break;
					}
				}
			}
		}
	
 	}
 }
 return G;
}
void printGraphLit( GraphList *G)
{
 /*输出邻接表,输出格式:顶点->邻接顶点编号->...*/
    int i;
	for(i=0;i<G->vcount;i++){
		printf("%c->",G->vexs[i]->vertex);
		EdgeList tp=G->vexs[i]->edgelist->nextedge;
		while(tp->nextedge!=NULL){
			printf("%d->",tp->endvex);
			tp=tp->nextedge;
		}
		printf("%d\n",tp->endvex);
	}
}
/*第三关 完成图的广度遍历(周游),可根据需要添加自定义函数
*/
int visited[N]={0};
void BFS_list(GraphList *G)
{
	int i,j;
	printf("%c ",G->vexs[0]->vertex);
	visited[0]=1;
	EdgeList tp=G->vexs[i]->edgelist->nextedge;
	while(tp->nextedge!=NULL){
		printf("%d ",tp->endvex);
		visited[tp->endvex]=1;
		tp=tp->nextedge;
	}
	printf("%d ",tp->endvex);
	visited[tp->endvex]=1;
	for(i=N-1;i>=0;i--){
		if(visited[i]==1){
			EdgeList tp=G->vexs[i]->edgelist->nextedge;
			while(tp->nextedge!=NULL && visited[tp->endvex]==0){
			printf("%d ",tp->endvex);
			visited[tp->endvex]=1;
			tp=tp->nextedge;
			}
		}
	}
	
}
/*第四关 完成图的深度遍历(周游),可根据需要添加自定义函数
*/
int visited2[N];
void DFS_list(GraphList *G)
{
	int i,j,k;
	for(i=0;i<N;i++){
		visited2[i]=0;
	}
	printf("%c ",G->vexs[0]->vertex);
	visited2[0]=1;
	EdgeList tp=G->vexs[0]->edgelist->nextedge;
	printf("%d ",tp->endvex);
	visited2[tp->endvex]=1;
	int num=4;
	while(1){
		for(i=0;i<G->vcount;i++){
			if(G->vexs[i]->vertex-'0'==tp->endvex){
				EdgeList tp2=G->vexs[i]->edgelist->nextedge;
				if(visited2[tp2->endvex]==0){
					tp=tp2;
					printf("%d ",tp2->endvex);
					visited2[tp2->endvex]=1;
					break;
				}
				else if(visited2[tp2->endvex]==1){
					for(tp2=tp2->nextedge;tp2!=NULL;tp2=tp2->nextedge){
						if(visited2[tp2->endvex]==0){
							tp=tp2;
							printf("%d ",tp2->endvex);
							visited2[tp2->endvex]=1;
							break;
						}
					}
					
				}
				
			}
		}
		int count=0;
		for(i=0;i<N;i++){
			if(visited2[i]==1) count++;
		}
		if(count==G->vcount) break;
	}
	
}

第5关:拓扑排序

本关任务:编写一个能输出有向无环图的拓扑排序的函数。

#include <stdio.h>
#include <stdlib.h>
#define N  6
#define MAX 100
typedef struct {
	int vex;
	int shortweight;
}ShortWeight;
typedef struct QueueNode{
	int val;
	struct QueueNode* next;
}QueueNode;
 
typedef struct Queue{
	QueueNode *head;
	QueueNode *tail;
}Queue;
//邻接矩阵数据结构 
typedef  struct{
   int vcount;//顶点数
   int type ;//0 无向图,1 有向图
   char  vexs[N]  ;     // 顶点信息
   int  arcs[N][N]; //关系矩阵
} GraphMatrix;
 
//邻接表数据结构
struct EdgeNode { //边表中的结点
      int  endvex;    //相邻顶点在顶点表中下标
      int  weight;  //边的权
      struct EdgeNode  * nextedge;   //链字段
};   
typedef struct EdgeNode * EdgeList;
 
typedef struct
{
   char  vertex;  //记录顶点信息
   int degree;//用于记录顶点的入度,在拓扑排序时需使用
   EdgeList  edgelist;  //指向边表的指针
} VexNode; 
typedef struct{
   VexNode  *vexs[N];  //N个顶点
   int type ;//0 无向图,1 有向图
   int vcount;//顶点数
} GraphList; 
/*第一关 完成图初始化-邻接矩阵
*/
GraphMatrix *initGraphMatrix( )
{
  /*第一行输入图的类型、图的顶点数和边数,第二行输入各条边的两顶点的编号,按顶点编号从小到大的顺序输入。
输出邻接矩阵,不需要考虑输入的数字非法情况,不输入顶点的信息*/
   GraphMatrix *G;
   G=(GraphMatrix *)malloc(sizeof(GraphMatrix));
   int t,v,s;
   scanf("%d %d %d",&t,&v,&s);
   G->vcount=v;
   G->type=t;
   int i,j;
   for(i=0;i<N;i++){
      for(j=0;j<N;j++){
         G->arcs[i][j]=0;
      }
   }
   int head,tail;
   if(t==0)
      for(i=0;i<N;i++){
         scanf("%d %d",&head,&tail);
         G->arcs[head][tail]=1;
         G->arcs[tail][head]=1;
      }
   if(t==1){
      for(i=0;i<N;i++){
         scanf("%d %d",&head,&tail);
         G->arcs[head][tail]=1;
      }
   }
   return G;
}
/*第二关 完成图初始化-邻接表,并完成输出图的邻接表函数
*/
GraphList *initGraphList()
{
  /*第一行输入图的类型、图的顶点数和边数,第二行输入各条边的两顶点的编号,按顶点编号从小到大的顺序输入。
输出邻接表。不需考虑输入的数字非法情况,输入顶点的信息*/
 GraphList *G=(GraphList*)malloc(sizeof(GraphList));
 int t,v,s;
 scanf("%d%d%d",&t,&v,&s);
 G->vcount=v;
 G->type=t;
 int i,j,k,l;
 char vex[N];
 char ch=getchar();
 for(i=0;i<v;i++){
 	scanf("%c",&vex[i]);
 }
 for(i=0;i<v;i++){
 	G->vexs[i]=(VexNode *)malloc(sizeof(VexNode));
 	G->vexs[i]->vertex=vex[i];
 	G->vexs[i]->edgelist=(EdgeList)malloc(sizeof(struct EdgeNode));
 	G->vexs[i]->edgelist->nextedge=NULL;
 	G->vexs[i]->degree=0;
 }
 for(i=0;i<s;i++){
	int head,tail;
	scanf("%d %d",&head,&tail);
	if(t==0){
		for(k=0;k<v;k++){
			if(G->vexs[k]->vertex-'0'==head){
				EdgeList node1=(EdgeList)malloc(sizeof(struct EdgeNode));
				for(j=0;j<v;j++){
					if(vex[j]-'0'==tail){
						node1->endvex=j;
						node1->nextedge=G->vexs[k]->edgelist->nextedge;
						G->vexs[k]->edgelist->nextedge=node1;
						break;
					}
				}
				for(j=0;j<v;j++){
					if(G->vexs[j]->vertex-'0'==tail){
						EdgeList node2=(EdgeList)malloc(sizeof(struct EdgeNode));
						for(l=0;l<v;l++){
							if(vex[l]-'0'==head){
								node2->endvex=l;
								node2->nextedge=G->vexs[j]->edgelist->nextedge;
								G->vexs[j]->edgelist->nextedge=node2;
								break;
							}
						}
					}
				}
			}
			
		
		}
	} 
	else if(t==1){
		for(k=0;k<v;k++){
			if(G->vexs[k]->vertex-'0'==head){
				EdgeList node1=(EdgeList)malloc(sizeof(struct EdgeNode));
				for(j=0;j<v;j++){
					if(vex[j]-'0'==tail){
						for(l=0;l<G->vcount;l++){
							if(G->vexs[l]->vertex-'0'==tail){
								G->vexs[l]->degree++;
							}
						}
						node1->endvex=j;
						node1->nextedge=G->vexs[k]->edgelist->nextedge;
						G->vexs[k]->edgelist->nextedge=node1; 
						break;
					}
				}
			}
		}
	
 	}
 }
 return G;
}
void printGraphLit( GraphList *G)
{
 /*输出邻接表,输出格式:顶点->邻接顶点编号->...*/
    int i;
	for(i=0;i<G->vcount;i++){
		printf("%c->",G->vexs[i]->vertex);
		EdgeList tp=G->vexs[i]->edgelist->nextedge;
		while(tp->nextedge!=NULL){
			printf("%d->",tp->endvex);
			tp=tp->nextedge;
		}
		printf("%d\n",tp->endvex);
	}
}
/*第三关 完成图的广度遍历(周游),可根据需要添加自定义函数
*/
int visited[N]={0};
void BFS_list(GraphList *G)
{
	int i,j;
	printf("%c ",G->vexs[0]->vertex);
	visited[0]=1;
	EdgeList tp=G->vexs[i]->edgelist->nextedge;
	while(tp->nextedge!=NULL){
		printf("%d ",tp->endvex);
		visited[tp->endvex]=1;
		tp=tp->nextedge;
	}
	printf("%d ",tp->endvex);
	visited[tp->endvex]=1;
	for(i=N-1;i>=0;i--){
		if(visited[i]==1){
			EdgeList tp=G->vexs[i]->edgelist->nextedge;
			while(tp->nextedge!=NULL && visited[tp->endvex]==0){
			printf("%d ",tp->endvex);
			visited[tp->endvex]=1;
			tp=tp->nextedge;
			}
		}
	}
	
}
/*第四关 完成图的深度遍历(周游),可根据需要添加自定义函数
*/
int visited2[N];
void DFS_list(GraphList *G)
{
	int i,j,k;
	for(i=0;i<N;i++){
		visited2[i]=0;
	}
	printf("%c ",G->vexs[0]->vertex);
	visited2[0]=1;
	EdgeList tp=G->vexs[0]->edgelist->nextedge;
	printf("%d ",tp->endvex);
	visited2[tp->endvex]=1;
	int num=4;
	while(1){
		for(i=0;i<G->vcount;i++){
			if(G->vexs[i]->vertex-'0'==tp->endvex){
				EdgeList tp2=G->vexs[i]->edgelist->nextedge;
				if(visited2[tp2->endvex]==0){
					tp=tp2;
					printf("%d ",tp2->endvex);
					visited2[tp2->endvex]=1;
					break;
				}
				else if(visited2[tp2->endvex]==1){
					for(tp2=tp2->nextedge;tp2!=NULL;tp2=tp2->nextedge){
						if(visited2[tp2->endvex]==0){
							tp=tp2;
							printf("%d ",tp2->endvex);
							visited2[tp2->endvex]=1;
							break;
						}
					}
					
				}
				
			}
		}
		int count=0;
		for(i=0;i<N;i++){
			if(visited2[i]==1) count++;
		}
		if(count==G->vcount) break;
	}
	
}
/*第五关 生成图的拓扑排序,可根据需要添加自定义函数
*/
void QueueInit(Queue* pq) {
	pq->head = pq->tail = NULL;
}
void QueuePush(Queue* pq, int x) {
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	newnode->val = x;
	newnode->next = NULL;
	if (pq->tail == NULL) {
		pq->head = pq->tail = newnode;
	}
	else {
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}
void QueuePop(Queue* pq) {
	if (pq->head->next == NULL) {
		pq->head = pq->tail = NULL;
	}
	else {
		QueueNode* next = pq->head->next;
		pq->head = next;
	}
}
int QueueFront(Queue* pq) {
	return pq->head->val;
}
int QueueEmpty(Queue* pq) {
	return pq->head == NULL;
}
void Top_list(GraphList* G)
{
	Queue* Q=(Queue *)malloc(sizeof(Queue));
	QueueInit(Q);
	int i;
	int deg[N];
	for (i = 0; i < N; i++) {
		deg[i] = 0;
	}
	for (i = 0; i < N; i++) {
		deg[i] = G->vexs[i]->degree;
	}
 
	for (i = 0; i < N; i++) {
		if (deg[i] == 0) {
			QueuePush(Q, i);
		}
	}
	while (!QueueEmpty(Q)) {
		int j = QueueFront(Q);
		printf("%d ", j);
		QueuePop(Q);
		EdgeList p;
		p = G->vexs[j]->edgelist->nextedge;
		while (p != NULL) {
			deg[p->endvex]--;
			if (deg[p->endvex] == 0) {
				QueuePush(Q, p->endvex);
			}
			p = p->nextedge;
		}
	}
}

第6关:prim算法生成最小生成树

本关任务:实现prim算法生成最小生成树。文章来源地址https://www.toymoban.com/news/detail-760341.html

#include <stdio.h>
#include <stdlib.h>
#define N  6
#define MAX 100
typedef struct {
	int vex;
	int shortweight;
}ShortWeight;
typedef struct QueueNode{
	int val;
	struct QueueNode* next;
}QueueNode;
 
typedef struct Queue{
	QueueNode *head;
	QueueNode *tail;
}Queue;
//邻接矩阵数据结构 
typedef  struct{
   int vcount;//顶点数
   int type ;//0 无向图,1 有向图
   char  vexs[N]  ;     // 顶点信息
   int  arcs[N][N]; //关系矩阵
} GraphMatrix;
 
//邻接表数据结构
struct EdgeNode { //边表中的结点
      int  endvex;    //相邻顶点在顶点表中下标
      int  weight;  //边的权
      struct EdgeNode  * nextedge;   //链字段
};   
typedef struct EdgeNode * EdgeList;
 
typedef struct
{
   char  vertex;  //记录顶点信息
   int degree;//用于记录顶点的入度,在拓扑排序时需使用
   EdgeList  edgelist;  //指向边表的指针
} VexNode; 
typedef struct{
   VexNode  *vexs[N];  //N个顶点
   int type ;//0 无向图,1 有向图
   int vcount;//顶点数
} GraphList; 
/*第一关 完成图初始化-邻接矩阵
*/
GraphMatrix *initGraphMatrix( )
{
  /*第一行输入图的类型、图的顶点数和边数,第二行输入各条边的两顶点的编号,按顶点编号从小到大的顺序输入。
输出邻接矩阵,不需要考虑输入的数字非法情况,不输入顶点的信息*/
   GraphMatrix *G;
   G=(GraphMatrix *)malloc(sizeof(GraphMatrix));
   int t,v,s;
   scanf("%d %d %d",&t,&v,&s);
   G->vcount=v;
   G->type=t;
   int i,j;
   for(i=0;i<N;i++){
      for(j=0;j<N;j++){
         G->arcs[i][j]=0;
      }
   }
   int head,tail;
   if(t==0)
      for(i=0;i<N;i++){
         scanf("%d %d",&head,&tail);
         G->arcs[head][tail]=1;
         G->arcs[tail][head]=1;
      }
   if(t==1){
      for(i=0;i<N;i++){
         scanf("%d %d",&head,&tail);
         G->arcs[head][tail]=1;
      }
   }
   return G;
}
GraphList* initGraphList()
{
	/*第一行输入图的类型、图的顶点数和边数,第二行输入各条边的两顶点的编号,按顶点编号从小到大的顺序输入。
  输出邻接表。不需考虑输入的数字非法情况,输入顶点的信息*/
	GraphList* G = (GraphList*)malloc(sizeof(GraphList));
	int t, v, s;
	scanf("%d%d%d", &t, &v, &s);
	G->vcount = v;
	G->type = t;
	int i, j, k, l;
	char vex[N];
	char ch = getchar();
	for (i = 0; i < v; i++) {
		scanf("%c", &vex[i]);
	}
	for (i = 0; i < v; i++) {
		G->vexs[i] = (VexNode*)malloc(sizeof(VexNode));
		G->vexs[i]->vertex = vex[i];
		G->vexs[i]->edgelist = (EdgeList)malloc(sizeof(struct EdgeNode));
		G->vexs[i]->edgelist->nextedge = NULL;
	}
	for (i = 0; i < s; i++) {
		int head, tail,w;
		scanf("%d %d %d", &head, &tail,&w);
		if (t == 0) {
			for (k = 0; k < v; k++) {
				if (G->vexs[k]->vertex - '0' == head) {
					EdgeList node1 = (EdgeList)malloc(sizeof(struct EdgeNode));
					for (j = 0; j < v; j++) {
						if (vex[j] - '0' == tail) {
							node1->weight = w;
							node1->endvex = j;
							node1->nextedge = G->vexs[k]->edgelist->nextedge;
							G->vexs[k]->edgelist->nextedge = node1;
							break;
						}
					}
					for (j = 0; j < v; j++) {
						if (G->vexs[j]->vertex - '0' == tail) {
							EdgeList node2 = (EdgeList)malloc(sizeof(struct EdgeNode));
							for (l = 0; l < v; l++) {
								if (vex[l] - '0' == head) {
									node2->weight = w;
									node2->endvex = l;
									node2->nextedge = G->vexs[j]->edgelist->nextedge;
									G->vexs[j]->edgelist->nextedge = node2;
									break;
								}
							}
						}
					}
				}
 
 
			}
		}
	}
	return G;
}
/*第三关 完成图的广度遍历(周游),可根据需要添加自定义函数
*/
int visited[N]={0};
void BFS_list(GraphList *G)
{
	int i,j;
	printf("%c ",G->vexs[0]->vertex);
	visited[0]=1;
	EdgeList tp=G->vexs[i]->edgelist->nextedge;
	while(tp->nextedge!=NULL){
		printf("%d ",tp->endvex);
		visited[tp->endvex]=1;
		tp=tp->nextedge;
	}
	printf("%d ",tp->endvex);
	visited[tp->endvex]=1;
	for(i=N-1;i>=0;i--){
		if(visited[i]==1){
			EdgeList tp=G->vexs[i]->edgelist->nextedge;
			while(tp->nextedge!=NULL && visited[tp->endvex]==0){
			printf("%d ",tp->endvex);
			visited[tp->endvex]=1;
			tp=tp->nextedge;
			}
		}
	}
	
}
/*第四关 完成图的深度遍历(周游),可根据需要添加自定义函数
*/
int visited2[N];
void DFS_list(GraphList *G)
{
	int i,j,k;
	for(i=0;i<N;i++){
		visited2[i]=0;
	}
	printf("%c ",G->vexs[0]->vertex);
	visited2[0]=1;
	EdgeList tp=G->vexs[0]->edgelist->nextedge;
	printf("%d ",tp->endvex);
	visited2[tp->endvex]=1;
	int num=4;
	while(1){
		for(i=0;i<G->vcount;i++){
			if(G->vexs[i]->vertex-'0'==tp->endvex){
				EdgeList tp2=G->vexs[i]->edgelist->nextedge;
				if(visited2[tp2->endvex]==0){
					tp=tp2;
					printf("%d ",tp2->endvex);
					visited2[tp2->endvex]=1;
					break;
				}
				else if(visited2[tp2->endvex]==1){
					for(tp2=tp2->nextedge;tp2!=NULL;tp2=tp2->nextedge){
						if(visited2[tp2->endvex]==0){
							tp=tp2;
							printf("%d ",tp2->endvex);
							visited2[tp2->endvex]=1;
							break;
						}
					}
					
				}
				
			}
		}
		int count=0;
		for(i=0;i<N;i++){
			if(visited2[i]==1) count++;
		}
		if(count==G->vcount) break;
	}
	
}
/*第五关 生成图的拓扑排序,可根据需要添加自定义函数
*/
void QueueInit(Queue* pq) {
	pq->head = pq->tail = NULL;
}
void QueuePush(Queue* pq, int x) {
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	newnode->val = x;
	newnode->next = NULL;
	if (pq->tail == NULL) {
		pq->head = pq->tail = newnode;
	}
	else {
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}
void QueuePop(Queue* pq) {
	if (pq->head->next == NULL) {
		pq->head = pq->tail = NULL;
	}
	else {
		QueueNode* next = pq->head->next;
		pq->head = next;
	}
}
int QueueFront(Queue* pq) {
	return pq->head->val;
}
int QueueEmpty(Queue* pq) {
	return pq->head == NULL;
}
void Top_list(GraphList* G)
{
	Queue* Q=(Queue *)malloc(sizeof(Queue));
	QueueInit(Q);
	int i;
	int deg[N];
	for (i = 0; i < N; i++) {
		deg[i] = 0;
	}
	for (i = 0; i < N; i++) {
		deg[i] = G->vexs[i]->degree;
	}
 
	for (i = 0; i < N; i++) {
		if (deg[i] == 0) {
			QueuePush(Q, i);
		}
	}
	while (!QueueEmpty(Q)) {
		int j = QueueFront(Q);
		printf("%d ", j);
		QueuePop(Q);
		EdgeList p;
		p = G->vexs[j]->edgelist->nextedge;
		while (p != NULL) {
			deg[p->endvex]--;
			if (deg[p->endvex] == 0) {
				QueuePush(Q, p->endvex);
			}
			p = p->nextedge;
		}
	}
}
/*第六关 prim算法生成最小生成树
*/
int GetShortWeight(GraphList* G,ShortWeight *shortw) {
	int i;
	int min = MAX;
	int loc;
	for (i = 1; i < G->vcount; i++) {
		if (min > shortw[i].shortweight && shortw[i].shortweight != 0) {
			min = shortw[i].shortweight;
			loc = i;
		}
	}
	return loc;
}
 
void Prim_list(GraphList* G)
{
	int i, j, k;
	ShortWeight shortw[10];
	for (i = 0; i < 10; i++) {
		shortw[i].shortweight = MAX;
	}
	k = 0;
	EdgeList tp = G->vexs[k]->edgelist->nextedge;
	while (tp) {
		shortw[tp->endvex].shortweight= tp->weight;
		shortw[tp->endvex].vex = k;
		tp = tp->nextedge;
	}
	shortw[k].shortweight = 0;
	for (i = 0; i < G->vcount - 1; i++) {
		k = GetShortWeight(G, shortw);
		printf("%d %d\n", shortw[k].vex, k);
		shortw[k].shortweight = 0;
		EdgeList tp2 = G->vexs[k]->edgelist->nextedge;
			while (tp2) {
				if (tp2->weight < shortw[tp2->endvex].shortweight) {
					shortw[tp2->endvex].shortweight = tp2->weight;
					shortw[tp2->endvex].vex = k;
				}
				tp2 = tp2->nextedge;
			}
	}
}

到了这里,关于头歌数据结构——图——课上课后练的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【头歌】数据结构-队列的应用

      第1关:循环队列 任务描述 本关任务:编写一个循环队列,实现入队、出队操作,判断队空、队满等特殊情况。 相关知识 为了完成本关任务,你需要掌握:1.循环队列定义,2.入队、出队的定义,3.队空、队满的情况。 循环队列定义 循环队列将数组存储区看成是一个首尾相

    2024年02月08日
    浏览(42)
  • 数据结构头歌实验梳理

    PS:该代码块表明了链接存储线性表所有常见相关用法及性质。对于初学者需要分成一小块一小块食用 特别说明: “当前位置”:当前位置由curr指针给出,当前位置的前一个位置由pre指针给出,当前位置的编号由position给出。后面将定义的若干操作与当前位置有关,例如:在

    2023年04月12日
    浏览(38)
  • 【数据结构实训】哈希表设计

    [问题描述] 针对某个集体中人名设计一个哈希表,使得平均查找长度不超过2,并完成相应的建表和查表程序。 [基本要求] 假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个,取平均查找长度的上限为2。哈希函数用除留余数法构造,用线性探测再散列法或

    2024年02月11日
    浏览(38)
  • 头歌实践平台(python数据结构)(1-6)

    第1关:栈抽象数据类型及其实现 任务描述 相关知识 栈抽象数据类型 List 的操作方法 编程要求 测试说明 任务描述 本关任务:编写代码实现栈的基本操作。 相关知识 为了完成本关任务,你需要掌握: 栈抽象数据类型; Python 中 List 的操作方法。 栈抽象数据类型 抽象数据类

    2024年02月07日
    浏览(35)
  • 数据结构与算法-头歌【1】顺序线性表--课上练

      本意是整理和复习,理解不深或者有错误的评论区提出即可。 只有第一关的代码里面有结构体的定义,其余我只放了功能函数。 任务描述 本关要求按照完成顺序表数据类型定义,并初始化一个顺序线性表。 编程要求 顺序线性表数据结构定义如下: 本关的编程任务是补全

    2023年04月25日
    浏览(41)
  • Java数据结构之排序(头歌平台,详细注释)

    目录 第1关:选择排序 任务描述 相关知识 代码:    第2关:插入排序 任务描述 相关知识 插入排序 代码:   第3关:归并排序 任务描述 相关知识 归并排序 原理 代码:    第4关:快速排序 任务描述 相关知识 快速排序 代码:    第5关:堆排序 任务描述 相关知识 堆

    2024年01月19日
    浏览(39)
  • 头歌(C语言)-数据结构与算法-数组(共7关)

    任务描述 本关任务:将十个数进行从大到小的顺序进行排列。 相关知识(略) 编程要求 根据提示,在右侧编辑器 Begin-End 处补充代码。 输入 输入十个整数。 输出 以从大到小的顺序输出这个十个数。 测试说明 样例输入: 1 2 3 4 5 6 7 8 9 10 样例输出: 10 9 8 7 6 5 4 3 2 1 代码:

    2024年02月11日
    浏览(42)
  • Java 数据结构之栈、队列(头歌平台,详细注释)

    目录 第1关:实现基于数组的 任务描述 相关知识 栈 栈的数组表示 Java 泛型简介 泛型方法 泛型类应用场景示例 代码:  第2关:实现基于链表的栈 任务描述 相关知识 栈的链式存储 入栈 出栈 代码:  第3关:基于数组的队列 任务描述 相关知识 队列 队列的数组实现 循环队列

    2024年04月25日
    浏览(41)
  • 构造哈夫曼树(数据结构实训)(难度系数85)

    构造哈夫曼树 题目描述: 根据给定的叶结点字符及其对应的权值创建哈夫曼树。 输入: 第一行为叶子结点的数目n(1=n=100)。第二行为一个字符串,包含n个字符,每个字符对应一个叶子结点,第三行为每个叶子结点的概率(即权值),要求根据各叶结点构造哈夫曼树。构造哈

    2024年02月03日
    浏览(31)
  • 【头歌】 Python数据结构 Python案例 实验一python初探(1)

    任务描述 本关任务:编写一个程序,依次输入用户的学号,姓名和手机号码 再依次输出相关信息 为了完成本关任务,你需要掌握: 1.如何输入数据 2.如何输出 输入语句 变量 = input( 提示性文字 ) 语句功能:系统显示提示性文字,等待用户输入。 将用户输入的信息存储在指定

    2024年04月11日
    浏览(83)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包