c - 将元素按升序插入单链表中。

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时但小于列表中最大的元素，需要将其插入到 header 和最后一个节点之间的某个位置。

排序插入的简单实现如下 -

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