4885

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

Лекция

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

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

Русский

2012-11-28

51 KB

32 чел.

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

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

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

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

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

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


 

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

47653. Системы управления. Сущность систем управления 302.44 KB
  Система – это некоторая целостность, состоящая из взаимозависимых частей, каждая из которых вносит свой вклад в характеристики целого. Или, другими словами, это совокупность взаимодействующих элементов, составляющих целостное образование с новыми свойствами, которые отсутствуют у других составляющих систему, элементов.
47655. ЛОКАЛЬНЫЕ СИСТЕМЫ АВТОМАТИКИ 1.26 MB
  Курсовой проект по курсу “Локальные системы автоматики†посвящен синтезу локальной системы регулирования технологического параметра объекта включающему в себя выбор необходимого закона регулирования регулятора и разработку системы в целом на базе приборов ГСП. Ниже рассматриваются основные системы регулирования барабанных котлов каждая из которых включена в отдельное задание на курсовое проектирование. СИСТЕМА РЕГУЛИРОВАНИЯ ДАВЛЕНИЯ ПАРА ПЕРЕД ТУРБИНОЙ к заданию № 1 Основным требованием предъявляемым к котлам является выработка...
47657. Бухгалтерський облік господарських операцій. Методичні рекомендації 311 KB
  Для виробничих потреб підприємство придбало автомобіль вартістю 100000 К1000 грн. Підприємством оплачено суму збору до Пенсійного фонду 3 та вартість державної реєстрації автомобіля в органах ДАІ 500 грн. Витрати зі страхування цивільноправової відповідальності автовласника склали 1000 грн. строк дії договору страхування – 1 рік; витрати на придбання полісу КАСКО – 3000 грн.
47658. Методические указания. Регионоведение 277 KB
  – Новосибирск: НГТУ 2009 Рецензент: Методические указания содержат сведения о квалификационных требованиях к курсовым работам для студентов специальности направления Регионоведение организации их выполнения и защиты на кафедре Международных отношений и регионоведения НГТУ консультативные рекомендации по выбору темы и теоретических основ работы обязательные требования в отношении композиции работы научного аппарата и оформления. План выполнения курсовой работы42 Приложение 2. Основная цель курсовой работы – выработка...
47659. Технологическое проектирование автотранспортного производства 665 KB
  Цель курсового проекта – формирование научных, профессиональных знаний и навыков в области технической эксплуатации подвижного состава автомобильного транспорта. При изучении дисциплины студенты получают знания о современных технологических процессах технического обслуживания и текущего ремонта автомобилей, об особенностях проектирования и реализации технологических процессов технической эксплуатации на предприятиях автомобильного транспорта
47660. Методичні вказівки. Чисельні методи в інформатиці 1.52 MB
  У тому випадку, коли заздалегідь невідомий ступінь багаточлена Лагранжа, який необхідно використовувати для забезпечення необхідної точності, уживають підхід, заснований на рекурентній схемі організації обчислень, яка звісна, як схема Ейткена
47661. Оптимизация распределения нагрузки электроэнергетической системы между работающими в ней электростанциями и их энергоблоками 208.5 KB
  Методические указания к выполнению лабораторной работы «Оптимизация распределения нагрузки электроэнергетической системы между работающими в ней электростанциями и их энергоблоками» по дисциплине «Автоматизация энергосистем» для студентов