link 列表上的冒泡排序在交换期间删除元素

Question

当前的大学生和我正在尝试通过仅交换 link 而不是数据（根据要求）

来对 link 列表进行排序

我的link定义是：

typedef struct iorb {
        int base_pri;
        struct iorb *link;
        char filler[100];
} IORB;

我正在这样构建列表：

void buildList(IORB **h, int size,int(*prio)(int)){
    int counter = size;
        // loop will run until the size of the list is reached 
        while(size > 0){ 
                IORB *temp = (IORB*)malloc(sizeof(IORB)); //alocating memory on the stack for the link list
                temp->base_pri = (rand() % 100); // assigning random number as the base pointer
                sprintf(temp->filler, "request %d : base priority = %d : priority = %d \n",
                counter, temp->base_pri,(*prio)(temp->base_pri));
                temp->link = *h; // making sure the head points to the next item in the list.
                *h = temp;
                counter--;
                size--;
                
        }
}

这是我的排序函数：

void sortList(IORB* head,int (*prio)(int)){
    int swapped = 1;

    while(swapped)
    {
        //pointers for the last current and next node
        IORB **prev = &head, *curr, *next;

        swapped = 0;
        for(curr = head; curr; prev = &curr->link, curr = curr->link)
        {
            next = curr->link;

            if(next && (*prio)(curr->base_pri) > (*prio)(next->base_pri))
            {
                curr->link = next->link;
                next->link = curr;
                *prev = next;

                swapped = 1;
            }
        }
    }
}

priComp 是附加函数，定义为：

int priComp(int bs){
    return (bs * 3);
}

并显示列表：

void displayList(IORB* head){
    while(head != NULL)
    {
        printf("%s",head->filler);
        head = head->link;
        
    }
    
}

我遇到的问题：构建列表并使用显示功能后，我可以正确地看到列表但是在我调用排序函数并重新打印列表之后，有时列表会打印排序但大多数时候我会丢失元素

例如-

排序前：

request 1 : base priority = 10 : priority = 30
request 2 : base priority = 3 : priority = 9
request 3 : base priority = 53 : priority = 159

排序后：

request 2 : base priority = 3 : priority = 9
request 1 : base priority = 10 : priority = 30

列表无法打印请求 3。（它并不总是跳过最后一个元素，但有时会跳过列表中间的元素）

当我通过调试器运行排序函数时，我无法确定 link 何时丢失或删除。循环和 if 语句似乎正确流动。

Answer 1

正如上面 trincot 和 WhozCraig 在评论中所建议的那样，您的列表已排序，但问题在于您没有新的负责人。我用一个丑陋的解决方法来回答你的问题，因为你似乎无法更改函数原型。但是，我坚持认为这不是一个好的解决方案。

最后一个列表元素的空指针用于取回列表的头部。

首先，将这些行添加到 sortlist 函数的末尾。

IORB *curr;
for(curr = head; curr->link; curr = curr->link);
curr->link=head;

!!!!!!!!!不要直接使用排序列表。现在，你有一个无限循环列表!!!!

但是调用这个函数：uglyWorkaround(&mylist,priComp);

uglyWorkaround(IORB** mylist,int (*prio)(int))
{
    sortList(*mylist,priComp);

    IORB *curr = *mylist;    
    while(!((*prio)(curr->base_pri) > (*prio)(curr->link->base_pri)))
        curr = curr->link;
    *mylist=curr->link;
    curr->link=NULL;
}

*** 编辑：回答关于函数原型 ***澄清的评论 ***

WhozCraig 解决方案

void sortList2(IORB** head,int (*prio)(int)){
    int swapped = 1;

    while(swapped)
    {
        //pointers for the last current and next node
        IORB  **prev=head, *curr, *next;

        swapped = 0;
        for(curr = *head; curr; prev = &curr->link, curr = curr->link)
        {
            next = curr->link;

            if(next && (*prio)(curr->base_pri) > (*prio)(next->base_pri))
            {
                curr->link = next->link;
                next->link = curr;
                *prev = next;

                swapped = 1;
            }
        }
    }
}

并称它为：sortList2(&mylist,priComp);

link 列表上的冒泡排序在交换期间删除元素

bubble sort on link list is removing elements during swap

c

linked-list

bubble-sort