4885

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

Лекция

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

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

Русский

2012-11-28

51 KB

51 чел.

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

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

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

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

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

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


 

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

33182. Взаимосвязь выручки, расходов и прибыли от реализации продукции. Показатели анализа безубыточности 41.86 KB
  61 Для прогнозирования максимально возможной прибыли в плановом году целесообразно сопоставить выручку от реализации продукции с общей суммой затрат подразделяемых на переменные постоянные и смешанные. Разность между фактическим количеством реализованной продукции и безубыточным объемом продаж продукции это зона безопасности прибыли и чем она больше тем стабильнее финансовое состояние предприятия. График позволяет установить при каком объеме реализации продукции предприятие получит...
33183. Понятие и расчет показателей рентабельности 273.64 KB
  62 РЕНТАБЕЛЬНОСТЬ это показатель характеризующий степень прибыльности или убыточности производства фирмы в целом или отдельных видов продукции. Расчет показателей рентабельности: Общая рентабельность определяется как отношение прибыли до налогообложения к выручке от реализации продукции. Рентабельность собственного капитала определяется как отношение чистой прибыли к величине собственного капитала организации.Формула расчета:где ЧПУОП чистая прибыль убыток отчетного периода;СК0 собственный капитал на начало года;СК1 ...
33184. Расчет порога рентабельности, запаса финансовой прочности, производственный леверидж 22.1 KB
  Рн объем реализации в натуральном выражении. ПРд порог рентабельности в денежном выражении. ПРн порог рентабельности в натуральном выражении. Формула расчета порога рентабельности в денежном выражении: ПРд = ВЗпост В Зпер Формула расчета порога рентабельности в натуральном выражении в штуках продукции или товара: ПРн = Зпост Ц ЗСпер Насколько далеко предприятие от точки безубыточности показывает запас финансовой прочности.
33185. Экономическое содержание оборотного капитала. Структура оборотных активов организации и источники их финансирования 16.37 KB
  Иными словами это средства фирмы вложенные в текущие активы оборотные средства. Оборотные средства это денежные средства авансируемые для образования оборотных производственных фондов и фондов обращения с целью обеспечения непрерывного процесса производства и реализации продукции. В состав оборотных средств входят: запасы товарноматериальных ценностей дебиторская задолженность средства в расчетах денежные средства. Кроме разделения по составу оборотные средства можно классифицировать: по месту и роли в процессе воспроизводства...
33186. Определение потребности в оборотном капитале организации и эффективность его использования 21.76 KB
  66 Эффективное использование оборотных средств во многом зависит от правильного определения потребности в них. Это обусловливает необходимость формирования оборотных средств в определенном размере. Выяснение потребности организации в финансовых ресурсах для создания конкретных видов запасов осуществляется посредством нормирования оборотных средств. Нормирование оборотных средств осуществляется на каждом предприятии в строгом соответствии со сметами затрат на производство и непроизводственные нужды и бизнеспланом отражающим все стороны...
33187. Сущность, содержание, принципы, предмет и метод бухгалтерского учета 17.45 KB
  67 Бухгалтерский учет представляет собой упорядоченную систему сбора регистрации и обобщения информации в денежном выражении об имуществе обязательствах организаций и их движении путем сплошного непрерывного и документального учета всех хозяйственных операций. Принципы бухгалтерского учета используемые в российской учетной практике: 1 бухгалтерский учет имущества обязательств и хозяйственных операций осуществляется способом двойной записи в соответствии с Планом счетов бухгалтерского учета финансовохозяйственной деятельности...
33188. Сущность аудита и его задачи. Постулаты аудита. Классификация видов аудита 15.83 KB
  Постулаты аудита. Классификация видов аудита.68 Аудит предпринимательская деятельность аудиторов аудиторских организаций по осуществлению независимых проверок бухгалтерской отчетности платежнорасчетной документации налоговых декларации и других финансовых обязательств и требований экономических субъектов с целью установления достоверности их бухгалтерской отчетности и соответствия совершенных ими финансовых и хозяйственных операций нормативным актам действующим в Российской Федерации.
33189. Финансовая аренда (лизинг). Виды лизинга. Преимущества лизинга. Схемы расчета лизинговых платежей 15.32 KB
  Финансовый лизинг характеризуется длительным сроком контракта от 5 до 10 лет и амортизацией всей или большей части стоимости оборудования. Возвратный лизинг заключается в продаже собственником промышленным предприятием оборудования лизинговой компании с одновременным заключением договора лизинга на это оборудование в качестве пользователя. В результате первоначальный собственник получает от лизинговой компании полную стоимость оборудования сохраняет за собой право владения и периодически платит за пользование оборудованием. Лизинг это...
33190. Понятие инвестиционного портфеля. Типы портфеля, принципы и этапы формирования, стратегия управления 14.84 KB
  90 Инвестиционный портфель совокупность ценных бумаг приобретенных инвесторами. Существует три типа портфеля ценных бумаг: рискованный портфель консервативный портфель и комбинированный портфель. Рискованный портфель формируется из рискованных ценных бумаг доля которых в портфеле составляет 70. Комбинированный портфель формируется из надежных ценных бумаг приобретаемых на отностительно большой период времени и из рискованных с повышенным доходом состав которых все время обновляется.