【 聲明：版權所有，歡迎轉載，請勿用於商業用途。 聯系信箱：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）如果存在可能，可以復用以前寫過的、穩定的算法代碼，比如說排序、查找、堆棧、二叉樹之類的代碼
