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

一步一步寫算法(之鏈表逆轉)

編輯:關於C語言

 

【 聲明:版權所有,歡迎轉載,請勿用於商業用途。  聯系信箱:feixiaoxing @163.com】

 

 

 

 

    鏈表逆轉是面試環境中經常遇到的一道題目,也是我們在實際開發中可能會遇到的開發需求。和線性逆轉不一樣,單向鏈表的節點需要一個一個進行處理。為了顯示兩者之間的區別,我們分別對線性內存和鏈表進行逆轉:

 

    (1)普通連續內存數據的反轉分析

 

 

STATUS normal_revert(int array[], int length) 

    int* pData ; 

    int index = length - 1; 

    if(NULL == array || 0 == length) 

        return FALSE; 

 

    pData = (int*)malloc(sizeof(int) * length); 

    assert(NULL != pData); 

    memset(pData, 0, sizeof(int) * length); 

 

    while(index >= 0) 

        pData[length - 1 - index] = array[index], index --; 

 

    memmove(array, pData, length * sizeof(int)); 

    free(pData); 

    return TRUE; 

STATUS normal_revert(int array[], int length)

{

       int* pData ;

       int index = length - 1;

       if(NULL == array || 0 == length)

              return FALSE;

 

       pData = (int*)malloc(sizeof(int) * length);

       assert(NULL != pData);

       memset(pData, 0, sizeof(int) * length);

 

       while(index >= 0)

              pData[length - 1 - index] = array[index], index --;

 

       memmove(array, pData, length * sizeof(int));

       free(pData);

       return TRUE;

}

 

我們看到連續內存反轉函數主要做了下面幾個工作:

 

    1)分配和原來數據一樣大的內存

 

    2)從原來數據末尾開始拷貝

 

    3)利用pData獲取的數據對原來的數據進行拷貝覆蓋,釋放內存

 

 

 

 

    (2)鏈表數據的反轉

 

 

STATUS link_revert(NODE** pNode) 

    NODE* pPrevNode; 

    NODE* pNextNode; 

    if(NULL == pNode || NULL == *pNode) 

        return FALSE; 

 

    pNextNode = (*pNode)->next; 

    (*pNode) ->next = NULL; 

 

    while(pNextNode){ 

        pPrevNode = pNextNode; 

        pNextNode = pNextNode->next; 

        pPrevNode->next = *pNode; 

        *pNode = pPrevNode; 

    } 

 

    return TRUE; 

STATUS link_revert(NODE** pNode)

{

       NODE* pPrevNode;

       NODE* pNextNode;

       if(NULL == pNode || NULL == *pNode)

              return FALSE;

 

       pNextNode = (*pNode)->next;

       (*pNode) ->next = NULL;

 

       while(pNextNode){

              pPrevNode = pNextNode;

              pNextNode = pNextNode->next;

              pPrevNode->next = *pNode;

              *pNode = pPrevNode;

       }

 

       return TRUE;

}和連續內存不同,鏈表節點的反轉需要進行下面一些操作:

 

    1) 判斷指針是否為空,判斷指針的指針是否為空

 

    2) 將指針分成兩個部分,一個是已經反轉成功的鏈表,即pNode;另外一個是待反轉的鏈表,即pPrevNode

 

    3) 對2)進行循環迭代處理,直到所有的節點都已經接受反轉

 

 

 

 

    建議大家可以好好觀察一下兩者之間的區別

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