前兩篇博客我們討論了prim最小生成樹(shù)的算法，熟悉了基本的流程?；旧蟻?lái)說(shuō)，我們是按照自上而下的順序來(lái)編寫(xiě)代碼的。首先我們搭建一個(gè)架構(gòu)，然后一步一步完成其中的每一個(gè)子功能，這樣最后構(gòu)成一個(gè)完成prim算法計(jì)算過(guò)程。

f）將DIR_LINE隊(duì)列中不符合的數(shù)據(jù)刪除，主要是雙節(jié)點(diǎn)都已經(jīng)訪問(wèn)過(guò)的DIR_LINE數(shù)據(jù)。

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）函數(shù)中使用了判定DIR_LINE合法性的函數(shù)，我們需要完善一下。

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） 最后就是對(duì)當(dāng)前已經(jīng)入隊(duì)的DIR_LINE數(shù)據(jù)排序，其實(shí)就是[**鏈表排序][1]。**

void insert_for_sort_operation(DIR_LINE** ppNode, DIR_LINE* pNode)
{
    DIR_LINE* prev;
    DIR_LINE* cur;

    /* 在第一個(gè)數(shù)據(jù)之前插入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);
    }
}

算法總結(jié)：

1）算法本身還有改進(jìn)的空間，比如是不是內(nèi)存分配上每一次都要重建DIR_LINE隊(duì)列有待商榷

2）算法編寫(xiě)不是一部就位的，中間有反復(fù)更有刪改，寫(xiě)四五次是很正常的事情

3）編寫(xiě)代碼的時(shí)候最好做到邊修改、邊測(cè)試，這樣可以一方面增加代碼的健壯度，一方面還能提高自己的信心

4）如果存在可能，可以復(fù)用以前寫(xiě)過(guò)的、穩(wěn)定的算法代碼，比如說(shuō)排序、查找、堆棧、二叉樹(shù)之類的代碼