邻接表的相关操作(类C语言)-创新互联

目录

站在用户的角度思考问题,与客户深入沟通,找到江源网站设计与江源网站推广的解决方案,凭借多年的经验,让设计与互联网技术结合,创造个性化、用户体验好的作品,建站类型包括:成都做网站、成都网站设计、企业官网、英文网站、手机端网站、网站推广、域名与空间、雅安服务器托管、企业邮箱。业务覆盖江源地区。

1.内容

2.分析

3.代码

1)头文件(Head.H)

2)功能函数(function.cpp)

3)主函数(main.cpp)

4.运行结果(DEV)

5.总结


1.内容

针对于有向图和无向图的邻接表的建立,求顶点的度以及广度和深度遍历图。(由于有向网和无向网与有向图和无向图大致一致,只是多了权值,这里不再赘述)

2.分析

结构:图的所有顶点存储在一个数组当中,然后数组中的每一个元素又是一个链表的头节点。

求顶点的度:对于有向图来说,出度就是顶点所在行所链接的元素的个数(使用链表的遍历即可)

 入度就是指指向这个顶点的个数,需要遍历每一行的链表,找到有多少结点链接了这   个顶点。(比如求D点的入度,也就是看有哪些行链接了D点)

深度遍历:采用了递归的思想(类比二叉树)

广度遍历:类似于二叉树的层序遍历。

在广度和深度遍历的时候,都需要考虑到图不连通的情况,故我在下面的代码中每个遍历都由两个函数构成。

3.代码

我在这儿是建立了一个项目,包括了头文件、功能函数以及主函数

1)头文件(Head.H)
#ifndef _FUNC_H 
#define _FUNC_H   

#define MVNum 100   //大顶点数
#define OK 1;
#define ERROR 0;

typedef char VerTexType;  //顶点数据类型 
typedef int Status; 
typedef int QElemType;

 
typedef struct ArcNode{  //边结点 
	int adjvex;    //邻接点的下标
	struct ArcNode *nextarc;  //指向下一个邻接点 
}ArcNode;

typedef struct VNode{  //顶点信息 
	VerTexType data;   //存放结点的内容
	ArcNode *firstarc;  //指向第一个邻接点 
}VNode,AdjList[MVNum];  //建立头结点和包含头结点的数组AdjList;  

typedef struct{
	AdjList vertices;   //包含头节点的数组 
	int vexnum,arcnum;  //边数和点数 
}ALGraph;

//队列的结构体
typedef struct QNode{
	QElemType data;  //数据
	struct QNode *next;  //指向下一个节点 
}QNode,*QueuePtr;
//链队列中又存在着头尾指针
typedef struct{
	QueuePtr front;  //队头指针
	QueuePtr rear;  //队尾指针 
}LinkQueue;

extern Status CreateUDG(ALGraph &G);
extern Status LocateVex(ALGraph &G,VerTexType v);
extern Status CreateDG(ALGraph &G);
extern Status CalculateUDGD(ALGraph &G,VerTexType v);
extern Status CalculateDGI(ALGraph &G,VerTexType v);
extern Status CalculateSum(ALGraph &G,VerTexType v);
extern void DFSTraverse(ALGraph G);
extern void DFS(ALGraph G,int v);
extern void BFSTraverse(ALGraph G);
extern void BFS(ALGraph G,int v);
extern Status Reverse(ALGraph G);
extern void print();

extern Status InitQueue(LinkQueue &Q);
extern Status EnQueue(LinkQueue &Q,int e);
extern Status DeQueue(LinkQueue &Q,QElemType &e);
extern Status  QueueEmpty(LinkQueue Q);
extern Status DestroyQueue(LinkQueue &Q);

#endif
2)功能函数(function.cpp)
#includeusing namespace std;
#include "Head.H"

bool visited[MVNum];  //查看点是否被遍历过 

//菜单栏
void print(){
	cout<<"==========================="<>G.vexnum>>G.arcnum;  //输入顶点数和边数
	cout<<"请输入各个顶点的内容:";
	for(i=0;i>G.vertices[i].data;   //建立数组的头节点 
		G.vertices[i].firstarc=NULL;  //使头节点指针的指向均为空 
	}
	for(k=0;k>v1>>v2;	
		i=LocateVex(G,v1);
		j=LocateVex(G,v2);
		ArcNode* p1=new ArcNode;  //开辟一个结点
		p1->adjvex=j;   
		p1->nextarc=G.vertices[i].firstarc;  //头插法插入 
		G.vertices[i].firstarc=p1;
		ArcNode* p2=new ArcNode;  //开辟节点
		p2->adjvex=i;
		p2->nextarc=G.vertices[j].firstarc; 
		G.vertices[j].firstarc=p2;
	}
	return OK;	
}
//有向图
Status CreateDG(ALGraph &G){
	int i,j,k;
	VerTexType v1,v2;
	cout<<"请输入此有向图的顶点和边数:";
	cin>>G.vexnum>>G.arcnum;
	cout<<"请输入每个顶点的内容:"; 
	for(i=0;i>G.vertices[i].data;
		G.vertices[i].firstarc=NULL;
	}
		
	for(k=0;k>v1>>v2; //输入相邻两点
		i=LocateVex(G,v1);  //定位
		j=LocateVex(G,v2);
		ArcNode *p=new ArcNode; //开辟一个空间
		p->adjvex=j;
		p->nextarc=G.vertices[i].firstarc;  //头插法插入 
		G.vertices[i].firstarc=p; 
	} 
	return OK; 
} 
Status LocateVex(ALGraph &G,VerTexType v){
	int i;
	for(i=0;inextarc;
		n++;
	} 
	return n;
} 
//有向图的入度
//需要把每个顶点遍历一次,找到到点i的情况,增加1 
Status CalculateDGI(ALGraph &G,VerTexType v){
	if(LocateVex(G,v)==-1)  return -1;  //输入的顶点错误的情况
	int i,j=LocateVex(G,v);  
	int n=0;  //计数
	ArcNode *p; //临时指针 
	for(i=0;iadjvex==j)
				n++;
			p=p->nextarc;	
		}	
	}
	return n; 
} 
//有向图的总度 
Status CalculateSum(ALGraph &G,VerTexType v){
	if(LocateVex(G,v)==-1) return  -1;
	return CalculateUDGD(G,v)+CalculateDGI(G,v); 
}
//遍历输出(深度优先搜索遍历) 
void DFSTraverse(ALGraph G){
	int i;
	for(i=0;inextarc){
		if(visited[p->adjvex]==false) DFS(G,p->adjvex);
	} 
}
//广度优先算法
void BFSTraverse(ALGraph G){
	int i;
	for(i=0;inextarc){
			if(visited[p->adjvex]==false){
				visited[p->adjvex]=true;
				EnQueue(Q,p->adjvex);
			}
		}
	} 
}
//存储结构的遍历
Status Reverse(ALGraph G){
	int i,j;
	ArcNode *p;
	for(i=0;i";
		for(p=G.vertices[i].firstarc;p;p=p->nextarc)
			cout<adjvex].data<<"->";
		cout<<""<next=NULL;  //头指针的指针域置空
	return OK;
} 
//入队列
Status EnQueue(LinkQueue &Q,int e){
	QueuePtr p=new QNode;  //开辟一个空间
	p->data=e;    //内容存储
	Q.rear->next=p;
	p->next=NULL;
	Q.rear=p;
	return OK; 
} 
//出队列
//判断是否为空
//不为空,判断是否是只有一个元素 
Status DeQueue(LinkQueue &Q,QElemType &e){
	if(Q.front==Q.rear)  return ERROR;
	QueuePtr p=Q.front->next; 
	e=p->data;  //得到元素值 
	Q.front->next=p->next;
	if(p==Q.rear){
		Q.rear=Q.front;
	} 
	delete p;
	return OK;
} 
//判空
Status  QueueEmpty(LinkQueue Q){
	return (Q.front==Q.rear); 
}
//销毁队列
Status DestroyQueue(LinkQueue &Q){
	QueuePtr p;
	while(Q.front){
		p=Q.front;
		Q.front=Q.front->next;
		delete p;
	}
	return OK;
} 
3)主函数(main.cpp)
#includeusing namespace std; 
#include "head.H"

int main(int argc, char** argv) {
	VerTexType v;
	ALGraph G;
	char order1,order2;  //选择用char类型,使得当选择输入为字母时,不会出错。 
	cout<<"============================"<>order1;			
	}while(order1!='1'&&order1!='2'&&order1!='0');
	switch(order1){
		case '1':
			do{
				print();
				cout<<"请输入你的选择:";
				cin>>order2;
				switch(order2){
					case '1':
						CreateUDG(G);
						cout<<"此无向图的邻接表建立成功!!!"<>v;
						if(CalculateUDGD(G,v)==-1)
							cout<>order2;
				switch(order2){
					case '1':
						CreateDG(G);
						cout<<"此有向图的邻接表建立成功!!!"<>v;
						if(CalculateUDGD(G,v)==-1)
							cout<
4.运行结果(DEV)

无向图:

建立

 

求度

遍历

有向图:

创建

 

求度

遍历

5.总结

总的来说,这个实验综合性较强,需要用到之前说学的链表和队列的操作,结构也更加复杂。

谢谢阅读,希望对大家有帮助吖!

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


当前文章:邻接表的相关操作(类C语言)-创新互联
文章位置:http://pwwzsj.com/article/gpjie.html