邻接表的相关操作(类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://myzitong.com/article/gpjie.html