邻接表

#include <iostream>
#include “stdio.h”
#include “stdlib.h”
#include “cstdlib”//syste()函数需要该头文件；

using namespace std;

#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;

typedef char VerTexType;
typedef int ArcType;
#define MVNum 100 //最大顶点数

//00 定义边结点 顶点结点 邻接表

 typedef struct ArcNode{ //边结点 

　　int adjvex; 　　　　 //该边所指向的顶点的位置，数组中的位置，下标0开始
　　ArcType weight; 　　 //和边相关的信息
　　struct ArcNode * nextarc; //指向下一条边的指针
}ArcNode;

typedef struct VNode{
　　VerTexType data; //顶点信息
　　ArcNode * firstarc; //指向第一条依附该顶点的边的指针，用到ArcNode类型，故放在边定义后
}VNode, AdjList[MVNum]; //AdjList表示邻接表类型，数组，里面是VNode型数据

typedef struct{
　　AdjList adjList; //邻接表，adjList是个VNode型数组，用来放顶点及邻接表指针
　　int vexnum, arcnum; //图的当前顶点数和边数
}ALGraph;

//01 定位

 int LocateVex(ALGraph G,char ch)

{
　　int i;
　　for(i=0;i<G.vexnum;i++){
　　　　if(ch==G.adjList[i].data)
　　　　　　return i;//return返回，下面-1不执行了。
　　}
　　return -1;
}

//02 创建，注意是图 有向图 网，不一样，里面代码也不同

Status CreateALGraph(ALGraph &G)
{
　　int i,j,k,w;//无向图权值可以不要，可以置0，后面不用输入
　　ArcNode *p1,*p2;//p1将来放到邻接表数组中的指针域，故声明指针型
　　char v1,v2;
　　printf(“Input the number of vertex and arc:\n”);
　　cin>>G.vexnum>>G.arcnum;
　　printf(“The number is %d and %d.\n”,G.vexnum,G.arcnum);//验证输入内容

　　for(i=0;i<G.vexnum;i++)
　　{
　　　　cin>>G.adjList[i].data;
　　　　G.adjList[i].firstarc=NULL;
　　}

　　//build 边表,构造的是无向图，书本中的例子
　　for(k=0;k<G.arcnum;k++)
　　{
　　　　printf(“输入边(vi,vj)上的顶点序号及权值:\n”);
　　　　cin>>v1>>v2>>w;

　　　　i=LocateVex(G,v1);
　　　　j=LocateVex(G,v2);
　　　　cout<<i<<“和”<<j<<endl;//验证
　　　　if(i==-1 || j==-1){
　　　　　　return ERROR;
　　　　}

　　　　//申请内存空间生成边表结点，单链表前插法
　　　　p1=new ArcNode;
　　　　if(p1==NULL)
　　　　{
　　　　　　return ERROR;
　　　　}
　　　　p1->adjvex=j;
　　　　p1->weight=w;
　　　　p1->nextarc=G.adjList[i].firstarc;//注意画个图
　　　　G.adjList[i].firstarc=p1;//前面最好声明p1为指针型

　　　　//无向图有这一步，有向图就不需要了
　　　　p2=new ArcNode;
　　　　if(p2==NULL)
　　　　　　return ERROR;
　　　　p2->adjvex=i;
　　　　p2->weight=w;
　　　　p2->nextarc=G.adjList[j].firstarc;//注意画个图
　　　　G.adjList[j].firstarc=p2;//此处赋值为指针，故前面最好声明p1为指针型
　　}
　　return OK;
}

//03打印
void PrintALGraphArc(ALGraph G)
{
　　int i=0;
　　ArcNode *p=NULL;
　　while(G.adjList[i].firstarc!=NULL && i<G.vexnum)
　　{
　　　　printf(“顶点%c与这些点连接：”,G.adjList[i].data);

　　　　p=G.adjList[i].firstarc;

　　　　while(p!=NULL){
　　　　　　printf(“%d %c “,p->adjvex,G.adjList[p->adjvex]); //打印边表的节点
　　　　　　p=p->nextarc;
　　　　}
　　　　i++;
　　printf(“\n”);
　　}
}

int main()
{
　　ALGraph G;
　　CreateALGraph(G);
　　PrintALGraphArc(G);
　　system(“pause”);
　　return OK;
}

今天的文章邻接表分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。