Liste liée: comment faire trieur de trieur en C?

Question

Je pensais que cela devrait fonctionner correctement ... Je ne suis pas sûr de ce qui ne va pas avec ça? Voici un extrait de mon code. Il est supposé retourner 0 si la liste donnée d'entiers ne sont pas dans l'ordre croissant et retourner 1 s'il est dans l'ordre croissant.

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

Vous invoquez un comportement non défini, comme l'a dit @Dai, quand vous faites pHead->pNext->data sans d'abord vérifier pHead->pNext != NULL. De plus, comme @JohnBollinger l'a dit, vous avez un return 1à l'intérieur le while, donc il reviendra après avoir vérifié list[0] < list[1] au lieu de passer par tout le truc.

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 
} 

Voici une version récursive aussi: (EDIT: Ni clang ni gcc semblent être assez intelligent pour remarquer la queue-récursion, même avec -O3 Oh bien..)

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 
} 

Answer 2

Ceci est votre (grand) problème:

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

Faire cela dans votre boucle renverra un ou zéro immédiatement, basé uniquement sur la comparaison des deux premiers articles. Cela suppose que ont au moins deux éléments là-dedans, sinon vous avez un comportement indéfini parce que vous déréférencer le pointeur nul.

je mettre en œuvre comme suit (pseudo-code), avec des contrôles simples à l'avant pour attraper les cas de bord (moins de deux articles) et continue de vérifier les articles pour commander plutôt que de retourner après un seul chèque:

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 

Answer 3

Juste une erreur dans votre code:

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

chaque fois que le traitement avec des boucles, assurez-vous de vérifier vos conditions de sortie. Par exemple, dans votre code, s'il ne va pas dans le bloc IF, il est renvoyé à 1. et votre itération de boucle ne se répétera jamais.

Alors c'est tout. Assurez-vous de penser à vos conditions de sortie tout en traitant des boucles.