Пример на связанные списки.
Сортировка с неизвестным числом элементов методом "пузырька".
Сортировка здесь на самом деле не главное. Главное - использование
связанных списков. Я помню, что у меня лично данная тема поначалу
вызвала серьезные затруднения и мне сторило большого труда понять, как
"общаться" с динамическими переменными. Поэтому я постараюсь осветить
данный вопрос подробно, насколько смогу. Очень надеюсь, что кому-нибудь
эта информация поможет. Первоначально я разбирался с материалом по этой
теме по книжке П. Грогоно, данные о которой можно посмотреть
здесь. Полный текст программы приведен
внизу данной страницы, так что можете сначала ознакомиться с ним, а потом
вернуться в начало, если что-то покажется непонятным. Если же текст
программы не вызовет у вас никаких вопросов, то и читать пояснения
вам совсем необязательно.
В тех случаях, когда неизвестен начальный набор
данных, нельзя использовать статические конструкции вроде массивов,
а необходимо создавать объекты по мере необходимости во время работы
программы. Такие структуры называются "динамическими". Самое главное
при работе с такими структурами помнить, что переменные, которыми
вы манипулируете являются лишь ссылками на реальные данные.
Начнем с объявления. Ссылочная переменная представляет собой
совокупность двух типов данных.
Первый тип - это собственно данные, которые могут быть любого разрешенного
типа (в этой программе это тип String). Второй тип - это ссылочная
переменная, которая должна иметь тип указатель (Pointer). Назначение
этой переменной - указывать область памяти, в которой хранятся данные.
Как минимум ссылочная переменная должна иметь одну переменную типа
указатель (в данном примере это next), но их может быть несколько.
Так, чтобы организовать список, по которому можно двигаться не только от
начала к концу, но и в обратном направлении, должен иметь еще одну
переменную указатель previous.
Понятно, что для огранизации типа данных с разными типами используется
тип record:
type
nameList = record
name:String;
next:Pointer;
end;
Обычно используется указатель не просто абстрактного типа Pointer, но
указатель именно на тот тип данных который используется. В данном примере
это тип nameList:
type
ptrNameList = ^nameList;
который является ссылкой на тип nameList (о чем говорит символ ^).
Pascal позволяет определять ссылочный тип на еще не определенный тип.
type
ptrNameList = ^nameList;
nameList = record
name:String;
next:ptrNameList;
end;
В данном примере мы используем ссылку на тип nameList (^nameList) перед
тем, как мы определили сам тип nameList. Нужно это для того, чтобы внутри
определения типа использовать ссылку на этот самый тип.
Теперь о том, как цепочка данных будет реализована в программе и
в памяти компьютра. Нам необходимо запомнить ссылку на самый первый
элемент данных. Ко всем последующим элементам можно обращаться
по ссылке из первого элемента:
Чтобы лучше понять, как это организовано, можно предложить аналогию
с обыкновенной очередью людей. Представьте, что вы приходите на прием
к врачу и видите в холле 15 человек. Вы спрашиваете обычно "Кто крайний?" и
садитесь ждете, когда тот, кто перед вами пройдет в кабинет. В принципе,
вам не важно знать всю последовательность пациентов, стоящих в очереди
перед вами, вам не надо знать, кто стоит за вами (если у вас есть эта
информация, то вот вам пример двунаправленного списка). Все, что вам нужно,
чтобы попасть в кабинет - это информация о том, кто перед вами. Обычно
списки пополняются добавлением записи в конец очереди (приходит еще один
посетитель и занимает очередь в конце), но иногда элементы могут добавлятся
и не в конец списка (пришел пациент с рентгена и встал в начало очереди -
добавили элемент в начало списка - он стал первым, а бывший первый стал
за ним; пришел знакомый А одного из стоящих в очереди Х и встал перед ним - он
стал за тем, за кем был Х, а Х стал за А). Кто-то ушел из очереди - вот
пример удаления элемента из списка - тот кто стоял за ушедшим, встает за тем,
кто стоял перед ушедшим.
Обратите внимание, что совершенно не важно, где физически находятся элементы
в памяти. Они не обязаны идти по порядку, как в массивах. Продолжая аналогию
с очередью в кабинет врача - совершенно не важно, кто где сидит в холле. Вполне
возможно, что ближайший к кабинету пациент стоит в конце очереди.
Создание списка. Посмотрите на объявленные переменные:
var firstElement,element,lastElement:ptrNameList;
Эти переменные являются лишь адресами областей памяти, в которых могут
располагаться реальные данные. Если вы добавите, например, переменную
element в окно
просмотра переменных, то увидите нечто подобное: PTR($605E,$0).
Чтобы посмотреть данные, нужно написать element^, тогда вы увидите
реальную запись.
Далее начинаем читать список из файла. Предположим сначала, что в нашем
списке уже есть три элемента и мы добавляем четвертый. Прочитали строку из
файла. Та строка, которая должна быть четвертым элементом, помещается
во временную переменную String. Схематически это представлено так:
Добавление любого элемента в список можно разбить на три этапа:
1. Создаем в памяти компьютера место для хранения переменной. В данный
момент ссылочная переменная element указывает именно на эту
область.
new(element);
Обратите внимание, что на этом этапе element^.name и
element^.next не определены.
2. Изменяем значение ссылки последнего элемента с nil на element
last_element^.next := element;
3. Присваиваем значения .name и .next для ссылочной переменной.
element^.name := nameString;
element^.next := nil;
Элемент добавлен.
Обратите внимание, что если у какого-либо элемента element определен
следующий за ним элемент, то имеет смысл запись:
element^.next^.next
Данная конструкция будет ссылаться на следующий за следующим элемент.
Это свойство позволяет перемещаться по всему списку используя только
одну ссылочную переменную. Действительно если записать:
element := element^.next
то из такого состояния списка
мы получим следующий:
Теперь как это организовано на практике.
{ Чтение списка }
firstElement := nil;
assign(f,'list.txt');
reset(f);
while not eof(f) do
begin
readln(f,nameString);
if (firstElement = nil) then
begin
new(element);
firstElement := element;
end
else
begin
new(element^.next);
element := element^.next;
end; { end if }
element^.name := nameString;
element^.next := nil;
end; { end while }
close(f);
Перед чтением списка (в данном случае из тектсового файла) переменной,
указывающей на начало списка, присваиваем значение nil, что является
пустым значением для типа pointer.
firstElement := nil;
Далее начинаем в цикле читать строки из файла.
Прочитали строку из файла. Проверяем,
есть ли какое-нибудь ненулевое значение у переменной firstElement.
Если значение нулевое, это означает, что список еще пуст. Тогда мы
резервируем место для новой переменной и указателю element присваиваем
адрес этой области памяти. Это есть начало списка. После этого адрес
начала нашего списка записываем в переменную firstElement.
new(element);
firstElement := element;
Затем присваиваем данные для первого элемента списка:
element^.name := nameString;
И поскольку на данный момент мы не знаем, есть ли в списке еще
элементы (может там всего один и был), указателю следующего за
первым элементом мы присваиваем значение nil.
element^.next := nil;
Потом переходим к чтению следующей строки.
Если же значение firstElement не равно nil, это означает,
что список уже не пуст. Значит далее мы резервируем
область памяти для следующего элемента:
new(temp);
где temp должна быть типа ptrNameList. Теперь надо поставить
элемент в конец списка. По идее надо бы найти ссылку на последний
элемент нашего списка. Но помня о том, что переменная element
указывает в данный момент как раз на последний элемент списка,
можем записать:
element^.next := temp;
Или объединяя два последних оператора в один:
new(element^.next);
Далее присваиваем ссылочной переменной element адрес этого вновь
соднанного элемента:
element := element^.next;
После этого также как и в первом случае, наполняем новый элемент
данными:
element^.name := nameString;
element^.next := nil;
Значение nil для ссылки на следующий элемент для последнего элемента
в списке можно не задававть, если есть другой способ распознавания
последнего элемента списка (например, если параллельно с чтением,
подсчитывать количество элементов n в списке и дальше устраивать
цикл используя полученное значение n. Но я все равно рекомендую
всегда присваивать данным какие-либо значения, поэтому данный способ
предпочтительнее).
Далее для сортировки нам потребуются два метода - сравнение и
перестановка двух ссылочных переменных - firstElementGreaterThanSecond и
switchElementsContent соответсвтвенно. В принципе, оба метода
используются в программе лишь единожды и посему выделение их в
отдельные процедуры сделано чисто для наглядности. Единственное от
чего хочеться уберечь начинающих программистов - сравнение и перестановка
ссылочных переменных это перестановка данных, а не ссылок. То есть, если
у нас определены ссылочные переменные:
var element1,element2,temp:ptrNameList;
то следующее сравнение лишено смысла:
if (element1 > element2) then ...
поскольку в этом случае сравниваются два адреса памяти, а не переменные.
Правильно будет так:
if (element1^.name > element2^.name) then ...
Аналогично с перестановкой переменных. Нельзя обращаться со ссылочными
переменными как, например, с целочисленными при сортировке. Поэтому так
будет неверно:
temp := element1;
element1 := element2;
element2 := temp;
Данные операторы приведут лишь к тому, что вы поменяете местами временные
ссылочные переменные:
было
стало
Как видно, порядок элементов в списке при этом никак не изменился.
Правильно написать перестановку можно двумя способами. Первый и достаточно
простой - поменять содержимое ссылочных переменных, не меняя порядок списка.
В данном случае нам потребуется временная переменная sTemp типа String:
sTemp := element1^.name;
element1^.name := element2^.name;
element2^.name := sTemp;
Второй способ гораздо сложнее и потребует несколько дополнительных операций
по поиску предыдущих элементов для элементов element1,element2. Я даже не
буду приводить здесь программный код для этого способа, а ограничусь лишь
схемой. Возвращаясь к аналогии с очередью к доктору, понятно, что если
необходимо переставить в очереди двух человек, то это означает надо
предупредить и "поменять следующего" у четырех людей - у двух, которые
меняются и у двух, которые стоят за ними.
Что касается собственно сортировки, то простейший метод "пузырька"
для численного массива а[N]:
for k := 1 to N-1 do
for j := 1 to N-k do
if (a[j] > a[j+1]) then
begin
temp := a[j];
a[j] := a[j+1];
a[j+1] := temp;
end;
Как видно внутренний цикл идет с постоянным уменьшением правой границы цикла.
В нашем же случае нам необходимо найти последний элемент списка
и после каждой итерации перемещать этот последний элемент на шаг
влево, пока не будет достигнут первый элемент. А как произвести
операцию сравнения и перестановки для
ссылочных переменных вы уже знаете.
Полный текст программы приведен ниже.
|
