ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 18.02.2021
Просмотров: 715
Скачиваний: 1
Работа алгоритма продемонстрирована на Рис.4. Данная вставка не работает, если добавление должно происходить перед первым узлом списка. Для этого необходимо предусмотреть дополнительный код, проверяющий условие This=HeadList или Pre=nil. В этом случае необходимо изменить значение адреса первого узла списка. Например, так
……….
New(NewNode); {выделяем память под новый узел, указатель - NewNode}
NewNode^.Data:=Xnew {заполняем поле Data для нового узла значением Хnew}
NewNode^.next:= HeadList;{связываем новый элемент NewNode с первым HeadList}
HeadList:=NewNode; {связываем первый элемент HeadList с новым NewNode}
……….
Создание упорядоченного списка.
Для получения упорядоченного списка вовсе не обязательно сортировать его после построения, достаточно добавлять новый элемент таким образом, чтобы список все время оставался упорядоченным. Такой метод позволяет иметь упорядоченный список на каждом шаге. Ключом, по которому производиться упорядочивание будем считать значение информационного поля Data. Структура узла списка выглядит следующим образом:
type
PElem = ^Elem;
Elem = record
Data : Integer; {Данные, хранящиеся в узле списка –целое число}
Next : PElem;
end;
При добавлении нового элемента в такой список необходимо предусмотреть следующие варианты:
-
добавление в пустой список;
-
добавление в начало списка, когда новый элемент меньше существующего первого;
-
добавление в середину существующего списка на подходящее место (частный случай этой ситуации – добавление в конец списка).
В третьем случае требуется сначала определить место, куда следует вставить новый элемент. Для этого будем двигаться по списку до тех пор, пола либо не найдется элемент, больший или равный вставляемому, либо не будет достигнут конец списка. Воспользуемся дополнительным указателем на предыдущий элемент – Pre. Все это учтено в процедуре Insert. Параметры процедуры P - указатель на начало списка, e - значение нового элемента.
procedure Insert(var p: PElem; e: Integer);
// p - указатель на список, e - значение нового элемента
var Temp,Pre,This: PElem;
Found: Boolean; // признак того, что место для вставки найдено
begin
if p=nil then
begin // список пуст, создание первого элемента, вариант 1.
new(p);
with p^ do begin
Data:=e;
Next:=Nil;
end;
end
else
begin // вставка элемента в список, варианты 2, 3
if e<=p^.Data then
begin // вставка перед списком, вариант 2
new(This);
with This^ do begin
Data:=e; Next:=p
end;
p:=This; // новое начало списка
end
else
begin // поиск места и вставка, начиная со второго элемента, вариант 3
found:=false; // место не найдено
This:=p^.Next; // текущий элемент равен второму
Pre:=p; // предыдущий равен первому
while not found and (This<>Nil) do // поиск места для вставки
if e<=This^.Data then
found:=true // место найдено
else
begin // двигаемся дальше по списку, запоминая адрес
// предыдущего элемента в переменной Pre
Pre:=This; This:=This^.Next;
end;
// добавляем новый элемент со значение е между Pre и This
new(Temp);
with Temp^ do begin
Data:=e; Next:=This;
end;
Pre^.Next:=Temp;
end
end
end;
Процедура Insert корректно работает в случае, если новый элемент необходимо добавить в конец списка (при поиске подходящего места по условию e<=This^.Data дошли до конца списка). При этом значение This=nil будет записано в поле Next последнего элемента.
Использование упорядоченного связного списка для частотного анализа данных
В качестве примера использования упорядоченного списка рассмотрим построение частотного распределения целых чисел. Эта задача возникает при анализе данных, когда необходимо определить, сколько и какое число встретилось раз, т.е. определить частоту появления каждого числа.
Решение заключается в следующем. Создадим список, который будет содержать числа. Если число встретилось первый раз, то оно заноситься в список. Если такое число уже есть в списке, то увеличивается счетчик появления этого числа. Поэтому внесем некоторые изменения в описание элемента списка Elem, добавив новое целочисленное поле cnt, которое будет являться счетчиком повторений. В основе алгоритма лежит процедура Add(), всегда вставляющая новый элемент в упорядоченный список. Однако теперь требуется дополнительная проверка на наличие в списке значения. В остальном процедура Add() аналогична процедуре Insert() описанной выше.
Рис.5 Блок-схема обработки значения при частотном анализе.
Листинг программы частотного анализа целых чисел.
program testsortlist;
{$APPTYPE CONSOLE}
type
PElem=^Elem;
elem=record
Data: integer; // значение
Cnt:integer; // число повторений данного значения
next: pelem;
end; {record}
var top: pelem; // указатель на начало частотного списка
N:integer;
Procedure Lists(p:pelem); // процедура вывода списка на экран, p – указатель на начало
begin
while p<>Nil do
begin writeln(p^.Data,' - ',P^.cnt); p:=p^.next; end;
writeln;
end;
Procedure Del(var p:pelem); // процедура удаления списка, p – указатель на начало
var g:pelem;
begin
while p<>nil do
begin g:=p; p:=p^.next; dispose(g); end;
end;
Procedure add (var Head:pelem; X:integer);// добавление значения Х в список Head
var Pre,This:Pelem;
Found:boolean;
Procedure Insert; { Процедура Insert вставляет новый элемент между Pre и This, учитывая случаи создания первого элемента и добавления в середину или конец существующего}
var P:Pelem;
begin
New(p);
P^.Data:=X;
P^.next:=This;
P^.Cnt:=1;
If pre= nil then
Head:=P //1-й элемент или добавление перед первым
else
Pre^.next:=P; // середина или конец
end;
begin
Pre:=Nil;
This:=Head;
Found:=False;
While (This<>Nil) and not Found Do // Поиск подходящего места вставки
if This.Data >= X then
Found:=True // место найдено
else begin
pre:=This; // место не найдено, переходим к следующему элементу списка
This:=This^.next;
end;
if not found then
Insert // дошли до конца списка или список пуст
else if This^.Data=X then // нашли место
Inc(This^.Cnt) // значения равны – увеличиваем счетчик
else
Insert; // значение больше Х, вставка перед элементом This
end;
begin {Начало программы. Вводим и анализируем числа. Ввод числа 999 – признак окончания ввода значений }
top:=Nil; {инициализациа списка}
Repeat
Write('Input N , (999-Exit) --> ');
Readln(n);
If N <> 999 then Add(top,N); {Добавление числа N в список Top}
until n=999;
Lists(top); { Вывод частотного списка на экран}
Del(top); {Удаление списка}
readln;
end.
Стеки
Еще одной известной и широко используемой структурой данных является стек. Стек представляет собой структуру, которая позволяет выполнять две основных операции: заталкивание для вставки элемента в стек и выталкивание с целью считывания данных из стека. Структура устроена таким образом, что операция выталкивания всегда возвращает элемент, вставленный в стек последним (самый “новый” элемент в стеке). Другими словами, элементы в стеке считываются в порядке, обратном порядку их записи в стек. Благодаря такому устройству стек известен как контейнер магазинного типа.
Рис.6 Операции заталкивания и выталкивания для стека
Написание кода стека не представляет никаких трудностей. Причем существуют два варианта реализации: первый - на основе односвязного списка, второй - на основе массива. Как и в случае со списками, будем считать, что записываться и считываться из стека будут целые числа. Рассмотрим организацию стека на базе связного списка.
В реализации стеков на основе односвязных списков операция заталкивания представляет собой вставку элемента в начало списка, а операция выталкивания - удаление элемента из начала списка и считывание его данных. Обе операции не зависят от количества элементов в списке, следовательно, их можно отнести к классу О(1).
Для работы со стеком необходимы следующие операции:
-
Инициализация стека, т.е. подготовка структуры.
-
Включение нового элемента в стек (заталкивание)
-
Проверка стека на пустоту.
-
Извлечение элемента из стека (выталкивание).
Реализовать работу стека можно в модуле, объявив в интерфейсной части минимальный набор процедур и функций:
Procedure Push(var Top:PElem; N:integer);
Процедура Push добавляет новый элемент в стек. Параметры процедуры : Top – указатель на начало стека, N – значение нового элемента. Обратите внимание, что параметр Top является параметром-переменной, т.к. при добавлении нового элемента всегда будет меняться и адрес начала стека.
Procedure Pop(var Top:PElem; var N:integer);
Процедура Pop извлекает из стека значение первого элемента через параметр-переменную N, удаляет первый элемент и переставляет указатель Top на следующий элемент. Параметры процедуры: Top – указатель на начало стека, N – передаваемое в программу значение первого элемента.
Function IsEmpty(Top:PElem):Boolean
Функция IsEmpty возвращает значение true, если стек пуст (если указатель на начало стека пустой). Параметр функции: Top – указатель на начало стека.
Перед вызовом процедуры Pop пользователь должен проверить есть ли элементы в стеке с помощью функции IsEmpty. Попытка извлечения элемента из пустого стека вызовет ошибку. Приведем листинг модуля Steck. Инициализацию стека необходимо сделать в программе до использования процедур и функций из модуля.
Листинг модуля Steck
Unit Steck;
interface
type
PElem = ^Elem;
Elem = record
Data : Integer;
Next : PElem;
end;
Procedure Push(var Top:PElem; N:integer);
Procedure Pop(var Top:PElem; var N:integer);
Function IsEmpty(Top:PElem):Boolean
implementation
Procedure Push(var Top:PElem; N:integer);
Var Temp:Pelem;
begin
new(Temp); // выделяем память под новый элемент
Temp^.Data:=N; // записываем значение N в новый элемент
Temp^.Next:=Top; // связываем новый элемент с первым
Top:=Temp;// новое начало стека – первый элемент указывает на новый
end;
Procedure Pop(var Top:PElem; var N:integer);
Var Temp:Pelem;
begin
N:=Top^.Data; // считываем значение из первого элемента в N
Temp:=Top; // запоминаем адрес первого элемента
Top:=Top^.Next; // переставляем указатель на первый элемент на следующий
Dispose(temp); // удаляем бывший первый элемент
end;
Function IsEmpty(Top:PElem):Boolean
begin
Result:=Top=nil; //
end;
end. {Steck}
Продемонстрируем использование стека из модуля Steck на примере решения следующей задачи – в текстовом файле записаны целые числа, распечатать на экране все числа в обратном порядке. Из условия задачи видно, что количество чисел в файле заранее неизвестно, поэтому поместить их все в массив и распечатать содержимое массива обратном порядке проблематично (размер массива должен быть задан заранее). Прочитать текстовый файл в обратном порядке невозможно, так как для текстовых файлов определен только последовательный доступ к его элементам. Один из простых вариантов решения этой задачи будет последовательное чтение данных из файла и заталкивание их в стек, потом надо просто извлечь все данные из стека и вывести их на экран. Листинг программы приведен далее. Из модуля Steck в программе использованы процедуры и функции и описание указателя на элемент стека тип - PElem.
Листинг программы, использующей модуль Steck.
Program TestSteck;
{$APPTYPE CONSOLE}
Uses SysUtils, Steck; // подключение модулей
Var N:integer;
HeadSteck:PElem; // HeadSteck – указатель на первый элемент стека
FileName:string; // имя файла с данными
F:text; // файловая переменная
Count:integer; // счетчик считанных из файла чисел
begin
HeadSteck:=nil; // инициализация стека, стек – пуст
repeat
Write(‘Введите имя файла с данными’);
Readln(FileName);
until FileExists(FileName); // цикл с вводом имени файла будет продолжаться до тех пор,
//пока не будет введено имя существующего файла
Assign(F,FileName); // связываем файловую переменную f с именем файла FileName
Reset(F); // открываем файл для чтения
Count:=0;
While not Eof(F) do
begin
Read(F,N) ; // читаем из файла число в переменную N
Inc(Count);
Push(HeadSteck,N); // заталкиваем число N в стек
end;
Close(f);
Writeln(‘Всего считано и добавлено в стек ‘, Count, ‘ чисел);
While not IsEmpty(HeadStecK) do // пока стек не пуст, будем извлекать данные и печатать
begin
Pop(HeadStecK,N);
Writeln(N);
end;
Readln;
end.
Очереди
Следующей широко известной базовой структурой данных является очередь. В то время как извлечение элементов из стека происходит в порядке, обратном тому, в котором они вносились, в очереди элементы выбираются в порядке их добавления. Таким образом, очередь относится к структурам типа "первый пришел, первый вышел" (FIFO – first in, first out). С очередью связаны две основные операции: постановка в очередь (т.е. добавление нового элемента в очередь) и снятие с очереди (т.е. извлечение из нее самого старого элемента).
Иногда эти операции ошибочно называют заталкиванием и выталкиванием. Это абсолютно неверные термины для очереди. Ближе к истине будут слова включение и исключение.
Рис.7. Постановка в очередь и снятие с очереди
Как и стеки, очереди можно реализовать на основе односвязных списков или массивов. Тем не менее, в отличие от стеков, очень трудно добиться высокой эффективности реализации на основе массивов. Если в процессе работы очередь то очень длинная, то короткая, имеет смысл реализовать очередь с использованием динамической структуры. К тому же организация очередей на базе связных списков очень проста. Поэтому рассмотрим построение очереди на базе односвязных списков. Фактически мы должны смоделировать обычную очередь в универмаге. С помощью списков это можно сделать очень легко, поскольку сами списки по своей сути являются очередями. Просто для моделирования очереди элементы должны добавляться с одной стороны и удаляться с другой. При использовании односвязного списка снятие с очереди будет выполняться с начала списка, а постановка в очередь - в конец списка. Очевидно, что операции с очередью не зависят от количества элементов в ней, т.е. они принадлежат к классу О(1).
Для работы с очередью необходимы следующие операции:
-
Инициализация очереди, т.е. подготовка структуры.
-
Включение нового элемента в конец очереди.
-
Проверка очереди на пустоту.
-
Извлечение элемента из начала очереди.
При работе с очередью удобно хранить два указателя: указатель на начало очереди (голову) и указатель на последний элемент (хвост). Использование последнего указателя позволяет убрать последовательный перебор всех элементов из алгоритма добавления нового узла в конец очереди. Для определения очереди возьмем тип запись (Record) с именем Tqueue, содержащую в качестве полей два этих указателя (Head - начало, Tail - конец). В этом случае очередь будет характеризоваться только одним параметром.
Листинг динамической реализации очереди
type
PElem = ^Elem; // описание указателя на элемент очереди
Elem = record // описание элемента очереди
Data : Integer;
Next : PElem;
end;
Tqueue =record // определение очереди
Head, // голова очереди
Tail: Pelem; // хвост очереди
end;
procedure InitQueue(var q:TQueue); { инициализация очереди, указателю на начало очереди присвоить пустое значение}
begin
q.Head:=nil;
end;
function QueueIsEmpty(q:TQueue): Boolean; { проверка очереди на пустоту, очередь пуста, если указатель на начало равен nil}
begin
Result:=q.Head = nil;
end;
procedure InQueue(var q:TQueue; x:integer); // поставить в очередь
var P:Pelem;
begin
new(p); {создаем и заполняем значениями новый элемент очереди}
p^.Data:=x;
p^.next:=nil;
{Далее необходимо рассмотреть 2 ситуации:
а) очередь пуста - добавление первого элемента очереди
б) очередь не пуста - добавление нового элемента в конец }
if QueueIsEmpty(q) then // очередь пуста – создаем первый элемент
begin
q^.Head:=p; q^.Tail:=p;
end
else
With q do begin
Tail^.next:=p; Tail:=p; { присоединяем новый элемент к концу очереди, присваиваем указателю на конец очереди новое значение}
end;
end;
function OutQueue(var q:TQueue):integer; // взять из очереди
var P:Pelem;
begin
With q do begin
Result:=Head^.Data; // возвращаем значение поля Data
p:=Head; // запоминаем адрес начала очереди
Head:=Head^.Next; // переставляем начало очереди на следующий элемент
Dispose(p); // удаляем бывший первый элемент
end;
end;
Функцию OutQueue (извлечь элемент из очереди) можно вызывать только в том случае, когда очередь не пустая. Поэтому перед извлечением очередного элемента необходимо проверять очередь на не пустоту, вызывая функцию not QueueIsEmpty.
Продемонстрируем использование очереди на решении следующей задачи. В текстовом файле записаны положительные и отрицательные числа. Вывести на экран сначала отрицательные, а затем положительные числа не изменив порядок их расположения. Выполнить данные действия необходимо за один проход по файлу.
С использованием очереди данная задача решается очень просто. Читаем число из файла, если оно положительное, то добавляем число в очередь, иначе выводим его на экран. После чтения всех чисел из файла, отрицательные выведены на экран, а положительные находятся в очереди. После этого необходимо извлечь все положительные числа из очереди и вывести их на экран