c - 双链表冒泡排序

Question

这是我的双链表实现和冒泡排序。其他功能运行良好，但在我对列表进行冒泡排序后，打印功能没有给出任何输出。

//
//  Double_linked_list.c
//
//
//  Created by Dengke Liu on 9/7/15.
//
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#include "list.h"


// initialize the list structure;
void init(slist_t *list){
    list->head=NULL;
    list->tail=NULL;
}

// add a string to the end of the list
void append(slist_t *list, char *val){

    // creating a newItem object
    list_item_t* newItem = (list_item_t*)malloc(sizeof(list_item_t));
    newItem->value = val;
    newItem->next=NULL;

    // if there are no elements, just use newItem as head
    if (!list->head) {
        newItem->prev=NULL;
        list->head=newItem;
        list->tail=newItem;
    }else{
        // otherwise append the node and point the tail at the end
        newItem->prev=list->tail;
        list->tail->next=newItem;
        list->tail=newItem;
    }
}

// print the elements of the list
void print(slist_t *list){

    list_item_t* temp=list->head;
    while (temp!=NULL) {
        printf("%s\n", temp->value);
        temp=temp->next;
    }
}

// empty the list
void empty(slist_t *list){

    list_item_t *temp=list->head;
    while (temp->next!=NULL) {
        temp=temp->next;
        free(temp);
    }
    free(list->head);
}

// sort the elements in list in lexical order using bubble sort
void bubblesort(slist_t *list){

    if (list->head==NULL) {
        printf("this is an empty list");
    }

    // to record the comparision state
    bool swapped=true;
    list_item_t *temp;

    while (swapped) {

        swapped=false;
        temp=list->head;

        // iterate through the list to swap unordered elements
        while (temp!=list->tail) {
            // compare two elements, if they are disordered, then swap
            if(strcmp(temp->value, temp->next->value)>0){

                // swap the elements
                if (temp->prev!=NULL) {
                    temp->prev->next=temp->next;
                }
                if (temp->next->next!=NULL) {
                    temp->next->next->prev=temp;
                }

                temp->next=temp->next->next;
                temp->next->next=temp->prev;
                temp->next->next=temp;
                temp->prev=temp->next;

                // change the swap record
                swapped=true;
            }
            temp=temp->next;
        }

        print(list);
    }
}

int main(){
    slist_t *list;
    init(list);
    append(list, "blue");
    append(list, "yellow");
    append(list, "black");
    append(list, "red");
    append(list, "green");
    print(list);
    bubblesort(list);
    print(list);
    empty(list);
    return 0;
}

main() 中的第一个打印函数给出了正确的输出，而第二个打印函数没有给出任何输出。谁能帮我调试一下？

Answer 1

你的程序在一般形式上看起来是合理的，但我越看它就越发现细节上的错误。特别是，

1) 在函数 main() 中，您声明变量 list，一个指针，但从未对其进行初始化。然后，您将这个不确定的值传递给 init() 函数，该函数继续取消引用它，就好像它是一个有效指针一样。这会产生未定义的行为。您可以为 list 动态分配存储空间，但在这种情况下，这样做更容易:

int main() {
    slist_t my_list;
    slist_t *list = &my_list;
    /* ... */

2) 您的 bubblesort() 函数在执行涉及节点的交换时无法更新 list->head 和 list->tail那些指向。这将在排序过程中和排序之后引起问题。

3) 您的 bubblesort() 函数没有正确交换列表节点。有不止一种方法可以做到，但您实际实现的不是其中之一。它首先在 temp->next->next=temp->prev 处中断，因为此时 temp->next 已经更新，结果 temp->next->next 不是您要修改的指针之一。构造这种交换的一种更简单的方法是从列表中删除节点 temp，然后在稍后重新插入一个位置。仔细跟踪哪个指针指向什么。它可以帮助绘制它的图表。

4) 您的bubblesort() 函数应避免在执行交换的内部循环迭代期间设置temp = temp->next。在那些情况下，您不知道 temp 与新的 temp->next 相比如何，甚至不知道是否有 temp->next 不再。如果没有(即如果新的 temp->next 是 NULL)那么更新 temp 将是灾难性的。如果没有发生这种情况，您将很幸运地完成排序例程的运行。