数据结构与算法王卓-习题-第六章图-创建无向图以及邻接表

目录

算法描述

算法预期效果

重难点

思路

个人解法

总结

测试样例与输出

---

算法描述

创建无向图以及其邻接表，并打印关系

算法预期效果

依次输入顶点数，边数，顶点V1~Vn，每条边依附的两个顶点，根据输入的顶点与边的关系，以链表结构构建无向网，与其邻接表。

打印出邻接表

PS：之后会写基于此篇内容的BFS与DFS算法，可以看后序文章。

重难点

没什么重难点，别犯小错误吧。

思路

盗一张自己的图（王老师课件的）

个人解法

#include 
using namespace std;
#define MVNum 100

typedef struct {
	char *base;
	int front, rear, size;
}Queue;

typedef struct ArcNode{
	int adjvex;
	struct ArcNode *nextarc;
}ArcNode;

typedef struct {
	char data;
	ArcNode *firstarc;
}VNode; 

typedef struct {
	VNode vexs[MVNum];
	int vexnum,arcnum;
}ALGraph; //adjacency matrix graph

int Searchvex(ALGraph A, char n) {
	for (int i = 0; i < A.vexnum; i++) 
		if (n == A.vexs[i].data)
			return i;
	return -1;
}

void CreateUDG(ALGraph &A) {
	char a, b; 
	cout << "creating undigraph(1/4): how many vexs do you have in this ALG?\n";
	cin >> A.vexnum;
	cout << "creating undigraph(2/4): how many arcs do you have in this ALG?\n";
	cin >> A.arcnum;
	for (int i = 0; i < A.vexnum; i++) {
		cout << "creating undigraph(3/4): Please Enter the vertex NO. " << i + 1 << endl;
		cin >> A.vexs[i].data;
		A.vexs[i].firstarc = NULL;
	}	
	for (int i = 0; i < A.arcnum; i++) {
		cout << "creating undigraph(4/4): Please Enter the arcs No. " << i + 1 <> a >> b;
		int from = Searchvex(A, a);
		int to = Searchvex(A, b);
		ArcNode *p = new ArcNode;
		p->adjvex = to;
		p->nextarc = A.vexs[from].firstarc;
		A.vexs[from].firstarc = p;
		ArcNode *q = new ArcNode;
		q->adjvex = from;
		q->nextarc = A.vexs[to].firstarc;
		A.vexs[to].firstarc = q;
	}
	cout << "undigraph created!"<< endl;
}

void ALshow(ALGraph A) {
	cout << "showing Graph connection..."<< endl; 
	for (int j = 0; j < A.vexnum; j++) {
		if (A.vexs[j].firstarc){
			ArcNode *p = A.vexs[j].firstarc;
			while (p) {
				cout << A.vexs[j].data << "→" << A.vexs[p->adjvex].data << " ";
				p = p->nextarc;
			}
			cout << endl;
		}
	}
	cout << "complete" << endl;
}


int main(){
	ALGraph a;
	CreateUDG(a);
	AMshow(a);
	return 0;
}

总结

遇到问题：ArcNode报错

解决方法：前面不加ArcNode会报错，后面不加ArcNode会警告，不懂为啥

typedef struct ArcNode{
	int adjvex;
	struct ArcNode *nextarc;
}ArcNode;

测试样例与输出

样例

输出（提示信息部分AM应为AL）

补充：input部分 （提示信息部分AMG应为ALG）