数据结构（栈、队列、二叉树、顺序查找、二分查找、图的遍历等）

#include"string.h" #include"malloc.h" /* malloc()等 */ #include"stdio.h" /* EOF(=^Z或F6),NULL */ #include"process.h" /* exit() */ typedef int InfoType; /* 顶点权值类型 */ #define MAX_NAME 3 /* 顶点字符串的最大长度+1 */ typedef char VertexType[MAX_NAME]; /* 字符串类型 */ /*图的邻接表存储表示 */ #define MAX_VERTEX_NUM 20 typedef enum{DG,DN,AG,AN}GraphKind; /* {有向图,有向网,无向图,无向网} */ typedef struct ArcNode { int adjvex; /* 该弧所指向的顶点的位置 */ struct ArcNode *nextarc; /* 指向下一条弧的指针 */ InfoType *info; /* 网的权值指针） */ }ArcNode; /* 表结点 */ typedef struct { VertexType data; /* 顶点信息 */ ArcNode *firstarc; /* 第一个表结点的地址,指向第一条依附该顶点的弧的指针 */ }VNode,AdjList[MAX_VERTEX_NUM]; /* 头结点 */ typedef struct { AdjList vertices; int vexnum,arcnum; /* 图的当前顶点数和弧数 */ int kind; /* 图的种类标志 */ }ALGraph; int LocateVex(ALGraph G,VertexType u) { /* 初始条件: 图G存在,u和G中顶点有相同特征 */ /* 操作结果: 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */ int i; for(i=0;i<G.vexnum;i++) if(strcmp(u,G.vertices[i].data)==0) return i; return -1; } void CreateGraph(ALGraph *G) { /* 采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造4种图) */ int i,j,k; int w; /* 权值 */ VertexType va,vb; ArcNode *p; //printf("Enter the type of map:(0~3): "); scanf("%d",&(*G).kind); //printf("Enter Vertex number,Arc number: "); scanf("%d %d",&(*G).vexnum,&(*G).arcnum); //printf("Enter %d Vertex :\n",(*G).vexnum); for(i=0;i<(*G).vexnum;++i) /* 构造顶点向量 */ { scanf("%s",(*G).vertices[i].data); (*G).vertices[i].firstarc=NULL; } //if((*G).kind==1||(*G).kind==3) /* 网 */ //printf("Enter order every arc weight,head and tail (Takes the gap by the blank space ):\n"); //else /* 图 */ //printf("Enter order every arc head and tail (Takes the gap by the blank space ):\n"); for(k=0;k<(*G).arcnum;++k) /* 构造表结点链表 */ { if((*G).kind==1||(*G).kind==3) /* 网 */ scanf("%d%s%s",&w,va,vb); else /* 图 */ scanf("%s%s",va,vb); i=LocateVex(*G,va); /* 弧尾 */ j=LocateVex(*G,vb); /* 弧头 */ p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=j; if((*G).kind==1||(*G).kind==3) /* 网 */ { p->info=(int *)malloc(sizeof(int)); *(p->info)=w; } else p->info=NULL; /* 图 */ p->nextarc=(*G).vertices[i].firstarc; /* 插在表头 */ (*G).vertices[i].firstarc=p; if((*G).kind>=2) /* 无向图或网,产生第二个表结点 */ { p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=i; if((*G).kind==3) /* 无向网 */ { p->info=(int*)malloc(sizeof(int)); *(p->info)=w; } else p->info=NULL; /* 无向图 */ p->nextarc=(*G).vertices[j].firstarc; /* 插在表头 */ (*G).vertices[j].firstarc=p; } } } VertexType* GetVex(ALGraph G,int v) { /* 初始条件: 图G存在,v是G中某个顶点的序号。操作结果: 返回v的值 */ if(v>=G.vexnum||v<0) exit(0); return &G.vertices[v].data; } int FirstAdjVex(ALGraph G,VertexType v) { /* 初始条件: 图G存在,v是G中某个顶点 */ /* 操作结果: 返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1 */ ArcNode *p; int v1; v1=LocateVex(G,v); /* v1为顶点v在图G中的序号 */ p=G.vertices[v1].firstarc; if(p) return p->adjvex; else return -1; } int NextAdjVex(ALGraph G,VertexType v,VertexType w) { /* 初始条件: 图G存在,v是G中某个顶点,w是v的邻接顶点 */ /* 操作结果: 返回v的(相对于w的)下一个邻接顶点的序号。 */ /* 若w是v的最后一个邻接点,则返回-1 */ ArcNode *p; int v1,w1; v1=LocateVex(G,v); /* v1为顶点v在图G中的序号 */ w1=LocateVex(G,w); /* w1为顶点w在图G中的序号 */ p=G.vertices[v1].firstarc; while(p&&p->adjvex!=w1) /* 指针p不空且所指表结点不是w */ p=p->nextarc; if(!p||!p->nextarc) /* 没找到w或w是最后一个邻接点 */ return -1; else /* p->adjvex==w */ return p->nextarc->adjvex; /* 返回v的(相对于w的)下一个邻接顶点的序号 */ } /*广度遍历*/ int visited[MAX_VERTEX_NUM]; /* 访问标志数组(全局量),未访问标记0，访问标记1 */ void(*VisitFunc)(char* v); /* 函数变量(全局量) */ typedef int QElemType; /* 队列类型 */ #define MAXSIZE 20 //#include"c1.h" /*基本类型定义头文件*/ //#include"c3-2.h" /*队列存储结构定义*/ //#include"bo3-2.c" /*队列基本函数实现*/ typedef struct{ QElemType *base; QElemType head; QElemType last; int isful; int size; }LinkQueue; void InitQueue(LinkQueue &Q){ Q.base = (QElemType *)malloc(MAXSIZE * sizeof(QElemType)); Q.head = 0; Q.last = 0; Q.isful = 0; Q.size = MAXSIZE; } QElemType getHead(LinkQueue &Q){ if(Q.head == Q.last && Q.isful == 0) return -1; return Q.head; } QElemType OutQueue(LinkQueue &Q){ if(Q.head == Q.last && Q.isful == 0) { printf("队列为空"); return -1; } Q.head = (Q.head+1)%Q.size; if(Q.isful == 1)//这行可有可无 Q.isful = 0; return (Q.head+Q.size-1)%Q.size; } int EnQueue(LinkQueue &Q , QElemType e){ if(Q.head == Q.last && Q.isful == 1) { printf("队列已满"); return -1; } Q.base[Q.last++] = e; if(Q.head == Q.last && Q.isful == 0) Q.isful = 1; return 1; } void print(char *i){ printf("%s " , i); } void BFSTraverse(ALGraph G,void(*Visit)(char*)) {/*按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited。算法7.6 */ int v,u,w; VertexType u1,w1; LinkQueue Q; for(v=0;v<G.vexnum;v++) visited[v]=0; /* 置初值 */ InitQueue(Q); /* 置空的辅助队列Q */ for(v=0;v<G.vexnum ; v++) if(!visited[v]) /* v尚未访问 */ { visited[v] = 1; Visit(G.vertices[v].data); EnQueue(Q , v);//入队 while(getHead(Q) != -1){//队列不为空 u = OutQueue(Q);//队头出队 strcpy(u1 , *GetVex(G, u)); for(w = FirstAdjVex(G,u1) ; w>=0 ; w = NextAdjVex(G , u1 , strcpy(w1 , *GetVex(G, w)))) if(!visited[w])//w为u的尚未访问的邻接顶点 { visited[w] = 1; Visit(G.vertices[w].data); EnQueue(Q, w);//入队 } } } printf("\n"); } int main() { ALGraph g; CreateGraph(&g); //printf("Below are the results of the depth of traversing:\n"); BFSTraverse(g,print); return 1; }