4885

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

Лекция

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

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

Русский

2012-11-28

51 KB

36 чел.

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

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

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

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

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

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


 

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

37302. Инженерный анализ моделей технических систем с помощью MathCAD 72.5 KB
  Освоить программу MathCAD и получить практические навыки ее использования при инженерном анализе моделей технических систем.
37303. Провести анализ напряженно-деформированного состояния конструкции балочного типа с заданным поперечным сечением, при статическом нагружении 512 KB
  Ввод координат 2 Задание материала Для задания характеристик материала выберем пункт меню Model= Mteril Модель= Материал. Рисунок 2 – Задание материала и его свойств Для сохранения введенного материала в библиотеке нажмем кнопку Sve ответив при этом утвердительно на запрос о подтверждении занесения Ст. Рисунок 3 – Выбор типа конечных элементов Нажмем кнопку Shpe Форма для задания формы и размеров поперечного сечения балки. Рисунок 4 – Задание формы поперечного сечения балки Выберем из списка Shpe сечение Chnnel C Section...
37305. Проектирование усилительного устройства, цифрового устройства 968.5 KB
  Усилитель напряжения УН усиливает входной сигнал до необходимого уровня. Действующее значение напряжения: .4 Выбор и расчёт усилителя напряжения Каскад УН строим на базе инвертирующего усилителя.2 – Инвертирующий усилитель напряжения на ОУ 1.
37306. Рачсчет мелкосерийного производства 977.88 KB
  Для современного этапа развития экономики страны особое значение приобретает полное использование преимуществ рыночной системы хозяйствования, положительного опыта предыдущего периода её функционирования, возможностей выявления резервов роста производства, которыми располагает народное хозяйство РБ.
37308. Усилитель звуковой частоты 723.5 KB
  Выбор обоснование и расчет структурной схемы усилителя. Расчет АЧХ усилителя. К тому же нужно обеспечить согласование источника сигнала со входом усилителя а также согласование нагрузки с выходом усилителя. В данном курсовом проекте рассматривается один из возможных вариантов синтеза усилителя звуковых частот с возможностью регулировки тембра и громкости.
37309. ЗАХИСТ КОНСТРУКЦІЙ З ДЕРЕВИНИ ВІД ПОЖЕЖНОЇ НЕБЕЗПЕКИ І БІОЛОГІЧНОГО УРАЖЕННЯ 41 KB
  Вогнестійкість конструкцій з деревини Горючість деревини. Горіння являє собою реакцію зєднання горючих компонентів деревини з киснем повітря яке супроводжується виділенням тепла або диму появою полумя і жевріння. Займання деревини може виникнути в результаті короткочасного нагріву її до температури 250С або тривалого впливу більш низьких температур.
37310. Сопротивление материалов 730 KB
  Лабораторная работа №1 Испытание образца на растяжение – 4 часа Цель работы: изучение процесса растяжения образца из малоуглеродистой стали вплоть до его разрушения разрыва изучение диаграммы растяжения определение механических характеристик. Краткие теоретические сведения Испытание при осевом статическом растяжении образца является наиболее распространенным способом механических испытаний материала что объясняется следующими преимуществами. Во всех точках поперечного сечения рабочей части образца напряжения одинаковы и...