一步一步写算法(之图添加及删除).doc

软件英才网 软件行业驰名招聘网站
一步一步写算法（之图添加和删除）
前面我们谈到的图的数据结构、图的创建，今天我们就来说一说如何在图中添加和删除边。边的添加和删除并不复杂，但是关键有一点需要记住，那就是一定要在小函数的基础之上构建大函数，否则很容易出现错误。

一、边的创建
边的创建一般来说可以分为下面以下几个步骤：
1）判断当前图中是否有节点，如果没有，那么在pGraph->head处添加一条边即可
2）如果当前图中有节点，那么判断节点中有没有以start点开头的，如果没有创建一个顶点和边，并插入图的head处
3）在当前有节点start中，判断是否end的边已经存在。如果end边存在，返回出错；否则在pVectex->neighbour处添加一条边
4）添加的过程中注意点的个数和边的个数处理
[cpp] view plaincopy

1 STATUS insert_vectex_into_graph(GRAPH* pGraph, int start, int end, int weight)
2 {
3 VECTEX* pVectex;
4 LINE* pLine;
5
6 if(NULL == pGraph)
7 return FALSE;
8
9 if(NULL == pGraph->head){
10 pGraph->head = create_new_vectex_for_graph(start, end, weight);
11 pGraph->head->number ++;
12 pGraph->count ++;
13 return TRUE;
14 }
15
16 pVectex = find_vectex_in_graph(pGraph->head, start);
17 if(NULL == pVectex){
18 pVectex = create_new_vectex_for_graph(start, end, weight);
19 pVectex->next = pGraph->head;
20 pGraph->head = pVectex;
21 pGraph->head->number ++;
22 pGraph->count ++;
23 return TRUE;
24 }
25
26 pLine = find_line_in_graph(pVectex->neighbor, end);
27 if(NULL != pLine)
28 return FALSE;
29
30 pLine = create_new_line(end, weight);
31 pLine->next = pVectex->neighbor;
32 pVectex->neighbor = pLine;
33 pVectex->number ++;
34 return TRUE;
35 }

二、边的删除 在进行边的删除之前，我们需要对链表子节点进行处理，构建delete小函数，这样可以在边删除函数中使用。
[cpp] view plaincopy

36 STATUS delete_old_vectex(VECTEX** ppVectex, int start)
37 {
38 VECTEX* pVectex;
39 VECTEX* prev;
40
41 if(NULL == ppVectex || NULL == *ppVectex)
42 return FALSE;
43
44 pVectex = find_vectex_in_graph(*ppVectex, start);
45 if(NULL == pVectex)
46 return FALSE;
47
48 if(pVectex == *ppVectex){
49 *ppVectex = pVectex->next;
50 free(pVectex);
51 return TRUE;
52 }
53
54 prev = *ppVectex;
55 while(pVectex != prev->next)
56 prev = prev->next;
57
58 prev->next = pVectex->next;
59 free(pVectex);
60 return TRUE;
61 }
62
63 STATUS delete_old_line(LINE** ppLine, int end)
64 {
65 LINE* pLine;
66 LINE* prev;
67
68 if(NULL == ppLine || NULL == *ppLine)
69 return FALSE;
70
71 pLine = find_line_in_graph(*ppLine, end);
72 if(NULL == pLine)
73 return FALSE;
74
75 if(pLine == *ppLine){
76 *ppLine = pLine->next;
77 free(pLine);
78 return TRUE;
79 }
80
81 prev = *ppLine;
82 while(pLine != prev->next)
83 prev = prev->next;
84
85 prev->next = pLine->next;
86 free(pLine);
87 return TRUE;
88 }

一般来说，边的删除和边的添加是可逆的，过程如下所示：
1）判断图中是否有节点存在，如果没有，返回出错
2）判断图中节点start是否存在，如果不存在，返回出错
3）判断节点start中是否end边存在，如果不存在，返回出错
4）删除对应的边
5）判断该节点的边计数number是否为0，如果为0，继续删除节点
6）删除过程中注意边和顶点的个数处理
[cpp] view plaincopy

89 STATUS delete_vectex_from_graph(GRAPH* pGraph, int start, int end, int weight)
90 {
91 VECTEX* pVectex;
92 LINE* pLine;
93 STATUS result;
94
95 if(NULL == pGraph || NULL == pGraph->head)
96 return FALSE;
97
98 pVectex = find_vectex_in_graph(pGraph->head, start);
99 if(NULL == pVectex)
100 return FALSE;
101
102 pLine = find_line_in_graph(pVectex->neighbor, end);
103 if(NULL != pLine)
104 return FALSE;
105
106 result = delete_old_line(&pVectex->neighbor, end);
107 assert(TRUE == result);
108 pVectex->number --;
109
110 if(0 == pVectex->number)
111 result = delete_old_vectex(&pGraph->head, start);
112
113 assert(TRUE == result);
114 pGraph->count --;
115 return TRUE;
116 }

注意事项： （1）注意写小函数，再复杂的功能都是有无数的小功能构建的，函数最好不要超过50行
（2）老规矩，代码务必要测试

有需要请联系我们