C中双向链表的插入排序

Question

我正在尝试对双向链表执行插入排序。当用户输入 'P' 时，它将打印存储的已排序元素。元素存储在列表中，直到行数用尽，这在代码中由 nLines 表示。

我遇到了分段错误。

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

typedef struct Node
{
    int data;
    struct Node* previous;
    struct Node* next;
}Node;

Node* head = {NULL};

// To insert new element into the doubly linked list
void insert(Node* currentPointer, int element)
{
   Node* temp = (Node*)malloc(sizeof(Node));

   if (head == NULL)
   {
        head = temp;
        currentPointer = head;
        head -> data = element;
        head -> previous = NULL;
        head -> next = NULL;
   }

   else
   {
        temp -> previous = currentPointer;
        currentPointer -> next = temp;
        currentPointer = temp;
        currentPointer -> data = element;
        currentPointer -> next = NULL;
   }
}

//Performing insertion sort on the doubly linked list
void insertionSort(Node* currentPointer)
{
    Node* temp = currentPointer;

    while (temp != NULL && temp -> data < (temp -> previous) -> data)
    {
        int variable = temp -> data;
        temp -> data = (temp -> previous) -> data;
        (temp -> previous) -> data = variable;
        temp = temp -> previous;
    }
}

//Function to print the sorted elements
void printSorted()
{
    Node* temp = head;
    while(temp != NULL)
    {
        printf("%d ",temp -> data);
        temp = temp -> next;
    }
    printf("\n");
}


int main()
{
    int nLines;
    Node* currentPointer0;
    printf("Enter the no. of lines: ");
    scanf("%d\n",&nLines);

    while(nLines--)
    {
        int variable;
        scanf("%d\n",&variable);

        if ((char)variable == 'P' )
        {
            printSorted();
        }

        else
        {
            insert(currentPointer0,variable);
            insertionSort(currentPointer0);
        }

    }

    //After the program is done free all the memory
    while(head != NULL)
    {
        Node* temp = head;
        head = head -> next;
        free(temp);
    }

    return 0;
}

Answer 1

从您的代码看来，您希望 insert 函数在 main.

中更新 currentPointer0

嗯，不是。

C 使用按值传递，当函数 returns 时，您在函数内对该值所做的任何更改都将丢失。换句话说：如果currentPointer0在你调用insert时的值是42，那么当你调用returns函数时，它的值仍然是42！ currentPointer -> next = temp; 等赋值在函数 returns.

时无效

在您的情况下，它是未初始化的，因此取消引用它（很可能）会导致崩溃。

您可能需要双指针：

void insert(Node** currentPointer, int element) // Notice
{
   Node* temp = (Node*)malloc(sizeof(Node));

   if (head == NULL)
   {
        head = temp;
        *currentPointer = head; // Notice
        head -> data = element;
        head -> previous = NULL;
        head -> next = NULL;
   }

   else
   {
        temp -> previous = *currentPointer;   // Notice
        (*currentPointer) -> next = temp;     // Notice
        (*currentPointer) = temp;             // Notice
        (*currentPointer) -> data = element;  // Notice
        (*currentPointer) -> next = NULL;     // Notice
   }
}

并这样称呼它：

insert(&currentPointer0,variable);

C中双向链表的插入排序

Insertion Sort on doubly linked list in C

c

linked-list

insertion-sort