4885

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

Лекция

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

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

Русский

2012-11-28

51 KB

35 чел.

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

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

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

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

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

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


 

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

76292. Сердце, cor, cardia 134.14 KB
  По пути к сердцу получает кровь из многих вен. ven cv superior идущая от головы короткая вена впадающая в правое предсердиеи собирающая венозную кровь от верхней части тела от головы шеи и верхних конечностей а также венозную кровь от лёгких и бронхов через бронхиальные вены впадающие сначала в v. hemizygos; частично собирает кровь и от стенок брюшной полости за счёт впадения в неё непарной вены.
76294. Артерии и вены сердца 115.84 KB
  A coronaria dextra – между легочным стволом и правым ушком, затем идет по венечной борозде и заходит назад. То есть, в основном, она снабжает правую половину сердца. Отдает r interventricularis posterior – это конечная ветвь, идет по одноименной борозде до самой верхушки, r marginalis dexter – вниз вдоль правого желудочка по краю.
76295. Дуга аорты, грудная часть аорты, их топография, ветви и межсистемные анастомозы 95.09 KB
  Дуга аорты грудная часть аорты их топография ветви и межсистемные анастомозы. Дуга аорты rcus orte расположена между местами отхождения плечеголовного ствола trunсus brchiocephliсus и левой подключичной артерии . На уровне IV грудного позвонка имеется сужение перешеек аорты isthmus orte. Дуга аорты являясь продолжением восходящей части аорты поворачивает влево и назад на уровне тела IV грудного позвонка переходит в нисходящую часть аорты.
76296. Наружная сонная артерия, ее топография, ветви и межсистемные анастомозы 249.62 KB
  Наружная соннаяа ртерия, a.carotis externa, сначала располагается медиальнее от внутренней сонной артерии, затем она постепенно отклоняется кпереди и латерально. Начальный отдел наружной сонной артерии прикрыт грудино-ключично-сосцевидной мышцей, потом она переходит в trigonum caroticum
76297. Артерии лица, из анастомозы 187.52 KB
  Поверхностная височная артерия снабжает кровью околоушную слюнную железу, кожу и мышцы латеральной области лица, височной, теменной и лобной областей волосистой части головы, ушную раковину и наружный слуховой проход. Она анастомозирует с лицевой, затылочной и глазной артериями.
76298. Внутренняя сонная артерия. Ветви, анастомозы 314.76 KB
  Внутренняя сонная артерия. Пройдя сонный канал артерия входит в sinus cvernosus. Пещеристая часть располагается в сонной борозде на боковой поверхности клиновидной кости где артерия проходит через sinus cvernosus твердой мозговой оболочки.
76299. Артерии головного мозга. Артериальный круг мозга 92.47 KB
  Артериальный круг мозга Кровоснабжение головного мозга осуществляется ветвями внутренних сонных артерий позвоночных артерий. communicns posterior зрительный перекрест серый бугор ножки мозга гипоталамус таламус хвостатое ядро. cerebri posterior – формируют сосудистое сплетение бокового и третьего желудочков мозга.
76300. Верхнечелюстная артерия, ее топография, ветви и анастомозы 1.51 MB
  Топография: начинается у шейки нижней челюсти, пронизывает m.pterygoideus lateralis и скрывается в fossa pterygopalatina.