数据结构(广度和深度优先遍历).doc

#include #include #include typedef struct GNodeint weight;int nIndex;struct GNode *next; * GList;struct GArraychar name5;GList next;typedef struct QNodeGArray * data;QNode * next;QNode, *QueuePtr;typedef structQueuePtr front;QueuePtr rear;LinkQueue;bool InitQueue(LinkQueue &Q)Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode);if(!Q.rear)exit(0);Q.front-next = NULL;return true;void DestroyQueue(LinkQueue &Q)while(Q.front)Q.rear = Q.front-next;free(Q.front);Q.front = Q.rear;bool EmptyQueue(LinkQueue &Q)if(Q.front = Q.rear)return true;elsereturn false;bool EnQueue(LinkQueue &Q, GArray * gl)QueuePtr p;p = (QueuePtr)malloc(sizeof(QNode);if(!p)exit(0); p-data = gl; p-next = NULL; Q.rear-next = p; Q.rear = p; return true;bool DeQueue(LinkQueue &Q, GArray *&gl)if(Q.front = Q.rear)return false;QueuePtr p;p = Q.front-next;gl = p-data;Q.front-next = p-next;if(Q.rear = p)Q.rear = Q.front;free(p);return true;void CreateG(GArray *GArr, int *arr, int n)for(int i = 0; i n; i+)GArri.next = NULL;char S20;if(i / 10 = 0)S0 = v;S1 = i + 0 + 1;S2 = 0;elseS0 = v;S1 = i / 10 + 1;S2 = i % 10 + 1 + 0;/ 顶点信息strcpy(GA, S);for(int j = 0; j weight = arrij;p-nIndex = j;p-next = GArri.next;GArri.next = p;void BFSTree(GArray *GArr, int n)bool * Visited;Visited = (bool *)malloc(n * sizeof(bool);if(!Visited)exit(0);for(int i = 0; i n; i+)Visitedi = false;LinkQueue Q;InitQueue(Q); / 初始化队列for(int i = 0; i next; pL; pL = pL-next)if(!VisitedpL-nIndex)VisitedpL-nIndex = true;printf(%s , GArrpL-nI);EnQueue(Q, &GArrpL-nIndex);/ 压入其临界点free(Visited);DestroyQueue(Q);void main()int n;scanf(%d, &n);int *array;GArray *GArr;array = (int *)malloc(sizeof(int *)*n);for(int i = 0; i n; i+)arrayi = (int *)malloc(sizeof(int) * n);GArr = (GArray *)malloc(sizeof(GArray) * n);for(int i = 0; i n; i+)for(int j = 0; j n; j+)scanf(%d, &arrayij);CreateG(GArr, array, n);BFSTree(GArr, n);/ 释放二维数组空间for(int i = 0; i n; i+)free(arrayi);free(array);/ 释放临界表存储空间for(int i = 0; i next;free(p1);/ 释放临界表数组free(GArr);#include #include #include typedef struct GNodeint weight;int nIndex;GNode * next; *GList;struct GArraychar name4;GList next;void InPut(int *array, int n)for(int i = 0; i n; i+)for(int j = 0; j n; j+)scanf(%d, &arrayij);void CreateG(GArray *GArr, int *array, int n)for(int i = 0; i n; i+)GArri.next = NULL;char s20;s0 = v;if(i / 10 = 0)s1 = i % 10+1 + 0;s2 = 0;elses1 = i / 10 + 0;s2 = i % 10+1 + 0;s3 = 0;strcpy(GA, s);for(int j = 0; j weight = arrayij;p-next = GArri.next;p-nIndex = j;GArri.next = p;/ 深度优先遍历void DFS(GArray *GArr, int i, int n, bool *Visited)Visitedi = true;printf(%s , GA);GList p;for(p = GArri.next; p; p = p-next)if(!Visitedp-nIndex)DFS(GArr, p-nIndex, n, Visited);void DFSTree(GArray *GArr, int n)bool *Visited;Visited = (bool *)malloc(sizeof(bool) * n);for(int i = 0; i n; i+)Visitedi = false;for(i = 0; i n; i+)if(!Visitedi) DFS(GArr, i, n, Visited);free(Visited);void main()int n;scanf(%d, &n);int *array;array = (int *)malloc(sizeof(int*)*n);for(int i = 0; i n; i+)arrayi = (int *)mal