数据结构课件附带经典算法

#include <stdio.h> #include <malloc.h> #define INF 32767 /*INF表示∞*/ typedef int InfoType; typedef char Vertex; #define MAXV 6 /*最大顶点个数*/ /*以下定义邻接矩阵类型*/ typedef struct /*图的定义*/ { InfoType edges[MAXV][MAXV]; /*邻接矩阵*/ int n,e; /*顶点数，弧数*/ Vertex vexs[MAXV]; /*存放顶点信息*/ } MGraph; /*图的邻接矩阵类型*/ /*以下定义邻接表类型*/ typedef struct ANode /*弧的结点结构类型*/ { int adjvex; /*该弧的终点位置*/ struct ANode *nextarc; /*指向下一条弧的指针*/ InfoType info; /*该弧的相关信息,这里用于存放权值*/ } ArcNode; typedef struct Vnode /*邻接表头结点的类型*/ { Vertex data; /*顶点信息*/ ArcNode *firstarc; /*指向第一条弧*/ } VNode; typedef VNode AdjList[MAXV]; /*AdjList是邻接表类型*/ typedef struct { AdjList adjlist; /*邻接表*/ int n,e; /*图中顶点数n和边数e*/ } ALGraph; /*图的邻接表类型*/ typedef struct { char vi,vj; int info; }etype; void MatToList(MGraph g,ALGraph *&G) /*将邻接矩阵g转换成邻接表G*/ { int i,j,n=g.n; ArcNode *p; G=(ALGraph *)malloc(sizeof(ALGraph)); for (i=0;i<n;i++) { G->adjlist[i].firstarc=NULL; G->adjlist[i].data=g.vexs[i]; } for (i=0;i<n;i++) for (j=n-1;j>=0;j--) if (g.edges[i][j]!=INF) { p=(ArcNode *)malloc(sizeof(ArcNode)); p->adjvex=j; p->info=g.edges[i][j]; p->nextarc=G->adjlist[i].firstarc; G->adjlist[i].firstarc=p; } G->n=n;G->e=g.e; } void ListToMat(ALGraph *G,MGraph &g) /*将邻接表G转换成邻接矩阵g*/ { int i,j,n=G->n; ArcNode *p; for(i=0;i<n;i++) for(j=0;j<n;j++) g.edges[i][j]=INF; for (i=0;i<n;i++) { g.vexs[i]=G->adjlist[i].data; p=G->adjlist[i].firstarc; while (p!=NULL) { g.edges[i][p->adjvex]=p->info; p=p->nextarc; } } g.n=n;g.e=G->e; } void DispMat(MGraph g) /*输出邻接矩阵g*/ { int i,j; for (i=0;i<g.n;i++) { for (j=0;j<g.n;j++) if (g.edges[i][j]==INF) printf("%3s","∞"); else printf("%3d",g.edges[i][j]); printf("\n"); } } void DispAdj(ALGraph *G)//不改变G的指向(不进行修改)返回时G仍然指向原来的位置 /*输出邻接表G*/ { int i; ArcNode *p; for (i=0;i<G->n;i++) { p=G->adjlist[i].firstarc; printf("\n%3d %c : ",i,G->adjlist[i].data ); while (p!=NULL) { printf("-->%c(%d)",G->adjlist[p->adjvex].data,p->info); p=p->nextarc; } printf("\n"); } } void creatmat(MGraph &g,char vex[],int n,etype edge[],int e)//无向图，改变G的指向(即进行修改)返回时G指向新的位置 //建立邻接矩阵 { g.n=n;g.e=e; int k,i,j; for(k=0;k<n;k++) g.vexs[k]=vex[k]; for(i=0;i<n;i++) for(j=0;j<n;j++) g.edges[i][j]=INF; for(k=0;k<e;k++) { i=0; while(g.vexs[i]!=edge[k].vi) i++; j=0; while(g.vexs[j]!=edge[k].vj) j++; g.edges[i][j]=g.edges[j][i]=edge[k].info; } } void creatlink(ALGraph *&G,char vex[],int n,etype edge[],int e)//无向图，改变G的指向(即进行修改)返回时G指向新的位置 //建立邻接表 { ArcNode *p; G=(ALGraph *)malloc(sizeof(ALGraph)); G->n=n;G->e=e; int k,i,j; for (i=0;i<n;i++) { G->adjlist[i].firstarc=NULL; G->adjlist[i].data=vex[i]; } for(k=0;k<e;k++) { i=0; while(G->adjlist[i].data !=edge[k].vi) i++; j=0; while(G->adjlist[j].data !=edge[k].vj) j++; p=(ArcNode *)malloc(sizeof(ArcNode)); p->adjvex=j; p->info=edge[k].info; p->nextarc=G->adjlist[i].firstarc; G->adjlist[i].firstarc=p; p=(ArcNode *)malloc(sizeof(ArcNode)); p->adjvex=i; p->info=edge[k].info; p->nextarc=G->adjlist[j].firstarc; G->adjlist[j].firstarc=p; } } char dfsv[10]; char bfsv[10]; int k; int visited[10]; void DFS(ALGraph *G,int v) { ArcNode *p; int w; dfsv[k]=G->adjlist[v].data;k++; visited[v]=1; p=G->adjlist[v].firstarc; while(p!=NULL) { w=p->adjvex; if(visited[w]==0) DFS(G,w); p=p->nextarc; } } void BFS(ALGraph *G,int v) { int q[MAXV],front,rear,i,w; ArcNode *p; front=rear=-1; k=0; bfsv[k++]=G->adjlist[v].data; visited[v]=1; rear++; q[rear]=v; while(front<rear) { front++; i=q[front]; p=G->adjlist[i].firstarc; while(p!=NULL) { w=p->adjvex; if(visited[w]==0) {bfsv[k++]=G->adjlist[w].data; visited[w]=1; rear++;q[rear]=w; } p=p->nextarc; } } } //以下主函数用作调试 void main() { MGraph g,g1; char vex[]="abcdef"; etype edge[]={{'a','b',4}, {'a','e',19}, {'a','f',8}, {'b','c',2},{'b','d',6},{'c','d',3},{'d','e',10},{'d','f',7}}; ALGraph *G,*G1; creatmat(g,vex,6,edge,8); printf("\n"); printf(" 有向图G的邻接矩阵:\n"); DispMat(g); creatlink(G,vex,6,edge,8); printf(" 图G的邻接矩阵转换成邻接表:\n"); DispAdj(G); printf(" 图G的邻接矩阵转换成邻接表:\n"); MatToList(g,G1); DispAdj(G1); printf(" 图G的邻接表转换成邻接邻阵:\n"); ListToMat(G,g1); DispMat(g1); printf("\n"); int i; for(i=0;i<MAXV;i++) visited[i]=0; DFS(G,0); for(i=0;i<MAXV;i++) visited[i]=0; BFS(G,0); }