데이터 구조의 그림 (그림 의 기본 조작)
53128 단어 데이터 구조
1 /*
2 ，
3 */
4 const int UNDIGRAPH = 0; // 5 const int DIGRAPH = 1; // 6 const int MAX_VERTEX_NUM = 20;
7
8 typedef struct ArchNode
9 {
10 int vertexIndex; // ， vertexs[20]
11 ArchNode *nextarc; //
12 InfoTypde info; //
13 }ArchNode;
14
15 typedef struct Vertex
16 {
17 VertexType data; //
18 ArchNode *firstarc; //
19 }Vertex;
20
21 // ， ， ！
22 typedef struct Graph
23 {
24 Vertex *vertexs[MAX_VERTEX_NUM]; // ,
25 int vexNum; //
26 int arcNum; //
27 int kind; // ，
28 }Graph; / / 그림 생 성
1 /*
2 ：kind ， .
3 ： 。--- ，
4 */
5 void createGraph(Graph *&G,int kind)
6 {
7 if(G) G = NULL;
8 G = (Graph *)malloc(sizeof(struct Graph));
9 assert(NULL != G);
10 for(int i = 0; i < MAX_VERTEX_NUM; ++i)
11 {
12 G->vertexs[i] = NULL; // NULL
13 }
14 G->kind = kind; //
15 G->vexNum = 0; //
16 G->arcNum = 0; //
17 }/ / 그림 의 소각
1 /*
2 ：G
3 ： 。--- ，
4 */
5 void destoryGraph(Graph *&G)
6 {
7 ArchNode *cur,*next;
8 if(NULL == G)
9 return;
10 //
11 for(int i = 0; i < G->vexNum; ++i)
12 {
13 if(!G->vertexs[i])
14 continue;
15 next = G->vertexs[i]->firstarc;
16 cur = G->vertexs[i]->firstarc;
17 while(cur)
18 {
19 next = cur->nextarc;
20 free(cur);
21 cur = next;
22 }
23 G->vertexs[i]->firstarc = NULL;
24 }
25 free(G);
26 G = NULL;
27 }/ / 그림 에 노드 추가
1 //
2 /*
3 ：G ，data
4 */
5 void addVertexToGraph(Graph *&G,VertexType data)
6 {
7 if(G->vexNum >= MAX_VERTEX_NUM)
8 {
9 cout << "Too many vertex!" << endl;
10 return ;
11 }
12 for(int i = 0; i < G->vexNum; ++i)
13 {
14 if(!G->vertexs[i])
15 continue;
16 if(G->vertexs[i]->data == data)
17 {
18 cout << "Already exists!" << endl;
19 return; //
20 }
21 }
22 Vertex *pVeterx;
23 pVeterx = (Vertex *)malloc(sizeof(struct Vertex));
24 pVeterx->data = data;
25 pVeterx->firstarc = NULL;
26 G->vertexs[G->vexNum] = pVeterx;
27 G->vexNum++;
28 }/ / 그림 에서 노드 를 삭제 합 니 다.
1 void delVertexFromGraph(Graph *&G,VertexType data)
2 {
3 bool haveThisVertex = false;
4 ArchNode *cur,*next,*temp,*pre;
5 Vertex *anotherVertex;
6 if(NULL == G)
7 return;
8 if(G->vexNum <= 0)
9 {
10 cout << "Have no vertex!" << endl;
11 return ;
12 }
13 for(int i = 0; i < G->vexNum; ++i)
14 {
15 if(!G->vertexs[i])
16 continue;
17 if(G->vertexs[i]->data == data)
18 {
19 haveThisVertex = true;
20 //
21 next = cur = G->vertexs[i]->firstarc;
22 if(G->kind == DIGRAPH) //
23 {
24 while(cur)
25 {
26 next = cur->nextarc;
27 free(cur);
28 G->arcNum --; //
29 cur = next;
30 }
31 G->vertexs[i] = NULL;
32 }
33 else if(G->kind == UNDIGRAPH) // ，
34 {
35 while(cur)
36 {
37 // ，
38 anotherVertex = G->vertexs[cur->vertexIndex]; //
39 temp = anotherVertex->firstarc,pre = NULL;
40 while(temp) //
41 {
42 if(temp->vertexIndex == i)
43 {
44 //
45 if(NULL == pre) // if(NULL == pre)
46 {
47 anotherVertex->firstarc = temp->nextarc;
48 free(temp);
49 }
50 else
51 {
52 pre->nextarc = temp->nextarc;
53 free(temp);
54 }
55 break; //
56 }
57 pre = temp;
58 temp = temp->nextarc;
59 }
60 next = cur->nextarc;
61 free(cur);
62 G->arcNum --; //
63 cur = next;
64 }
65 G->vertexs[i] = NULL;
66 }
67 for(int j = i; j < G->vexNum - 1; ++j)
68 {
69 G->vertexs[j] = G->vertexs[j + 1];
70 }
71 G->vertexs[j] = NULL; //
72 G->vexNum-- ; //
73 break;
74 }
75 }
76 if(!haveThisVertex)
77 cout << " ！" << endl;
78 }// 1 // ：G ，data
2 int findVertexIndexInGraph(const Graph *G,VertexType data)
3 {
4 if(NULL == G)
5 return -1;
6 for(int i = 0; i < G->vexNum; ++i)
7 {
8 if(!G->vertexs[i])
9 continue;
10 if(G->vertexs[i]->data == data)
11 {
12 return i;
13 break;
14 }
15 }
16 return -1;
17 }/ / 그림 에 호 를 추가 합 니 다. 방향 그림 과 방향 없 는 그림 의 구분 이 있 습 니 다.
1 // ：G ， ，
2 void addArchToGraph(Graph *&G,VertexType startData,VertexType endData,InfoTypde weight = 0)
3 {
4 ArchNode *pArchNode,*cur;
5 // start end
6 if(NULL == G)
7 return;
8 int startVertexIndex = findVertexIndexInGraph(G,startData);
9 int endVertexIndex = findVertexIndexInGraph(G,endData);
10 cur = G->vertexs[startVertexIndex]->firstarc;
11 while(cur)
12 {
13 if(cur->vertexIndex == endVertexIndex)
14 {
15 cout << "Already have this arch!" << endl;
16 return ;
17 }
18 cur = cur->nextarc;
19 }
20 if(startVertexIndex >= 0 && endVertexIndex >= 0)
21 {
22 if(G->kind == DIGRAPH) //
23 {
24 pArchNode = (ArchNode *)malloc(sizeof(struct ArchNode)); //
25 pArchNode->info = weight;
26 pArchNode->nextarc = NULL;
27 pArchNode->vertexIndex = endVertexIndex;
28 cur = G->vertexs[startVertexIndex]->firstarc;
29 if(NULL == cur)
30 {
31 G->vertexs[startVertexIndex]->firstarc = pArchNode;
32 }
33 else
34 {
35 while(cur->nextarc)
36 {
37 cur = cur->nextarc;
38 }
39 cur->nextarc = pArchNode;
40 }
41 G->arcNum ++; //
42 }
43 else if(G->kind == UNDIGRAPH) //
44 {
45 pArchNode = (ArchNode *)malloc(sizeof(struct ArchNode)); //
46 pArchNode->info = weight;
47 pArchNode->nextarc = NULL;
48 pArchNode->vertexIndex = endVertexIndex;
49 cur = G->vertexs[startVertexIndex]->firstarc;
50 if(NULL == cur)
51 {
52 G->vertexs[startVertexIndex]->firstarc = pArchNode;
53 }
54 else
55 {
56 while(cur->nextarc)
57 {
58 cur = cur->nextarc;
59 }
60 cur->nextarc = pArchNode;
61 }
62 pArchNode = (ArchNode *)malloc(sizeof(struct ArchNode)); //
63 pArchNode->info = weight;
64 pArchNode->nextarc = NULL;
65 pArchNode->vertexIndex = startVertexIndex;
66 cur = G->vertexs[endVertexIndex]->firstarc;
67 if(NULL == cur)
68 {
69 G->vertexs[endVertexIndex]->firstarc = pArchNode;
70 }
71 else
72 {
73 while(cur->nextarc)
74 {
75 cur = cur->nextarc;
76 }
77 cur->nextarc = pArchNode;
78 }
79 G->arcNum ++; //
80 }
81 }
82 else
83 {
84 cout << " ！" << endl;
85 return ;
86 }
87 }/ / 그림 에서 호 하 나 를 삭제 합 니 다.
1 // ：G ，
2 void delArchFromGraph(Graph *&G,VertexType startData,VertexType endData)
3 {
4 ArchNode *cur,*pre;
5 // start end
6 if(NULL == G)
7 return;
8 int startVertexIndex = findVertexIndexInGraph(G,startData);
9 int endVertexIndex = findVertexIndexInGraph(G,endData);
10 if(startVertexIndex >= 0 && endVertexIndex >= 0)
11 {
12 if(G->kind == DIGRAPH)
13 {
14 cur = G->vertexs[startVertexIndex]->firstarc,pre = NULL;
15 while(cur)
16 {
17 if(cur->vertexIndex == endVertexIndex)
18 {
19 break;
20 }
21 pre = cur;
22 cur = cur->nextarc;
23 }
24 if(NULL == cur)
25 {
26 cout << " ！" << endl;
27 return ;
28 }
29 else
30 {
31 if(NULL == pre) //
32 G->vertexs[startVertexIndex]->firstarc = cur->nextarc;
33 else
34 pre->nextarc = cur->nextarc;
35 free(cur);
36 G->arcNum --;
37 }
38 }
39 else if(G->kind == UNDIGRAPH)
40 {
41 cur = G->vertexs[startVertexIndex]->firstarc,pre = NULL;
42 while(cur)
43 {
44 if(cur->vertexIndex == endVertexIndex)
45 {
46 break;
47 }
48 pre = cur;
49 cur = cur->nextarc;
50 }
51 if(NULL == cur)
52 {
53 cout << " ！" << endl;
54 return ;
55 }
56 else
57 {
58 if(NULL == pre) //
59 G->vertexs[startVertexIndex]->firstarc = cur->nextarc;
60 else
61 pre->nextarc = cur->nextarc;
62 free(cur);
63 //G->arcNum --;
64 }
65
66 cur = G->vertexs[endVertexIndex]->firstarc,pre = NULL;
67 while(cur)
68 {
69 if(cur->vertexIndex == startVertexIndex)
70 {
71 break;
72 }
73 pre = cur;
74 cur = cur->nextarc;
75 }
76 if(NULL == cur)
77 {
78 cout << " ！" << endl;
79 return ;
80 }
81 else
82 {
83 if(NULL == pre) //
84 G->vertexs[endVertexIndex]->firstarc = cur->nextarc;
85 else
86 pre->nextarc = cur->nextarc;
87 free(cur);
88 G->arcNum --;
89 }
90 }
91 }
92 else
93 {
94 cout << " ！" << endl;
95 return ;
96 }
97 }/ / 깊이 우선
1 // ： G
2 void DFSdetails(const Graph *G,int i,int satusArr[])
3 {
4 ArchNode *cur;
5 if(satusArr[i] == 1 )
6 return;
7 cout << G->vertexs[i]->data << " ";
8 satusArr[i] = 1;
9 cur = G->vertexs[i]->firstarc;
10 while(cur)
11 {
12 DFSdetails(G,cur->vertexIndex,satusArr);
13 cur = cur->nextarc;
14 }
15 }
16
17 void DFS(const Graph *G)
18 {
19 int satusArr[MAX_VERTEX_NUM] = {0};
20 cout << " ：";
21 if(NULL == G)
22 return;
23 for(int i = 0; i < G->vexNum; ++i)
24 {
25 DFSdetails(G,i,satusArr);
26 }
27 cout << endl;
28 }좋은 웹페이지 즐겨찾기
