会python真的可以为所欲为0(回)
353天前
这里还有人吗1(回)
538天前这里还有人吗0(回)
538天前
每天面对着电脑屏幕，敲打键盘。我所面对的并不只是代码，而是一种生活方式。0(回)
763天前到处都是羊，不想上班0(回)
843天前
鸽子
0(回)
847天前#include<iostream> |
using namespace std; |
const int MVN = 21; |
typedef char VeuType;//顶点元素类型 |
typedef struct ArcNode |
{ |
int adjveu;//弧指向的顶点位置 |
int adj;//权 |
ArcNode *neutarc;//指向下一条弧的顶点 |
}*ArcPtr; |
struct VeuNode |
{ |
VeuType data;//顶点数据 |
ArcPtr firstarc;//指向第一条依附于该顶点的弧 |
bool visited;//是否被访问过 |
}; |
struct ALGraph |
{ |
VeuNode veus[MVN]; |
int kind, veunum, arcnum;//类型，顶点数，弧数 |
}; |
int LocateVeu(ALGraph &G, VeuType v);//在图G中查找顶点 |
bool InsertArc(ALGraph &G, VeuType u, VeuType v, int w = 1); |
void CreateGraph(ALGraph &G, int Kind, char v[]); |
void GraphPrint(ALGraph &G); |
bool insertdian(ALGraph &G, VeuType u);//插入一个顶点 |
bool DeleteHu(ALGraph &G, VeuType u, VeuType v);//删除一条弧 |
bool Deletedian(ALGraph &G, VeuType u); |
int main() |
{ |
char g[] = "sacd#sascsdacadcd#"; |
cout << "原始序列为 "<< endl<<g <<endl; |
int Kind = 1; |
ALGraph G; |
CreateGraph(G, Kind, g); |
GraphPrint(G); |
VeuType v = 'c'; |
Deletedian(G, v); |
cout << "删除顶点" <<v<< endl; |
GraphPrint(G); |
VeuType u = 'e'; |
insertdian(G, u); |
cout << "插入顶点" <<u<< endl; |
GraphPrint(G); |
VeuType v1 = 's'; |
VeuType v2 = 'a'; |
cout << "删除弧<"<<v1<<","<<v2<<">" << endl; |
DeleteHu(G, v1, v2); |
GraphPrint(G); |
return 0; |
} |
int LocateVeu(ALGraph &G, VeuType v) |
{ |
int i; |
for (i = G.veunum; i > 0 && G.veus[i].data != v; i--); |
return i; |
} |
bool InsertArc(ALGraph &G, VeuType u, VeuType v, int w ) |
{ |
ArcPtr p; |
int i, j; |
bool found; |
i = LocateVeu(G, u); |
if (i == 0) |
{ |
return false; |
} |
j = LocateVeu(G, v); |
if (j == 0 || j == i) |
{ |
return false; |
} |
for (found = false, p = G.veus[i].firstarc; p && !found; p = p->neutarc)//若弧存在，插入失败 |
{ |
if (p->adjveu == j) |
{ |
found = true; |
} |
} |
if (found) |
{ |
return false; |
} |
G.arcnum++; |
p = new ArcNode; |
p->adjveu = j; |
p->adj = w; |
p->neutarc = G.veus[i].firstarc; |
G.veus[i].firstarc = p;//表头插入弧，假设对弧的次序无要求 |
if (G.kind <= 2) |
{ |
return true; |
} |
G.arcnum++; |
p = new ArcNode; |
p->adjveu = i; |
p->adj = w; |
p->neutarc = G.veus[j].firstarc; |
G.veus[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.veus[i].data = v[i - 1]; |
G.veus[i].firstarc = NULL; |
} |
G.veunum = 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 << "顶点数：" << G.veunum << " " << "弧数：" << G.arcnum << endl;; |
cout << "邻接表" << endl; |
for (int i = 1; i <= G.veunum; i++) |
{ |
cout << G.veus[i].data; |
for (p = G.veus[i].firstarc; p; p = p->neutarc) |
{ |
cout << "->" << p->adjveu; |
} |
cout << endl; |
|
} |
} |
bool insertdian(ALGraph &G, VeuType u) |
{ |
int i; |
i = LocateVeu(G, u); |
if (i != 0) |
{ |
return false; |
} |
G.veunum++; |
G.veus[G.veunum].data = u; |
G.veus[G.veunum].firstarc = NULL; |
return true; |
} |
bool DeleteHu(ALGraph &G, VeuType u, VeuType v) |
{ |
ArcPtr p,q; int i, j; bool found; |
i = LocateVeu(G, u); |
if (i == 0) return false; |
j = LocateVeu(G, v); |
if (j == 0 || j == i)return false; |
found = false; |
p = NULL; |
q = G.veus[i].firstarc; |
while (q && !found) |
{ |
if (q->adjveu == j)found = true; |
else { |
p = q; |
q = q->neutarc; |
} |
} |
if (!found)return false;//没有该弧 |
if (p) p->neutarc = q->neutarc; |
else G.veus[i].firstarc = q->neutarc; |
|
delete q; G.arcnum--; |
if (G.kind <= 2) return true; |
//无向图的情况 |
found = false; |
p = NULL; |
q = G.veus[j].firstarc; |
while (q && !found) |
{ |
if (q->adjveu == i)found = true; |
else { |
p = q; |
q = q->neutarc; |
} |
} |
if (p) p->neutarc = q->neutarc; |
else G.veus[j].firstarc = q->neutarc; |
delete q; |
G.arcnum--; |
return true; |
|
} |
bool Deletedian(ALGraph &G, VeuType u) |
{ |
ArcPtr p, q; int i,j; bool found; |
i = LocateVeu(G, u); |
if (i == 0) return false; |
|
//删除出弧，弧数对应减少 |
p = G.veus[i].firstarc; |
while (p) |
{ |
q = p; |
p = p->neutarc; |
delete q; |
G.arcnum--; |
} |
//删除入弧,弧数对应减少 |
for ( j = 1; j <= G.veunum; j++) |
{ |
if (j != i) |
{ |
found = false; |
p = NULL; |
q = G.veus[j].firstarc; |
while (q && !found) |
{ |
if (q->adjveu == i) found = true; |
else |
{ |
p = q; |
q = q->neutarc; |
} |
} |
if (!found) |
continue; |
if (p) |
p->neutarc = q->neutarc; |
else |
G.veus[j].firstarc = q->neutarc; |
delete q; |
G.arcnum--; |
} |
} |
G.veus[i] = G.veus[G.veunum]; |
for ( j = 1; j <= G.veunum; j++) |
{ |
|
for (p= G.veus[j].firstarc;p;p=p->neutarc) |
{ |
if (p->adjveu == G.veunum) |
{ |
p->adjveu = i; |
break; |
} |
} |
} |
G.veunum--; |
return true; |
|
} |
