时间戳

首页 > 解决方案 > 使用 qsort 算法对链表进行排序

c - 使用 qsort 算法对链表进行排序

问题描述

我仍在学习链表是如何工作的，并且我在使用 qsort 算法和节点进行排序时有点挣扎。这就是我到目前为止所做的。

所以我在代码的某个地方发生了崩溃，我不知道这个 qsort 算法是否以这种方式与链表一起工作。

代码更新

void swapString(char **str1, char **str2)
{
    char *temp = *str2; 
    *str2 = *str1;
    *str1 = temp;
}

TCD *partition(TCD *Start, TCD *End, int (*cmp)(const void *, const void*))
{
    TCD *partitionIdx = Start;
    TCD *i ;
   
    for (i = Start; i != End; i=i->Next)
    { 
        if (cmp(i->Titel, End->Titel) < 0)
        {
            swapString(&i->Titel, &partitionIdx->Titel);
     
            partitionIdx->Prev = partitionIdx;
            partitionIdx = partitionIdx->Next;
        }
    }

    swapString(&partitionIdx->Titel, &End->Titel);
    
    return partitionIdx; 
}

void Quicksort(TCD *Start, TCD *End, int (*cmp)(const void *, const void *))
{
    if (Start !=NULL && End != Start && End!= Start->Next)
    {
        TCD *partitionIdx = partition(Start, End, cmp);
       
        Quicksort(Start, partitionIdx->Prev, cmp);
        Quicksort(partitionIdx->Next, End, cmp);
    }
}

顺便说一下，这是TCD的定义

typedef struct F
{
 char *Titel;
 struct F *Next;
 struct F *Prev;
}TCD;

标签： clinked-list

解决方案

您的代码有几个问题：

  1. 这条线partitionIdx->Prev = partitionIdx;没有意义。它使节点指向自身。这不可能是正确的。链表的目的是让一个节点指向下一个节点和前一个节点，但从不指向它自己。

  2. 您的函数partition正在崩溃，因为它的参数Start有时会指向链接列表中超出End参数的位置。这是因为您调用函数Quicksort时没有确保其Start参数不指向End参数之外的位置。

  3. if条件if ( Start != NULL && End != Start && End != Start->Next )没有意义。子表达式End != Start->Next测试分区的大小是否为 2。如果是这种情况，则不处理分区。但是，必须对大小为 2 的分区进行排序，因此必须对其进行处理。仅当大小为 1 时才不应对其进行处理。

我已经通过修复上述问题更改了算法的代码，现在它似乎可以工作了。另外，我添加了一些函数来测试算法。这是代码：

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

typedef struct F
{
    char *Titel;
    struct F *Next;
    struct F *Prev;
} TCD;

void swapString( char **str1, char **str2 )
{
    char *temp = *str2;
    *str2 = *str1;
    *str1 = temp;
}

TCD *partition( TCD *Start, TCD *End, int( *cmp )(const void *, const void*) )
{
    TCD *partitionIdx = Start;
    TCD *i;

    for ( i = Start; i != End; i = i->Next )
    {
        if ( cmp( i->Titel, End->Titel ) < 0 )
        {
            swapString( &i->Titel, &partitionIdx->Titel );

            //NOTE: I disabled the following line from the original code, as it was doing nonsense. It was causing a node to point to itself.
            //partitionIdx->Prev = partitionIdx;

            partitionIdx = partitionIdx->Next;
        }
    }

    swapString( &partitionIdx->Titel, &End->Titel );

    return partitionIdx;
}

void Quicksort( TCD *Start, TCD *End, int( *cmp )(const void *, const void *) )
{
    //NOTE: In the following if condition, I disabled part of the original code, because a partition of two elements must be sorted
    if ( Start != NULL && End != Start /*&& End != Start->Next*/ )
    {
        TCD *partitionIdx = partition( Start, End, cmp );

        if ( Start != partitionIdx )
            Quicksort( Start, partitionIdx->Prev, cmp );
        if ( partitionIdx != End )
            Quicksort( partitionIdx->Next, End, cmp );
    }
}

// NOTE:
// The following functions are not part of the algorithm, but are only
// used to test the algorithm.

void AddToList( TCD **head, TCD **tail, char *str )
{
    TCD *p;

    //allocate new node and fill it with the data
    p = malloc( sizeof(*p) );
    assert( p != NULL );
    p->Titel = str;
    p->Next = NULL;
    p->Prev = *tail;

    //attach new node to list by updating head or next pointer
    if ( *head == NULL )
        *head = p;
    else
        (*tail)->Next = p;

    //update tail pointer too
    *tail = p;

}

void PrintList( FILE *stream, TCD *head )
{
    TCD *p;

    for ( p = head; p != NULL; p = p->Next )
    {
        fprintf( stream, "%s\n", p->Titel );
    }

    fprintf( stream, "\n" );
}

void FreeList( TCD *head )
{
    TCD *p = head;

    while ( p != NULL )
    {
        TCD *tmp = p;

        p = p->Next;

        free( tmp );
    }
}

int main( void )
{
    TCD *head = NULL, *tail = NULL;

    //create linked list with a bit of unsorted test data
    AddToList( &head, &tail, "string8" );
    AddToList( &head, &tail, "string4" );
    AddToList( &head, &tail, "string2" );
    AddToList( &head, &tail, "string7" );
    AddToList( &head, &tail, "string3" );
    AddToList( &head, &tail, "string5" );
    AddToList( &head, &tail, "string1" );
    AddToList( &head, &tail, "string6" );

    //print list before sorting
    fprintf( stderr, "List before sort:\n" );
    PrintList( stderr, head );

    //do the actual sorting
    Quicksort( head, tail, strcmp );

    //print list after sorting
    fprintf( stderr, "List after sort:\n" );
    PrintList( stderr, head );

    //free the linked list
    FreeList( head );

    return 0;
}

推荐阅读