c - 插入链表

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

如果要插入的前两个值按降序排列，您的代码将不起作用。它会给出分段错误。

对于第二个元素的插入，您需要小心

所以在if条件之后

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

Answer 2

你的代码做的太多了。如果编码不同，则没有特殊情况（如在列表顶部插入，在列表尾部插入）。

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

Answer 3

我编译并运行它，它似乎工作正常，除了一件事。 insertNode被定义为返回一个 int，但有 3 个返回语句是 void 返回。为了让它编译，我将它们更改为return 0;. 如果您能够按原样编译和运行它，那么可能是堆栈被不一致的返回破坏了。