首页 > 代码库 > 一步一步写算法(之prim算法 下)
一步一步写算法(之prim算法 下)
原文: 一步一步写算法(之prim算法 下)
g) 在f)函数中使用了判定DIR_LINE合法性的函数,我们需要完善一下。
h) 最后就是对当前已经入队的DIR_LINE数据排序,其实就是链表排序。
【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing @163.com】
前两篇博客我们讨论了prim最小生成树的算法,熟悉了基本的流程。基本上来说,我们是按照自上而下的顺序来编写代码的。首先我们搭建一个架构,然后一步一步完成其中的每一个子功能,这样最后构成一个完成prim算法计算过程。
f)将DIR_LINE队列中不符合的数据删除,主要是双节点都已经访问过的DIR_LINE数据。
void delete_unvalid_line_from_list(DIR_LINE** ppHead, MINI_GENERATE_TREE* pMiniTree){ DIR_LINE* prev; DIR_LINE* pcur; STATUS result; prev = NULL; pcur = *ppHead; while(pcur){ if(!check_valid_for_line(pcur, pMiniTree)){ result = delete_line_from_queue(ppHead, pcur); assert(TRUE == result); if(NULL == prev) pcur = *ppHead; else pcur = prev->next; continue; } prev = pcur; pcur = pcur->next; } return;}
g) 在f)函数中使用了判定DIR_LINE合法性的函数,我们需要完善一下。
int check_valid_for_line(DIR_LINE* pDirLine, MINI_GENERATE_TREE* pMiniTree){ int index; int flag_start; int flag_end; flag_start = 0; flag_end = 0; for(index = 0; index < pMiniTree->node_num; index ++){ if(pDirLine->start == pMiniTree->pNode[index]){ flag_start = 1; break; } } for(index = 0; index < pMiniTree->node_num; index ++){ if(pDirLine->end == pMiniTree->pNode[index]){ flag_end = 1; break; } } return (1 == flag_start && 1 == flag_end) ? 0 : 1;}
h) 最后就是对当前已经入队的DIR_LINE数据排序,其实就是链表排序。
void insert_for_sort_operation(DIR_LINE** ppNode, DIR_LINE* pNode) { DIR_LINE* prev; DIR_LINE* cur; /* 在第一个数据之前插入pNode */ if(pNode->weight < (*ppNode)->weight){ pNode->next = *ppNode; *ppNode = pNode; return; } cur = *ppNode; while(cur){ if(pNode->weight < cur->weight) break; prev = cur; cur = cur->next; } pNode->next = prev->next; prev->next = pNode; return; } void sort_for_line_list(DIR_LINE** ppNode){ DIR_LINE* prev; DIR_LINE* curr; if(NULL == ppNode || NULL == *ppNode) return; curr = (*ppNode) ->next; (*ppNode) ->next = NULL; while(curr){ prev = curr; curr = curr->next; insert_for_sort_operation(ppNode, prev); }}
算法总结:
1)算法本身还有改进的空间,比如是不是内存分配上每一次都要重建DIR_LINE队列有待商榷
2)算法编写不是一部就位的,中间有反复更有删改,写四五次是很正常的事情
3)编写代码的时候最好做到边修改、边测试,这样可以一方面增加代码的健壮度,一方面还能提高自己的信心
4)如果存在可能,可以复用以前写过的、稳定的算法代码,比如说排序、查找、堆栈、二叉树之类的代码
一步一步写算法(之prim算法 下)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。