C中单链表的插入排序

Question

我正在努力提高我在算法和数据结构方面的知识，因此在过去的 5-6 天里，我一直在尝试在不同的数据结构上实现不同的算法。基本了解单链表、双链表、循环链表，可以用数组实现插入排序算法

然而，使用单向链表实现插入排序算法比我最初预期的要困难得多。我不喜欢看别人的代码然后照搬他们来理解一个概念。我真的很喜欢先尝试自己做。所以，我写了一些行：

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

typedef struct Node node;
struct Node{
    int num;
    node *next;
};

void printLinkedList(node *ptr);
void insertionSortLinkedList(node *p,node *head,int sizeOfList);

/* Driver program applying Insertion Sort to a Singly Linked List */
int main(int argc,char *argv[]){
    
    int i, sizeOfList=argc-1;
    node *head,*ptr;
    ptr=(node*)malloc(sizeOfList*sizeof(node));
    for(i=0;i<sizeOfList;i++){
        (ptr+i)->num=atoi(argv[i+1]);
        (ptr+i)->next=(ptr+i+1);
    }
    (ptr + sizeOfList-1)->next=NULL;
    head=ptr;

    printLinkedList(head);

    insertionSortLinkedList(ptr,head,sizeOfList);
    return 0;
}


void printLinkedList(node *ptr) {
    
    while (ptr != NULL) {
        printf("%d ", ptr->num);
        ptr=ptr->next;
    }

    printf("\n\n");
}

void insertionSortLinkedList(node *p,node *head,int sizeOfList){
    int i=0;
    int N=1;
    int flag;
    node *temp;
    while(N<sizeOfList){
        flag=0;
        /* node N > node i */
        if((p+N)->num>(p+i)->num){
            i++;
        }
        /* node i >= node N */
        else{
            /* node i = node N */
            if((p+N)->num==(p+i)->num){ // FIRST ERROR HERE. DOES NOT ENTER HERE FOR 2 1 3 1 5 4 3 WHEN 1(i) 2 3 1(N) 5 4 3
                /* i = N */
                if(i==N){
                    flag=1;
                }
                /* i != N */
                else{
                    temp=(p+N);
                    (p+N-1)->next=(p+N)->next;
                    temp->next=(p+i)->next;
                    (p+i)->next=temp;
                    flag=1;
                }
            }
            /* node i > node N */
            else{
                /* i = 0 and Head needs to change */
                if(i==0){ 
                    temp=(p+N);
                    (p+N-1)->next=(p+N)->next;
                    temp->next=(p+i);
                    head=temp;
                    flag=1;
                }
                /* i != 0 and Head needs to change */
                else{
                    temp=(p+N);
                    (p+N-1)->next=(p+N)->next;
                    temp->next=(p+i);
                    (p+i-1)->next=temp;
                    flag=1;
                }
            }   
        }
        /* Increase N and set i equal zero */
        if(flag==1){
            i=0;
            N++;
        }
    }
    printf("Our ordered values in the LinkedList: ");
    printLinkedList(head);
}

我的代码似乎在特定点上运行良好。例如，如果我进入终端：

./a.out 2 1 3 1 5 4 3

第一个“枢轴”工作正常，算法交换了“2”和“1”。因此我们得到：

1 2 3 1 5 4 3

然后下一个枢轴也可以正常工作，算法首先比较“1”和“3”，然后比较“2”和“3”，然后决定什么都不做，只是递增“枢轴”。所以我们得到：

1 2 3 1 5 4 3

在这一点上我的算法变得疯狂，它比较“1”和“1”决定“1（第一个节点）”大于“1（枢轴）”。该算法的其余部分不起作用。作为最终结果，打印出的所谓“排序”数组是：

1 4

我在其他网站上看到过与链表插入排序相关的问题，但是它们采用的方法与我的代码尝试执行的方法不同。如果可能的话，我只想解决这个算法背后的错误。如果没有，那么我可能会像其他人一样放弃并实现代码。如果有人能指导我以正确的心态解决这个问题，或者告诉我为什么这段代码可能不起作用，我将不胜感激。另外，如果这方面的某些事情从根本上是错误的，请告诉我...

Answer 1

你算法的主要问题是你把链表结构当成一个数组，并试图执行像p+N这样的操作......实际上链表不是数组所以指向的指针节点没有按顺序放置在内存中，而是分散在地址 space 周围，操作 p+N 并不总是指向下一个节点。因此，要遍历列表，您只能使用 p->next 语句。

Answer 2

感谢@Mykola 的指导，我能够正确地在链表中实现插入排序。我意识到我最大的问题之一是没有仔细处理节点的指针。相反，通过他们的参考是一个很大的帮助。我也意识到我没有正确遍历链表。由于这些更正，我不得不稍微更改我的代码。我也试图让我的代码更清晰，我添加了一个 push() 函数。

我将在下面包含我的代码，以便如果有人发现自己处于与我相似的情况，他们可以查看它作为参考：

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

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

void printList(node* head);
void push(node** head_ref,int data);
void insertionSort(node** head_ref);
void insertIntoSorted(node** sorted_ref,node* new_node);

/* Driver program that applies insertion sort to singly linked lists */
int main(int argc, char* argv[]){
    int i, sizeOfList;
    sizeOfList=argc-1;
    node *head;
    head=NULL;
 
    for(i=sizeOfList;i>0;i--){
       push(&head,atoi(argv[i]));
    }

    /* Print the linked list before the insertion sort */
    printf("Your list before the insertion sort is: ");
    printList(head);

    /* insertion sort function */
    insertionSort(&head);

    /* Print the linked list after the insertion sort */
    printf("Your list after the sort is: ");
    printList(head);

    return EXIT_SUCCESS;
}


/* Utility function that inserts a new node at the beginning of a linked list */
void push(node** head_ref,int data){
    //allocate node and fill
    node* new_node;
    new_node=(node*)malloc(sizeof(node));
    new_node->data=data;    

    //link
    new_node->next=*head_ref;
    *head_ref=new_node;
}


/* Utility function to print a linked list */
void printList(node* head){
    node* temp;
    temp=head;
    while(temp!=NULL){
        printf("%d ",temp->data);
        temp=temp->next;
    }
    printf("\n");
}


/* Function to sort a singly linked list using insertion sort */
void insertionSort(node** head_ref){

    /* Initialize the sorted linked list */
    node* sorted;
    sorted=NULL;

    /* Traverse the given linked list and insert every node to "sorted" */
    node* current;
    current=*head_ref;
    while(current!=NULL){
        /* Store "next" for next iteration */ 
        node* next;
        next=current->next;

        /*Insert "current" into the "sorted" linked list */
        insertIntoSorted(&sorted, current);

        /* Update "current" to the next node */
        current=next;
    }
    *head_ref=sorted;
}


/* Function to insert a given node in the "sorted" linked list. Where
 * the insertion sort actually occurs.
 */ 
void insertIntoSorted(node** sorted_ref,node* new_node){
    node* current; 
    /* Special case for the head end of the "sorted" */
    if ((*sorted_ref == NULL) || ((*sorted_ref)->data >= new_node->data)) 
    { 
        new_node->next = *sorted_ref; 
        *sorted_ref = new_node; 
    }
    /* Locate the node before the point of insertion */
    else
    {
        current = *sorted_ref; 
        while ((current->next!=NULL) && (current->next->data < new_node->data)){ 
            current = current->next; 
        } 
        new_node->next = current->next; 
        current->next = new_node; 
    } 
}

C中单链表的插入排序

Insertion Sort for Singly Linked List in C

c

sorting

data-structures

linked-list

insertion-sort