#define Default_Vertex_Size 10
#define T char
typedef struct GraphMtx
{
int MaxVertices;//最大顶点容量
int NumVertices;//图中顶点个数
int NumEdges;//图中边的条数
T *VerticesList;//指向存有顶点的空间的指针
int **Edge;//指向存矩阵的空间的指针
}GraphMtx;
void InitGraph(GraphMtx *g)
{
g->MaxVertices = Default_Vertex_Size;
g->NumVertices = g->NumEdges = 0;
//为存储顶点的空间进行初始化
g->VerticesList = (T*)malloc(sizeof(T)*(g->MaxVertices));
assert(g->VerticesList != NULL);
//为存储矩阵的空间进行初始化
g->Edge = (int**)malloc(sizeof(int*) * g->MaxVertices);
assert(g->Edge != NULL);
for(int i=0; i<g->MaxVertices; ++i)
{
g->Edge[i] = (int*)malloc(sizeof(int) * g->MaxVertices);
}
for(i=0; i<g->MaxVertices; ++i)
{
for(int j=0; j<g->MaxVertices; ++j)
{
g->Edge[i][j] = 0;
}
}
}
1F0E90~1F0EB8一共40字节
发现了每个行的地址是连续，但是行存储的地址之间相差了104（10进制）
从这里就可以知道为什么要用int ** 去定义edge。想要获得矩阵里的值，就要先去取edge[i]行里面存的地址，找到那一行的所在列，再根据列的地址找到存储的那个值。
void main()
{
GraphMtx gm;
InitGraph(&gm);
InsertVertex(&gm,'A');
InsertVertex(&gm,'B');
InsertVertex(&gm,'C');
InsertVertex(&gm,'D');
InsertVertex(&gm,'E');
InsertEdge(&gm,'A','B');
InsertEdge(&gm,'A','D');
InsertEdge(&gm,'B','C');
InsertEdge(&gm,'B','E');
InsertEdge(&gm,'C','E');
InsertEdge(&gm,'C','D');
ShowGraph(&gm);
//int p = GetFirstNeighbor(&gm,'D');
int p = GetNextNeighbor(&gm,'D','C');
}
void InsertVertex(GraphMtx *g, T v)
{
if(g->NumVertices >= g->MaxVertices)
return;
g->VerticesList[g->NumVertices++] = v;
}
插入完毕
思路是获取矩阵的行列，如果顶点A和顶点B相连，首先找到A的位置和B的位置；矩阵[A][B]=[B][A]=1
//获取顶点在连续内存（看做数组）中的的位置
int GetVertexPos(GraphMtx *g, T v)
{
for(int i=0; i<g->NumVertices; ++i)
{
if(g->VerticesList[i] == v)
return i;
}
return -1;
}
//插入边
void InsertEdge(GraphMtx *g, T v1, T v2)
{
int p1 = GetVertexPos(g,v1);
int p2 = GetVertexPos(g,v2);
if(p1==-1 || p2==-1)
return;
if(g->Edge[p1][p2] != 0)
return;
g->Edge[p1][p2] = g->Edge[p2][p1] = 1;
g->NumEdges++;
}
找到A的位置是0，B的位置是1
找到边对应的位置，把矩阵的行列设为0
void RemoveEdge(GraphMtx *g, T v1, T v2)
{
int p1 = GetVertexPos(g,v1);
int p2 = GetVertexPos(g,v2);
if(p1==-1 || p2==-1)
return;
if(g->Edge[p1][p2] == 0)
return;
g->Edge[p1][p2] = g->Edge[p2][1] = 0;
g->NumEdges--;
}
不仅要删除顶点，还要删除相关联的边。这里采用类似顺序表的删除方法
void RemoveVertex(GraphMtx *g, T v)
{
int p = GetVertexPos(g,v);
if(p == -1)
return;
int numedges = 0;
for(int i=p; i<g->NumVertices-1; ++i)
{
g->VerticesList[i] = g->VerticesList[i+1];//假设删除C，在顶点表中让D给C赋值，E给D赋值
}
for(i=0; i<g->NumVertices; ++i)
{
if(g->Edge[p][i] != 0)
{
numedges++;
}
}
for(i=p; i<g->NumVertices-1; ++i)
{
for(int j=0; j<g->NumVertices; ++j)
{
g->Edge[i][j] = g->Edge[i+1][j];//让删除顶点所在位置的下一行的列给上一行的列赋值
}
}
for(i=p; i<g->NumVertices; ++i)
{
for(int j=0; j<g->NumVertices; ++j)
{
g->Edge[j][i] = g->Edge[j][i+1];//让删除顶点所在位置的下一列的行给前一列赋值
}
}
g->NumVertices--;
g->NumEdges -= numedges;
}
如图所示v1-V5表示A-E
也可以直接拿最后一个顶点覆盖要删除的顶点，这样效率更高。
void DestroyGraph(GraphMtx *g)
{
free(g->VerticesList);
g->VerticesList = NULL;
for(int i=0; i<g->NumVertices; ++i)
{
free(g->Edge[i]);
}
free(g->Edge);
g->Edge = NULL;
g->MaxVertices = g->NumEdges = g->NumVertices = 0;
}
int GetFirstNeighbor(GraphMtx *g, T v)
{
int p = GetVertexPos(g,v);
if(p == -1)
return -1;
for(int i=0; i<g->NumVertices; ++i)
{
if(g->Edge[p][i] == 1)
return i;
}
return -1;
}
int GetNextNeighbor(GraphMtx *g, T v, T w)
{
int pv = GetVertexPos(g,v);//先定位行
int pw = GetVertexPos(g,w);//从pw+1开始遍历，再定位列
if(pv==-1 || pw==-1)
return -1;
for(int i=pw+1; i<g->NumVertices; ++i)
{
if(g->Edge[pv][i] == 1)
return i;
}
return -1;
}
