第12週目、項目2－操作用隣接テーブルに格納した図
9262 ワード
問題およびコード:
(1)テスト関数:main.cpp、関連するテスト作業を完成する;
(1)テスト関数:main.cpp、関連するテスト作業を完成する;
/*
*Copyright(c) 2015,
*All rights reserved.
* ：test.cpp
* ：
* ：2015 11 16
* ；v1.0
*
* ： G ， ：
（1） G ；
（2） G ， ；
（3） G 0 ；
（4） G <i,j> 。
， 。
<img src="http://img.blog.csdn.net/20151116164015972?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="" /> * ：
* ：
*/
#include <stdio.h>
#include <malloc.h>
#include "graph.h"
// G v
int OutDegree(ALGraph *G,int v)
{
ArcNode *p;
int n=0;
p=G->adjlist[v].firstarc;
while (p!=NULL)
{
n++;
p=p->nextarc;
}
return n;
}
// G
void OutDs(ALGraph *G)
{
int i;
for (i=0; i<G->n; i++)
printf(" %d:%d
",i,OutDegree(G,i));
}
// G
void OutMaxDs(ALGraph *G)
{
int maxv=0,maxds=0,i,x;
for (i=0; i<G->n; i++)
{
x=OutDegree(G,i);
if (x>maxds)
{
maxds=x;
maxv=i;
}
}
printf(" %d， =%d
",maxv,maxds);
}
// G 0
void ZeroDs(ALGraph *G)
{
int i,x;
for (i=0; i<G->n; i++)
{
x=OutDegree(G,i);
if (x==0)
printf("%2d",i);
}
printf("
");
}
// G <i,j>
bool Arc(ALGraph *G, int i,int j)
{
ArcNode *p;
bool found = false;
p=G->adjlist[i].firstarc;
while (p!=NULL)
{
if(p->adjvex==j)
{
found = true;
break;
}
p=p->nextarc;
}
return found;
}
int main()
{
ALGraph *G;
int A[7][7]=
{
{0,1,1,1,0,0,0},
{0,0,0,0,1,0,0},
{0,0,0,0,1,1,0},
{0,0,0,0,0,0,1},
{0,0,0,0,0,0,0},
{0,0,0,1,1,0,1},
{0,1,0,0,0,0,0}
};
ArrayToList(A[0], 7, G);
printf("(1) :
");
OutDs(G);
printf("(2) :");
OutMaxDs(G);
printf("(3) 0 :");
ZeroDs(G);
printf("(4) <2,6> ？");
if(Arc(G,2,6))
printf("
");
else
printf("
");
printf("
");
return 0;
}
（2） ：graph.h， 、 、 ；#ifndef GRAPH_H_INCLUDED
#define GRAPH_H_INCLUDED
#define MAXV 100 //
#define INF 32767 //INF ∞
typedef int InfoType;
//
typedef struct
{
int no; //
InfoType info; // ，
} VertexType; //
typedef struct //
{
int edges[MAXV][MAXV]; //
int n,e; // ，
VertexType vexs[MAXV]; //
} MGraph; //
//
typedef struct ANode //
{
int adjvex; //
struct ANode *nextarc; //
InfoType info; // ,
} ArcNode;
typedef int Vertex;
typedef struct Vnode //
{
Vertex data; //
int count; // ,
ArcNode *firstarc; //
} VNode;
typedef VNode AdjList[MAXV]; //AdjList
typedef struct
{
AdjList adjlist; //
int n,e; // n e
} ALGraph; //
// ： ，
// ：Arr - ， ， Arr （ int ）
// n -
// g -
void ArrayToMat(int *Arr, int n, MGraph &g); //
void ArrayToList(int *Arr, int n, ALGraph *&); //
void MatToList(MGraph g,ALGraph *&G);// g G
void ListToMat(ALGraph *G,MGraph &g);// G g
void DispMat(MGraph g);// g
void DispAdj(ALGraph *G);// G
#endif // GRAPH_H_INCLUDED
（3） ：graph.cpp， ；#include <stdio.h>
#include <malloc.h>
#include "graph.h"
// ： ，
// ：Arr - ， ， Arr （ int ）
// n -
// g -
void ArrayToMat(int *Arr, int n, MGraph &g)
{
int i,j,count=0; //count ， 0
g.n=n;
for (i=0; i<g.n; i++)
for (j=0; j<g.n; j++)
{
g.edges[i][j]=Arr[i*n+j]; // Arr n×n ，Arr[i*n+j] Arr[i][j]，
if(g.edges[i][j]!=0)
count++;
}
g.e=count;
}
void ArrayToList(int *Arr, int n, ALGraph *&G)
{
int i,j,count=0; //count ， 0
ArcNode *p;
G=(ALGraph *)malloc(sizeof(ALGraph));
G->n=n;
for (i=0; i<n; i++) //
G->adjlist[i].firstarc=NULL;
for (i=0; i<n; i++) //
for (j=n-1; j>=0; j--)
if (Arr[i*n+j]!=0) // ， Arr n×n ，Arr[i*n+j] Arr[i][j]
{
p=(ArcNode *)malloc(sizeof(ArcNode)); // *p
p->adjvex=j;
p->info=Arr[i*n+j];
p->nextarc=G->adjlist[i].firstarc; // *p
G->adjlist[i].firstarc=p;
}
G->e=count;
}
void MatToList(MGraph g, ALGraph *&G)
// g G
{
int i,j;
ArcNode *p;
G=(ALGraph *)malloc(sizeof(ALGraph));
for (i=0; i<g.n; i++) //
G->adjlist[i].firstarc=NULL;
for (i=0; i<g.n; i++) //
for (j=g.n-1; j>=0; j--)
if (g.edges[i][j]!=0) //
{
p=(ArcNode *)malloc(sizeof(ArcNode)); // *p
p->adjvex=j;
p->info=g.edges[i][j];
p->nextarc=G->adjlist[i].firstarc; // *p
G->adjlist[i].firstarc=p;
}
G->n=g.n;
G->e=g.e;
}
void ListToMat(ALGraph *G,MGraph &g)
// G g
{
int i,j;
ArcNode *p;
for (i=0; i<g.n; i++) //
for (j=0; j<g.n; j++)
g.edges[i][j]=0;
for (i=0; i<G->n; i++) // ，
{
p=G->adjlist[i].firstarc;
while (p!=NULL)
{
g.edges[i][p->adjvex]=p->info;
p=p->nextarc;
}
}
g.n=G->n;
g.e=G->e;
}
void DispMat(MGraph g)
// g
{
int i,j;
for (i=0; i<g.n; i++)
{
for (j=0; j<g.n; j++)
if (g.edges[i][j]==INF)
printf("%3s","∞");
else
printf("%3d",g.edges[i][j]);
printf("
");
}
}
void DispAdj(ALGraph *G)
// G
{
int i;
ArcNode *p;
for (i=0; i<G->n; i++)
{
p=G->adjlist[i].firstarc;
printf("%3d: ",i);
while (p!=NULL)
{
printf("-->%d/%d ",p->adjvex,p->info);
p=p->nextarc;
}
printf("
");
}
}
：<img src="http://img.blog.csdn.net/20151116164031559?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="" />