Описание и использование списка списков. Метод пирамидальной сортировки массивов

• Номер работы:
  143323
• Раздел:
  Все работы   →   Ответы на вопросы /ГОСы и экзамены   →   Информационное обеспечение, программирование
• Год подготовки:
  30.01.2010
• Объем работы:
  16 стр.
• Содержание:
  1. Описание и использование списка списков
  2. Метод пирамидальной сортировки массивов
• Выдержка из работы:
  1. Описание и использование списка списков
  
  Списки являются чрезвычайно гибкой структурой, так как их легко сделать большими или меньшими, и их элементы доступны для вставки или удаления в любой позиции списка. Списки также можно объединять или разбивать на меньшие списки. Списки регулярно используются в приложениях, например в программах информационного поиска, трансляторах программных языков или при моделировании различных процессов.
  В математике список представляет собой последовательность элементов определенного типа, который в общем случае будем обозначать как elementtype (тип элемента). Мы будем часто представлять список в виде последовательности элементов, разделенных запятыми: а1, а2, ..., аn где n>0 и все аi имеют тип elementtype. Количество элементов п будем называть длиной списка. Если n>1, то а1 называется первым элементом, а аn – последним элементом списка. В случае n=0 имеем пустой список, который не содержит элементов.
  2. Метод пирамидальной сортировки массивов
  
  Сортировкой, или упорядочиванием списка объектов называется расположение этих объектов по возрастанию или убыванию согласно определенному линейному отношению порядка, такому как отношение «<« для чисел. Это очень большая тема, поэтому она разбита на две части: внутреннюю и внешнюю сортировку. При внутренней сортировке все сортируемые данные помещаются в оперативную память компьютера, где можно получить доступ к данным в любом порядке (т.е. используется модель памяти с произвольным доступом). Внешняя сортировка применяется тогда, когда объем упорядочиваемых данных слишком большой, чтобы все данные можно было поместить в оперативную память. Здесь узким местом является механизм перемещения больших блоков данных от устройств внешнего хранения данных к оперативной памяти компьютера и обратно. Тот факт, что физически непрерывные данные надо для удобного перемещения организовывать в блочную структуру, заставляет нас применять разнообразные методы внешней сортировки.