92芦荟胶怎么用:一步一步写算法（之图添加和删除）

【 声明：版权所有，欢迎转载，请勿用于商业用途。 联系信箱：feixiaoxing @163.com】

前面我们谈到的图的数据结构、图的创建，今天我们就来说一说如何在图中添加和删除边。边的添加和删除并不复杂，但是关键有一点需要记住，那就是一定要在小函数的基础之上构建大函数，否则很容易出现错误。

一、边的创建

边的创建一般来说可以分为下面以下几个步骤：

1）判断当前图中是否有节点，如果没有，那么在pGraph->head处添加一条边即可

2）如果当前图中有节点，那么判断节点中有没有以start点开头的，如果没有创建一个顶点和边，并插入图的head处

3）在当前有节点start中，判断是否end的边已经存在。如果end边存在，返回出错；否则在pVectex->neighbour处添加一条边

4）添加的过程中注意点的个数和边的个数处理

view plaincopy to clipboardprint?

1. STATUS insert_vectex_into_graph(GRAPH* pGraph, int start, int end, int weight)
2. {
3. VECTEX* pVectex;
4. LINE* pLine;
6. if(NULL == pGraph)
7. return FALSE;
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. }
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. }
26. pLine = find_line_in_graph(pVectex->neighbor, end);
27. if(NULL != pLine)
28. return FALSE;
30. pLine = create_new_line(end, weight);
31. pLine->next = pVectex->neighbor;
32. pVectex->neighbor = pLine;
33. pVectex->number ++;
34. return TRUE;
35. }

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

view plaincopy to clipboardprint?

1. STATUS delete_old_vectex(VECTEX** ppVectex, int start)
2. {
3. VECTEX* pVectex;
4. VECTEX* prev;
6. if(NULL == ppVectex || NULL == *ppVectex)
7. return FALSE;
9. pVectex = find_vectex_in_graph(*ppVectex, start);
10. if(NULL == pVectex)
11. return FALSE;
13. if(pVectex == *ppVectex){
14. *ppVectex = pVectex->next;
15. free(pVectex);
16. return TRUE;
17. }
19. prev = *ppVectex;
20. while(pVectex != prev->next)
21. prev = prev->next;
23. prev->next = pVectex->next;
24. free(pVectex);
25. return TRUE;
26. }
28. STATUS delete_old_line(LINE** ppLine, int end)
29. {
30. LINE* pLine;
31. LINE* prev;
33. if(NULL == ppLine || NULL == *ppLine)
34. return FALSE;
36. pLine = find_line_in_graph(*ppLine, end);
37. if(NULL == pLine)
38. return FALSE;
40. if(pLine == *ppLine){
41. *ppLine = pLine->next;
42. free(pLine);
43. return TRUE;
44. }
46. prev = *ppLine;
47. while(pLine != prev->next)
48. prev = prev->next;
50. prev->next = pLine->next;
51. free(pLine);
52. return TRUE;
53. }

一般来说，边的删除和边的添加是可逆的，过程如下所示：

1）判断图中是否有节点存在，如果没有，返回出错

2）判断图中节点start是否存在，如果不存在，返回出错

3）判断节点start中是否end边存在，如果不存在，返回出错

4）删除对应的边

5）判断该节点的边计数number是否为0，如果为0，继续删除节点

6）删除过程中注意边和顶点的个数处理

view plaincopy to clipboardprint?

1. STATUS delete_vectex_from_graph(GRAPH* pGraph, int start, int end, int weight)
2. {
3. VECTEX* pVectex;
4. LINE* pLine;
5. STATUS result;
7. if(NULL == pGraph || NULL == pGraph->head)
8. return FALSE;
10. pVectex = find_vectex_in_graph(pGraph->head, start);
11. if(NULL == pVectex)
12. return FALSE;
14. pLine = find_line_in_graph(pVectex->neighbor, end);
15. if(NULL != pLine)
16. return FALSE;
18. result = delete_old_line(&pVectex->neighbor, end);
19. assert(TRUE == result);
20. pVectex->number --;
22. if(0 == pVectex->number)
23. result = delete_old_vectex(&pGraph->head, start);
25. assert(TRUE == result);
26. pGraph->count --;
27. return TRUE;
28. }

（1）注意写小函数，再复杂的功能都是有无数的小功能构建的，函数最好不要超过50行

（2）老规矩，代码务必要测试