绣春刀.修罗战场 mp4:一步一步写算法（之prim算法 下）

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

前两篇博客我们讨论了prim最小生成树的算法，熟悉了基本的流程。基本上来说，我们是按照自上而下的顺序来编写代码的。首先我们搭建一个架构，然后一步一步完成其中的每一个子功能，这样最后构成一个完成prim算法计算过程。

f）将DIR_LINE队列中不符合的数据删除，主要是双节点都已经访问过的DIR_LINE数据。

view plaincopy to clipboardprint?

1. void delete_unvalid_line_from_list(DIR_LINE** ppHead, MINI_GENERATE_TREE* pMiniTree)
2. {
3. DIR_LINE* prev;
4. DIR_LINE* pcur;
5. STATUS result;
7. prev = NULL;
8. pcur = *ppHead;
9. while(pcur){
10. if(!check_valid_for_line(pcur, pMiniTree)){
11. result = delete_line_from_queue(ppHead, pcur);
12. assert(TRUE == result);
14. if(NULL == prev)
15. pcur = *ppHead;
16. else
17. pcur = prev->next;
19. continue;
20. }
22. prev = pcur;
23. pcur = pcur->next;
24. }
26. return;
27. }

view plaincopy to clipboardprint?

1. int check_valid_for_line(DIR_LINE* pDirLine, MINI_GENERATE_TREE* pMiniTree)
2. {
3. int index;
4. int flag_start;
5. int flag_end;
7. flag_start = 0;
8. flag_end = 0;
10. for(index = 0; index < pMiniTree->node_num; index ++){
11. if(pDirLine->start == pMiniTree->pNode[index]){
12. flag_start = 1;
13. break;
14. }
15. }
17. for(index = 0; index < pMiniTree->node_num; index ++){
18. if(pDirLine->end == pMiniTree->pNode[index]){
19. flag_end = 1;
20. break;
21. }
22. }
24. return (1 == flag_start && 1 == flag_end) ? 0 : 1;
25. }

view plaincopy to clipboardprint?

1. void insert_for_sort_operation(DIR_LINE** ppNode, DIR_LINE* pNode)
2. {
3. DIR_LINE* prev;
4. DIR_LINE* cur;
6. /* 在第一个数据之前插入pNode */
7. if(pNode->weight < (*ppNode)->weight){
8. pNode->next = *ppNode;
9. *ppNode = pNode;
10. return;
11. }
13. cur = *ppNode;
14. while(cur){
15. if(pNode->weight < cur->weight)
16. break;
18. prev = cur;
19. cur = cur->next;
20. }
22. pNode->next = prev->next;
23. prev->next = pNode;
24. return;
25. }
27. void sort_for_line_list(DIR_LINE** ppNode)
28. {
29. DIR_LINE* prev;
30. DIR_LINE* curr;
32. if(NULL == ppNode || NULL == *ppNode)
33. return;
35. curr = (*ppNode) ->next;
36. (*ppNode) ->next = NULL;
38. while(curr){
39. prev = curr;
40. curr = curr->next;
41. insert_for_sort_operation(ppNode, prev);
42. }
43. }

算法总结：

1）算法本身还有改进的空间，比如是不是内存分配上每一次都要重建DIR_LINE队列有待商榷

2）算法编写不是一部就位的，中间有反复更有删改，写四五次是很正常的事情

3）编写代码的时候最好做到边修改、边测试，这样可以一方面增加代码的健壮度，一方面还能提高自己的信心

4）如果存在可能，可以复用以前写过的、稳定的算法代码，比如说排序、查找、堆栈、二叉树之类的代码