链接列表上的c-bubble排序是在交换期间删除元素

Question

当前的大学学生和我正试图通过只交换链接而不交换数据来对链接列表进行排序(根据要求(

我的链接定义是：

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失败。(它并不总是跳过的最后一个元素，但有时会跳过列表中间的元素(

当我通过调试器运行排序函数时，我无法确定链接何时丢失或删除。循环和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);