Linked list sorting in C

问题:

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

回答1:

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?

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.

回答2:

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

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 article with 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!

回答3:

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
}  

回答4:

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

回答5:

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->value will get set to 1, which gets assigned to a, which ends up skipping the inner while loop.