首页 > 程序开发 > 软件开发 > C语言 >

一步一步写算法(之prim算法 下)

2011-11-16

【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing @163.com】 前两篇博客我们讨论了prim最小生成树的算法,熟悉了基本的流程。基本上来说,我们是按照自上而下的顺序来编写代码的。首...

【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱: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;

}

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;

}

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);

}

}

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)如果存在可能,可以复用以前写过的、稳定的算法代码,比如说排序、查找、堆栈、二叉树之类的代码

相关文章
最新文章
热点推荐