Линейные списки. Структуры хранения. Корректировка последовательных структур данных

Лекция № 3 Линейные списки

Список представляет собой некоторые обобщения такой базовой структуры данных как строка.

Строка - конечная последовательность символов некоторого алфавита.

Основные операции для строк:

n последовательный просмотр символов строки,

n включение в строку некоторого символа,

n исключение символа из строки.

Сигнатуру для этой базовой вычислительной структуры приведена в книге Бауэра [ ]. В качестве важного замечания по приложениям следует отметить, что строки являются ключевым  понятием для процедур редактирования.

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

Запись - упорядоченный набор ассоциативно связанных друг с другом атрибутов (полей) .

Пример:

tt. exe     22.02.95     1224

t.c           12.03.95     2012

g. txt       30.06.95     2016

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

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

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

n размер списка может изменятся;

n элемент списка в большинстве случаев идентифицируется не индексом, а ключом.

Структуры хранения 

1. Простейшая структура хранения для списка - это совокупность массивов, где i-ые элементы массивов составляют в совокупности запись списка.

Type

I200 = Array[0..200] of Integer;

C200= Array [0..200]of String;

VAR  f, s, y, qst: I200;

VAR G: C200;

2.   Применение такой базовой структуры алгоритмических языков, как «запись» или «структура» позволяет использовать для списка такую структуру хранения, как массив записей:

TYPE

TGroup=RECORD

fac : integer;

s : integer;

y : integer;

g : array[1..10] of char;

qst : integer;

End;

var:

groups : array [1..200] of TGroup; 

3.  Дополнение информационных полей записей списка полей типа «указатель» позволяет использовать для списка связанные структуры хранения.

Наряду с базовыми операциями, характерными для строк, при программной реализации списковых структур необходимо обеспечить выполнение ряда специфических операций, характерных для линейных списков:

n копирование списка;

n упорядочение элементов списка;

n поиск в списке;

n корректировка записей списка ;

n сцепление списков;

n расщепление списка по заданному элементу;

n определение числа элементов в списке и т. д.

Мы остановимся подробнее на трех первых типах операций:

СОРТИРОВКА - упорядочение записей списка в соответствии с некоторым критерием, сформулированным обычно относительно ключевых полей списка.

Для оценки эффективности методов сортировки используются следующие критерии:

n количество сравнения пар признаков;

n количество пересылок при изменении порядка элементов;

n число обращений к внешней памяти для чтения или записи элементов;

n размер памяти, необходимый для сортировки.

При изучении методов упорядочения можно упростить ситуацию за счет двух предложений:

n использование массива локатора при упорядочении записей;

n сведение к одному вспомогательному атрибуту, критерия, сформулированного относительно нескольких полей записи.

Например, для списка студентов таким вспомогательным атрибутом может быть:

К_сорт = (f ⁶ + S) y

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

Пример: упорядочить записи списка, соответствующие строкам матрицы  по максимальным элементам этих строк.

Этот подход позволяет избежать фактической перестановки записей и тем самым свести все к сортировке массива локатора.

С учетом сказанного выше можно построить следующее дерево, характеризующее методы сортировки.

Внешняя сортировка [external sorting] - упорядочение данных, размещенных внешней памяти. Внутренняя сортировка [internal sorting] - упорядочение данных, размещенных в основной памяти.

Сортировка обменом - сравнение и последовательный обмен местами элементов массива.

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

Сортировка вставками - упорядочение массива при помощи вставки элементов в некоторый существующий отсортированный массив.

При этом среднее количество сравнений зависит от метода сортировки и при рациональном выборе достигает минимума, зависящего от размера массива записей:  C = n[log₂n]

Методы поиска.

Поиском называется процедура выделения из множества записей спискаподмножества, записи которого удовлетворяют заранее поставленному условию. Классификационная схема для методов поиска предоставлена на рисунке.

Рис.

Возможны следующие условия поиска:

n по совпадению;

n по интервалу;

n по близости;

n по арифметическому условию;

n по семантическому условию;

n по комбинации условий.

Пример: Найти в массиве контингент студентов, всех студентов старше 40 лет.

Алгоритмы для указанных условий поиска можно получить из алгоритма поиска по совпадению.

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