4885

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

Лекция

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

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

Русский

2012-11-28

51 KB

44 чел.

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

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

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

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

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

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


 

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

13903. Республика Шкид. Глупость под лупой 30.5 KB
  Эссе Республика Шкид. Глупость под лупой Один день содержит 24 часа или 1440 минут. Сколько необходимо человеку для того чтобы совершить глупость И главное почему человек ее делает как так получается А что происходит после ее совершения Под ненаучным термином г
13904. Психологический роман русского классика Ф.М. Достоевского Преступление и наказание 40 KB
  За основу своего эссе я взял психологический роман русского классика Ф.М. Достоевского Преступление и наказание а именно анализ поведения и характера главного героя Родиона Раскольникова. В романе описывается история бывшего студента СанктПетербурга ко
13905. ОЛЕКСАНДР ДОВЖЕНКО: ТРАГІЧНЕ ЖИТТЯ Й ТИТАНІЧНА ПРАЦЯ 99.5 KB
  ОЛЕКСАНДР ДОВЖЕНКО: ТРАГІЧНЕ ЖИТТЯ Й ТИТАНІЧНА ПРАЦЯ УРОК УКРАЇНСЬКОЇ ЛІТЕРАТУРИ 11 КЛАС Мета: ознайомити учнів з біографією письменника і його внеском у розвиток української кінематографії; дати уявлення про кіноповість як різновид твору призначеного для постанов
13906. УРОКИ СЕКТОВЕДЕНИЯ т. II. ПУТЬ К ПУСТОТЕ 1.58 MB
  УРОКИ СЕКТОВЕДЕНИЯ т. II. ПУТЬ К ПУСТОТЕ ПРЕДИСЛОВИЕ Гл. 1. Учили ли отцы Церкви пантеизму Гл. 2 ХРИСТИАНСКАЯ МЫСЛЬ ПЕРЕД ТАЙНОЙ ЛИЧНОСТИ Гл. 3 ЧЕЛОВЕЧЕСКОЕ СЛОВО ПЕРЕД ЛИЦОМ БОГА Гл. 4. БОГОСЛОВИЕ МЕСТОИМЕНИЯ Гл. 5. СПОСОБНО ЛИ ХРИСТИАНСТВО ВЫДЕРЖАТЬ КРИТИКУ ПАН
13907. УРОКИ СЕКТОВЕДЕНИЯ Ч.1. КАК УЗНАТЬ СЕКТУ 3.09 MB
  УРОКИ СЕКТОВЕДЕНИЯ Ч.1. КАК УЗНАТЬ СЕКТУ На примере рериховского движения Ни разу в жизни я не отказывал себе в удовольствии поспорить с теософом. Гилберт Честертон. ОТ АВТОРА Гл. 1. О ЧЕМ СПОР Знаток Востока не знающий языков. Рерих просит себе Но
13908. ВОСПРИЯТИЕ НА СЛУХ И ТРЕНИРОВКА ПАМЯТИ 67.5 KB
  УРОК 4 ВОСПРИЯТИЕ НА СЛУХ И ТРЕНИРОВКА ПАМЯТИ 1. Запишите на слух ряд чисел и повторите их по записи: 2. Повторите следующие имена собственные выражающие индивидуальные понятия в любом порядке: 3. Повторите в любом порядке существительные выражающие абстрактн
13909. О.П. Довженко «Україна в огні», її справедлива критика «культу особи». Особливості сюжету й композиції. Проблеми «людина і війна», «історична пам’ять народу». Образ Запорожця як символ нескореності свого народу 49.5 KB
  Урок української літератури 11 клас ТЕМА: О.П. Довженко Україна в огні її справедлива критика культу особи. Особливості сюжету й композиції. Проблеми людина і війна історична память народу. Образ Запорожця як символ нескореності свого народу. МЕТА: ознай
13910. Урок. У чому виявляється істинний патріотизм? (За поезією Тараса Шевченка «Минають дні, минають ночі) 30.99 KB
  Тема. У чому виявляється істинний патріотизм За поезією Тараса Шевченка Минають дні минають ночі Мета: допомогти учням поглибити знання про творчу діяльність великого митця зосередити увагу на ідейнохудожньому аналізі поезії Минають дні минають ночі засвої
13911. Зарождение демократии в Афинах 57 KB
  Конспект урока по истории Древнего мира в 6м классе Тема: Зарождение демократии в Афинах. Цель: дать представление о зарождении демократии в Афинах реконструировать социальный конфликт между демосом и аристократией в Афинах в VI в до н.э. ознакомить с рефо...