Тестирование списка

type

pstud=^stud; {- указатель на запись}

stud=record {Запись:}

fio:string[20]; {- фамилия студента}

nz:integer; {- номер зачётки}

rs:real; {- размер стипендии}

ptr:pstud; { - указатель на следующий элемент списка}

end;

var

spis:pstud;

i:integer;

err:boolean;

{ --------Инициализация типизированных констант записей-------------}

const

st1:stud=(fio:'Иванов';nz:12;rs:50;ptr:nil); st2:stud=(fio:'Петров';nz:13;rs:40;ptr:nil);

st3:stud=(fio:'Сидоров';nz:14;rs:30;ptr:nil);

{-----------Вывод данных одной записи-------------------}

procedure p(st:stud);

begin

writeln(st.fio:15,st.nz:4, st.rs:7:2);

end;

{-----------Проверка пустоты списка-------------------}

function pp(s:pstud):boolean;

begin

if s =nil then

begin

writeln ('список пуст');

pp:=true

end

else pp:=false;

end;

{-----------Дополнение списка одной новой записью-------------------}

procedure dop(var s:pstud; dat:stud );

var

nov,cur,pr:pstud;

key:integer;

begin

cur:=s;

pr:=nil;

key:= dat.nz;

writeln (' key=', key);

new(nov);

nov^:=dat;

while(cur<>nil) and (cur^.nz < key) do

begin

pr:=cur; {- движение вдоль списка}

cur:=cur^.ptr;

end;

nov^.ptr:=cur; {подключение нового элемента справа}

{Подключение нового элемента слева:}

if pr=nil then s:=nov {- в начало списка}

else pr^.ptr:= nov { - в середину списка}

end;

{-----------Вывод данных списка-------------------}

procedure cht(s:pstud );

var

cur:pstud;

begin

writeln('чтение списка');

cur:=s;

if pp(s) then exit; { - проверка пустоты списка }

while cur<> nil do

begin

p(cur^); { вывод данных списка }

cur:=cur^.ptr; {- движение вдоль списка}

end

end;

{-----------Поиск в списке по заданному значению ключа------------------}

procedure poisk(s:pstud; tnz:integer);

var

cur:pstud;

begin

writeln('поиск tnz', tnz);

if pp(s) then exit; { - проверка пустоты списка }

cur:=s;

while (cur<> nil) and (cur^.nz<>tnz) do {- движение вдоль списка}

cur:=cur^.ptr;

if cur=nil then writeln('поиск неуспешен')

else p(cur^); {вывод найденного элемента списка}

end;

{-----------Удаление из списка записи с заданным значением ключа----------}

procedure ud(var s:pstud; tnz:integer);

var

cur,pr:pstud;

begin

writeln('удаление tnz', tnz);

if pp(s) then exit; { - проверка пустоты списка }

cur:=s;

pr:=nil;

while (cur<> nil) and (cur^.nz<>tnz) do {- движение вдоль списка}

begin

pr:=cur;

cur:=cur^.ptr;

end;

if cur=nil then begin

writeln('удаление неуспешно');

exit

end;

p(cur^);

if pr=nil then begin

writeln('удаляем 1-й элемент списка');

s:=cur^.ptr;

end

else begin

writeln('удаляем не 1-й элемент списка');

pr^.ptr:=cur^.ptr;

end;

dispose(cur);

end;

{-----------Уничтожение списка и освобождение ОП------------------}

procedure osv(var s:pstud );

var

cur,pr:pstud;

begin

writeln(' список уничтожается!!');

if pp(s) then exit; { - проверка пустоты списка }

cur:=s;

pr:=nil;

while cur<> nil do

begin

pr:=cur;

cur:=cur^.ptr;

dispose(pr);

end;

s:=nil

end;

{-----------Основная программа-----------------------------}

begin

assign (output,'150.pas');

rewrite(output);

spis:=nil;

writeln(#10#13, 'проверка пустоты списка чтением,поиском, удалением');

cht( spis);

poisk(spis,12);

ud(spis,12);

writeln('заполнение списка');

dop( spis, st1 );

dop( spis, st2 );

dop( spis, st3 );

cht(spis);

writeln('поиск элементов списка по заданному значению ключа');

poisk(spis,13);

poisk(spis, 12);

poisk(spis,5);

poisk(spis,14);

writeln('удаление данных из списка и проверка поиском');

ud(spis,13);

poisk(spis,13);

ud(spis,12);

poisk(spis,12);

writeln('дополнение списка');

dop( spis, st3 );

dop( spis, st1 );

dop( spis, st3 );

cht(spis);

writeln('уничтожение списка');

osv(spis);

writeln('проверка пустоты списка чтением');

cht(spis);

close(output);

end.

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

Формальные параметры процедуры dop:

s – указатель на начало (вершину списка), параметр-переменная;

dat –запись типа stud, содержащая информацию для нового элемента списка, параметр – значение.

Локальные переменные:

cur – указатель текущего (очередного) элемента списка;

pr – предыдущего (перед cur) элемента списка;

nov – указатель на новый элемент списка;

key – значение ключа - номера зачётки нового элемента списка.

Начальные значения локальных переменных:

cur:=s; – указывает на начало (вершину списка), если список пуст, s равен nil;

pr:= nil; – не указывает ни на что;

key:=dat.nz; – значение ключа нового элемента списка.

В процедуре dop с помощью процедуры new(nov) для нового элемента списка выделяется ОП, адрес которой запоминается в nov –локальном указателе списка. Затем новый элемент списка заполняется информацией nov^:=dat;. Новый элемент списка должен быть подключён к списку, не нарушив упорядоченности его элементов, то есть после элемента, имеющего nz меньше key, и до элемента, имеющего nz не менее key.

Продвижение вдоль списка от его начала к его концу осуществляется с помощью двух указателей: cur и pr. Выполним анализ значений cur, cur^.nz и key:

1. если cur<> nil и cur^.nz< key, то есть список не пуст и значение nz текущего элемента меньше key, происходит перемещение указателей: cur и pr вправо к концу списка с помощью операторов:

pr:= cur; - указатель предыдущего элемента адресует текущий;

cur:= cur^.ptr;- указатель текущего элемента переключается на следующий справа элемент списка;

2. если cur:= nil; или cur^.nz >key= key, продвижение указателей cur и pr прекращается, так как место для нового элемента в списке найдено:

- обнаружен конец списка cur:= nil;

- найден элемент списка, значение ключа которого не меньше key.

Место найдено. Новый элемент надо включить в список с помощью указателей:

- справаот нового элемента путём определения значения его указателя nov^.ptr:= cur;

- слева от нового элемента путём определения значения указателя на начало нового элемента.

Для определения значения указателя слева на новый элемент списка анализируем значение pr:

1. если pr= nil, то есть движения вдоль списка не было, новый элемент становится в начало списка. Указатель его начала (вершины) получает значение адреса нового элемента s:= nov;. Возможные случаи:

- cur = pr= nil; - список пуст и новый элемент становится первым и его единственным элементом;

- cur<> nil и pr= nil; - список не пуст, но новый элемент имеет значение ключа, меньшее, чем ключ первого элемента;

2. если pr<> nil, то движение вдоль списка было, pr адресует левый элемент старого (не дополненного) списка, к которому и присоединяется новый элемент списка pr^.ptr:= nov;.

Процедура cht предназначена для вывода данных всего списка.

Формальные параметры процедуры cht:

s – указатель на начало (вершину списка), параметр-значение.

Локальные переменные:

cur – указатель на очередной элемент списка.

Начальные значения локальных переменных:

cur:=s; – указывает на начало (вершину) списка.

Сначала проверяется заполнение списка с помощью функции pp. Её значение true, если список пуст. Если значение pp false, список не пуст, начинается вывод всех значений элементов списка с использованием указателя cur.

Если cur<> nil, то при каждом его значении:

a. выводится содержимое очередного элемента с помощью процедуры p(cur^);

b. указатель cur переключается на следующий элемент списка cur:= cur^.ptr;.

При cur= nil выполнение процедуры cht завершается.

Процедура poisk предназначена для поиска и вывода требуемого значения элемента списка.

nz - ключ-номер зачётки.

Формальные параметры процедуры poisk:

s – указатель на начало (вершину списка), параметр- значение;

tnz – значение поискового признака, параметр – значение.

Локальные переменные:

cur – указатель на очередной элемент списка.

Начальные значения локальных переменных:

cur:=s; – указывает на начало (вершину) списка.

До начала поиска производится проверка заполнения списка и выдача сообщения так же, как в cht.

Если список не пуст, организуется продвижение вдоль списка от его начала до элемента со значением nz= tnz или до конца списка.

Анализируем результат выражения (cur<> nil) and (cur^.nz<> tnz):

1. если оно истинно, то есть конец списка не достигнут и значение nz очередного элемента не равно заданному, то указатель cur перемещается к следующему элементу списка cur:= cur^.ptr;

2. если оно ложно, поиск завершён, движение прекращается:

- список исчерпан;

- найден элемент списка nz= tnz.

Из анализа значения cur следует:

1. если cur= nil, то достигнут конец списка, требуемый элемент не найден, поиск не успешен;

2. если cur<> nil, то есть cur^.nz= tnz, требуемый элемент найден, вывод производится с помощью p(cur^). Поиск завершён.

Процедура ud предназначена для поиска и удаления заданного элемента списка.

nz - ключ-номер зачётки.

Формальные параметры процедуры ud:

s – указатель на начало (вершину списка), параметр- переменная;

tnz – значение поискового признака, параметр – значение.

Локальные переменные:

cur – указатель текущего (очередного) элемента списка;

pr – предыдущего (перед cur) элемента списка;

Начальные значения локальных переменных:

cur:=s; – указывает на начало (вершину) списка;

pr:= nil;– не указывает ни на что.

Схема удаления заданного элемента списка

Поиск заданного элемента списка аналогичен поиску в процедуре poisk.

Далее поочерёдно анализируем значения cur и pr:

1. если cur= nil, то достигнут конец списка, требуемый элемент не найден, удаление не успешно;

2. если cur<>nil, требуемый элемент найден, на него указывает cur, элемент выводится с помощью p(cur^). Затем определяется, удаляется первый или очередной элемент списка.

Для этого анализируем значение pr:

1. если pr= nil, то удаляется первый элемент списка, s переносится на второй элемент списка s:= cur^.ptr;

2. если pr<>nil, то удаляется очередной или последний элемент списка.

Указатель слева от удаляемого элемента переключается на элемент справа от удаляемого элемента, исключая удаляемый элемент из списка путём выполнения pr^.ptr:= cur^.ptr;.

ОП освобождается с помощью dispose(cur);.

Процедура osv предназначена для освобождения ОП списка, то есть его уничтожения.

Формальные параметры процедуры osv:

s – указатель на начало (вершину списка), параметр- переменная.

Локальные переменные:

cur – указатель текущего (очередного) элемента списка;

pr – предыдущего (перед cur) элемента списка;

Начальные значения локальных переменных:

cur:=s; – указывает на начало (вершину) списка;

pr:= nil; – не указывает ни на что.

Указатель cur перемещается до конца списка. При каждом текущем значении указателя cur, не равном nil, происходит продвижение вдоль списка:

pr:=cur; - указатель pr предыдущего элемента переключается на следующий элемент списка;

cur:= cur^.ptr; - указатель cur переключается на следующий элемент списка;

dispose(pr); - освобождает ОП очередного элемента списка.

По завершению освобождения ОП обнуляется указатель на начало списка s:= nil; . На этом завершается выполнение процедуры osv.

Литература

1. Фаронов В.В Турбо-Паскаль 7.0.Начальный курс: учебное пособие. М.: Нолидж, 2002. -616 с.

2. Епанишников А.М., Епанешников В.А. Программирование в среде Turbo -Pascal 7.0. М.: Диалог- МИФИ. 2001. -288 с.

3. Коффман Э.Б. TURBO PFSCAL. -М.: Издательский дом «Вильямс», 2003.-896 с.

4. Пильщиков В.Н. Сборник упражнений по языку Паскаль. - М.: Наука, 1988.- 160 с.

5. Климова Л.М. Практическое программирование. Решение типовых задач. Pascal 7.0- M.: Кудиц -образ. 2000.- 496 с.