会python真的可以为所欲为0(回)
353天前
这里还有人吗1(回)
538天前这里还有人吗0(回)
538天前
每天面对着电脑屏幕，敲打键盘。我所面对的并不只是代码，而是一种生活方式。0(回)
763天前到处都是羊，不想上班0(回)
843天前
鸽子
0(回)
847天前#include <iostream> |
#include <fstream> |
using namespace std; |
#include<iostream> |
using namespace std; |
const int MVN = 21; |
typedef char VexType;//顶点元素类型 |
typedef int QElemType; |
typedef struct QNode |
{ |
QElemType data; |
QNode *next; |
}*LQueuePtr; |
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;//类型，顶点数，弧数 |
}; |
struct LQueue |
{ |
LQueuePtr front, rear;//队头指针，队尾指针 |
}; |
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); |
void QueueInit(LQueue &Q); |
void Enqueue(LQueue &Q, QElemType e); |
bool Dequeue(LQueue &Q, QElemType &e); |
void visit(VexType u); |
bool existroad(ALGraph &G, VexType u, VexType v); |
int main() |
{ |
char g[] = "sacdw#sascsdacadcd#"; |
cout << "序列为 "<< endl<< g<< endl; |
int Kind = 3; |
ALGraph G; |
CreateGraph(G, Kind, g); |
GraphPrint(G); |
VexType u = 'a'; |
//VexType v1 = 'c'; |
VexType v1 = 'w'; |
bool f1 =existroad(G, u, v1); |
cout <<u<<"到"<<v1<<"的路径"<< (f1?"":"不")<<"存在" << endl; |
return 0; |
} |
void QueueInit(LQueue &Q) |
{ |
Q.front = new QNode; |
Q.front->next = NULL; |
Q.rear = Q.front; |
} |
void Enqueue(LQueue &Q, QElemType e) |
{ |
LQueuePtr p; |
p = new QNode; |
p->data = e; |
p->next = NULL; |
Q.rear->next = p; |
Q.rear = p; |
} |
bool Dequeue(LQueue &Q, QElemType &e) |
{ |
LQueuePtr p; |
if (Q.rear == Q.front) |
{ |
return false; |
} |
p = Q.front; |
Q.front = p->next; |
e = Q.front->data; |
delete p; |
return true; |
} |
void visit(VexType u) |
{ |
cout << u << ","; |
} |
bool existroad(ALGraph &G, VexType u, VexType v) |
{ |
int i, j, k, m; |
ArcPtr p; |
LQueue q; |
m = LocateVex(G, u); |
if (m == 0) |
{ |
return false; |
} |
if (!G.vexs[m].firstarc) |
{ |
return false; |
} |
for (i = 1; i <= G.vexnum; i++) |
{ |
G.vexs[i].visited = false; |
} |
G.vexs[m].visited = true; |
QueueInit(q); |
Enqueue(q, m); |
while (Dequeue(q, j)) |
{ |
for (p = G.vexs[j].firstarc; p; p = p->nextarc) |
{ |
k = p->adjvex; |
if (G.vexs[k].visited) |
{ |
continue; |
} |
if (G.vexs[k].data == v) |
{ |
return true; |
} |
G.vexs[k].visited = true; |
Enqueue(q, k); |
} |
} |
return false; |
} |
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; |
} |
} |
