实验名称：数据结构实验五
实验内容：1.使用邻接矩阵建立一个图，深度遍历。2．使用邻接表建立一个图，广度遍历。3.建立一个图，存储结构自己确定，并进行拓扑排序。
实验代码：
1.#include \"stdio.h\" #define Infinity 100 #define MaxVertexNum 20 typedef enum {DG,DN,UDG,UDN} GraphKind; typedef int VRType; typedef char VertexType; bool Visit[MaxVertexNum]; typedef struct ArcCell { VRType adj; }ArcCell,AdjMatrix[MaxVertexNum][MaxVertexNum]; typedef struct
{
VertexType vexs[MaxVertexNum];
AdjMatrix arcs;
//邻接矩阵
int vexnum,arcnum;
//图的当前顶点数和弧数
GraphKind kind; }MGraph;
int LocateVex(MGraph G,VertexType v) { for(int i=0;i
if(v==G.vexs[i])
return i; } if (i = G.vexnum)
printf(\"输入的顶点不合法\\n\"); return 0; }
VertexType v1,v2; VRType w; void CreateUDG(MGraph &G) { int i,j,k; printf(\"请输入顶点数：\\n\"); scanf(\"%d\",&G.vexnum); printf(\"请输入弧数：\\n\"); scanf(\"%d\",&G.arcnum); i = 0; while(i
printf(\"请输入第%d个顶点\\n\",i);
getchar();
scanf(\"%c\",&G.vexs[i]);
++i; } for(i=0;i
for(j=0;j
G.arcs[i][j].adj = 0; } for(k=0;k
printf(\"请输入一条边依附的顶点及权值（v1 v2 w）\\n\");
getchar();
scanf(\"%c %c %d\",&v1,&v2,&w);
i =LocateVex(G,v1);
j =LocateVex(G,v2);
G.arcs[i][j].adj= w;
G.arcs[j][i] = G.arcs[i][j];
} return; }
void DFSTraverse(MGraph &G,int i) {
printf(\"%c \",G.vexs[i]); Visit[i]=true; for(int j=0;j
if(G.arcs[i][j].adj==1&&!Visit[j])
{
DFSTraverse(G,j);
} } }
void DFS(MGraph &G) { int i; for(i=0;i
if(!Visit[i])
{
DFSTraverse(G,i);
} } }
void main() { MGraph graph; CreateUDG(graph); printf(\"顶点集合为：：\"); for (int i=0;i
printf(\"%c \",graph.vexs[i]); printf(\"\\n深度遍历结果是：\"); DFS(graph); printf(\"\\n\"); return; }
2．
#include \"stdio.h\" #include \"stdlib.h\" #define MaxVertexNum 20 typedef int InfoType; typedef char VertexType; typedef VertexType QElemType; bool visited[MaxVertexNum];
typedef struct ArcNode { int adjvex;
//该弧指向的顶点位置
struct ArcNode *nextarc;
//指向下一条弧的指针
InfoType *info; }ArcNode;
typedef struct VNode { VertexType data;
//顶点信息
ArcNode *firstarc;
//指向第一条依附该顶点的弧的指针 }VNode,AdjList[MaxVertexNum];
typedef struct { AdjList vertices; int vexnum,arcnum;
//图的当前顶点数和弧数 }ALGraph;
typedef struct QNode { QElemType data; struct QNode *next; }QNode,*Queueptr;
typedef struct { Queueptr front; Queueptr rear; }LinkQueue;
void InitQueue(LinkQueue &Q) { Q.front = Q.rear = (Queueptr)malloc(sizeof(QNode)); if(!Q.front) return; Q.front->next = NULL; return; } void EnQueue(LinkQueue &Q,QElemType e) { Queueptr p = NULL; p = (Queueptr)malloc(sizeof(QNode)); if(!p) return; p->data = e; p->next = NULL; Q.rear->next = p; Q.rear = p; return; }
QElemType DeQueue(LinkQueue &Q,QElemType &e) { Queueptr p; if(Q.front==Q.rear) return \' \'; p = Q.front->next; e = p->data; Q.front->next = p->next; if(Q.rear==p)
Q.rear = Q.front; free(p); return e; }
int QueueEmpty(LinkQueue Q) { if(Q.front==Q.rear)
return 1; else
return 0; }
int Locate(ALGraph G,VertexType v) { for(int k=0;k
if(v==G.vertices[k].data)
return k; } if (k = G.vexnum)
printf(\"输入的顶点不合法\\n\"); return 0; }
void CreateALGraph(ALGraph &G) {
VertexType v1,v2; int i,j,k; ArcNode *p,*r; printf(\"请输入顶点数和弧数（以空格分开） : \"); scanf(\"%d %d\",&G.vexnum,&G.arcnum); for(i=0;i
getchar();
printf(\"请输入第%d个结点 : \",i);
scanf(\"%c\",&G.vertices[i].data);
G.vertices[i].firstarc = NULL; } for(i=0;i
printf(\"请输入第%d条弧（格式：顶点 顶点（以空格隔开））
getchar();
scanf(\"%c %c\",&v1,&v2);
k=Locate(G,v1);
j=Locate(G,v2);
p = (ArcNode*)malloc(sizeof(ArcNode));
r = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = j;
p->info = NULL;
r->adjvex = k;
r->info = NULL;
p->nextarc=G.vertices[k].firstarc;
G.vertices[k].firstarc=p;
r->nextarc=G.vertices[j].firstarc;
G.vertices[j].firstarc=r; } return; }
void BFSTraverse(ALGraph G,QElemType x) { int i,v; ArcNode *p; QElemType v1; for(v=0;v
visited[v] = false; LinkQueue Q;
: \",i); InitQueue(Q); EnQueue(Q,x); i = Locate(G,x); visited[i] = true; for(v=0;v
while(!QueueEmpty(Q))
{
DeQueue(Q,v1);
printf(\"%c \",v1);
i=Locate(G,v1);
p = G.vertices[i].firstarc;
while(p!=NULL)
{
if(!visited[p->adjvex])
{
visited[p->adjvex] = true;
EnQueue(Q,G.vertices[p->adjvex].data);
}
p = p->nextarc;
}
}
if(!visited[v])
{
visited[v] = true;
EnQueue(Q,G.vertices[v].data);
} } }
void main() { char flag1; ALGraph graph2; QElemType x; CreateALGraph(graph2); flag1 = \'Y\'; while(flag1 == \'Y\'||flag1 == \'y\') {
printf(\"请输入遍历的起点 : \");
getchar();
scanf(\"%c\",&x);
printf(\"广度遍历结果是：\\n\"); BFSTraverse(graph2,x); printf(\"\\n继续遍历（Y/N）: \");
getchar();
scanf(\"%c\",&flag1); } return; } 3．
#include \"stdio.h\" #include \"stdlib.h\" #define StackInitSize 20 #define StackIncrement 5 #define MaxVertexNum 20 typedef int InfoType; typedef char VertexType; typedef VertexType SElemType; typedef struct { SElemType *base; SElemType *top; int stacksize; }SqStack;
typedef struct ArcNode { int adjvex;
struct ArcNode *nextarc;
InfoType *info; }ArcNode;
typedef struct VNode { int indegree; VertexType data;
ArcNode *firstarc;
}VNode,AdjList[MaxVertexNum];
typedef struct { AdjList vertices; int vexnum,arcnum;
}ALGraph;
//该弧指向的顶点位置 //指向下一条弧的指针
//顶点信息
//指向第一条依附该顶点的弧的指针
//图的当前顶点数和弧数
bool InitStack(SqStack &s) { s.base = (SElemType * )malloc(StackInitSize * sizeof(SElemType)); if(!s.base) return false; s.top = s.base; s.stacksize = StackInitSize; return true; }
bool Pop(SqStack &s, int &e) { if(s.top==s.base)
return false; e = * --s.top; return true; }
bool Push(SqStack &s, int e) { if(s.top-s.base>=s.stacksize) {
s.base = (SElemType sizeof(SElemType) );
if(!s.base)
return false;
s.top = s.base+s.stacksize;
s.stacksize+=StackIncrement; } * s.top++ = e; return true; }
bool StackEmpty(SqStack s) { if(s.top == s.base)
return true; else
return false; }
int Locate(ALGraph G,VertexType v) {
*)realloc(s.base,(s.stacksize+StackIncrement) * for(int k=0;k
if(v==G.vertices[k].data)
return k; } if (k = G.vexnum)
printf(\"输入的顶点不合法\\n\"); return 0; }
void CreateALGraph(ALGraph &G)
//邻接表存储 {
VertexType v1,v2; int i,j,k; ArcNode *p; printf(\"请输入顶点数和弧数（以空格分开） : \"); scanf(\"%d %d\",&G.vexnum,&G.arcnum); for(i=0;i
getchar();
printf(\"请输入第%d个结点 : \",i);
scanf(\"%c\",&G.vertices[i].data);
G.vertices[i].firstarc = NULL;
G.vertices[i].indegree = 0; } for(i=0;i
printf(\"请输入第%d条有向弧弧（格式：顶点 顶点（以空格隔开））
getchar();
scanf(\"%c %c\",&v1,&v2);
k=Locate(G,v1);
j=Locate(G,v2);
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = j;
p->info = NULL;
p->nextarc=G.vertices[k].firstarc;
G.vertices[k].firstarc=p; } return; }
void FindInDegree(ALGraph G ,int a[MaxVertexNum]) { int i,k;
: \",i); ArcNode *p; for(i=0;i
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{
k = p->adjvex;
a[k] = ++G.vertices[k].indegree;
} } return; }
void TopologicalSort(ALGraph G)
//拓扑排序算法 { int i,j, count; ArcNode *p; SqStack s; int indegree[MaxVertexNum]; for(i=0;i
indegree[i] = 0; FindInDegree(G,indegree); InitStack(s); for(i=0;i
if(!indegree[i])
Push(s,i); } count =0; while(!StackEmpty(s)) {
Pop(s,i);
printf(\"%c \",G.vertices[i].data);
++count;
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{
j = p->adjvex;
if(!(-- indegree[j])) Push(s,j);
} } if(count
printf(\"错误!该有向图有回路!\\n\"); else return; } void main() { ALGraph graph3; CreateALGraph(graph3); printf(\"拓扑排序的结果是 ：\\n\"); TopologicalSort(graph3); printf(\"\\n\"); return; }
