鏈接列表：如何在C中進行分揀機檢查？

我認爲這應該工作正常...我不知道它有什麼問題嗎？這是我的代碼片段。如果給定的整數列表不是按升序排列，則返回1，如果按升序排列則返回1。鏈接列表：如何在C中進行分揀機檢查？

struct Node{ 
    int data; 
    Node *pNext; 
}; 

int isItSorted(Node *pHead){ 
    while(pHead != NULL){ 
     if(pHead->data > pHead->pNext->data) 
      return 0; 
     else 
      return 1; 
     pHead = pHead->pNext; 
    } 
    return 1; 
}

來源

2017-09-04 Anymee

您的代碼會遇到未定義的行爲，因爲您在取消引用前不驗證'pHead-> pNext！= NULL'。這可能是你的問題的原因。 – Dai

另外，請發佈創建列表的代碼 - 可能您沒有正確初始化字段（例如，在適當時將pNext'明確設置爲NULL）。 – Dai

您的代碼永遠不會執行循環的多次迭代，因爲循環體中存在無條件的'return'。 –

你調用未定義的行爲，如@Dai說，當你做pHead->pNext->data沒有檢查pHead->pNext != NULL。另外，正如@JohnBollinger所說，你在裏面有return 1,while，所以它在檢查list[0] < list[1]後會返回，而不是檢查整個事情。

struct Node{ int data; Node *pNext; }; int isItSorted(Node *pHead){ while(pHead != NULL && pHead->pNext != NULL) { // 0 and 1 element lists are always sorted, so this is fine. if(pHead->data > pHead->pNext->data) return 0; // Break out and return else pHead = pHead->pNext; // Or keep going } return 1; // Lift out end case from loop }

這裏有一個尾遞歸版本，太：（編輯：無論clang也不gcc似乎是足夠聰明，尾遞歸，即使-O3哦。）

int isSorted(Node *list) { return list == NULL // [] is sorted || list->pNext == NULL // [x] is sorted || list->data <= list->pNext->data && isSorted(list->pNext); // x:y:z is sorted if x < y and y:z is sorted }

來源

2017-09-05 00:11:33 HTNW

這是你的（大）的問題：

if(pHead->data > pHead->pNext->data) 
    return 0; 
else 
    return 1;

這樣做你的循環中會返回一個或立即零，僅基於前兩項的比較。這是假設你有至少有兩項在那裏，否則你有未定義的行爲，因爲你解引用空指針。

我會執行它如下（僞代碼），用前面的普通檢查來捕捉邊緣情況（少於兩個項目），並且繼續檢查項目的排序而不是單個檢查後返回：

def isSorted(head): 
    # Less than two items means sorted no matter what the data is. 

    if head == NULL: 
     return true 

    if head.next == NULL: 
     return true 

    # Continue while there are at least two items to check. 

    node = head 
    while node.next != NULL: 
     # If those two items out of order, it'snot sorted. 
     # If they are in order, advance and keep checking. 

     if node.data > node.next.data: 
      return false 
     node = node.next 

    # Reaching here means all items were in order. 

    return true

來源

2017-09-05 01:28:27 paxdiablo

在你的代碼只是一個錯誤：

struct Node{ 
    int data; 
    Node *pNext; 
}; 

int isItSorted(Node *pHead){ 
    while(pHead != NULL){ 
     if(pHead->next != NULL && pHead->data > pHead->pNext->data) { 
      return 0; 
     } 
     pHead = pHead->pNext; 
    } 
    return 1; 
}

每當與循環處理，請務必檢查您的退出條件。例如，在你的代碼中，如果它沒有進入IF塊，那麼它將返回1，並且你的循環迭代將不會重複。

就這樣。確保在處理循環時考慮退出條件。

來源

2017-09-05 02:43:06

鏈接列表：如何在C中進行分揀機檢查？

回答

相關問題