在链表中排序插入程序

Question

我是数据结构的初学者，现在正在学习 linked 列表。我遇到了一个关于排序插入的程序，我有一个 add() 函数来按排序顺序添加节点

         /*Linked List program to add ascending order sorted nodes in     

         the list */
 #include <stdio.h>
  #include <stdlib.h>
enter code here
 struct node {
   int data ;
   struct node link;

 };

 void add(struct node **q,int num){
    struct node *r,*temp = *q;
    r = malloc(sizeof(struct node )); //Data Allocated
    r->data = num;

    if(*q==NULL ||(*q)->data >num){
     *q = r;
     (*q)->link = temp;

    }else{
      while(temp !=NULL){
         if(temp->data <=num &&(temp->link->data >num                    
                                             ||temp->link==NULL)){
             r->link = temp->link;
             temp->link=r;
             return;
         }
          temp = temp->link;
      }

    }

 }

 void main(){
 struct node *p;
 p = NULL;

 }

我原本希望按升序排序添加节点，但是当我输入数据时，错误是 shown.I am Using Code Blocks to 运行 C

中的程序

我认为它必须对结束条件 temp->link == null 做一些事情，但我无法找出那部分代码的确切条件。请帮忙！

Answer 1

你应该使用

( temp->link == NULL || temp->link->data > num )

而不是

( temp->link->data > num || temp->link == NULL )

因为如果 temp->link 为 NULL，第一个代码在检查第一个条件后会立即 return 为真，不会检查第二个条件，因此您不会得到错误。但是当你像在第二个表达式中那样使用它时，如果 temp->link 是 NULL，你会得到一个错误，因为你正试图使用代码[到达 NULL 对象的名为 "data" 的字段

temp->link->data

Answer 2

结构 struct node 的定义不正确。我认为这是一个错字。应该是struct node *link;
你遍历循环的条件不正确。如评论中所述，您正在访问 temp->link 以防它可能是 NULL.
您没有检查要添加的数字大于所有数字并且要添加到列表末尾的条件。

修改后的函数如下

 void add(struct node **q,int num){
    struct node *r,*temp = *q;
    r = malloc(sizeof(struct node )); //Data Allocated
    r->data = num;
    r->link = NULL;

    if(*q==NULL ||(*q)->data >num){
     *q = r;
     (*q)->link = temp;

    }else{
      while(temp->link !=NULL){
         if(temp->data <=num &&(temp->link->data >num)){
             r->link = temp->link;
             temp->link=r;
             return;
         }
         temp = temp->link;
      }
      temp ->link = r; // add at the end as not added at any other location.
    }
}

Answer 3

除了Rishikesh Raje's （你需要在struct内部使用一个指针：struct node* link;；你需要检查first for link为 null，然后访问 link->data)，循环可以简化很多：

// advance only, if we need to insert (at least) after temp->link:
while(temp->link && temp->link->data <= num)
{
    temp = temp->link;
}
// once the loop is done, temp points to the last element smaller than num, so:
r->link = temp->link;
temp->link = r;

暂时不需要检查temp->data > num；我们只重新进入循环，如果之前满足循环条件，它已经准确地检查了这个条件；仍然是第一个循环运行；但是，在这种情况下，循环之前的 if 已经覆盖了条件。

旁注：是否需要在现有元素之后插入新元素？如果不是，在前面插入 会更快一些，您只需将 <= 替换为 < 并将 > 替换为 >=...

在链表中排序插入程序

Sorted insert program in a linked list

c

linked-list

singly-linked-list