c - 在c中的通用链表上使用选择排序

Question

我有一个双向链接的通用链表。我正在尝试对列表的节点数据可能是什么进行排序。在对整数数组进行排序时，我可以使用此选择排序，但修改它以对链接列表进行排序时，它无法排序。以下是来自各种 .c 文件的足够代码来测试排序。我正在使用 ints 列表进行测试。我认为只交换节点中的数据比交换整个节点并且需要重置每个节点的 node->next 和 node->prev 更容易。非常感谢您提前提供的帮助!

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

struct node
{
    void * data;
    struct node * next;
    struct node * prev;
};
typedef struct node Node;

struct linkedlist
{
    Node * head;
    int size;
};
typedef struct linkedlist LinkedList;

struct my_int
{
    int value;
};
typedef struct my_int MyInt;

LinkedList * linkedList()
{
    LinkedList * list = (LinkedList*)malloc(sizeof(LinkedList));
    list->head = malloc(sizeof(Node)); // Dummy head node
    list->size = 0;
    return list;
}

// function pointer to compare node data of int
int compareInt(const void * p1, const void * p2)
{
    if(p1 == NULL || p2 == NULL)
    {
        perror("Method compareInt() failed - NULL parameter");
        exit(-99);
    }
    MyInt * int1 = (MyInt*)p1;
    MyInt * int2 = (MyInt*)p2;
    if(int1 < int2)
        return -1;
    if(int1 > int2)
        return 1;
    return 0;
}

void addFirst(LinkedList * theList, int data)
{
    if(theList == NULL)
    }
        perror("Call to addFirst() failed - passed in LinkedList * was NULL\n");
        exit(-99);
    }
    Node * nn = (Node*)calloc(1,sizeof(Node));
    nn->next = theList->head->next;
    theList->head->next = nn;
    nn->prev = theList->head;
    nn->data = data;
    theList->size = theList->size + 1;
}

void sort(LinkedList * theList, int (*compare)(const void *, const void *))
{
    Node * cur = theList->head->next;
    Node * temp = malloc(sizeof(Node));
    for(; cur->next != NULL; cur = cur->next)
    {
        Node * minNode = cur;
        for(Node * j = cur->next; j != NULL; j = j->next)
        {
            if(compare(j, minNode) < 0)
                minNode = j;
        }
        temp->data = minNode->data;
        minNode->data = cur->data;
        cur->data = temp->data;
    }
    free(temp);
}

// Driver to test the sort
int main()
{
    LinkedList * intList = linkedList();
    addFirst(intList,3);
    addFirst(intList,5);
    addFirst(intList,4);
    addFirst(intList,1);
    addFirst(intList,2);

    Node * cur = intList->head->next;
    while(cur != NULL)
    {
        printf("%d\n",cur->data);
        cur = cur->next;
    }
    printf("\n");

    sort(intList, compareInt);

    cur = intList->head->next;
    while(cur != NULL)
    {
        printf("%d\n",cur->data);
        cur = cur->next;
    }
    return 0;
}

Answer 1

快速浏览一下您的compareInt函数，您正在比较指针而不是它们指向的值:

MyInt * int1 = (MyInt*)p1;
MyInt * int2 = (MyInt*)p2;
if(int1 < int2)

我认为你需要:

if (*int1 < *int2) etc...