插入鏈表

Question

我寫了一個程序，按降序將節點插入到鏈表中。但是每當我按照這個順序測試我的代碼時，數字爲12,14,13,19,7。每當我輸入7時，我都拿到了7，已經在列表中。但是作爲在我插入之前很容易看到7不在列表中。給出這個錯誤後，如果我通過輸入2我的程序選擇了打印選項，我的程序在無限循環中輸入。我看不到我的錯誤，我很困惑。

#include <stdio.h> 
#include <stdlib.h> 

struct node { 
    int content; 
    struct node* nextLink; 
}; 

typedef struct node NODE; 

void print (NODE*); 
int insertNode (NODE** head, int x); 

int main (void) 
{ 
    int num, choice; 
    NODE* head; 
    head = NULL; 

    do { 
     printf("\nPlease press 1 to insert or press 2 to print or press 0 to exit\n"); 
     scanf("%d", &choice); 
     switch (choice) { 
     case 0: 
      return 0; 
      break; 

     case 1: 
      printf("Enter an integer to insert into the linkedlist: "); 
      printf("\n"); 
      scanf("%d", &num); 
      insertNode(&head, num); 
      break; 

     case 2: 
      print(head); 
      break; 

     default: 
      printf("You entered an invalid number\n"); 
      return 0; 
      break; 
     } 
    } while (choice == 1 || choice == 2); 

    return 0; 
} 

int insertNode (NODE** head, int i) 
{ 
    NODE* newNode; 
    newNode   = (NODE*)malloc(sizeof(NODE)); 
    newNode->content = i; 
    NODE* temporary = *head; 
    newNode->nextLink = NULL; 

    if ((*head == NULL) || ((*head)->content) < i) { 
     *head    = newNode; 
     (*head)->nextLink = temporary; 
    } 
    else { 
     do { 
     if (((temporary->content) > i) && ((temporary->nextLink->content) < i)) { 
      newNode->nextLink = temporary->nextLink; 
      temporary->nextLink = newNode; 
      return; 
     } 
     else if (temporary->content == i) { 
      printf("To be inserted value is already in the list\n"); 
      return; 
     } 
     temporary = temporary->nextLink; 
     } while (temporary->nextLink != NULL); 

     if (temporary->content == i) { 
     printf("To be inserted value is already in the list\n"); 
     return; 
     } 

     temporary->nextLink = newNode; 
    } 
    return 0; 
} 

void print (NODE* head) 
{ 
    if (head == NULL) { 
     printf("\nLinkedList is empty \n"); 
    } 

    while (head != NULL) { 
     printf("%d ", head->content); 
     head = head->nextLink; 
    } 
} 

Answer 1

我編譯它並運行它，它似乎工作正常，除了一件事。 insertNode定義爲返回一個int，但3個返回語句是無效返回。爲了編譯它，我將它們改爲return 0;。如果你能夠按原樣編譯並運行它，那麼它可能是由於不一致的返回而被破壞。

Answer 2

如果要插入的前兩個值按降序排列，則您的代碼將不起作用。它會給分段錯誤。

對於第二個元素的插入，你需要小心

所以經過如果條件

else if (temporary->content > i && temporary->nextLink==NULL) 
     (*head)->nextLink = newNode; 

Answer 3

你的代碼是做得太多。如果以不同的方式對其進行編碼，則沒有特殊情況（例如頂部插入，插入尾部列表）。

int insertNode (NODE **head, int val) 
{ 
    NODE *newnode; 

    for (; *head; head = &(*head)->nextLink) { 
     if ((*head)->content == val) { 
      printf("To be inserted value (%d)is already in the list\n", val); 
      return 0; 
      } 
     if ((*head)->content > val) break; 
     } 
    newnode = malloc(sizeof *newnode); // Maybe check return here ;-) 
    newnode->content = val; 
    newnode->nextLink = *head; 
    *head = newnode; 
    return 1; 
}