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