4885

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

Лекция

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

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

Русский

2012-11-28

51 KB

38 чел.

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

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

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

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

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

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


 

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

16907. Создание сайта на основе таблицы 443.5 KB
  Лабораторная работа №10. Создание сайта на основе таблицы. В данной лабораторной работе мы построим сайт с нуля пользуясь таблицей. Создайте новую папку KompoZer_2 и скопируйте в нее папку images из LR_10. Создайте пустой документ: Выполните команду Форма
16908. Создание WEB – страниц на основе таблиц 117.87 KB
  Лабораторная работа № 11 Создание WEB – страниц на основе таблиц. Оборудование: ПЭВМ Программное обеспечение: Windows Kompozer. Цель работы: приобретение и закрепление практических навыков работы во Kompozer. Задание: Включите ПК. Запустить Kompozer.
16909. Создание WEB узла 36 KB
  Лабораторная работа № 12 Создание WEB узла. Оборудование: ПЭВМ Программное обеспечение: Windows Kompozer. Цель работы: приобретение и закрепление практических навыков работы во Kompozer. Задание: Перекопируйте папку...
16910. Создание электронных таблиц в OpenOffice.org Calc 299.5 KB
  Лабораторная работа №13 Создание электронных таблиц в OpenOffice.org Calc Оборудование: ПК Программное обеспечение: Windows OpenOffice.org Calc. Цель работы: приобретение и закрепление практических навыков работы в OpenOffice.org Calc Теоретическая часть Что такое Calc Calc это модуль электрон
16911. Адресация ячеек в OpenOffice.org Calc 160 KB
  Лабораторная работа № 14Адресация ячеек в OpenOffice.org Calc Оборудование: ПК Программное обеспечение: Windows OpenOffice.org Calc. Цель работы: приобретение и закрепление практических навыков работы в OpenOffice.org Calc Теоретическая часть У каждой ячейки есть свой адрес. Он однозначно оп
16912. Порядок разработки теста в OpenOffice.org Calc 126.5 KB
  Лабораторная работа № 15 Порядок разработки теста в OpenOffice.org Calc Оборудование: ПЭВМ Программное обеспечение: Windows OpenOffice.org Calc. Цель работы: приобретение и закрепление практических навыков работы в OpenOffice.org Calc Теоретическая часть. Тест на тему ЛИЧ...
16913. Логические функции в OpenOffice.org Calc 203.5 KB
  Лабораторная работа № 16 Логические функции в OpenOffice.org Calc Оборудование: ПК Программное обеспечение:Windows OpenOffice.org Calc. Цель работы: приобретение и закрепление практических навыков работы в OpenOffice.org Calc Теоретическая часть Логические функции в OpenOffice.org Calc: 1. IF Условие; Выр
16914. Создание диаграммы в OpenOffice.org Calc 120 KB
  Лабораторная работа №17 Создание диаграммы. Оборудование: ПЭВМ Программное обеспечение: OpenOffice.org Calc. Цель работы: приобретение и закрепление практических навыков работы в OpenOffice.org Calc. Таблица 1. Запустите OpenOffice.org Calc. Сохраните...
16915. Работа с несколькими листами в OpenOffice.org Calc 89.5 KB
  Лабораторные работы № 18Работа с несколькими листами Оборудование: ПК Программное обеспечение: Windows OpenOffice.org Calc. Цель работы: приобретение и закрепление практических навыков работы в OpenOffice.org Calc Задание: 1. Запустить OpenOffice.org Calc. 2. Вычислить объем продаж в магазине То