我仍在学习链表的工作原理，并且我有点难以使用 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;
您的代码存在几个问题：
-
partitionIdx->Prev = partitionIdx;行没有意义。它会导致节点指向自身。这不可能是正确的。链表的目的是让节点指向下一个节点和上一个节点，但从不指向自身。 -
您的函数
partition崩溃，因为它的参数Start有时会指向链表中超出End参数的位置。这是因为您调用函数Quicksort而不确保其Start参数不指向End参数之外的位置。 -
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, "%sn", 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;
}