C语言，C语言数据结构代码实例

#include <iostream.h> #include "stdlib.h" #define MAXN 50 typedef struct ArcNode{ int adjvex; struct ArcNode *nextarc; int info; }ArcNode; //边结点类型 typedef struct VNode{ char data; ArcNode *firstarc; }VNode,AdjList[MAXN]; typedef struct{ AdjList vertices; //邻接表 int vexnum,arcnum; }ALGraph; //查找顶点u的序号 int LocateVex(ALGraph G,char u) { int i; for (i=0;i<G.vexnum;i++) { if(u==G.vertices[i].data) return i; } if (i==G.vexnum) {cout<<"Error u!\n";exit(1);} return 0; } //建立无向网的邻接邻接表 void CreateUDG(ALGraph &G) { int i,j,k,w; char v1,v2; ArcNode *p; cout<<"输入无向网的顶点数和边数:vexnum & arcnum:"; cin>>G.vexnum>>G.arcnum; cout<<"输入顶点:"; for (i=0;i<G.vexnum;i++) { cin>>G.vertices[i].data; G.vertices[i].firstarc=NULL; } cout<<"Input Arcs(v1,v2 & w): "; for (k=0;k<G.arcnum;k++) { cin>>v1>>v2>>w; i=LocateVex(G,v1); j=LocateVex(G,v2); p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=j; p->info = w; p->nextarc=G.vertices[i].firstarc; G.vertices[i].firstarc=p; p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=i; p->info = w; p->nextarc=G.vertices[j].firstarc; G.vertices[j].firstarc=p; } } //建立有向网的邻接表 void CreateDG(ALGraph &G) { int i,j,k,w; char v1,v2; ArcNode *p; cout<<"请输入有向网的顶点数和弧数vexnum & arcnum:"; cin>>G.vexnum>>G.arcnum; cout<<"输入顶点Vertices:"; for (i=0;i<G.vexnum;i++) { cin>>G.vertices[i].data; G.vertices[i].firstarc=NULL; } cout<<"Input Arcs(v1,v2 & w): "; for (k=0;k<G.arcnum;k++) { cin>>v1>>v2>>w; i=LocateVex(G,v1); j=LocateVex(G,v2); p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=j; p->info = w; p->nextarc=G.vertices[i].firstarc; G.vertices[i].firstarc=p; } } //输出图的邻接表的存储结构 void printG(ALGraph G) {int i;ArcNode *p; cout<<"图的邻接表是："<<endl; for(i=0;i<G.vexnum;i++) {cout<<i<<" "<<G.vertices[i].data<<" "; p=G.vertices[i].firstarc; while(p!=0) {cout<<"->"<<p->adjvex<<" "<<p->info;p=p->nextarc;} cout<<endl; } } int visited[MAXN];//全局变量 //从第v个顶点出发DFS //深度优先搜索 void DFS(ALGraph G, int v) { ArcNode *p; cout<<G.vertices[v].data; visited[v]=1; p=G.vertices[v].firstarc; while (p) {if (!visited[p->adjvex]) DFS(G,p->adjvex); p=p->nextarc; } } //深度优先遍历图中所有顶点 void DFSTraverse(ALGraph G){ for (int v=0;v<G.vexnum;++v) visited[v]=0; for (v=0;v<G.vexnum;++v) if (!visited[v]) DFS(G,v); cout<<endl; } //广度优先遍历，从顶点v出发BFS void BFS(ALGraph G,int v) { ArcNode *p; int qu[MAXN],front,rear; front=rear=0; cout<<G.vertices[v].data; visited[v]=1; rear=(rear+1)%MAXN; qu[rear]=v; while (front!=rear) { front=(front+1)%MAXN; v=qu[front]; p=G.vertices[v].firstarc; while (p) { if (!visited[p->adjvex]) {cout<<G.vertices[p->adjvex].data; visited[p->adjvex]=1; rear=(rear+1)%MAXN; qu[rear]=p->adjvex; } p=p->nextarc; } } } //广度优先遍历图中所有顶点 void BFSTraverse(ALGraph G){ for (int v=0;v<G.vexnum;++v) visited[v]=0; cout<<"广度优先遍历序列为："<<endl; for (v=0;v<G.vexnum;++v) if (!visited[v]) BFS(G,v); } //求有向网各顶点的出度 void chudu(ALGraph G) {int i; int du[100]; ArcNode *p; for(i=0;i<G.vexnum;i++) du[i]=0; for(i=0;i<G.vexnum;i++) { p=G.vertices[i].firstarc; while(p!=0) {du[i]++; p=p->nextarc; } } cout<<"有向网中各顶点的出度是："<<endl; for(int k=0;k<G.vexnum;k++) cout<<G.vertices[k].data<<"的出度是："<<du[k]<<endl; } int rudu[100]; //求有向网各顶点入度 void rdu(ALGraph G) {int i; ArcNode *p; for(i=0;i<G.vexnum;i++) rudu[i]=0; for(i=0;i<G.vexnum;i++) { p=G.vertices[i].firstarc; while(p!=0) {rudu[p->adjvex]++; p=p->nextarc; } } cout<<"有向网中各顶点的入度是："<<endl; for(int k=0;k<G.vexnum;k++) cout<<G.vertices[k].data<<"的入度是："<<rudu[k]<<endl; } //拓扑排序 int topsort(ALGraph G) { rdu(G); int stack[30],top=-1; int count,j,k; ArcNode *p; for(int i=0;i<G.vexnum;i++) if(rudu[i]==0) stack[++top]=i; count=0; while(top!=-1) { j=stack[top--]; cout<<j<<" "<<G.vertices[j].data<<endl; ++count; for(p=G.vertices[j].firstarc;p;p=p->nextarc) {k=p->adjvex; if(--rudu[k]==0) stack[++top]=k; } } if(count<G.vexnum) return -1; else return 1; } //求有向网中各顶点的度 void du(ALGraph G) {int i; int du[100]; ArcNode *p; for(i=0;i<G.vexnum;i++) du[i]=0; for(i=0;i<G.vexnum;i++) {p=G.vertices[i].firstarc; while(p!=0) {du[p->adjvex]++;du[i]++; p=p->nextarc; } } cout<<"有向网中各顶点的度是："<<endl; cout<<"顶点"<<" 度"<<endl; for(int k=0;k<G.vexnum;k++) cout<<G.vertices[k].data<<" "<<du[k]<<endl; } //遍历算法的应用 //试写一算法，判别有向图中是否存在由顶点i到顶点j的路径(i!=j)，分别用深度和广度优先搜索 //1.深度方法1 int tag[MAXN]; int pathexist(ALGraph G,int i,int j) {ArcNode *p; int k; if(i==j) return 1; else { tag[i]=1; for(p=G.vertices[i].firstarc;p;p=p->nextarc) { k=p->adjvex; if(tag[k]==0&& pathexist(G,k,j)) return 1; } } return 0; } //深度方法2 int ispath(ALGraph G,int i,int j) { int k; for(k=0;k<G.vexnum;k++) visited[k]=0; DFS(G,i); if(visited[j]==1) return 1; else return 0; } //2.基于广度 int pathBFS(ALGraph G,int i,int j) { ArcNode *p; int qu[MAXN],front,rear,k,u; front=rear=0; rear=(rear+1)%MAXN; qu[rear]=i; while (front!=rear) { front=(front+1)%MAXN; k=qu[front]; qu[rear]=k; tag[k]=1; for(p=G.vertices[k].firstarc;p;p=p->nextarc) { u=p->adjvex; if(u==j) return 1; if(tag[u]==0) { rear=(rear+1)%MAXN; qu[rear]=u; } } } return 0; } //假设G采用邻接表存储，设计一个算法，判断无向图G是否连通 int connect(ALGraph G) { int i,flag=1; for(i=0;i<G.vexnum;i++) visited[i]=0; DFS(G, 0); for(i=0;i<G.vexnum;i++) if(visited[i]==0) {flag=0; break; } return flag; } void main() { ALGraph G1; //CreateUDG(G1); //printG(G1); CreateDG(G1); printG(G1); //BFSTraverse(G1); //rudu(G1); //chudu(G1); topsort(G1);cout<<endl; BFSTraverse(G1);cout<<endl; DFSTraverse(G1); if(pathBFS(G1,0,3)) cout<<"exit"<<endl; else cout<<"no"; if (pathexist(G1,0,5)) cout<<"exit"<<endl; else cout<<"no"; }