《数据结构》实验报告
               
程序名： 图的生成和连通性判断                                              
一、上机实验的问题和要求：
1、设计一个程序生成图并判断该图是否连通，如不连通，输出其联通分量个数。
2、连通OR不连通
描述：给定一个无向图，一共n个点，m条边。请编写一个程序实现两种操作：
D x y从原图中删除连接x，y节点的边。
Q x y询问x，y节点是否连通
输入：
第一行两个数n,m（5<=n<=40000,1<=m<=100000）
接下来m行，每行一对整数x y（x,y<=n）,表示x,y之间有边相连。保证没有重复的边。
接下来一行一个整数q（q<=1000003
以下q行每行一种操作，保证不会有非法删除。 输出 
按询问次序输出所有Q操作的回答，连通的回答C，不连通的回答D
样例输入：
3 3
1 2
1 3
2 3
5
Q 1 2
D 1 2
Q 1 2
D 3 2
Q 1 2

样例输出
CCD


二、程序设计的基本思想，原理和算法描述：
（包括程序的结构，数据结构，输入/输出设计，符号名说明等）







三、源程序及注释（将所有代码直接复制于此）：
#ifndef MGraph_H//避免包含MGraph.h头文件
#define MGraph_H
const int MaxSize = 10;//图中最多顶点个数//以下是类MGraph的声明
extern int visited[MaxSize];
template<class T>
class MGraph
{
public:
	MGraph(T a[], int n, int e);//构造函数，建立n个顶点e条边的图
	  ~MGraph() {};//析构函数为空
	  void DFSTraverse(int v);//深度优先遍历图
	  void BFSTraverse(int v);//广度优先遍历图
	  void judge();
	  void cancel();
	  void degree();
private:
	T vertex[MaxSize];
	int arc[MaxSize][MaxSize];
	int vertexNum;
	int	arcNum;
};

#endif
#include <iostream>
using namespace std;
#include"MGraph.h"
template<class T>
MGraph<T>::MGraph(T a[], int n, int e)//构造函数，建立n个顶点e条边的图
{
	int i, j, k;
	vertexNum = n;
	arcNum = e;
	for (i = 0; i < vertexNum; i++)
		vertex[i] = a[i];
	for (i = 0; i < vertexNum; i++)
		for (j = 0; j < vertexNum; j++)
			arc[i][j] = 0;
	for (k = 0; k < arcNum; k++)
	{
		cout << "请输入边的两个顶点的序号";
		cin >> i >> j;
		arc[i][j] = 1;
		arc[j][i] = 1;

	}
}
template<class T>
void MGraph<T>::DFSTraverse(int v)//深度优先遍历图

{
	cout << vertex[v]; visited[v] = 1;
	for (int j = 0; j < vertexNum; j++)
		if (arc[v][j] == 1 && visited[j] == 0)
			DFSTraverse(j);

}
template<class T>
void  MGraph<T>::BFSTraverse(int v)//广度优先遍历图
{
	int Q[MaxSize];
	int front = -1, rear = -1;
	cout << vertex[v]; visited[v] = 1; Q[++rear] = v;
	while (front != rear)
	{
		v = Q[++front];
		for(int j=0;j<vertexNum;j++)
			if (arc[v][j] == 1 && visited[j] == 0)
			{
				cout << vertex[j]; visited[j] = 1; Q[++rear] = j;
			}
	}
}
template<class T>
void MGraph<T>::judge()
{
	int i, j;
	cout << "请输入查找的两个顶点的序号：";
	cin >> i >> j;
	if (arc[i][j])
		cout << "两个顶点邻接" << endl;
	else cout << "两个顶点不邻接" << endl;
}
template <class T>
void MGraph<T>::cancel()
{
	int i, j;
	cout << "请输入你要删除的邻接顶点的序号";
	cin >> i >> j;
	arc[i][j] = arc[j][i] =0;
}
template <class T>
void MGraph<T>::degree() {
	int v;
	int count = 0;
		cout << "请输入要查询的顶点的序号：" << endl;
	cin >> v;
	for (int j = 0; j < vertexNum; j++)
	{
		if (arc[v][j])
			count++;

	}
	cout << "第" << v << "个顶点的度数是：" << endl;
}
#include<iostream>
using namespace std;
#include"MGraph.cpp"
int visited[MaxSize] = { 0 };
int main()
{
	//char ch[] = { 'A','B','C','D','E' };
	//MGraph<char>MG(ch, 5, 6);
	char ch[MaxSize];
	int x, y, n;
	cout << "请输入顶点个数" << endl;
	cin >> x;
	cout << "请输入" << x << "个字符" << endl;
	for(int i=0;i<x;i++)
	cin >> ch[i];
	cout << "请输入邻接边条数" << endl;
	cin >> y;
	MGraph<char> MG(ch, x, y);
	cout << "请输入以下你想完成操作的序号" << endl;
	cout << "1.深度优先遍历输出" << endl << "2.广度优先遍历输出" << endl
		<< "3.查询连接" << endl << "4.删除连接" << endl << "查询度数" << endl;
	cin >> n;
	char sign = 'y';
	while (sign == 'y' || sign== 'Y')
	{
		switch (n)
		{
		case 1:
			for (int i = 0; i < MaxSize; i++)
				visited[i] = 0;
			cout << "深度优先遍历的序列是：";
			MG.DFSTraverse(0);
			cout << endl;
			break;
		case 2:
			for (int i = 0; i < MaxSize; i++)
				visited[i] = 0;
			cout << "广度优先遍历的序列是：";
			MG.BFSTraverse(0);
			cout << endl;
			break;
		case 3:
			MG.judge(); break;
		case 4:
			MG.cancel(); break;
		case 5:
			MG.degree(); break;
		default:break;
		}
		cout << "是否还要做其他操作？（Y/N）" << endl;
		cin >> sign;
	}return 0;
	
}
#ifndef ALGraph_H
#define ALGraph_H
using namespace std;
const int MaxSize = 10;
extern int visited[MaxSize];
struct ArcNode
{
	int adjvex;
	ArcNode* next;
};
template <class T>
struct VertexNode
{
	T vertex;
	ArcNode* firstEdge;
};
template<class T>
class ALGraph {
public:
	ALGraph(T a[], int n, int e);
	~ALGraph();
	void DFSTraverse(int v);
	void BFSTraverse(int v);
	void judge();
	void cancel();
	void degree();
private:
	VertexNode<T>adjlist[MaxSize];
	int vertexNum, arcNum;

};

#endif
#include<iostream>
using namespace std;
#include"ALGraph.h"
template<class T>
ALGraph<T>::ALGraph(T a[], int n, int e)
{
	ArcNode* s;
	int i, j, k;
	vertexNum = n; arcNum = e;
	for (i = 0; i < vertexNum; i++)
	{
		adjlist[i].vertex = a[i];
		adjlist[i].firstEdge = NULL;

	}
	for (k = 0; k < arcNum; k++)
	{
		cout << "请输入边的两个顶点符号：";
		cin >> i >> j;
		s = new ArcNode; s->adjvex = j;
		s->next = adjlist[i].firstEdge = s;
	}
}
template<class T>
ALGraph<T>::~ALGraph()
{
	ArcNode* p = NULL;
	for (int i = 0; i < vertexNum; i++)
	{
		p = adjlist[i].firstEdge;
		while (p != NULL)
		{
			adjlist[i].firstEdge = p->next;
			delete p;
			p = adjlist[i].firstEdge;
		}
	}
}
template<class T>
void  ALGraph<T>:: DFSTraverse(int v)
{
	ArcNode* p = NULL; int j;
	cout << adjlist[v].vertex;
	visited[v] = 1;
	p = adjlist[v].firstEdge;
	while (p != NULL)
	{
		j = p->adjvex;
		if (visited[j] == 0)DFSTraverse(j);
		p = p->next;
	}
}
template<class T>
void  ALGraph<T>:: BFSTraverse(int v)
{
	int Q[MaxSize];
	int front = -1, rear = -1;
	ArcNode* p = NULL;
	cout << adjlist[v].vertex; visited[v] = 1; Q[++rear] = v;
	while (p != NULL)
	{

		int j = p->adjvex;
		if (visited[j] == 0)
		{
			cout << adjlist[j].vertex;
			visited[j] = 1; Q[++rear] = j;
		}
		p = p->next;
	}
}
template<class T>
void  ALGraph<T>::judge()
{
	int i,j;
cin>>i>>j;
	int sign= 0;
	ArcNode * p = NULL;
	p= adjlist[i].firstEdge;
   while(p!= NULL)
	{
	   if (p->adjvex == j)sign = 1;
		p= p->next;
	}
	if(sign==1)cout << "邻接" << endl;
	else cout<< "不邻接" << endl;
}
template<class T>
void  ALGraph<T>::cancel()
{
	int i, j;
cout << "两个顶点序号：";
cin>> i>> j;
	ArcNode * p= NULL; 
	p= adjlist[i].firstEdge;
	while(p!= NULL)
	{
		if(p->next->adjvex== j) { p->next= p->next->next;delete p->next; }
		p= p->next;
	}
}
template<class T>
void  ALGraph<T>::degree()
{
	int x;
	cout<<"输入你要查询度的顶点的序号";
	cin>>x;
	ArcNode* p = NULL;
	p= adjlist[x].firstEdge;
int count  = 0;
	while(p!= NULL)
	{
		count++;
		p= p->next;
	}
	cout<< count<< endl;
}

#include"ALGraph.cpp"
#include<iostream>
using namespace std;
int visited[MaxSize];
int main()
{
	//char ch[] = { 'A','B','C','D','E' };
	int i;
	//ALGraph<char>ALG(ch, 5, 6);
	char ch[MaxSize];
	int x, y, n;
	cout << "请输入顶点个数"<<endl;
		cin >> x;
		cout<< "输入" << x<< "个字符" << endl;
		for(i= 0;i< x;i++)
			cin>> ch[i];
		cout<< "输入邻接边条数" << endl;
		cin>> y;
		ALGraph<char>MG(ch, x, y);
		cout<< "输入数字选择你想完成的操作" << endl;
		cout<< "1.深度优先级输出" << endl;
		cout<< "2.广度优先级输出" << endl;
		cout <<"3.查询连接" << endl;
		cout<< "4.删除连接" << endl;
		cout<< "5.查询度数" << endl;
		cin>> n;
		char sign= 'y';
		while(sign== 'y' || sign== 'Y')
		{
			switch(n)
			{
			case1:
				for(int j= 0;j< MaxSize;j++)visited[j]= 0;
				cout<< "深度优先级遍历输出:" << endl;
				MG.DFSTraverse(0);cout<< endl;
				break;
			case2:
				for(int j= 0; j< MaxSize;j++)visited[j] = 0;
				cout<< "广度优先级遍历输出:" << endl;
				MG.BFSTraverse(0);cout<< endl;
			case3:
				MG.judge();cout<< endl;break;
			case4:
				MG.cancel();cout<< endl;break;
			case5:
				MG.degree();cout<< endl;break;
			}
			cout<< "你是否还想做其他的操作(Y OR N)" << endl;
			cin>> sign;
		}
		return 0;
}



#pragma once
#include<iostream>
#include<stdlib.h>
using namespace std;

const int MaxSize = 10;
typedef struct ArcNode
{
	int adjvex;        //该弧所指向的顶点的位置
	struct ArcNode* nextarc;//指向下一条弧的指针
	//InfoType *info;
}ArcNode;
typedef struct VertexNode
{
	char data;         //顶点信息
	ArcNode* firstarc;  //指向第一条依附该顶点的弧的指针
}VNode, AdjList[MaxSize];


template<class T>
class ALGraph {
public:
	ALGraph();
	ALGraph(T a[], int n, int e);
	~ALGraph();
	void DFSTraverse(int v);
	void BFSTraverse(int v);
	void judge();
	void cancel();
	void degree();
int vertexNum, arcNum;
AdjList vertices;
private:
	VertexNode<T>adjlist[MaxSize];

};
#include"连.h"
using namespace std;
int visited[MaxSize];
template<class T>
ALGraph<T>::ALGraph(T a[], int n, int e)
{
	ArcNode* s;
	int i, j, k;
	vertexNum = n; arcNum = e;
	for (i = 0; i < vertexNum; i++)
	{
		adjlist[i].vertex = a[i];
		adjlist[i].firstEdge = NULL;

	}
	for (k = 0; k < arcNum; k++)
	{
		cout << "请输入边的两个顶点符号：";
		cin >> i >> j;
		s = new ArcNode; s->adjvex = j;
		s->next = adjlist[i].firstEdge = s;
	}
}
template<class T>
ALGraph<T>::~ALGraph()
{
	ArcNode* p = NULL;
	for (int i = 0; i < vertexNum; i++)
	{
		p = adjlist[i].firstEdge;
		while (p != NULL)
		{
			adjlist[i].firstEdge = p->next;
			delete p;
			p = adjlist[i].firstEdge;
		}
	}
}
template<class T>
void  ALGraph<T>::DFSTraverse(int v)
{
	ArcNode* p = NULL; int j;
	cout << adjlist[v].vertex;
	visited[v] = 1;
	p = adjlist[v].firstEdge;
	while (p != NULL)
	{
		j = p->adjvex;
		if (visited[j] == 0)DFSTraverse(j);
		p = p->next;
	}
}
template<class T>
void  ALGraph<T>::BFSTraverse(int v)
{
	int Q[MaxSize];
	int front = -1, rear = -1;
	ArcNode* p = NULL;
	cout << adjlist[v].vertex; visited[v] = 1; Q[++rear] = v;
	while (p != NULL)
	{

		int j = p->adjvex;
		if (visited[j] == 0)
		{
			cout << adjlist[j].vertex;
			visited[j] = 1; Q[++rear] = j;
		}
		p = p->next;
	}
}
template<class T>
void  ALGraph<T>::judge()
{
	int i, j;
	cin >> i >> j;
	int sign = 0;
	ArcNode* p = NULL;
	p = adjlist[i].firstEdge;
	while (p != NULL)
	{
		if (p->adjvex == j)sign = 1;
		p = p->next;
	}
	if (sign == 1)cout << "邻接" << endl;
	else cout << "不邻接" << endl;
}
template<class T>
void  ALGraph<T>::cancel()
{
	int i, j;
	cout << "两个顶点序号：";
	cin >> i >> j;
	ArcNode* p = NULL;
	p = adjlist[i].firstEdge;
	while (p != NULL)
	{
		if (p->next->adjvex == j) { p->next = p->next->next; delete p->next; }
		p = p->next;
	}
}
template<class T>
void  ALGraph<T>::degree()
{
	int x;
	cout << "输入你要查询度的顶点的序号";
	cin >> x;
	ArcNode* p = NULL;
	p = adjlist[x].firstEdge;
	int count = 0;
	while (p != NULL)
	{
		count++;
		p = p->next;
	}
	cout << count << endl;
}



int num = 0;
bool found = false;
int LocateVertices(ALGraph<char> MG, char a)
//查找字符a在图中的位置
{
	for (int i = 0; i < MG.vertexNum; i++)
		if (MG.vertices[i].data == a)
			return i;
	return -1;
}
int LocateArc(ALGraph<char> MG, char a, char b)
//判断弧ab是否已经存在于图中，若已经存在则返回1，否则返回0
{
	ArcNode* p;
	if (LocateVertices(MG, a) >= 0)
	{
		p = MG.vertices[LocateVertices(MG, a)].firstarc;
		while (p && p->adjvex != LocateVertices(MG, b))
			p = p->nextarc;
		if (p)
			return 1;
		return 0;
	}
	return 0;
}
void  CreateGraph(ALGraph<char>& MG)
//利用邻接表存储结构构造有向图
{
	int a, b;
	char s1, s2;
	ArcNode* p;
	for (int i = 0; i < MG.vertexNum; i++)
	{
		MG.vertices[i].data = '#';
		MG.vertices[i].firstarc = NULL;
	}
	for (int i = 1; i <= MG.arcNum; i++)
	{
		cin >> s1;
		a = LocateVertices(MG, s1);
		if (a < 0)
		{
			num++;
			MG.vertices[num - 1].data = s1;
			a = LocateVertices(MG, s1);
		}
		cin >> s2;
		b = LocateVertices(MG, s2);
		if (b < 0)
		{
			num++;
			MG.vertices[num - 1].data = s2;
			b = LocateVertices(MG, s2);
		}
		if (!LocateArc(MG, s1, s2))
		{
			p = new ArcNode;
			if (!p)
				return;
			p->adjvex = b;
			p->nextarc = MG.vertices[a].firstarc;
			MG.vertices[a].firstarc = p;
			p = new ArcNode;
			if (!p)
				return;
			p->adjvex = a;
			p->nextarc = MG.vertices[b].firstarc;
			MG.vertices[b].firstarc = p;
		}
	}
}
int FirstAdjVex(ALGraph<char> MG, int v)
//查找图中位置v的第一个邻接点在图中所在的位置
{
	if (MG.vertices[v].firstarc)
		return MG.vertices[v].firstarc->adjvex;
	return -1;
}
int NextAdjVex(ALGraph<char> MG, int v, int w)
//查找相对于图中位置v的邻接点w的下一邻接点在图中的位置
{
	ArcNode* p;
	p = MG.vertices[v].firstarc;
	while (p->adjvex != w)
		p = p->nextarc;
	if (p->nextarc)
		return p->nextarc->adjvex;
	return -1;
}
void DestroyGraph(ALGraph<char>& MG)
//销毁图
{
	ArcNode* p, * p1;
	for (int i = 0; i < MG.vertexNum; i++)
	{
		p = MG.vertices[i].firstarc;
		if (p)
			p1 = p->nextarc;
		while (p)
		{
			delete p;
			p = p1;
			if (p1)
				p1 = p1->nextarc;
		}
	}
}
void DFSearch(ALGraph<char> G, int i, int s)
//查找i与s之间是否有路径，以此来判断二者是否连通，若连通found=true，否则found=false
{
	int w;
	//	for(int x=0;x<G.vexnum;x++)
	//		visited[x]=false;
	visited[i] = true;
	for (w = FirstAdjVex(G, i); w >= 0 && !found; w = NextAdjVex(G, i, w))
	{
		if (w == s)
		{
			found = true;
			visited[s] = true;
		}
		else if (!visited[w])
			DFSearch(G, w, s);
	}
}
void DeleteArc(ALGraph<char>& MG, char a, char b)
//删除有向边ab
{
	ArcNode* p, * p1;
	if (LocateVertices(MG, a) >= 0)
	{
		p1 = MG.vertices[LocateVertices(MG, a)].firstarc;
		while (p1 && p1->adjvex != LocateVertices(MG, b))
		{
			p = p1;
			p1 = p1->nextarc;
		}
		if (!p1)
			return;
		if (p1 == MG.vertices[LocateVertices(MG, a)].firstarc)
		{
			MG.vertices[LocateVertices(MG, a)].firstarc = p1->nextarc;
			free(p1);
		}
		else
		{
			p->nextarc = p1->nextarc;
			free(p1);
		}
	}
	return;
}

#include"连.cpp"
#include <iostream>
using namespace std;
void main()
{
	ALGraph<int> G;
	char ch[MaxSize];
	int x, y, n;
	cout << "请输入顶点个数" << endl;
	cin >> x;
	cout << "输入" << x << "个字符" << endl;
	for (int i = 0; i < x; i++)
		cin >> ch[i];
	cout << "输入邻接边条数" << endl;
	cin >> y;
	ALGraph<char>MG(ch, x, y);        //定义图变量
	bool visited[MaxSize];        //访问标志数组
	int num = 0;
	bool found = false;
    char a, b, k;
	int n;
	cin >>MG.vertexNum >>MG.arcNum;
	CreateGraph(MG);
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		found = false;
		cin >> k;
		switch (k)
		{
		case 'Q':
			cin >> a >> b;
			int x;
			for (x = 0; x < MG.vertexNum; x++)
				visited[x] = false;
			MG.DFSTraverse(0);
			if (found)
			{
				cout << "C" << endl;
			}
			else
			{
				cout << "D" << endl;
			}
			break;
		case 'D':
			cin >> a >> b;
			DeleteArc(MG, a, b);
			DeleteArc(MG, b, a);
			break;
		default:
			cout << "输入有误" << endl;
			break;
		}
	}
	DestroyGraph(MG);
}






四、运行输出结果：
（可以将运行结果抓图贴至此处）







五、调试和运行程序过程中产生的问题及采取的措施：







六、对算法的程序的讨论、分析，改进设想，其它经验教训：





七、对数据结构教学的意见和建议：