Уроки 66 - 68
Структуры (записи)
(§39. Структуры (записи))

Содержание урока

Зачем нужны структуры?

Объявление структур

Обращение к полю структуры

Работа с файлами

Сортировка

Вопросы и задания

Задачи

Сортировка

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

Отсортируем массив Books (типа TBook) по фамилиям авторов в алфавитном порядке. В данном случае ключом будет поле author. Предположим, что фамилия состоит из одного слова, а за ней через пробел следуют инициалы. Тогда сортировка методом пузырька выглядит так:

for i:=1 to N-1 do
for j:=N-l downto i do
if Books[j].author>Books[j+1].author then begin
В:=Books[j]; Books[j]:=Books[j + 1];
Books[j+1]:=B;
end;

Здесь i и j — целочисленные переменные, а В — вспомогательная структура типа TBook.

Как вы знаете из курса 10 класса, при сравнении двух символьных строк они рассматриваются посимвольно до тех пор, пока не будут найдены первые различающиеся символы. Далее сравниваются коды этих символов по кодовой таблице. Так как код пробела меньше, чем код любой русской (и латинской) буквы, строка с фамилией «Волк» окажется выше в отсортированном списке, чем строка с более длинной фамилией «Волков», даже с учётом того, что после фамилии есть инициалы. Если фамилии одинаковы, сортировка происходит по первой букве инициалов, затем — по второй букве.

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

Указатель — это переменная, в которой можно сохранить адрес любой переменной заданного типа.

То есть содержимое указателя — это адрес памяти. Чтобы избежать случайных ошибок, каждому указателю при объявлении присваивается тип данных, адреса которых он может хранить. Например, объявление

type РВоок=ˆТВоок;

вводит новый тип данных — указатель на структуру типа TBook. Адреса переменных других типов в такой указатель записывать нельзя. Имя типа-указателя удобно начинать с буквы «Р» от английского слова pointer — указатель.

Для сортировки массива Books нужно разместить в памяти массив таких указателей и одну вспомогательную переменную, которая будет использована при сортировке:

var р: array[1..N] of PBook;
p1: PBook;

Следующий этап — расставить указатели так, чтобы i-й указатель был связан с г-й структурой из массива Books:

for i:=1 to N do p[i]:=@Books[i] ;

Знак @ обозначает операцию взятия адреса, т. е. в указатель записывается адрес структуры.

Для того чтобы от указателя перейти к объекту, на который он ссылается, используют операцию ˆ. Например, в нашем случае (после показанной выше начальной установки указателей) запись р [i] ˆ обозначает то же самое, что и Books [i], а р [i] ˆ . title — то же самое, что и Books [i] .title.

Теперь можно перейти к сортировке. Рассмотрим идею на примере массива из трёх структур. Сначала указатели стоят по порядку (рис. 6.1, а). В результате сортировки нужно переставить их так, чтобы р[1] указывал на первую структуру в отсортированном списке, р[2] — на вторую и т. д. (рис. 6.1, б).

Рис. 6.1

Обратите внимание, что при этом сами структуры в памяти не перемещаются.

При сортировке обращение к полям структур идёт через указатели, и меняются местами тоже указатели, а не сами структуры:

for i:=l to N-l do
for j:=N-l downto i do
if p[j]ˆ.author > p[j+1]ˆ.author then 
begin
pl:=p[j]; 
p[j]:=p[j+1]; 
p[j+1]:=pl;
end;

Здесь использован метод пузырька, a pi — это временная переменная типа РВоок, которая служит для перестановки указателей.

Теперь можно вывести отсортированные данные, обращаясь к ним через указатели (а не через массив Books):

for i: =1 to N do
writeln(p[i]ˆ.author, '; '
p[i]ˆ.title, '; '
p[i]ˆ.count);

Следующая страница Вопросы и задания

Cкачать материалы урока