Связные списки. Пузырьковая сортировка. Неэффективный, но наиболее простой способ: смена звеньев местами
Сортировать элементы связных списков можно в двух вариантах:
- 1. Переставлять внутренние элементы одного звена с внутренними элементами второго звена напрямую. Способ наиболее простой, но очень долгая работа программы.
- 2. Изменять связи в указателях. Более правильный способ, программа будет работать значительно быстрее, чем если использовать первый способ. И реализовать такой, и понять такой намного сложнее, чем первый.
Здесь будет показан способ наиболее простой к пониманию. Т. е. когда элементы копируются, а не меняется связь указателей. Для начала будет показана основа, от которой мы будем отталкиваться. Пусть, например, мы имеем вот такой список:
|
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 |
//Листинг #1 Основа к примерам, демонстрируемым в статье #include <iostream> using namespace std; struct Node{ //Эта структура — это структура объекта, который будет элементом очереди int x; Node *Next, *Prev; //Указатели связи. Эти указатели направляются на соседствующие элементы. }; class List{ Node *Head, *Tail; //Указатели, признаки начала списка и последнего элемента списка (голова и хвост) public: List():Head(NULL), Tail(NULL){} //КОнструктор по умолчанию, направляет голову и хвост вникуда ~List(); //Прототип деструктора. Деструктор нужен для высвобождения памяти от оъекта, представляющего собой список void add(int); //Прототип функции добавления элемента в список, добавляется целое int void show(); //Прототип функции обхода и вывода каждого элемента на экран }; /* ФУНКЦИЯ ДОБАВЛЕНИЯ ЭЛЕМЕНТА В СПИСОК */ void List::add(int value){ Node *temp = new Node; //Выделяем память для звена, чтобы потом записать в эту память значения и сцепить с новыми звеньями temp->x = value; //записываем значения в звено списка. В звене одна переменная x, записываем в него пришедшее в функцию целое temp->Next = NULL; //Обязательно обозначаем, что следующего соседа пока ещё нет, это основной признак последнего элемента списка /*Теперь организуем связи путём направления указателей*/ if (!Head){ //Если Head==NULL, то temp->Prev = NULL; //Предыдущий элемент указывает в пустоту (нет раньшего соседа) Head = Tail = temp; //Голова тот же же элемент, что и хвост } else { temp->Prev = Tail; //Предыдущий элемент относительно новоявленного — это хвостовой элемент не обновлённого ещё списка Tail->Next = temp; //Следующий элемент относительно новоявленного — это прицепляемый элемент к необновлённого ещё списка, цепляем к хвостовому новоявленный Tail = temp; //Меняем адрес хвоста, чем как бы обновляем связи, получая эффект обновлёние списка. } } void List::show(){ Node * temp = Head; //Направляем указатель на начало списка while (temp){ //Обходим список, то же что и while (temp != NULL) cout << temp->x << '\t'; //Выводим нужные элементы из текущего звена temp = temp->Next; //Направляем указатель на следующий элемент списка } } List::~List(){ while (Head) //Пока по адресу на начало списка что-то есть { Tail = Head->Next; //Резервная копия адреса следующего звена списка delete Head; //Очистка памяти от первого звена Head = Tail; //Смена адреса начала на адрес следующего элемента } } int main () { List lst; lst.add(100); lst.add(200); lst.add(300); lst.show(); } |
Как вы можете догадаться, чтобы понимать основную тему этой интернет-страницы, необходимо понимать, что это за код такой в листинге #1. (Посмотреть описание написания подобного кода можно на странице Двусвязный список) В листинге #1 реализован двусвязный список. Сам факт двусвязности обозначает, что при необходимости программу легко или дополнить или переписать так, чтобы, например, обход элементов происходил или слева-направо или справа-налево, т. е. по вкусу. Я выбираю наиболее привычную из чтения форму обхода: слева-направо. Или бежишь от хвоста по указателям на прошлое значение (по Prev), либо от начала по указателям на следующие (по Next).
Кроме этого, если вы вообще не знакомы с сортировками, то скорее всего понять саму эту темы вам не получится. Нужно понимать хотя бы самую простую, пузырьковую, сортировку обычного одномерного массива. Поскольку пузырьковая сортировка наипростейшая в реализации, в темах сайта часто используется именно она. Не исключение и эта тема.
Итак, чтобы сортировать список, можно пойти наиболее простым путём, не обновляя связи в указательных переменных, а прямым копированием звеньев. Каждую внутренность переставляемого звена нужно будет копировать во временное звено, выступающее в качестве буфера хранения. Это примитивный алгоритм перестановки, когда для перестановки двух переменных используется вспомогательная переменная для временного хранения переставляемого элемента. Из-за копирования всего звена и из-за возможно большого количества звеньев такой способ очень неэффективен, но поскольку он наиболее простой, в моём представлении, к пониманию новичками, показываю его. Добавляем функцию сортировки к нашему классу List.
|
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 |
//Листинг #2 #include <iostream> #include <algorithm> using namespace std; struct Node{ //Эта структура — это структура объекта, который будет элементом очереди int x; Node *Next, *Prev; //Указатели связи. Эти указатели направляются на соседствующие элементы. }; class List{ Node *Head, *Tail; //Указатели, признаки начала списка и последнего элемента списка (голова и хвост) public: List():Head(NULL), Tail(NULL){} //КОнструктор по умолчанию, направляет голову и хвост вникуда ~List(); //Прототип деструктора. Деструктор нужен для высвобождения памяти от оъекта, представляющего собой список void add(int); //Прототип функции добавления элемента в список, добавляется целое int void show(); //Прототип функции обхода и вывода каждого элемента на экран void sort(); }; /* ФУНКЦИЯ ДОБАВЛЕНИЯ ЭЛЕМЕНТА В СПИСОК */ void List::add(int value){ Node *temp = new Node; //Выделяем память для звена, чтобы потом записать в эту память значения и сцепить с новыми звеньями temp->x = value; //записываем значения в звено списка. В звене одна переменная x, записываем в него пришедшее в функцию целое temp->Next = NULL; //Обязательно обозначаем, что следующего соседа пока ещё нет, это основной признак последнего элемента списка /*Теперь организуем связи путём направления указателей*/ if (!Head){ //Если Head==NULL, то temp->Prev = NULL; //Предыдущий элемент указывает в пустоту (нет раньшего соседа) Head = Tail = temp; //Голова тот же же элемент, что и хвост } else { temp->Prev = Tail; //Предыдущий элемент относительно новоявленного — это хвостовой элемент не обновлённого ещё списка Tail->Next = temp; //Следующий элемент относительно новоявленного — это прицепляемый элемент к необновлённого ещё списка, цепляем к хвостовому новоявленный Tail = temp; //Меняем адрес хвоста, чем как бы обновляем связи, получая эффект обновлёние списка. } } void List::show(){ Node * temp = Head; //Направляем указатель на начало списка while (temp){ //Обходим список, то же что и while (temp != NULL) cout << temp->x << '\t'; //Выводим нужные элементы из текущего звена temp = temp->Next; //Направляем указатель на следующий элемент списка } } void List::sort(){ Node *left = Head; //Первый элемент — это пусть будет голова Node *right = Head->Next; //Второй элемент — это пусть будет следующий за головой элемент Node *temp = new Node; //Временное звено для хранения переставляемого всех значений переставляемого звена while (left->Next){ //Обходим по всем звеньям, за исключением крайнего правого while (right){ //Обходим по всем звеньям, включая крайний правый (по всем относительно первого левого на текущий момент) if ((left->x) < (right->x)){ //Проверяем необходимость перестановки temp->x = left->x; //И переставляем все внутренние элементы, за исключением указателей связи, местами left->x = right->x; //Сейчас у нас имеется только x, поэтому только его right->x = temp->x; //иначе бы нужно было это проделывать для каждого несвязующего элемента } right = right->Next; //не забываем направлять указатель на следующий элемент (по подобию инкремента), иначе цикл зависнет } left = left->Next; //не забываем направлять указатель на следующий элемент (по подобию инкремента), иначе цикл зависнет right = left->Next; //Поскольку второй указатель убежал немного вперёд, обязательно возвращаем его назад, это следующий элемент относительно текущего первого } } List::~List(){ while (Head) //Пока по адресу на начало списка что-то есть { Tail = Head->Next; //Резервная копия адреса следующего звена списка delete Head; //Очистка памяти от первого звена Head = Tail; //Смена адреса начала на адрес следующего элемента } } int main () { List lst; lst.add(100); lst.add(200); lst.add(300); lst.sort(); lst.show(); } |
Алгоритм пузырьковой сортировки, который использован здесь, эквивалент вот такому:
|
1 2 3 4 5 6 7 8 9 10 |
//Листинг #aa int arr[3] = {100,200,300}; for (int i=0; i<2; i++){ for (int j=1; j<3; j++){ if (arr[i] < arr[j]) std::swap(arr[i], arr[j]); } } for (auto i:arr) cout << i << '\n'; |
Поскольку у нас имеется список, количество элементов которого не отслеживается, то мы не можем столь же удобно использовать цикл for для обхода. Поэтому в пользу читаемости кода используетя цикл while. Единственное, что наиболее важно при использовании цикла while сейчас — это не забывать обновлять значение, очередное обновление которого служит признаком прекращения цикла. Поскольку для определения необходимости завершения цикла мы используем указательные переменные, и во внутреннем цикле указательная переменная бежит только на следующий элемент, при завершении внутреннего цикла эту убегающую указательную переменную нужно откатывать немного назад, для чего сначала нужно перенаправить указатель из внешнего цикла на следующий элемент, а потом направить убежавший указатель на следующий элемент относительно указателя внешнего цикла. В общем, нужно обязатель ловить беглеца и показывать ему его место.
Как уже было дважды отмечено, сам факт копирования объектов обозначает, что программа будет работать достаточно долго. Ведь объекты могут большими и их может быть много. Вместо этого можно обновлять связи. Обновление связей реализовывается сложнее, но зато программа будет работать при таком премного эффективнее.
- Похожие темы:
- Одномерный массив. Пузырьковая сортировка.
- Двумерный массив. Пузырьковая сортировка строк
- Двусвязный список
- С++ для начинающих Однонаправленный список LIFO
- С++ для начинающих Стек
- С++ для начинающих Однонаправленный список FIFO
- С++ для начинающих Очередь на основе линейного однонаправленного списка (Стека)
7 комментариев на «“Связные списки. Пузырьковая сортировка. Неэффективный, но наиболее простой способ: смена звеньев местами”»
Добавить комментарий
Случайная книга в электронном формате
спасибо
Спасибо
а как удалять элементы?
Для двусвязного списка
http://ci-plus-plus-snachala.ru/?p=3242
rebyat v std::list ispolzuetsya «Merge sort» a ne «Buble sort (v perevode s angl — puzirkovaya sortirovka) » tak chto etot primer ochen’ ploxoy ne kogda ne sortiruyte spiski takim obvrazom, eto bezgramotno
Здравствуй, друг. Нужен твой совет, всего 2,5 маленьких вопроса.
1) На 25 строке написано просто while(Head), а на 39 и 57 — if (Head!=NULL) и while (temp!=NULL) соответственно. В двух последних случаях мы можем написать также, как и в первом? Если нет, то почему?
2)Второй вопрос связан с сортировкой: когда алгоритм обнаруживает, что значение одного элемента больше значения другого, то он меняет значения этих указателей:
if( node->x > node2->x ){
int i = node->x;
node->x = node2->x;
node2->x = i;}
Будет ли корректным менять последовательность сами указатели?
if (n1->data > n2->data) {
Node *i = node;
node = node2;
node2 = i;}
Кстати, обязательная ли 36 строка? Как ты думаешь?
25-я строка.
Нет обхода списка, поэтому сразу циклом происходит обход всего списка, чтобы позвенно (по звеньям) удалить элементы списка.
if поспособствует удалению только одного указателя, а надо удалять столько указателей, сколько в список добавлено было.
========================
39-я строка.
Это просто проверка на пустоту списка, мало ли добавление не получилось, не создавать же новое звено. Цикл тут не нужен, достаточно проверит ифом.
=======================
57 строка
Это обход цикла. Нужно множество звеньев, поэтому цикл, одним ифом не обойтись.
=======================
Head — это начало списка, если написать while(head) — то это то же, что написать while (head == true), так можно повесить программу, если head Не указывает вникуда, то будет бесконечный цикл.
=======================
36-я, думаю, обязательна, но могу ошибиться.
=======================
Последний вопрос. Можно проверить самому ведь. Это неправильно.
Спасибо! Помог 🙂