按升序將元素插入單向鏈表中。

Question

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

typedef struct node 
{ 
    int data; 
    struct node *link; 
}list; 

list *header =NULL; 

void insert(int num) 
{ 
    printf("num:%d ", num); 
    struct node *temp, *r; 
    temp = header; 

    r = malloc(sizeof(struct node)); 
    r -> data = num; 

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

void display() 
{ 
    struct node *temp; 
    temp = header; 

    while(temp != NULL) 
    { 
     printf("%d ", temp->data); 
     temp = temp->link; 
    } 
} 

void main() 
{ 
    insert(10); 
    insert(5); 
    insert(17); 
    insert(8); 
    insert(23); 
    insert(78); 

    display(); 
} 

這裏我試圖按升序插入元素。令我驚訝的是，我得到的輸出是5 78 23 8 17 10，這是不正確的，任何人都可以看看這個嗎？任何幫助，將不勝感激..

Answer 1

爲了插入升序節點的鏈接列表，你就必須解決以下場景 -
1.列表爲空：當有列表中的
沒有元素 2.在開始處插入：當r->data < header->data時，它需要插入到列表的最開始處。
3.在末尾插入：當r->data大於列表中具有最大值的節點時，它需要在最後插入（假設我們在此處進行排序插入），因爲用戶@keltar已經指出。
4.在中間插入：當r->data > header->data但小於列表中最大的元素時，它需要插入到標頭和最後一個節點之間的某處。

簡單實現有序插入的是如下 -

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

#define LEN 13 

struct node { 
    int data; 
    struct node *next; 
}; 
/* 
* print_list() - To print the state of the list 
*/ 
void print_list(struct node *head) 
{ 
    struct node *tmp = head; 
    while (tmp) { 
     printf(" %d ", tmp->data); 
     tmp = tmp->next; 
    } 
    printf("\n\n"); 
} 
/* 
* insert_node_sorted() - To insert nodes into the list 
* in sorted order 
*/ 
struct node *insert_node_sorted(struct node *head, int data) 
{ 
    struct node *tmp; 
    struct node *e_ptr; 
    struct node *new_node = malloc(sizeof(struct node)); 
    if (!new_node) 
     exit(0); 
    new_node->data = data; 
    new_node->next = NULL; 
    /* When the list is empty */ 
    if (!head) 
     return new_node; 
    else { 
     /* Initialize tmp & e_ptr */ 
     tmp = head; 
     e_ptr = head; 
     /* Make e_ptr point to the largest element of the list, i.e. last element */ 
     while (e_ptr->next) 
      e_ptr = e_ptr->next; 
     /* If the element to be inserted is smaller than the head node */ 
     if (head->data > new_node->data) { 
      new_node->next = head; 
      head = new_node; 
     } else if (new_node->data > e_ptr->data){ /* Data to be inserted is larger than the largest element in the list */ 
      e_ptr->next = new_node; 
     } else { /* New node should be placed somewhere in between head and e_ptr */ 
      while (tmp->next && tmp->next->data < new_node->data) 
       tmp = tmp->next; 
      new_node->next = tmp->next; 
      tmp->next = new_node; 
     } 
    } 
    return head; 
} 
/* 
* Driver function 
*/ 
int main(int argc, char **argv) 
{ 
    struct node *head = NULL; 
    int i; 
    /* Populate the list */ 
    for (i = 0; i < LEN; i++) 
     head = insert_node_sorted(head, rand() % 1000); 
    /* Print the state of the list */ 
    printf("State of the list -\n\n"); 
    print_list(head); 
    return 0; 
}