Bubble Сортировать по двойному перечню с

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, или даже там is a temp->next. Если нет (т. Е. Если новый temp->next равен NULL), то обновление temp будет катастрофическим. Вам повезет завершить запуск сортировки без этого.