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


 

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

30578. Розанов о тв-ве, таланте, литературе («Уединенное», «Опавшие листья») 77.5 KB
  Розанов о твве таланте литературе Уединенное Опавшие листья Василий Васильевич Розанов целое явление в русской философии отдельное от всех не принадлежащее ни к какому течению. Розанов выработал собственный стиль а стиль это душа вещей как он писал сам. Розанов интересен еще тем что он не был устоявшимся раз и навсегда мыслителем который всю свою научную карьеру отстаивает какието свои убеждения и мысли или развивает их свои идеи он постоянно обновлял или подвергал критике. Среди работ важных для понимания...
30579. Лосев А. о творчестве 34.5 KB
  Лосев А. Лосев 23. Лосева учителя математики страстного любителя музыки скрипачавиртуоза и Н. Лосевой дочери настоятеля храма Михаила Архангела протоиерея о.
30580. Неосферные трансформации СМИ 34 KB
  Война и мир цивилизаций Лукьянов: все культуры имеют единый генетический код; есть единый культурный архетип. Война: агрессор стремится разрушить перепрограммировать массовое сознание. 3я мировая информация психологическая война. С 3 мая 1946 речь Черчилля в Фултоне Стадии: холодная война до1988 информационнопсихологическая война с 1988 Медиа как военные средства.
30581. Творчество Юрия Роста 27.61 KB
  Творчество Юрия Роста.Юрий Михайлович РОСТ родился в 1939 году в городе Киеве.Юрий Рост очень интересный человек. Работал в Комсомолке Литературке на RENTV Конюшня Роста в Общей газете.
30582. Информационные потоки и их особенности 30.69 KB
  В его рамках объединены и производство и распространение МИП причем во всей сложности того и другого. В отличие от всех этих видов творчества ориентированных на создание определенного типа произведений жка оказывается еще и деятельностью направленной на производство МИП.Что представляет собой структура распространения МИП В ней четко определяются три взаимосвязанных обусловливающих друг друга элемента:1 тиражирование информационных продуктов;2 хранение их;3 доставка получателю.А если в качестве основания для рассмотрения взять...
30583. История журналистской профессии 20.29 KB
  Но журналистика могла развернуться лишь с появлением печатных периодических изданий возникших в Европе в XVI веке в России в XVII веке.Массовой журналистика стала после отмены крепостного права.Дореволюционная журналистика знала замечательных репортеров профессионалов мастеров своего дела умеющих быть мобильными находчивыми остроумными и подчас смелыми людьми писал Б.После 1917 года журналистика изменилась другими стали требования к журналисту.
30584. Журнализм в мире профессии (по Бахтину) 16.02 KB
  Он утверждал что слово является непосредственным фактом жизнедеятельности то есть слово поступок. По сути это переход от формулы слово и дело к формуле и слово есть дело . Для журналиста это принципиально важно ведь для нас господа слово действительно дело.Бахтин изучал даже не столько само слово сколько границы звучащего слова.
30585. Теория и методика журналистского творчества 19.86 KB
  Долгое время считалось что мозг производит мысли участвует в творческой деятельности так же как слюнная железа выделяет слюну. А вот каким образом мозг производит мысли Как объяснить когда в головах сразу у нескольких людей живущих в разных концах света рождается одно и то же научное открытиеИзобретатель Александр Белл опередил своих конкурентов с заявкой на телефон всего на несколько часов.А может действительно нашей мыслительной творческой деятельностью ктото управляетЯ могу экспериментально подтвердить что работа сознания не...
30586. Методы и методика журналистского творчества 35 KB
  Интервью от англ. По содержанию интервью делятся на так называемые документальные интервью изучение событий прошлого уточнение фактов и интервью мнений цель которых выявление оценок взглядов суждений и т.Есть формализованное интервью стандартизированное и структуризованное общение: интервью имеет четкую структуру; каждый вопрос логически вытекает из другого а все вместе они подчинены общему замыслу беседы; открытые закрытые и полузакрытые вопросы. Неформализованном интервью ориентировано на глубинное познание объекта и...