Как отсортировать односвязный список си
Pers.narod.ru. Алгоритмы. Cортировка односвязного списка перестановкой указателей
Сортировка односвязного списка — одна из самых типовых «головоломных» задач для начинающих.
В принципе, если список состоит, к примеру, из больших структур, теоретически имеет смысл при сортировке не копировать данные, а менять их местами с помощью имеющихся в структуре указателей на связанные элементы.
Но на практике даже простейшая пузырьковая сортировка заметно усложняется связями указателей. поэтому в инете куча неработающих решений и неверных мнений, не стану приводить ссылки на все.
По-моему, вся беда типовых «студенческих» кодов в том, что авторы пытались применить любимый «пузырёк» к списку по аналогии с массивом, а в списке из-за перестановок указателей начиналась путаница.
Метод вставок рулит, что б там не писали на форумах. Остальные комменты в исходнике:
#include #include #include #include #define MAX 30 typedef struct student < unsigned char f[MAX]; //Фамилия int ekz[4]; //4 оценки student *next; //Указатель на следующего студента >; int show (student *head) < //Показать список, начиная с эл. head и вернуть кол-во записей int count=0; while (1) < printf ("\n%s",head->f); for (int i=0; iekz[i]); count++; if (!head->next) break; head=head->next; > return count; > student *sort (student *ph) < //Сортируем список по алфавиту (фамилии, полю f) и возвращаем //указатель на начало измененного списка student *q,*out=NULL,*p,*pr; //out - выход - сначала пуст while (ph !=NULL) < //пока не конец входного списка q = ph; ph = ph->next; //исключить очередной элемент for (p=out,pr=NULL; p!=NULL && strcmp(q->f,p->f)>0; pr=p,p=p->next); //ищем, куда включить очередной элемент - тут strcmp //задает критерий сравнения элементов, в вашей задаче м.б. другой if (pr==NULL) < q->next=out; out=q; > //включение в начало else < q->next=p; pr->next=q; > //или после предыдущего > return out; > void main () < student group[] = < //В начале фамилии в списке расставлены как в массиве - //предыдущий элемент показывает на следующий ,&group[1]>, ,&group[2]>, ,&group[3]>, ,&group[4]>, ,NULL> >; printf ("\nИсходный список:"); int count=show (&group[0]); printf ("\nВсего записей: %d",count); //Сортируем список структур по алфавиту student *ptr=sort (group); printf ("\nОтсортированный список:"); show (ptr); getchar(); >
Проверил в консольном Borland C++ 3.1, работает, завершается без Null pointer assignment, значит, есть надежда, что нормально. хотя вырожденные случаи не смотрел, а писал в спешке, мож чего и не так, тогда жду поправок.
Как отсортировать односвязный список си
Сортировка односвязного списка
Посмотрите пожалуйста свежим взглядом на функцию sort не могу понять что не правильно она зациклятся(((
#include #include #include #include #include #include struct Node< int d; char *NM; Node *next; >; Node * first(FILE * fp)< int d; fscanf(fp,"%d",&d); char str[50]; fgets(str,50,fp); int strln=strlen(str); Node *pv=new Node; pv->NM=new char [strln+1]; strcpy(pv->NM,str); pv->d=d; pv->next=0; return pv; > void add(Node **pend, FILE * fp)< int d; fscanf(fp,"%d",&d); char str[50]; fgets(str,50,fp); int strln=strlen(str); Node *pv=new Node; pv->NM=new char [strln+1]; strcpy(pv->NM,str); pv->d=d; pv->next=0; (*pend)->next=pv; *pend=pv; > void sort(Node **pbeg,Node **pend) < Node *f=*pbeg; Node *temp=0; Node *tmp=0; Node *pv=f->next; int l=0; int min; while (f->next)< min=f->d; l=0; pv=f->next; while(pv)< if(pv->dd; l++; tmp=pv; > pv=pv->next; > if(l>0) < if(f==*pbeg) temp=f->next; f->next=tmp->next; tmp->next=temp; f=temp; > else next;> > > void print(Node *pv) < while (pv)< printf("%d %s",pv->d,pv->NM); pv=pv->next; > > int main() < clrscr(); FILE * fp; fp=fopen("D:\\WORK\\TC\\7.txt","r+"); if (fp==NULL) < printf("Ochibka otkritia fila 7.txt"); >Node *pbeg=first(fp); Node *pend=pbeg; while(!feof(fp)) < add(&pend,fp); >Node *pv=pbeg; print(pv); printf("\n\n"); sort(&pbeg,&pend); print(pv); fclose(fp); while(pv) < delete[]pv->NM; pv=pv->next; > getch(); return 0; > Форумчанин
Регистрация: 02.10.2009
Сообщений: 104
что то у тебя много кода, попробуй переделать сортировку методом вставок по аналогии:
list *sort(list *ph) // функция возвращает заголовок нового списка < list *q, *out, *p , *pr; out = NULL; // выходной список пуст while (ph !=NULL) // пока не пуст входной список < q = ph; ph = ph->next; // исключить очередной // поиск места включения for ( p=out,pr=NULL; p!=NULL && q->val>p->val; pr=p,p=p->next); if (pr==NULL) // включение перед первым < q->next=out; out=q; > else // иначе после предыдущего < q->next=p; pr->next=q; > > return out; >| blackbanny |
| Посмотреть профиль |
| Найти ещё сообщения от blackbanny |
| Похожие темы | ||||
| Тема | Автор | Раздел | Ответов | Последнее сообщение |
| СИ. Списки. Описание структуры односвязного списка | Jane-sad | Помощь студентам | 9 | 17.05.2010 14:40 |
| Мин. элемент. односвязного списка в СИ | Sultan237 | Общие вопросы C/C++ | 0 | 22.03.2010 23:24 |
| Сортировка односвязного списка | btf | Общие вопросы C/C++ | 0 | 15.02.2010 14:40 |
| Сортировка списка | DOJ | Общие вопросы C/C++ | 3 | 23.08.2009 19:36 |
| Cортировка односвязного списка | alesfoss | Общие вопросы C/C++ | 3 | 30.03.2009 19:46 |
Сортировка односвязного списка
Здравствуйте уважаемые киберфорумщики!
Нужна срочная помощь.
В общем у меня есть задача которую нужно сделать но нет ни знаний ни времени на изучение сего вопроса.
Поэтому прошу помочь мне с этим знающих людей. Желательно с объяснениями)
Построить класс для работы с односвязным списком. Элементы списка — целые числа. сформировать
список, упорядочить элементы списка по возрастанию, используя сортировку: a) методом
выбора, б) методом пузырька, в) методом вставки.
Лучшие ответы ( 1 )
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:
Сортировка односвязного списка
Доброго времени суток. Третий день пытаюсь понять как мне отсортировать сведения структуры.
Сортировка односвязного списка
Помогите пишу курсач сделал все ф-ции кроме сортировки в голову не приходит как что не пробовал без.
Сортировка односвязного списка
Прошу сразу не ругаться ,знаю что на форуме миллион разных кодов сортировки ,но я не понимаю как их.
Сортировка односвязного списка
Добрый день форумчанам! Есть задача но не знаю как написать ее так как не знаю динамического.
Почетный модератор
5850 / 2861 / 392
Регистрация: 01.11.2011
Сообщений: 6,907
Для нахождения остальных десяти тысяч тем, воспользуйтесь поиском по форуму: поиск по форуму.
838 / 641 / 940
Регистрация: 26.06.2015
Сообщений: 1,409
Сообщение было отмечено taiggerrock как решение
Решение
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178
#include #include struct node { node* next; int val; }; class slist { private: node* lst; size_t cnt; public: slist(void); ~slist(); bool add(int val); void clear(void); void isort(void); void bsort(void); void ssort(void); size_t size(void) const { return cnt; } bool empty(void) const { return (lst == NULL); } node* begin(void) const { return lst; } node* begin(void) { return lst; } }; void slist_print(std::ostream& _out, const slist& lst); int main(void){ int n; slist l1, l2, l3; for(int i = 0; i 32; ++i){ n = rand() % 10; l1.add(n); l2.add(n); l3.add(n); } l1.bsort(); l2.ssort(); l3.isort(); slist_print(std::cout, l1); slist_print(std::cout, l2); slist_print(std::cout, l3); return 0; } slist::slist(void):lst(NULL), cnt(0){} slist::~slist(){ clear(); } //Сортировка вставками void slist::isort(void){ node* a, *b, *p, *h = NULL; for(node* i = lst; i != NULL; ) { a = i; i = i->next; b = h; for(p = NULL; (b != NULL) && (a->val > b->val); ) { p = b; b = b->next; } if(p == NULL){ a->next = h; h = a; } else { a->next = b; p->next = a; } } if(h != NULL) lst = h; } //Пузырьковая сортировка void slist::bsort(void){ node* t, *m, *a, *b; if(lst == NULL) return; for(bool go = true; go; ){ go = false; a = t = lst; b = lst->next; while(b != NULL){ if(a->val > b->val){ if(t == a) lst = b; else t->next = b; a->next = b->next; b->next = a; m = a, a = b, b = m; go = true; } t = a; a = a->next; b = b->next; } } } //Сортировка выбором void slist::ssort(void){ node* a, *b; node* p1, *p2, *r1, *r2; for(p1 = r1 = lst; p1 != NULL; p1 = p1->next){ a = p2 = r2 = p1; for(b = p1->next; b != NULL; b = b->next){ if(b->val p2->val){ r2 = a; p2 = b; } a = b; } if(p1 != p2){ if(p1 == lst) lst = p2; else r1->next = p2; b = p2->next; if(p1 == r2){ p2->next = p1; p1->next = b; } else { a = p1->next; r1->next = p2; r2->next = p1; p1->next = b; p2->next = a; } p1 = p2; } r1 = p1; } } //добавление bool slist::add(int val){ node* p = new (std::nothrow) node(); if(p != NULL){ p->val = val; p->next = lst; lst = p; ++cnt; } return (p != NULL); } //удаление всех void slist::clear(void){ node* t; while(lst != NULL){ t = lst; lst = lst->next; delete t; } cnt = 0; } //печать void slist_print(std::ostream& _out, const slist& lst){ for(const node* p = lst.begin(); p != NULL; p = p->next) _out - >val <' '; _out :: endl; }
Односвязный список
О дносвязный список – структура данных, в которой каждый элемент (узел) хранит информацию, а также ссылку на следующий элемент. Последний элемент списка ссылается на NULL.
Для нас односвязный список полезен тем, что
- 1) Он очень просто устроен и все алгоритмы интуитивно понятны
- 2) Односвязный список – хорошее упражнение для работы с указателями
- 3) Его очень просто визаулизировать, это позволяет «в картинках» объяснить алгоритм
- 4) Несмотря на свою простоту, односвязные списки часто используются в программировании, так что это не пустое упражнение.
- 5) Эта структуру данных можно определить рекурсивно, и она часто используется в рекурсивных алгоритмах.
Для простоты рассмотрим односвязный список, который хранит целочисленное значение.
Односвязный список
Односвязный список состоит из узлов. Каждый узел содержит значение и указатель на следующий узел, поэтому представим его в качестве структуры
typedef struct Node < int value; struct Node *next; >Node;
Чтобы не писать каждый раз struct мы определили новый тип.
Теперь наша задача написать функцию, которая бы собирала список из значений, которые мы ей передаём. Стандартное имя функции – push, она должна получать в качестве аргумента значение, которое вставит в список. Новое значение будет вставляться в начало списка. Каждый новый элемент списка мы должны создавать на куче. Следовательно, нам будет удобно иметь один указатель на первый элемент списка.
Node *head = NULL;
Вначале списка нет и указатель ссылается на NULL.
Для добавления нового узла необходимо
- 1) Выделить под него память.
- 2) Задать ему значение
- 3) Сделать так, чтобы он ссылался на предыдущий элемент (или на NULL, если его не было)
- 4) Перекинуть указатель head на новый узел.
1) Создаём новый узел
Создали новый узел, на который ссылается локальная переменная tmp
2) Присваиваем ему значение
Присвоили ему значение
3) Присваиваем указателю tmp адрес предыдущего узла
Перекинули указатель tmp на предыдущий узел
4) Присваиваем указателю head адрес нового узла
Перекинули указатель head на вновь созданный узел tmp
5) После выхода из функции переменная tmp будет уничтожена. Получим список, в который будет вставлен новый элемент.
Новый узел добавлен
void push(Node **head, int data) < Node *tmp = (Node*) malloc(sizeof(Node)); tmp->value = data; tmp->next = (*head); (*head) = tmp; >
Так как указатель head изменяется, то необходимо передавать указатель на указатель.
Теперь напишем функцию pop: она удаляет элемент, на который указывает head и возвращает его значение.
Если мы перекинем указатель head на следующий элемент, то мы потеряем адрес первого и не сможем его удалить и тем более вернуть его значения. Для этого необходимо сначала создать локальную переменную, которая будет хранить адрес первого элемента
Локальная переменная хранит адрес первого узла
Уже после этого можно удалить первый элемент и вернуть его значение
Перекинули указатель head на следующий элемент и удалили узел
int pop(Node **head) < Node* prev = NULL; int val; if (head == NULL) < exit(-1); >prev = (*head); val = prev->value; (*head) = (*head)->next; free(prev); return val; >
Не забываем, что необходимо проверить на NULL голову.
Таким образом, мы реализовали две операции push и pop, которые позволяют теперь использовать односвязный список как стек. Теперь добавим ещё две операции — pushBack (её ещё принято называть shift или enqueue), которая добавляет новый элемент в конец списка, и функцию popBack (unshift, или dequeue), которая удаляет последний элемент списка и возвращает его значение.
Для дальнейшего разговора необходимо реализовать функции getLast, которая возвращает указатель на последний элемент списка, и nth, которая возвращает указатель на n-й элемент списка.
Так как мы знаем адрес только первого элемента, то единственным способом добраться до n-го будет последовательный перебор всех элементов списка. Для того, чтобы получить следующий элемент, нужно перейти к нему через указатель next текущего узла
Node* getNth(Node* head, int n) < int counter = 0; while (counter < n && head) < head = head->next; counter++; > return head; >
Переходя на следующий элемент не забываем проверять, существует ли он. Вполне возможно, что был указан номер, который больше размера списка. Функция вернёт в таком случае NULL. Сложность операции O(n), и это одна из проблем односвязного списка.
Для нахождение последнего элемента будем передирать друг за другом элементы до тех пор, пока указатель next одного из элементов не станет равным NULL
Node* getLast(Node *head) < if (head == NULL) < return NULL; >while (head->next) < head = head->next; > return head; >
Теперь добавим ещё две операции — pushBack (её ещё принято называть shift или enqueue), которая добавляет новый элемент в конец списка, и функцию popBack (unshift, или dequeue), которая удаляет последний элемент списка и возвращает его значение.
Для вставки нового элемента в конец сначала получаем указатель на последний элемент, затем создаём новый элемент, присваиваем ему значение и перекидываем указатель next старого элемента на новый
void pushBack(Node *head, int value) < Node *last = getLast(head); Node *tmp = (Node*) malloc(sizeof(Node)); tmp->value = value; tmp->next = NULL; last->next = tmp; >
Односвязный список хранит адрес только следующего элемента. Если мы хотим удалить последний элемент, то необходимо изменить указатель next предпоследнего элемента. Для этого нам понадобится функция getLastButOne, возвращающая указатель на предпоследний элемент.
Node* getLastButOne(Node* head) < if (head == NULL) < exit(-2); >if (head->next == NULL) < return NULL; >while (head->next->next) < head = head->next; > return head; >
Функция должна работать и тогда, когда список состоит всего из одного элемента. Вот теперь есть возможность удалить последний элемент.
void popBack(Node **head) < Node *lastbn = NULL; //Получили NULL if (!head) < exit(-1); >//Список пуст if (!(*head)) < exit(-1); >lastbn = getLastButOne(*head); //Если в списке один элемент if (lastbn == NULL) < free(*head); *head = NULL; >else < free(lastbn->next); lastbn->next = NULL; > >
Удаление последнего элемента и вставка в конец имеют сложность O(n).
Можно написать алгоритм проще. Будем использовать два указателя. Один – текущий узел, второй – предыдущий. Тогда можно обойтись без вызова функции getLastButOne:
int popBack(Node **head) < Node *pFwd = NULL; //текущий узел Node *pBwd = NULL; //предыдущий узел //Получили NULL if (!head) < exit(-1); >//Список пуст if (!(*head)) < exit(-1); >pFwd = *head; while (pFwd->next) < pBwd = pFwd; pFwd = pFwd->next; > if (pBwd == NULL) < free(*head); *head = NULL; >else < free(pFwd->next); pBwd->next = NULL; > >
Теперь напишем функцию insert, которая вставляет на n-е место новое значение. Для вставки, сначала нужно будет пройти до нужного узла, потом создать новый элемент и поменять указатели. Если мы вставляем в конец, то указатель next нового узла будет указывать на NULL, иначе на следующий элемент
void insert(Node *head, unsigned n, int val) < unsigned i = 0; Node *tmp = NULL; //Находим нужный элемент. Если вышли за пределы списка, то выходим из цикла, //ошибка выбрасываться не будет, произойдёт вставка в конец while (i < n && head->next) < head = head->next; i++; > tmp = (Node*) malloc(sizeof(Node)); tmp->value = val; //Если это не последний элемент, то next перекидываем на следующий узел if (head->next) < tmp->next = head->next; //иначе на NULL > else < tmp->next = NULL; > head->next = tmp; >
Покажем на рисунке последовательность действий
Создали новый узел и присвоили ему значение
После этого делаем так, чтобы новый элемент ссылался на следующий после n-го
Теперь значение next нового узла хранит адрес того же узла, что и элемент, на который ссылается head
Перекидываем указатель next n-го элемента на вновь созданный узел
Теперь узел, адрес которого хранит head, указывает на новый узел tmp
Функция удаления элемента списка похожа на вставку. Сначала получаем указатель на элемент, стоящий до удаляемого, потом перекидываем ссылку на следующий элемент за удаляемым, потом удаляем элемент.
int deleteNth(Node **head, int n) < if (n == 0) < return pop(head); >else < Node *prev = getNth(*head, n-1); Node *elm = prev->next; int val = elm->value; prev->next = elm->next; free(elm); return val; > >
Рассмотрим то же самое в картинках. Сначала находим адреса удаляемого элемента и того, который стоит перед ним
Для удаления узла, на который ссылается elm необходим предыдущий узел, адрес которого хранит prev
После чего прокидываем указатель next дальше, а сам элемент удаляем.
Прекидываем указатель на следующий за удалённым узел и освобождаем память
Кроме создания списка необходимо его удаление. Так как самая быстрая функция у нас этот pop, то для удаления будем последовательно выталкивать элементы из списка.
void deleteList(Node **head) < while ((*head)->next) < pop(head); *head = (*head)->next; > free(*head); >
Вызов pop можно заменить на тело функции и убрать ненужные проверки и возврат значения
void deleteList(Node **head) < Node* prev = NULL; while ((*head)->next) < prev = (*head); (*head) = (*head)->next; free(prev); > free(*head); >
Осталось написать несколько вспомогательных функций, которые упростят и ускорят работу. Первая — создать список из массива. Так как операция push имеет минимальную сложность, то вставлять будем именно с её помощью. Так как вставка произойдёт задом наперёд, то массив будем обходить с конца к началу:
void fromArray(Node **head, int *arr, size_t size) < size_t i = size - 1; if (arr == NULL || size == 0) < return; >do < push(head, arr[i]); >while(i--!=0); >
И обратная функция, которая возвратит массив элементов, хранящихся в списке. Так как мы будем создавать массив динамически, то сначала определим его размер, а только потом запихнём туда значения.
int* toArray(const Node *head) < int leng = length(head); int *values = (int*) malloc(leng*sizeof(int)); while (head) < values[--leng] = head->value; head = head->next; > return values; >
И ещё одна функция, которая будет печатать содержимое списка
void printLinkedList(const Node *head) < while (head) < printf("%d ", head->value); head = head->next; > printf("\n"); >
Теперь можно провести проверку и посмотреть, как работает односвязный список
void main() < Node* head = NULL; int arr[] = ; //Создаём список из массива fromArray(&head, arr, 10); printLinkedList(head); //Вставляем узел со значением 333 после 4-го элемента (станет пятым) insert(head, 4, 333); printLinkedList(head); pushBack(head, 11); pushBack(head, 12); pushBack(head, 13); pushBack(head, 14); printLinkedList(head); printf("%d\n", pop(&head)); printf("%d\n", popBack(&head)); printLinkedList(head); //Удаляем пятый элемент (индексация с нуля) deleteNth(&head, 4); printLinkedList(head); deleteList(&head); getch(); >
Сортировка односвязного списка
Сортировать список будем слиянием. Этот метод очень похож на сортировку слиянием для массива. Для его реализации нам понадобятся две функции: одна буде делить список пополам, а другая будет объединять два упорядоченных односвязных списка, не создавая при этом новых узлов. Наша реализация не будет оптимальной, однако, некоторые решения, которые мы применим, могут быть использованы и в других алгоритмах.
Вспомогательная функция – слияние двух отсортированных списков. Функция не должна создавать новых узлов, так что будем использовать только имеющиеся. Для начала проверим, если хоть один из списков пуст, то вернём другой.
Node tmp; *c = NULL; if (a == NULL) < *c = b; return; >if (b == NULL)
После этого нужно, чтобы наша локальная переменная стала хранить адрес большего из узлов двух списков, от него и будем танцевать дальше
if (a->value < b->value) < *c = a; a = a->next; > else < *c = b; b = b->next; >
Теперь сохраним указатель c, так как в дальнейшем он будет использоваться для прохода по списку
tmp.next = *c;
После этого проходим по спискам, сравниваем значения и перекидываем их
while (a && b) < if (a->value < b->value) < (*c)->next = a; a = a->next; > else < (*c)->next = b; b = b->next; > (*c) = (*c)->next; >
В конце, может остаться один список, который пройден не до конца. Добавим его узлы
if (a) < while (a) < (*c)->next = a; (*c) = (*c)->next; a = a->next; > > if (b) < while (b) < (*c)->next = b; (*c) = (*c)->next; b = b->next; > >
Теперь указатель c хранит адрес последнего узла, а нам нужна ссылка на голову. Она как раз хранится во второй переменной tmp
*c = tmp.next;
void merge(Node *a, Node *b, Node **c) < Node tmp; *c = NULL; if (a == NULL) < *c = b; return; >if (b == NULL) < *c = a; return; >if (a->value < b->value) < *c = a; a = a->next; > else < *c = b; b = b->next; > tmp.next = *c; while (a && b) < if (a->value < b->value) < (*c)->next = a; a = a->next; > else < (*c)->next = b; b = b->next; > (*c) = (*c)->next; > if (a) < while (a) < (*c)->next = a; (*c) = (*c)->next; a = a->next; > > if (b) < while (b) < (*c)->next = b; (*c) = (*c)->next; b = b->next; > > *c = tmp.next; >
Ещё одна важная функция – нахождение середины списка. Для этих целей будем использовать два указателя. Один из них — fast – за одну итерацию будет два раза изменять значение и продвигаться по списку вперёд. Второй – slow, всего один раз. Таким образом, если список чётный, то slow окажется ровно посредине списка, а если список нечётный, то второй подсписок будет на один элемент длиннее.
void split(Node *src, Node **low, Node **high) < Node *fast = NULL; Node *slow = NULL; if (src == NULL || src->next == NULL) < (*low) = src; (*high) = NULL; return; >slow = src; fast = src->next; while (fast != NULL) < fast = fast->next; if (fast != NULL) < fast = fast->next; slow = slow->next; > > (*low) = src; (*high) = slow->next; slow->next = NULL; >
Очевидно, что можно было один раз узнать длину списка, а потом передавать размер в каждую функцию. Это было бы проще и быстрее. Но мы не ищем лёгких путей)))
Теперь у нас есть функция, которая позволяет разделить список на две части и функция слияния отсортированных списков. С их помощью реализуем функцию сортировки слиянием.
Сортировка слиянием для односвязного списка
Функция рекурсивно вызывает сама себя, передавая части списка. Если в функцию пришёл список длинной менее двух элементов, то рекурсия прекращается. Идёт обратная сборка списка. Сначала из двух списков, каждый из которых хранит один элемент, создаётся отсортированный список, далее из таких списков собирается новый отсортированный список, пока все элементы не будут включены.
void mergeSort(Node **head) < Node *low = NULL; Node *high = NULL; if ((*head == NULL) || ((*head)->next == NULL)) < return; >split(*head, &low, &high); mergeSort(&low); mergeSort(&high); merge(low, high, head); >
Если Вы желаете изучать этот материал с преподавателем, советую обратиться к репетитору по информатике
ru-Cyrl 18- tutorial Sypachev S.S. 1989-04-14 sypachev_s_s@mail.ru Stepan Sypachev students
Всё ещё не понятно? – пиши вопросы на ящик