目录
站在用户的角度思考问题，与客户深入沟通，找到江源网站设计与江源网站推广的解决方案，凭借多年的经验，让设计与互联网技术结合，创造个性化、用户体验好的作品，建站类型包括：成都做网站、成都网站设计、企业官网、英文网站、手机端网站、网站推广、域名与空间、
雅安服务器托管、企业邮箱。业务覆盖江源地区。
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语言）-创新互联
当前URL：
http://www.cdkjz.cn/article/gpjie.html
