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

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

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

Уважаемые ! Продолжаются мое обучение, а с ним и появляются новые вопросы. Пытаюсь остортировать двусвязный список быстрой сортировка. Делаю по аналогии с пузырком и с быстрой сортировкой массива. Вот код:
Листинг программы 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5.  typedef struct L {
  6. int value;
  7. char name[10];
  8. struct L *next, *prev;
  9. } ListItem;
  10.  
  11. static ListItem base,*current,*pos,*prev2,*next2,*current2,*current3;
  12. static int a,b,c,k,g,num;
  13.  
  14. void print_pos(void);
  15. void creation_zero(void);
  16. void creation(void);
  17. void scan_creation(void);
  18. void swap_sort(void);
  19. void quicksort(ListItem*,ListItem*,ListItem*);
  20. void start_pointer_sort(void);
  21.  
  22. int main(){
  23. creation_zero();
  24. do{
  25.  scan_creation();
  26. if(pos->value==0){
  27.     free(pos);
  28.     break;
  29. }
  30. creation();
  31. }
  32. while(1);
  33. print_pos();
  34. quicksort(current,current->next,current->prev);
  35. printf("\n\n");
  36. print_pos();
  37. return 0;
  38. }
  39.  
  40. void print_pos(){/*Печать всего списка*/
  41.     pos=current->prev;
  42. while(pos!=&base){
  43.     printf("\nname=%s                 \ttall=%d\n",pos->name,pos->value);
  44.     pos=pos->prev;
  45. }}
  46.  
  47. void creation_zero(){/*Создать нулевое звено*/
  48.     current = &base;
  49.     base.next = base.prev = &base;
  50.     num=0;
  51.     }
  52.  
  53. void scan_creation(){/*Выделение памяти и запись значений*/
  54.     pos = (ListItem*)malloc(sizeof(ListItem));
  55.     printf("\nWhat is your name? \t");
  56.     scanf("%s",&pos->name);
  57.     printf("\nHow tall are you? \t");
  58.     scanf("%d",&pos->value);
  59.     }
  60.  
  61. void creation(){/*Создание звена и определение его местоположения*/
  62.     pos->next = current->next;
  63.     pos->prev = current;
  64.     current->next->prev = pos;
  65.     current->next = pos;
  66.     num++;
  67. }
  68.  
  69. void quicksort(ListItem *k,ListItem *first,ListItem *last){//быстрая сортировка(указатель на структуру, на начало списка,на конец списка)
  70.     ListItem *i=first,*j=last;
  71.     ListItem *first1=i->prev,*last1=j->next;
  72.     int x=(first->value+last->value)/2;
  73.  
  74.     do {
  75.         while (i->value < x) i=i->next;
  76.        while (j->value > x) j=j->prev;
  77.  
  78.         if(i!=j) {
  79.                 if (i->value > j->value){
  80.             i->next->prev=j;
  81.             i->prev->next=j;
  82.             j->prev->next=i;
  83.             j->next->prev=i;
  84.             j->next=i->next;
  85.             i->next=last1;
  86.             i->prev=j->prev;
  87.             j->prev=first1;
  88.             i=j->next;
  89.             j=i->prev;
  90.             first1=i->prev;
  91.             last1=j->next;
  92.                 }
  93.         }
  94.     } while (i!=j);
  95.   if (last!=i)
  96.         quicksort(k,i,last);
  97.    if (first!=j)
  98.        quicksort(k,first,j);
  99. }
Если выключить рекурсию, и все условия, код с перестановкой местами ячеек работает. Подозреваю что что то не так в логических условиях. Помогите , наведите на правильную мысль! Спасибо"

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

textual
Листинг программы 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <assert.h>
  5. #include "llist.h"
  6.  
  7. #define NAME_LENGTH (32)
  8. #define get_name(s) ( scanf("%31s", (s)) == 1 )
  9.  
  10. typedef struct DATA {
  11.     char name[NAME_LENGTH];
  12.     int value;
  13. } data_t;
  14.  
  15. void * copy_data(const void * dataTemplate) {
  16.     void * ptr = malloc(sizeof(data_t));
  17.     assert(ptr);
  18.     return memcpy(ptr, dataTemplate, sizeof(data_t));
  19. }
  20.  
  21. void destroy_data(void * dataPtr) {
  22.     free(dataPtr);
  23. }
  24.  
  25. void print_data(const void * ptr) {
  26.     data_t * pData = (data_t*)ptr;
  27.     printf("%3d\t%s\n", pData->value, pData->name);
  28. }
  29.  
  30. int compare_data(const void * pA, const void * pB) {
  31.     data_t * a = (data_t*)pA;
  32.     data_t * b = (data_t*)pB;
  33.     int ret = a->value - b->value;
  34.     
  35.     return ( ret ) ? ret : strcmp(a->name, b->name);
  36. }
  37.  
  38. void print_help(void) {
  39.     printf("1 - help\n"
  40.             "2 - add value\n"
  41.             "3 - delete value\n"
  42.             "4 - dump list\n"
  43.             "5 - sort list\n"
  44.             "6 - find data\n"
  45.             "7 - change data\n"
  46.             "8 - list size\n"
  47.             "0 - quit\n\n"
  48.         );
  49. }
  50.  
  51. void flush_input(void) {
  52.     char c;
  53.     
  54.     while ( scanf("%c", &c) == 1 && c != '\n' )
  55.         ;
  56. }
  57.  
  58. int fill_data(data_t * pData) {
  59.     memset(pData, 0, sizeof(data_t));
  60.     printf("Name: ");
  61.     if ( ! get_name(pData->name) )
  62.         return -1;
  63.     printf("Value: ");
  64.     if ( scanf("%d", &(pData->value)) != 1 )
  65.         return -1;
  66.     flush_input();
  67.     
  68.     return 0;
  69. }
  70.  
  71. int menu(void) {
  72.     int ret;
  73.     
  74.     printf("[1 - help] > ");
  75.     if ( scanf("%d", &ret) != 1 ) {
  76.         flush_input();
  77.         return -1;
  78.     }
  79.     
  80.     flush_input();
  81.     return ret;
  82. }
  83.  
  84. int main(void) {
  85.     int ret, done = 0;
  86.     llist_t * list = llist_new(copy_data, destroy_data, compare_data);
  87.     assert(list);
  88.     
  89.     while ( ! done ) {
  90.         switch ( menu() ) {
  91.             case 1:
  92.                 print_help();
  93.                 break;
  94.             case 2: {
  95.                 data_t data;
  96.                 ret = fill_data(&data);
  97.                 assert(ret == 0);
  98.                 ret = llist_add(list, &data);
  99.                 assert(ret == 0);
  100.                 printf("Ok\n");
  101.                 
  102.                 break;
  103.             }
  104.             case 3: {
  105.                 data_t data;
  106.                 ret = fill_data(&data);
  107.                 assert(ret == 0);
  108.                 ret = llist_remove(list, &data);
  109.                 if ( ret )
  110.                     printf("Not in list!\n");
  111.                 else
  112.                     printf("Ok\n");
  113.                 
  114.                 break;
  115.             }
  116.             case 4:
  117.                 llist_foreach(list, print_data);
  118.                 break;
  119.             case 5:
  120.                 llist_sort(list, NULL);
  121.                 printf("Ok\n");
  122.                 break;
  123.             case 6: {
  124.                 data_t data;
  125.                 ret = fill_data(&data);
  126.                 assert(ret == 0);
  127.                 printf("%sound.\n", ( llist_contains(list, &data) ) ? "F" : "Not f");
  128.                 
  129.                 break;
  130.             }
  131.             case 7: {
  132.                 data_t oldData, newData;
  133.                 printf("Old data\n");
  134.                 ret = fill_data(&oldData);
  135.                 assert(ret == 0);
  136.                 printf("New data\n");
  137.                 ret = fill_data(&newData);
  138.                 assert(ret == 0);
  139.                 ret = llist_update(list, &oldData, &newData);
  140.                 printf("%s\n", ( ret ) ? "Error!\n" : "Ok");
  141.                 
  142.                 break;
  143.             }
  144.             case 8: 
  145.                 printf("%d items in list.\n", llist_size(list));
  146.                 break;
  147.             case 0:
  148.                 done = 1;
  149.                 break;
  150.             default:
  151.                 printf("Wrong choice!\n");
  152.                 break;
  153.         }
  154.     }
  155.     
  156.     llist_del(list);
  157.     
  158.     return 0;
  159. }

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

В данном коде реализована быстрая сортировка двусвязного списка. Список представляет собой структуру данных 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

Нужна аналогичная работа?

Оформи быстрый заказ и узнай стоимость

Бесплатно
Оформите заказ и авторы начнут откликаться уже через 10 минут
Похожие ответы