Сортировка связанного списка в C

Question

Я пишу простой файл для одного из моих классов, который является простым действием связанного списка, и мне нужно отсортировать связанный список.

Это мой исходный код:

/*
 * 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) ;
//  }
}

У меня проблемы с моим методом сортировки. Я даже пошел шаг за шагом, и я не могу найти проблему.

Ниже вывод моей программы.

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 .: Оригинальный алгоритм сортировки был здесь: Сортировка вставки связанного списка

Answer 1

Ну, этот цикл будет идти только один раз (в хорошем случае):

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

Поскольку это домашнее задание, просто подсказка: что такое tmpNxt, а какое tmpPtr после первой итерации?

следующие строки, на которые стоит обратить внимание:

tmpPtr = head;
tmpNxt = tmpNxt->next;

оба примера объясняют, почему в вашем примере были заменены только первые два элемента.

Answer 2

MByD уже указал на проблему (мое мнение для вас, MByD), поэтому с учетом этого я хотел бы дать несколько советов.

Сортировка - одна из проблем, которая решалась снова и снова, снова и снова в истории информатики. Есть отличная статья Википедии с индексом и сравнением множества алгоритмов сортировки. Выберите несколько и узнайте, как они работают! Обратный инжиниринг (своего рода) алгоритмы - отличный способ улучшить свои навыки.

Попробуйте, например, пузырьковую сортировку, сортировку вставкой и быструю сортировку.

ура!

Answer 3

Вот моя версия сортировки связанных списков с использованием алгоритма быстрой сортировки.Проверьте, помогает ли это ..

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

Answer 4

Я понял это после нескольких следов стека с другом. Вот фиксированный код:

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
}  

Answer 5

Вместо того, чтобы копировать чужой код с известными проблемами, я бы предложил создать свой собственный. Вы узнаете намного больше, и, возможно, в итоге будет меньше ошибок.

Тем не менее, если вы хотите знать, что это не работает, проследите, что произойдет, когда наименьшее значение достигнет заголовка списка. tmpPtr->value будет установлен в 1, что присваивается a, что в итоге пропускает внутренний цикл while.