4885

Связный список. Сортировка списков

Лекция

Информатика, кибернетика и программирование

Связный список. Сортировка списков. Как известно, массив всегда занимает непрерывный блок памяти, что позволяет быстро получать доступ к произвольному элементу массива по индексу, однако существенно затрудняет вставку и удаление элементов, поскольку...

Русский

2012-11-28

51 KB

46 чел.

Связный список. Сортировка списков.

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

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

Простейший односвязный список представляет собой линейную последовательность элементов, для каждого из которых, кроме последнего, известен следующий элемент:

 Элементы такого списка можно описать в следующем виде:

struct ListNode

{

  ListNode * next; // Указатель на следущий элемент списка

  ...          // Произвольная информация

};

Доступ к такому списку обеспечивается через указатель на его первый элемент:

struct LinkedList

{

  ListNode * head; // Указатель на первый элемент списка

};

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

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

Такой список позволяет осуществлять удаление элементов так же эффективно, как и вставку. Тем не менее, осуществление произвольного доступа к элементам по индексу в списках гораздо менее эффективно, чем в массивах.

В следующем примере показано заполнение односвязного списка и реализация функций вывода списка на экран и очистки памяти:

// Структура, описывающая односвязный список

struct ListNode

{

  ListNode * next;

  int value;

};

// Функция выводит список на экран

void printList( const ListNode * head )

{

  const ListNode * it = head;

  while ( true )

  {

     cout << it->value << " ";

     if ( it->next == 0 )

        break;

     

     it = it->next;

  }

  cout << endl;

}

// Функция рекурсивно освобождает память, занятую односвязным списком

void clearList( ListNode * a )

{

  if ( a->next )

     clearList( a->next );

  cout << "Deleting: " << a->value << endl;

  delete a;

}

void main()

{

  ListNode * head = new ListNode;

  head->value = 0;

  // Указатель на предыдущий узел

  ListNode * prevnode = head;

  const int N = 10;

  int A[N] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

  

  for ( int i = 0; i < N; ++i )

  {

     ListNode * tmp = new ListNode; // новый узел

     tmp->value = A[i];

     

     // Связываем предыдущий узел с новым

     prevnode->next = tmp;

     // Обновляем указатель на предыдущий узел

     prevnode = tmp;

  }

  // Устанавливаем конец списка

  prevnode->next = 0;

  printList( head );

  clearList( head );

}

Сортировка списков.

Поскольку для связных списков отсутствует возможность прямого обращения к элементам по индексу, непосредственное использование большинства рассмотренных алгоритмов сортировки будет существенно затруднено. Как и в случае с внешними данными, для сортировки списков наиболее удобно использовать алгоритм сортировки слиянием.

Как и ранее, реализация предусматривает две функции: функция mergeLists  осуществляет упорядоченное слияние двух списков в один, а рекурсивная функция mergeSort выполняет разделение списка и возвращает указатель на отсортированный список. Заметим, что эта реализация не требует выделения дополнительной памяти для временного хранения упорядоченных данных – список сортируется путем переупорядочивания связей. Однако, никакого дополнительного преимущества в этом нет – фактический расход памяти на организацию связей в списке имеет примерно тот же порядок.

// Функция осуществляет слияние двух списков

ListNode * mergeLists( ListNode * a, ListNode * b )

{

  ListNode tmp;

  ListNode * head = & tmp;

  ListNode * c = head;

  // Сливаем

  while ( ( a != 0 ) && ( b != 0 ) )

  {

     if ( a->value < b->value )

     {

        c->next = a;

        c = a;

        a = a->next;

     }

     else

     {

        c->next = b;

        c = b;

        b = b->next;

     }

  }

  // Присоединяем оставшийся "хвост"

  c->next = ( a == 0 ) ? b : a ;

  return head->next;

}

// Сортировка связного списка слиянием

ListNode * mergeSort( ListNode * c )

{

  if ( c == 0 || c->next == 0 ) // сортировать нечего

     return c;

  ListNode * a = c; // a хранит начало первой части

  ListNode * b = c->next; // служебный указатель

  while ( ( b != 0 ) && ( b->next != 0 ) )

  {

     c = c->next; // первый указатель делает один шаг

     b = b->next->next; // второй - два шага

  }

  b = c->next; // в b записали начало второй части списка

  c->next = 0; // разрываем связь - конец первой части списка

  printList( a );

  printList( b );

  cout << "----" << endl;

  // Рекурсивно вызываем ту же процедуру и сливаем части списка

  return mergeLists( mergeSort(a), mergeSort(b) );

}


L1

L2

L3

4

L1

L2

L3

L4

Lnew

L1

L2

L3

L4


 

А также другие работы, которые могут Вас заинтересовать

23898. Гесиод Теогония, или О происхождении богов 18.18 KB
  Потом от Ночи родился День а от ЗемлиГеи НебоУран и МореПонт. Один за другим они вздували чрево материЗемли и вот ей стало невмоготу. Третьего звали Иапет от него родились могучий Атлант который стоит на западе земли и держит небо на плечах и мудрый Прометей который прикован к столбу на востоке земли а за что об этом будет речь дальше. Теперь их самих заточили в Тартар в самую глубь: сколько от неба до земли столько и от земли до Тартара.
23899. Гомер Илиада 20.07 KB
  Этот эпизод гнев Ахилла величайшего из последнего поколения греческих героев. Главным вождем был сильнейший из царей правитель города Аргос Агамемнон; с ним были брат его Менелай ради которого и началась война могучий Аякс пылкий Диомед хитроумный Одиссей старый мудрый Нестор и другие; но самым храбрым сильным и ловким был юный Ахилл сын морской богини Фетиды которого сопровождал друг его Патрокл. Это тот самый брак от которого родился Ахилл. Это был Ахилл.
23900. Гомер Одиссея 26.48 KB
  Одиссея поэма сказочная и бытовая действие ее разворачивается с одной стороны в волшебных краях великанов и чудовищ где скитался Одиссей с другой в его маленьком царстве на острове Итаке и в ее окрестностях где ждали Одиссея его жена Пенелопа и его сын Телемах. Обо всем что было раньше Одиссей рассказывает на пиру в середине поэмы и рассказывает очень сжато: на все эти сказочные приключения в поэме приходится страниц пятьдесят из трехсот. В Троянской войне Одиссей очень много сделал для греков особенно там где нужна была...
23901. Еврипид Ифигения в Авлиде 17.11 KB
  Греки собрались на них огромным войском во главе его встал аргосский царь Агамемнон брат Менелая и муж Клитемнестры сестры Елены. Может быть Агамемнон на досуге развлекаясь охотою одной стрелою поразил лань и не в меру гордо воскликнул что сама Артемида не ударила бы метче а это было оскорблением богине. Гадатель сказал: богиня требует себе человеческой жертвы пусть на алтаре будет зарезана родная дочь Агамемнона и Клитемнестры красавица Ифигения. За Ифигенией послали гонцов: пусть ее привезут в греческий стан царь Агамемнон...
23902. Еврипид Ифигения в Тавриде 17.56 KB
  У великого аргосского царя Агамемнона главного вождя греческой рати в Троянской войне была жена Клитемнестра и было от нее трое детей: старшая дочь Ифигения средняя дочь Электра и младший сын Орест. Агамемнон сделал это; как это произошло Еврипид показал в трагедии Ифигения в Авлиде. При этом храме Ифигения стала жрицей.
23903. Еврипид Медея 17.48 KB
  В Колхиде правил могучий царь сын Солнца; дочь его царевнаволшебница Медея полюбила Ясона они поклялись друг Другу в верности и она спасла его. Вовторых когда они отплывали из Колхиды Медея из любви к мужу убила родного брата и разбросала куски его тела по берегу; преследовавшие их колхидяне задержались погребая его и не смогли настичь беглецов. Втретьих когда они вернулись в Иолк Медея чтобы спасти Ясона от коварства Пелия предложила дочерям Пелия зарезать их старого отца обещав после этого воскресить его юным.
23904. Софокл Антигона 17.64 KB
  Когда Эдип отрекся от власти и удалился в изгнание править стали вдвоем Этеокл и Полиник под надзором старого Креонта свойственника и советника Эдипа. После гибели Этеокла и Полиника власть над Фивами принял Креонт. Но Креонт думал не о людях и не о богах а о государстве и власти. Навстречу хору выходит Креонт и оглашает свой указ: герою честь злодею срам тело Полиника брошено на поругание к нему приставлена стража кто нарушит царский указ тому смерть.
23905. Софокл Трахинянки 17.08 KB
  Знаменит он только тем что в нем прожил свои последние годы величайший из греческих героев Геракл сын Зевса. Почти все греческие герои были царями в разных городах и городках кроме Геракла. Когда Геракл кончил свою подневольную службу он пошел на край Греции свататься к Деянире. Геракл схватился с богом в борьбе придавил его как гора; тот обернулся змеем Геракл стиснул ему горло; тот обернулся быком Геракл сломил ему рог.