Сортировка двустороннего списка - 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; static ListItem *current; static ListItem *pos; static ListItem *prev2; static ListItem *next2; static ListItem *current2; static int a,b,c,k,g; static int num; void print_pos(void); void creation_zero(void); void creation(void); void scan_creation(void); void sort(void); int main(){ creation_zero(); do{ scan_creation(); if(pos->value==0){ free(pos); break; } creation(); } while(1); sort(); 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; } return 0; } void creation_zero()/*Создать нулевое звено*/ { current = &base; base.next = base.prev = &base; num=0; return 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); return 0; } void creation()/*Создание звена и определение его местоположения*/ { pos->next = current->next; pos->prev = current; current->next->prev = pos; current->next = pos; num++; return 0; } void sort()// Сортировка пузырьком { next2=current->prev;//указатель для главного цикла(передвигает вперед по списку, после завершения внутреннего цикла) current->next=current->prev->prev;//Смотрим на следующий элемент после current->prev current2=current->prev;//Запоминем значения current->prev для перестановки местами. while(next2!=&base) /*Если next2 попадед в base то останавливаем цикл*/{ while(current->prev->prev!=&base)//Если следующий элемнт ceurrent->prev будет base, останавливаем цикл { if(current->prev->value>current->next->value){//Сама сортировка if(current->next->prev==&base){//Условие для того чтобы можно было сравнить посление элемнты и перставить current-prev на поледний current->prev->prev=current->next->prev; current->prev->next=current->next->prev->next; current->next->prev->next=current->prev; current->next->prev=current->prev; current->next->next=current2->next; current->prev=current->next; } else{ current->prev->prev=current->next->prev; current->prev->next=current->next->prev->next; current->next->prev->next=current->prev; current->next->prev=current->prev; current->next->next=current2->next; current->next=current->prev->prev; current2=current->prev; } } current->prev=current->next; current->next=current->prev->prev; current2=current->prev; } while(current->prev->next!=&base){//Возвращаем на место указатели current->prev=current->prev->next; } current2=current->prev; current->next=current->prev->prev; next2=next2->prev; } while(current->next->prev!=&base){//По оканчанию сортировки , возвращаем Current->next на место, current->prev уже должен быть на месте current->next=current->next->prev; } }
голову ломаю, но не могу найти причины(
Решение задачи: «Сортировка двустороннего списка»
textual
Листинг программы
#include <stdio.h> #include <string.h> #include <malloc.h> typedef struct L { char name[10]; struct L* next; struct L* prev; } list_t; int list_add(list_t** head, list_t** tail, const char* s); void list_clear(list_t** head, list_t** tail); //сортировка void list_sort(list_t** ph, list_t** pt){ list_t* p, *n, *e, *t, *i, *l; if((*ph == NULL) || ((*ph)->next == NULL)) return; p = n = e = NULL; for(i = l = t = *ph; (t != NULL) && (t->next != NULL); t = t->next->next) { l = i; i = i->next; } l->next = NULL; list_sort(ph, pt); list_sort(&i, pt); while((*ph != NULL) || (i != NULL)){ if(i == NULL) { n = *ph; *ph = (*ph)->next; } else if(*ph == NULL) { n = i; i = i->next; } else if(strcmp((*ph)->name, i->name) < 0) { n = *ph; *ph = (*ph)->next; } else { n = i; i = i->next; } if(p == NULL) p = n; else e->next = n; n->prev = e; e = n; } *ph = p; *pt = e; } int main(void) { list_t* p, *head = NULL, *tail = NULL; list_add(&head, &tail, "cccccc"); list_add(&head, &tail, "xxxxxx"); list_add(&head, &tail, "zzzzzz"); list_add(&head, &tail, "bbbbbb"); list_add(&head, &tail, "dddddd"); list_add(&head, &tail, "eeeeee"); list_add(&head, &tail, "aaaaaa"); list_sort(&head, &tail); list_sort(&head, &tail); for(p = head; p != NULL; p = p->next) printf("%s ", p->name); putchar('\n'); for(p = tail; p != NULL; p = p->prev) printf("%s ", p->name); putchar('\n'); list_clear(&head, &tail); return 0; } //добавление int list_add(list_t** head, list_t** tail, const char* s){ list_t* p = (list_t*)malloc(sizeof(list_t)); if(p != NULL){ strcpy(p->name, s); p->next = p->prev = NULL; if(*head == NULL) *head = *tail = p; else { p->prev = *tail; (*tail)->next = p; *tail = p; } } return (p != NULL); } //удаление void list_clear(list_t** head, list_t** tail){ list_t* t; while(*head != NULL){ t = *head; *head = (*head)->next; free(t); } *tail = NULL; }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д