会python真的可以为所欲为0(回)
349天前
这里还有人吗1(回)
534天前这里还有人吗0(回)
534天前
每天面对着电脑屏幕，敲打键盘。我所面对的并不只是代码，而是一种生活方式。0(回)
759天前到处都是羊，不想上班0(回)
839天前
鸽子
0(回)
843天前#include<iostream> |
using namespace std; |
const int MVN = 21; |
typedef char VexType;//顶点元素类型 |
typedef struct ArcNode |
{ |
int adjvex;//弧指向的顶点位置 |
int adj;//权 |
ArcNode *nextarc;//指向下一条弧的顶点 |
}*ArcPtr; |
struct VexNode |
{ |
VexType data;//顶点数据 |
ArcPtr firstarc;//指向第一条依附于该顶点的弧 |
bool visited;//是否被访问过 |
}; |
struct ALGraph |
{ |
VexNode vexs[MVN]; |
int kind, vexnum, arcnum;//类型，顶点数，弧数 |
}; |
int LocateVex(ALGraph &G, VexType v);//查找顶点 |
bool InsertArc(ALGraph &G, VexType u, VexType v, int w = 1);//插入弧 |
void CreateGraph(ALGraph &G, int Kind, char v[]); |
void GraphPrint(ALGraph &G); |
int Outdegree(ALGraph &G, VexType u);//求一个顶点的出度 |
int Indegree(ALGraph &G, VexType u);//求一个顶点的入度 |
int* degree(ALGraph &G);//求全部顶点的入度 |
int main() |
{ |
char g[] = "sbcd#sbscsdbcbdcd#"; |
cout << "序列为 "<< endl<<g<< endl; |
int Kind = 1; |
ALGraph G; |
CreateGraph(G, Kind, g); |
GraphPrint(G); |
VexType u = 's'; |
int n = Outdegree(G, u); |
cout << "顶点"<<u<<"的出度为" << n << endl; |
VexType v = 'c'; |
int m = Indegree(G, v); |
cout << "顶点"<<v<<"的入度为" << m << endl; |
int *a = degree(G); |
cout << "各个顶点的入度依次为:"; |
for (int j = 1; j <= G.vexnum; j++) |
{ |
cout << a[j] << " "; |
} |
cout << endl; |
return 0; |
} |
int LocateVex(ALGraph &G, VexType v) |
{ |
int i; |
for (i = G.vexnum; i>0 && G.vexs[i].data != v; i--); |
return i; |
} |
bool InsertArc(ALGraph &G, VexType u, VexType v, int w ) |
{ |
ArcPtr p; |
int i, j; |
bool found; |
i = LocateVex(G, u); |
if (i == 0) |
{ |
return false; |
} |
j = LocateVex(G, v); |
if (j == 0 || j == i) |
{ |
return false; |
} |
for (found = false, p = G.vexs[i].firstarc; p && !found; p = p->nextarc) |
{ |
if (p->adjvex == j) |
{ |
found = true; |
} |
} |
if (found) |
{ |
return false; |
} |
G.arcnum++; |
p = new ArcNode; |
p->adjvex = j; |
p->adj = w; |
p->nextarc = G.vexs[i].firstarc; |
G.vexs[i].firstarc = p; |
if (G.kind <= 2) |
{ |
return true; |
} |
G.arcnum++; |
p = new ArcNode; |
p->adjvex = i; |
p->adj = w; |
p->nextarc = G.vexs[j].firstarc; |
G.vexs[j].firstarc = p; |
return true; |
} |
void CreateGraph(ALGraph &G, int Kind, char v[]) |
{ |
int i, w; |
G.kind = Kind; |
G.arcnum = 0; |
i = 0; |
while (true) |
{ |
if (v[i] == '#') |
{ |
break; |
} |
i++; |
G.vexs[i].data = v[i - 1]; |
G.vexs[i].firstarc = NULL; |
} |
G.vexnum = i; |
i++; |
while (true) |
{ |
if (v[i] == '#') |
{ |
break; |
} |
if (G.kind == 1 || G.kind == 3) |
{ |
w = 1; |
} |
else |
{ |
w = v[i + 2] - 48; |
} |
InsertArc(G, v[i], v[i + 1], w); |
i = i + 2; |
if (w == 2 || w == 4) |
{ |
i++; |
} |
} |
} |
void GraphPrint(ALGraph &G) |
{ |
ArcPtr p; |
cout << "邻接表" << endl; |
for (int i = 1; i <= G.vexnum; i++) |
{ |
cout << G.vexs[i].data; |
for (p = G.vexs[i].firstarc; p; p = p->nextarc) |
{ |
cout << "->" << p->adjvex; |
} |
cout << endl; |
} |
} |
int Outdegree(ALGraph &G, VexType u) |
{ |
int i = LocateVex(G, u); |
int n = 0; |
ArcPtr p; |
for (p = G.vexs[i].firstarc; p; p = p->nextarc) |
{ |
n++; |
} |
return n; |
} |
int Indegree(ALGraph &G, VexType u) |
{ |
int i = LocateVex(G, u); |
int n = 0; |
ArcPtr p; |
for (int j = 1; j <= G.vexnum; j++) |
{ |
if (j == i) |
{ |
continue; |
} |
for (p = G.vexs[j].firstarc; p; p = p->nextarc) |
{ |
if (p->adjvex == i) |
{ |
n++; |
break; |
} |
} |
} |
return n; |
} |
int* degree(ALGraph &G) |
{ |
int *a; |
a = new int[G.vexnum + 1]; |
for (int i = 1; i <= G.vexnum; i++) |
{ |
a[i] = 0; |
} |
ArcPtr p; |
for (int j = 1; j <= G.vexnum; j++) |
{ |
for (p = G.vexs[j].firstarc; p; p = p->nextarc) |
{ |
a[p->adjvex]++; |
} |
} |
return a; |
} |
