4885

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

Лекция

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

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

Русский

2012-11-28

51 KB

34 чел.

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

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

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

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

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

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


 

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

32564. Центральная память ПЛК 60.65 KB
  Очень часто особенно в простых микроконтроллерах типа SIMTIC S7200 их центральная память бывает организована в виде стековой памяти. Стековая память Пример реализации логической функции управления c использованием стековой памяти На рис. 35 показан последовательный механизм программной реализации логической функции управления Y с использованием стековой памяти ПЛК.
32565. Память ПЛК SIMATIC S7-220 51.19 KB
  – В сегменте памяти программы хранится программа пользователя и содержится список команд которые должны выполняться в CPU для реализации разработанного решения по системе управления. – Память данных содержит область временных данных программы и область памяти объектов. В этом же сегменте памяти хранятся результаты вычислений промежуточные данные и константы а также таймеры счетчики высокоскоростные счетчики и аналоговые входы выходы. К конфигурируемым параметрам относятся такие элементы как уровень защиты пароль адрес станции и...
32566. Модули ввода/вывода (МВв/МВыв) 36.68 KB
  Модули выпускают в различном исполнении: входные выходные или комбинированные ввода вывода дискретные логические аналоговые и специальные в обычном или безопасном исполнении и пр. Модуль ввода вывода дискретных сигналов. 36 показан возможный вариант модуля ввода вывода логических сигналов для 8разрядного микроконтроллера.
32567. Аналого-цифровые (АЦП) и цифро-аналоговые (ЦАП) преобразователи 38.92 KB
  Для этой цели в модулях ввода вывода аналоговых сигналов используются аналогоцифровые АЦП и цифроаналоговые ЦАП преобразователи. Основной характеристикой ЦАП и АЦП является их разрядность определяемая длиной двоичного кода применяемого для представления аналогового сигнала. В схеме использован 8разрядный АЦП выходы которого соединены с входами регистра порта ввода. Для согласования уровня входного сигнала АЦП используется усилитель входного сигнала.
32568. Программаторы 43.12 KB
  Программаторы – это устройства, предназначенные для ввода управляющих программ, их редактирования и отладки, параметрирования системы
32569. Программно-математическое обеспечение (ПМО) контроллеров 248.4 KB
  Алгоритм программы Монитор Прикладное промышленное программное обеспечение Прикладное программное обеспечение рассмотрим на примере SIMTIC Soft фирмы Siemens – это система тесно связанных инструментальных средств для программирования и обслуживания систем автоматизации SIMTIC S7 C7 а также систем компьютерного управления SIMTIC WinC. Интегрирование всех пакетов программ в единый интерфейс позволяет существенно повысить эффективность использования промышленного программного обеспечения SIMTIC и использовать однородные операции на всех...
32570. АСУ ТП на базе промышленных сетей 218.52 KB
  В условиях бурно растущего производства микропроцессорных устройств альтернативным решением стали цифровые промышленные сети Fieldbus состоящие из многих узлов обмен между которыми производится цифровым способом. Использование промышленной сети позволяет расположить узлы в качестве которых выступают контроллеры и интеллектуальные устройства вводавывода максимально приближенно к оконечным устройствам датчикам и исполнительным механизмам благодаря чему длина аналоговых линий сокращается до минимума. Каждый узел промышленной сети...
32571. Общие сведения о ТСА. Основные понятия и определения 15.82 KB
  Основные понятия и определения Целью курса Технические средства автоматизации ТСА является изучение элементной базы систем автоматического управления технологическими процессами. Элемент устройство – конструктивно законченное техническое изделие предназначенное для выполнения определённых функций в системах автоматизации измерение передача сигнала хранение информации ее обработка выработка команд управления и т. Система автоматического управления САУ – совокупность технических устройств и программнотехнических средств...
32572. Тенденции развития ТСА 29.04 KB
  Увеличение функциональных возможностей ТСА: – в функции управлении от простейшего пуска останова и автоматического реверса к цикловому и числовому программному и адаптивному управлению; – в функции сигнализации от простейших лампочек до текстовых и графических дисплеев; – в функции диагностики от индикации обрыва цепи до программного тестирования всей системы автоматики; – в функции связи с другими системами от проводной связи до сетевых промышленных средств.