c - 链表: how to make sorter checker in C?

Question

我认为这应该可以正常工作...我不确定它出了什么问题？这是我的代码片段。如果给定的整数列表不是按升序排列，则假定返回 0；如果按升序排列，则返回 1。

 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;
 }

Answer 1

正如 @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
}