Быстрая сортировка двусвязного списка - C (СИ)

Узнай цену своей работы

Формулировка задачи:

Уважаемые ! Продолжаются мое обучение, а с ним и появляются новые вопросы. Пытаюсь остортировать двусвязный список быстрой сортировка. Делаю по аналогии с пузырком и с быстрой сортировкой массива. Вот код:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
 typedef struct L {
int value;
char name[10];
struct L *next, *prev;
} ListItem;
 
static ListItem base,*current,*pos,*prev2,*next2,*current2,*current3;
static int a,b,c,k,g,num;
 
void print_pos(void);
void creation_zero(void);
void creation(void);
void scan_creation(void);
void swap_sort(void);
void quicksort(ListItem*,ListItem*,ListItem*);
void start_pointer_sort(void);
 
int main(){
creation_zero();
do{
 scan_creation();
if(pos->value==0){
    free(pos);
    break;
}
creation();
}
while(1);
print_pos();
quicksort(current,current->next,current->prev);
printf("\n\n");
print_pos();
return 0;
}
 
void print_pos(){/*Печать всего списка*/
    pos=current->prev;
while(pos!=&base){
    printf("\nname=%s                 \ttall=%d\n",pos->name,pos->value);
    pos=pos->prev;
}}
 
void creation_zero(){/*Создать нулевое звено*/
    current = &base;
    base.next = base.prev = &base;
    num=0;
    }
 
void scan_creation(){/*Выделение памяти и запись значений*/
    pos = (ListItem*)malloc(sizeof(ListItem));
    printf("\nWhat is your name? \t");
    scanf("%s",&pos->name);
    printf("\nHow tall are you? \t");
    scanf("%d",&pos->value);
    }
 
void creation(){/*Создание звена и определение его местоположения*/
    pos->next = current->next;
    pos->prev = current;
    current->next->prev = pos;
    current->next = pos;
    num++;
}
 
void quicksort(ListItem *k,ListItem *first,ListItem *last){//быстрая сортировка(указатель на структуру, на начало списка,на конец списка)
    ListItem *i=first,*j=last;
    ListItem *first1=i->prev,*last1=j->next;
    int x=(first->value+last->value)/2;
 
    do {
        while (i->value < x) i=i->next;
       while (j->value > x) j=j->prev;
 
        if(i!=j) {
                if (i->value > j->value){
            i->next->prev=j;
            i->prev->next=j;
            j->prev->next=i;
            j->next->prev=i;
            j->next=i->next;
            i->next=last1;
            i->prev=j->prev;
            j->prev=first1;
            i=j->next;
            j=i->prev;
            first1=i->prev;
            last1=j->next;
                }
        }
    } while (i!=j);
  if (last!=i)
        quicksort(k,i,last);
   if (first!=j)
       quicksort(k,first,j);
}
Если выключить рекурсию, и все условия, код с перестановкой местами ячеек работает. Подозреваю что что то не так в логических условиях. Помогите , наведите на правильную мысль! Спасибо"

Решение задачи: «Быстрая сортировка двусвязного списка»

textual
Листинг программы
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "llist.h"
 
#define NAME_LENGTH (32)
#define get_name(s) ( scanf("%31s", (s)) == 1 )
 
typedef struct DATA {
    char name[NAME_LENGTH];
    int value;
} data_t;
 
void * copy_data(const void * dataTemplate) {
    void * ptr = malloc(sizeof(data_t));
    assert(ptr);
    return memcpy(ptr, dataTemplate, sizeof(data_t));
}
 
void destroy_data(void * dataPtr) {
    free(dataPtr);
}
 
void print_data(const void * ptr) {
    data_t * pData = (data_t*)ptr;
    printf("%3d\t%s\n", pData->value, pData->name);
}
 
int compare_data(const void * pA, const void * pB) {
    data_t * a = (data_t*)pA;
    data_t * b = (data_t*)pB;
    int ret = a->value - b->value;
    
    return ( ret ) ? ret : strcmp(a->name, b->name);
}
 
void print_help(void) {
    printf("1 - help\n"
            "2 - add value\n"
            "3 - delete value\n"
            "4 - dump list\n"
            "5 - sort list\n"
            "6 - find data\n"
            "7 - change data\n"
            "8 - list size\n"
            "0 - quit\n\n"
        );
}
 
void flush_input(void) {
    char c;
    
    while ( scanf("%c", &c) == 1 && c != '\n' )
        ;
}
 
int fill_data(data_t * pData) {
    memset(pData, 0, sizeof(data_t));
    printf("Name: ");
    if ( ! get_name(pData->name) )
        return -1;
    printf("Value: ");
    if ( scanf("%d", &(pData->value)) != 1 )
        return -1;
    flush_input();
    
    return 0;
}
 
int menu(void) {
    int ret;
    
    printf("[1 - help] > ");
    if ( scanf("%d", &ret) != 1 ) {
        flush_input();
        return -1;
    }
    
    flush_input();
    return ret;
}
 
int main(void) {
    int ret, done = 0;
    llist_t * list = llist_new(copy_data, destroy_data, compare_data);
    assert(list);
    
    while ( ! done ) {
        switch ( menu() ) {
            case 1:
                print_help();
                break;
            case 2: {
                data_t data;
                ret = fill_data(&data);
                assert(ret == 0);
                ret = llist_add(list, &data);
                assert(ret == 0);
                printf("Ok\n");
                
                break;
            }
            case 3: {
                data_t data;
                ret = fill_data(&data);
                assert(ret == 0);
                ret = llist_remove(list, &data);
                if ( ret )
                    printf("Not in list!\n");
                else
                    printf("Ok\n");
                
                break;
            }
            case 4:
                llist_foreach(list, print_data);
                break;
            case 5:
                llist_sort(list, NULL);
                printf("Ok\n");
                break;
            case 6: {
                data_t data;
                ret = fill_data(&data);
                assert(ret == 0);
                printf("%sound.\n", ( llist_contains(list, &data) ) ? "F" : "Not f");
                
                break;
            }
            case 7: {
                data_t oldData, newData;
                printf("Old data\n");
                ret = fill_data(&oldData);
                assert(ret == 0);
                printf("New data\n");
                ret = fill_data(&newData);
                assert(ret == 0);
                ret = llist_update(list, &oldData, &newData);
                printf("%s\n", ( ret ) ? "Error!\n" : "Ok");
                
                break;
            }
            case 8: 
                printf("%d items in list.\n", llist_size(list));
                break;
            case 0:
                done = 1;
                break;
            default:
                printf("Wrong choice!\n");
                break;
        }
    }
    
    llist_del(list);
    
    return 0;
}

Объяснение кода листинга программы

В данном коде реализована быстрая сортировка двусвязного списка. Список представляет собой структуру данных llist_t, которая содержит функции для работы с этим списком. Код включает в себя следующие функции:

  1. copy_data - функция для копирования данных из одного указателя в другой.
  2. destroy_data - функция для освобождения памяти, выделенной под данные.
  3. print_data - функция для вывода данных на экран.
  4. compare_data - функция для сравнения двух элементов списка.
  5. print_help - функция для вывода на экран списка команд.
  6. flush_input - функция для очистки входного потока данных.
  7. fill_data - функция для заполнения структуры данных data_t.
  8. menu - функция для вывода на экран списка команд и выбора команды пользователем.
  9. main - основная функция программы. В основной функции программы происходит инициализация списка, заполнение его данными, выбор команды пользователем и выполнение этой команды. После выполнения всех команд программа выводит сообщение Ok и завершается.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

14   голосов , оценка 4.071 из 5
Похожие ответы