1

我正在编写一个冒泡排序函数来对双向链表中的节点进行排序。我的功能非常接近工作，但我错过了一些简单的东西，我无法弄清楚。

void sort (struct lnode** head, void (*swapPtr) (struct lnode** head, struct lnode* n1, struct lnode* n2),
                            int(*comparePtr) (void* v1, void* v2)) {

struct lnode* next;
struct lnode* temp = *head;
int comp;
struct lnode* temp2;
int count = 0;

while (temp != NULL) {
    temp2 = nodeGetNext(temp);
    temp = temp2;
    count++;

}

temp = *head;
for(int i = 0; i < count; i++) {
    next = nodeGetNext(temp);


    comp = comparePtr(temp,next);
    if (comp == 1)
        swapPtr(head, temp, next);
    else if (comp == -1)
        swapPtr(head, next, temp);

    temp = nodeGetNext(next);
}


}

当我运行该函数时，它只交换前两个节点。我猜我在for循环结束时没有正确设置温度。我尝试了一些不同的事情，但没有任何成功。我将不胜感激任何帮助！

4

2 回答 2

2

看起来你只在列表中传递了一次。您需要继续循环遍历列表并继续交换，直到没有可交换的内容。查看此答案以获取示例，并查看Wikipedia以获取详细的算法描述。

于 2012-10-10T02:50:46.277 回答
0

我使用嵌套循环完成了此操作，因为您遍历列表的次数等于节点数减 1，这是最坏的情况。当没有从上一次传递中完成交换时，传递的循环将停止（感谢失谐）。

hasSwap = 1; /* enable the first pass to execute */
for(i=0; i<len-1 && hasSwap == 1; i++)
{
    hasSwap = 0; /* initially, there is no swap in this pass */
    for(j=0; j<len-1; j++)
    {
       if(l[j] > l[j+1])
       {
            t = l[j];
            l[j] = l[j+1];
            l[j+1] = t; 
            hasSwap = 1; /* the pass has at least 1 swap, if not set, there will be no other pass */
       } 
    }

    printf("Pass %d: ", i);
    for(k=0; k<len; k++)
    {
       printf("%d", l[k]);
    }
    printf("\n");
}

示例 1：最坏的情况，列表按降序排序。

5、4、3

第一关：

i = 0, j = 0, hasSwap = 1 -> [5], [4], 3

i = 0, j = 1, hasSwap = 1 -> 4, [5], [3]

有前一次通过的掉期吗？是的，继续。

第二关：

i = 1, j = 0, hasSwap = 1 -> [4], [3], 5

i = 1, j = 1, hasSwap = 1 -> 3, [4], [5]

有前一次通过的掉期吗？没有，但达到了最大通过次数。

示例 2：这已经排序。

3、4、5

第一关：

i = 0, j = 0, hasSwap = 0 -> 3, 4, 5

i = 0, j = 1, hasSwap = 0 -> 3, 4, 5

有前一次通过的掉期吗？没有，停下。

于 2012-10-10T02:57:35.067 回答