程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> 一步一步寫算法(之prim算法 下)

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

編輯:關於C語言

 

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

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved