HOME ПРИМЕРЫ THANKS НОВИЧКАМ ДОКИ LINKS JavaScript Mail


 
В этот день много лет назад...
1 мая. В 1891 году (126 лет назад) - Первая маевка в Петербурге, организованная социал-демократической группой М.И. Бруснева.
 
 

Turbo Pascal Examples

Графика:
Построение графика функции
Прыгающий по экрану мячик.
Качание маятника.
Вложенные цветные круги.
Броуновское движение. Использование объектов.
Матрицы и массивы:
Сортировка элементов массива.
Удаление одинаковых элементов.
Простой пример на поворот матрицы.
Сортировка методом Шелла. +функции измерения временных интервалов.
Проверка выпуклости многоугольника.
Перемоножение матриц
Вычисление определителя матрицы. Рекурсия.
Нахождение обратной матрицы.
Задача об автостоянке.
Рекурсия. Подземелье сокровищ.
Численные методы:
Задачка на определение угла между стрелками часов.
Проверка на принадлежность точки многоугольнику.
Нахождение точки пересечения двух отрезков на плоскости.
Сортировка методом Шелла. +функции измерения временных интервалов.
Сортировка методом "пузырька". Пример на динамические структуры данных. Связанные списки.
Нахождение корня функции методом половинного деления.
Вычисление арккосинуса
Нахождение суммы цифр натурального числа.
Работа с фалами:
Рекурсивное сканирование директорий.
Работа со строками:
Работа со словами в предложении с разделителями.
Простейший синтаксический анализатор для распознавания и вычисления многчлена.
Синтаксический анализатор для распознавания и вычисления многчлена.
Работа со строками: смена кодировки, удаление тегов из HTML текста, обработка
Переименование файлов из кириллицы в латиницу.
Выдача контекстной подсказки.
Частотный словарь символов.
Подсчет повторяющихся символов в строке.
Ссылочные переменные:
Моделирование стека.
Пасьянс "Косынка".
Игры:
Пасьянс "Косынка".
Игра "Питон"
Игра "Анацефал". Пример использования объектов.
Игра "Минное поле"
Большие проекты:
Электронная картотека (без исходника)


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

В тех случаях, когда неизвестен начальный набор данных, нельзя использовать статические конструкции вроде массивов, а необходимо создавать объекты по мере необходимости во время работы программы. Такие структуры называются "динамическими". Самое главное при работе с такими структурами помнить, что переменные, которыми вы манипулируете являются лишь ссылками на реальные данные.
Начнем с объявления. Ссылочная переменная представляет собой совокупность двух типов данных. Первый тип - это собственно данные, которые могут быть любого разрешенного типа (в этой программе это тип 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. Схематически это представлено так:
Шаг 0. Строка сохранена во временной переменной
Добавление любого элемента в список можно разбить на три этапа:
1. Создаем в памяти компьютера место для хранения переменной. В данный момент ссылочная переменная element указывает именно на эту область.
    new(element);
Шаг 1. Резервирование места в памяти.
Обратите внимание, что на этом этапе element^.name и element^.next не определены.
2. Изменяем значение ссылки последнего элемента с nil на element
    last_element^.next := element;
Шаг 2. Ссылка с последнего элемента указывает теперь на element
3. Присваиваем значения .name и .next для ссылочной переменной.
  element^.name := nameString;
  element^.next := nil;
Шаг 3. Присваиваем значения .name и .next для ссылочной переменной
Элемент добавлен.

Обратите внимание, что если у какого-либо элемента 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;

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

Полный текст программы приведен ниже.



program sortnames;
type
  ptrNameList = ^nameList;
  nameList = record
    name:String;
    next:ptrNameList;
    end;
var firstElement,element,lastElement:ptrNameList;
    f:text;
    nameString:String;

function firstElementGreaterThanSecond(element1,element2:ptrNameList):boolean;
  begin
  firstElementGreaterThanSecond := (element1^.name > element2^.name);
  end;

procedure switchElementsContent(element1,element2:ptrNameList);
var temp:String;
  begin
  temp := element1^.name;
  element1^.name := element2^.name;
  element2^.name := temp;
  end;

procedure printList;
var element:ptrNameList;
  begin
  element := firstElement;
  while (element<>nil) do
    begin
    writeln(element^.name);
    element := element^.next;
    end;
  writeln('конец списка');
  end;


begin

{ Чтение списка }

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);

{ Печать исходного списка }

writeln('Исходный список');
printList;

{ Сортировка методом пузырька }

element := firstElement;

{ Найдем последний элемент }

while (element<>nil) do
  element := element^.next;
lastElement := element;

while (firstElement<>lastElement) do
  begin
  element := firstElement;
  while (element^.next<>lastElement) do
    begin
    if firstElementGreaterThanSecond(element,element^.next) then
      switchElementsContent(element,element^.next);
    element := element^.next;
    end;
  lastElement := element;
  end;

{ Печать результата }

writeln('Отсортированный список');
printList;
end.

 

 

 

 

 

 

 


HOME