C语言 C中的链表排序

Linked list sorting in C

提问by DestroyerDust

I'm writing a simple file for one of my classes that is a simple linked list activity and I need to sort a linked list.

我正在为我的一个类编写一个简单的文件，它是一个简单的链表活动，我需要对一个链表进行排序。

This is my source code so far:

到目前为止，这是我的源代码：

/*
 * Simple list manipulation exercise.
 * 1. Create a list of integers.
 * 2. Print the list.
 * 3. Sort the list.
 * 4. Print the list
 * 5. Free the list nodes.
 */

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

struct node {
    int value ;
    struct node *next ;
} ;

extern struct node *mk_node(int v) ;
extern void print_list(struct node *head) ;
extern struct node *sort_list(struct node *head) ;
extern void free_list(struct node *head) ;

#define NVALUES (6)

int initial_contents[] = { 3, 8, 2, 5, 1, 9 } ;

/*
 * Main driver program. Create the list from the initial_contents,
 * print it, sort it, print it, free it, and return.
 */

int main() {
    struct node *head = NULL ;
    struct node *curp ;

    int i ;

    /*
     * Put the initial values into the list. This algorithm
     * will result in the values being inserted in reverse
     * order of the array.
     */
    for( i = 0 ; i < NVALUES ; i++ ) {
        curp = mk_node( initial_contents[i] ) ;
        curp->next = head ;
        head = curp ;
    }

    print_list(head) ;
    head = sort_list(head) ;
    print_list(head) ;
    free_list(head) ;

    return 0 ;
}

/*
 * Return a new node with 'v' as the label and a NULL next link.
 */

struct node *mk_node(int v) {
    struct node *newp = malloc( sizeof(struct node) ) ;
    newp->value = v;
    newp->next = NULL;  

    return newp ; // Place holder
}

/*
 * Print the list headed by 'head', one value per line.
 */

void print_list(struct node *head) {
    printf("List: ");
    struct node *ptr = head;
    while(ptr!=NULL){
        printf("%d ", ptr->value);
        ptr=ptr->next;
    }
    putchar('\n');
}    

/*
 * Sort the list headed by 'head', returning a pointer to the node
 * that ends up at the head of the list.
 */

struct node *sort_list(struct node *head) {
    struct node *tmpPtr;
    struct node *tmpNxt;

    tmpPtr = head;
    tmpNxt = head->next;

    int a, tmp;

    while(tmpNxt != NULL){
        a = tmpPtr->value;
        while(tmpNxt != tmpPtr && tmpNxt->value < a){
            tmp = a;
            tmpPtr->value = tmpNxt->value;
            tmpNxt->value = tmp;
            tmpPtr = tmpPtr->next;
        }
        tmpPtr = head;
        tmpNxt = tmpNxt->next;
    }

    return tmpPtr ; // Place holder
}

/*
 * Free all the nodes in the list headed by 'head'.
 */

void free_list(struct node *head) {
    //struct node *releasep ;
    //while( head != NULL ){
//      releasep = head;
//      head = head->next ;
//
//      free(releasep->value) ;
//      free(releasep) ;
//  }
}

I'm having troubles with my sort method. I even even went step by step and I can't find the problem.

我的排序方法有问题。我什至一步一步都找不到问题所在。

Below is my program's output.

下面是我的程序的输出。

XXXXXXX@linus:~/350/c_memory_activity$ gcc -o test listsort.c 
XXXXXXX@linus:~/350/c_memory_activity$ ./test 
List: 9 1 5 2 8 3 
List: 1 9 5 2 8 3 
XXXXXXX@linus:~/350/c_memory_activity$ 

P.S.: Original sorting algorithm was here: Linked list insertion sort

PS：原始排序算法在这里：链表插入排序

回答by MByD

Well, This loop will only go once (in the good case):

好吧，这个循环只会运行一次（在好的情况下）：

 while(tmpNxt != tmpPtr && tmpNxt->value < a){
        tmp = a;
        tmpPtr->value = tmpNxt->value;
        tmpNxt->value = tmp;
        tmpPtr = tmpPtr->next;
    }

Since it's homework, just a hint: which is tmpNxt and which is tmpPtr after the first iteration?

既然是作业，就提示一下：第一次迭代后哪个是tmpNxt，哪个是tmpPtr？

another lines to look at are those:

要查看的另一行是：

tmpPtr = head;
tmpNxt = tmpNxt->next;

both examples explain why only the first two elements were replaced in your example.

这两个示例都解释了为什么在您的示例中只替换了前两个元素。

回答by slezica

MByD already pointed out the problem (my upvote for you, MByD), so with that addressed, I'd like to contribute some advice.

MByD 已经指出了这个问题（我对你的支持，MByD），所以解决这个问题后，我想提供一些建议。

Sorting is one of the problems that have been tackled over, and over, and over and over in the history of computer science. There's an excellent Wikipedia articlewith an index and comparison of tons of sorting algorithms. Pick a few and learn how they work! Reverse-engineering (sort of) algorithms is a great way to improve your own skills.

排序是计算机科学史上反复解决的问题之一。有一篇出色的维基百科文章，其中包含大量排序算法的索引和比较。选择一些并了解它们的工作原理！逆向工程（某种）算法是提高自己技能的好方法。

Try for example bubble sort, insertion sort and quick sort.

尝试例如冒泡排序、插入排序和快速排序。

Cheers!

干杯!

回答by DestroyerDust

I figured it out after some stack traces with a friend. Heres the fixed code:

我在与朋友进行了一些堆栈跟踪后发现了它。这是固定代码：

struct node *sort_list(struct node *head) {

    struct node *tmpPtr = head;
    struct node *tmpNxt = head->next;

    int tmp;

    while(tmpNxt != NULL){
           while(tmpNxt != tmpPtr){
                    if(tmpNxt->value < tmpPtr->value){
                            tmp = tmpPtr->value;
                            tmpPtr->value = tmpNxt->value;
                            tmpNxt->value = tmp;
                    }
                    tmpPtr = tmpPtr->next;
            }
            tmpPtr = head;
            tmpNxt = tmpNxt->next;
    }
         return tmpPtr ; // Place holder
}  

回答by user1596193

Here is my version of linked list sorting using Quick Sort Algorithm. Check if this helps..

这是我使用快速排序算法的链接列表排序版本。检查这是否有帮助..

#include "stdafx.h"
#include "malloc.h"

typedef struct node {
    struct node *next;
    int val;
} node;

bool insert_node(struct node **head, int val)
{
    struct node *elem;
    elem = (struct node *)malloc(sizeof(struct node));
    if (!elem)
        return false;
    elem->val = val;
    elem->next = *head;
    *head = elem;
    return true;
}

int get_lval(struct node *head, int l)
{
    while(head && l) {
        head = head->next;
        l--;
    }
    if (head != NULL)
        return head->val;
    else
        return -1;
}

void swap(struct node *head, int i, int j)
{
    struct node *tmp = head;
    int tmpival;
    int tmpjval;
    int ti = i;
    while(tmp && i) {
        i--;
        tmp = tmp->next;
    }
    tmpival = tmp->val;
    tmp = head;
    while(tmp && j) {
        j--;
        tmp = tmp->next;
    }
    tmpjval = tmp->val;
    tmp->val = tmpival;
    tmp = head;
    i = ti;
    while(tmp && i) {
        i--;
        tmp = tmp->next;
    }
    tmp->val = tmpjval;
}


struct node *Quick_Sort_List(struct node *head, int l, int r)
{
    int i, j;
    int jval;
    int pivot;
    i = l + 1;
    if (l + 1 < r) {
        pivot = get_lval(head, l);
        printf("Pivot = %d\n", pivot);
        for (j = l + 1; j <= r; j++) {
            jval = get_lval(head, j);
            if (jval < pivot && jval != -1) {
                swap(head, i, j);
                i++;
            }
        }
        swap(head, i - 1, l);
        Quick_Sort_List(head, l, i);
        Quick_Sort_List(head, i, r);
    }
    return head;
}

struct node *Sort_linkedlist(struct node *head)
{
    struct node *tmp = head;
    // Using Quick sort.
    int n = 0;

    while (tmp) {
        n++;
        tmp = tmp->next;
    }
    printf("n = %d\n", n);
    head = Quick_Sort_List(head, 0, n);
    return head;
}

void print_list(struct node *head)
{
    while(head) {
        printf("%d->", head->val);
        head = head->next;
    }
    printf("\n");
}

int _tmain(int argc, _TCHAR* argv[])
{
    struct node *head = NULL;
    struct node *shead = NULL;

    insert_node(&head, 10);
    insert_node(&head, 12);
    insert_node(&head, 9);
    insert_node(&head, 11);
    insert_node(&head, 7);
    insert_node(&head, 1);
    insert_node(&head, 3);
    insert_node(&head, 8);
    insert_node(&head, 5);
    insert_node(&head, 2);
    insert_node(&head, 4);
    insert_node(&head, 6);
    print_list(head);

    shead = Sort_linkedlist(head);
    print_list(shead);

    return 0;
}

回答by BMitch

Rather than copy someone else's code that has known issues, I'd suggest making your own. You'll learn a lot more and just might end up with fewer bugs.

与其复制其他有已知问题的代码，我建议您自己制作。你会学到更多，但最终可能会减少错误。

That said, if you want to know what it's not working, follow through what happens once the smallest value reaches the head of the list. tmpPtr->valuewill get set to 1, which gets assigned to a, which ends up skipping the inner whileloop.

也就是说，如果您想知道它不工作的地方，请查看一旦最小值到达列表的头部会发生什么。 tmpPtr->value将被设置为 1，它被分配给a，最终跳过内部while循环。