Создание списков в языке Паскаль

Программа включает три процедуры реализации линейного списка: добавление нового элемента на указанное место в списке, удаление элемента с указанным номером из списка, просмотр содержимого списка. Специальное действие также реализовано с помощью отдельной процедуры.

Процедура добавления: процедуре по ссылке передается ссылка на начало списка. Также передается номер, на котором должен оказаться новый элемент, и значение элемента. Создается новый элемент, его значением становится передаваемый процедуре аргумент. Если ссылка на начало равна nil или передаваемый номер элемента равен единице, тогда элемент вставляется на первое место. В противном случае список проходится в цикле либо до нахождения нужного номера, либо до конца списка. Элемент вставляется на найденное место с соответствующей модификацией ссылок.

Процедура удаления: процедуре передается номер удаляемого элемента и (по ссылке) ссылка на начало списка. Если список не пуст, то выполняются следующие действия. Если номер удаляемого равен 1, то модифицируется ссылка на начало, если нет, то список проходится в цикле, либо до нахождения соответствующего номера, либо до конца списка. Если номер удаляемого находится в пределах списка, то соответствующий элемент удаляется с высвобождением памяти и модификацией ссылки на этот элемент.

Процедура просмотра: Список просто проходится в цикле до конца с выводом каждого элемента.

Специальная процедура: сначала список проходится в цикле с подсчетом количества элементов. Если размер списка меньше чем переданное процедуре количество удаляемых элементов, то ничего не происходит, если меньше, то опять в цикле происходит последовательное удаление элементов с высвобождением памяти, ссылка на начало после этого будет указывать на (k+1) элемент.

Основная программа: реализуется в виде меню. В цикле предлагается ввести число, соответствующее вышеперечисленным процедурам. Цикл завершается, если введен ноль, означающий конец программы. Вначале программа создает список, т. е. присваивает ссылке на начало значение nil.

Описание основных переменных и констант приведено в таблице 1.

Таблица 1

Описание основных переменных и констант Имя Тип Назначение Основная программа: pn link Ссылка на начало списка. arg integer Значение нового элемента. m integer Переменная меню. Подпрограммы: Neo, ind link Ссылочные переменные употребляются для прохода списка. i integer Счетчик цикла.

Входными и выходными данными являются целые значения элементов.

Тестовые примеры: программа протестирована на всевозможные действия над списком, в том числе и некорректные, например, удаление элемента из пустого списка или с номером, превышающим размер списка (смотри рисунок 20).

Рис. 20. Тестирование программы ЗАКЛЮЧЕНИЕ При выполнении работы были получены теоретические знания и практические навыки по работе со списками.

На первом этапе выполнения работы был проведен обзор литературных источников по теме работы: «Создание списков в Паскаль». Основными изученными изданиями были книги, написанные Немнюгиным С. А., Поповым В. и Павловской Т. А. Книги описывают программирование на языке высокого уровня Паскаль. Содержат подробное изложение языка программирования. Описание списков содержится в главах посвященных динамическим структурам данных языка Паскаль. Изучение литературы позволило сформировать структуру работы (план изложения материала), выделить основные главы, определить этапы изучения вопроса создания списков в Паскаль.

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

Однако в ряде случаев использование динамических структур оказывается более эффективным, чем статических, а иногда и единственно возможной реализацией поставленной задачи. Обработка больших массивов данных с неопределенным размером вот пример такой задачи. Или сортировка большого объема информации тоже окажется более эффективной с использованием динамических структур.

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

Для того чтобы создать список в Паскаль, был изучен синтаксис языка, структура написания программы на языке Паскаль, изучены основные типы данных используемые в языке. В первой главе работы были определены основные понятия, связанные со списками в Паскаль.

Изучение типов данных позволило представить иерархию типов данных в структурированном виде. Более подробно описан специфический тип указатели. Определен синтаксис описания, особенности данного типа. Данный тип используется при создании списков.

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

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

Теоретические знания по теме списков позволили реализовать программу с создание списка в Паскаль. Результат работы программы это создание списка, добавление в него элементов, удаление из него элементов, удаление сразу нескольких элементов. Написанная программа протестирована на весь функционал. При выполнении практической части произошло полезное ознакомление с механизмом работы динамических структур, которые позволяют создавать структуры данных, ограниченных по размеру только объемом оперативной памяти. Полезно было бы дополнить эту работу реализацией процедуры сохранения списков в файлах и их обратного преобразования в динамику.

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

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ Андреева Т. А Программирование на языке Pascal. — М.: Бином. Лаборатория знаний, 2006. — 240 с.

Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы / Пер. с англ. — М.: Вильямс, 2001. 384 с.

Вирт Н. Алгоритмы и структуры данных. — 2-е изд. — СПб: «Невский Диалект», 2001. — 352 с.

Климова Л. М. Pascal 7.

0.Практическое программирование. Решение типовых задач. Изд. 4-е, доп. М: КУДИЦ-ОБРАЗ, 2003. — 528 с.

Культин Н. Turbo Pascal в задачах и примерах. — СПб.: БХВ-Петербург, 2006. — 256 с.

Малыхина М. П. Программирование на языке высокого уровня Turbo Pascal. — СПб.: БХВ-Петербург, 2006. — 544 с.

Моргун А. Н. Программирование на языке Паскаль (Pascal). Основы обработки структур данных. — М.: Диалектика, 2005. — 576 с.

Немнюгин С.А. Turbo Pascal. — СПб.: Питер, 2000. — 496 с.

Павловская Т. А. Паскаль. Программирование на языке высокого уровня: Учебник для вузов. — СПб.: Питер, 2007. — 393 с.

Попов В. Б. Паскаль и Дельфи. Самоучитель. — СПб.: Питер, 2004. — 544 с.

Рапаков Г. Г. Программирование на языке Pascal. — СПб.: БХВ-Петербург, 2004. — 480 с.

Стивене Р. D elphi. Готовые алгоритмы.

— 2-е изд., стер.: Пер. с англ. Мерещука П. А. — М.: ДМК Пресс; - СПб.: Питер, 2004.

— 384 с.

Сухарев М. Turbo Pascal 7.

0. Теория и практика программирования. — СПб.: Наука и техника, 2006. — 544 с.

Фаронов В.В. Delphi: Программирование на языке высокого уровня: Учебник для вузов. — СПб.: Питер, 2007. — 640 с.

Фаронов В.В. Turbo Pascal. — СПб.: БХВ-Петербург, 2004. — 1056 с.

Федоренко Ю. Алгоритмы и программы на Turbo Pascal. Учебный курс. — СПб.: Питер, 2001. — 240 с.

Домнин Ф. А. Язык программирования Паскаль (Turbo Pascal). Обучающие уроки — 2009. — 28 декабря [Электронный ресурс]. URL:

http://www.life-prog.ru/view_zam.php?id=32&cat=1&page=2 (дата обращения: 16.

05.2012).

Васильев Н. А. Краткая справка по языку программирования Turbo Pascal. — 2004. [Электронный ресурс]. URL:

http://forprogrammer.narod.ru/pascal/index.htm (дата обращения: 16.

05.2012).

Язык Паскаль. Динамические структуры данных. — 2011. — 2 июля [Электронный ресурс]. URL:

http://pas1.ru/dynamicstructures (дата обращения: 16.

05.2012).

Динамические структуры данных в Паскаль. — 2011. — 3 августа [Электронный ресурс]. URL:

http://the-programmer.ru/publ/pascal/obuchenie_pascal/dinamicheskie_struktury_dannykh_v_pascal/7−1-0−157 (дата обращения: 16.

05.2012).

ПРИЛОЖЕНИЕ 1

Создание линейного списка в Паскаль

program Spisok;

type

link = ^kom;

kom = record

ini: integer;

next: link;

end;

var

pn: link;

arg, j, m: integer;

procedure add (var n: link; x, num: integer);

var

neo, ind: link;

i: integer;

begin

new (neo);

neo^.ini:=x;

if n=nil then begin

n:= neo;

neo^.next:=nil;

end

else if num=1 then begin

neo^.next:=n;

n:= neo;

end

else begin

i:=0;

ind:= n;

while (i<>num-2) and (ind^.next<>nil) do begin

i:= i+1;

ind:= ind^.next;

end;

neo^.next:=ind^.next;

ind^.next:= neo;

end;

end; { add }

procedure del (var n: link; num: integer);

var

neo, ind: link;

i: integer;

begin

if n<>nil then begin

if num=1 then begin

neo:=n;

n:=n^.next;

dispose (neo);

end

else begin

i:=0;

ind:=n;

while (i<>num-2) and (ind^.next<>nil) do begin

i:=i+1;

ind:=ind^.next;

end;

if ind^.next<>nil then begin

neo:=ind^.next;

ind^.next:=neo^.next;

dispose (neo);

end;

end;

end;

end; { del }

procedure veiw (n: link);

var

ind: link;

i: integer;

begin

ind:=n;

i:=0;

if ind=nil then writeln ('List is empty')

else begin

writeln; writeln ('The list is');

while ind<>nil do begin

i:=i+1;

writeln (i,') ', ind^.ini);

ind:=ind^.next;

end;

end;

end; { veiw }

procedure spec (var n: link; num: integer);

var

ind: link;

i: integer;

begin

i:=0;

ind:=n;

while ind<>nil do begin

i:=i+1;

ind:=ind^.next;

end;

if i

else begin

i:=0;

while i<>num do begin

i:= i+1;

ind:=n;

n:=n^.next;

dispose (ind);

end;

end;

end; { spec }

begin

pn:=nil;

m:=1;

while m<>0 do begin

writeln; writeln;

writeln ('Type «1» to ADD new element to the list');

writeln ('Type «2» to DELETE element from the list');

writeln ('Type «3» to VEIW the list');

writeln ('Type «4» to DELETE first k-elements');

writeln ('Type «0» to exit program');

writeln;

readln (m);

case m of

1: begin

write ('Enter new element: ');

readln (arg);

write ('Enter place: ');

readln (j);

add (pn, arg, j);

end;

2: begin

write ('Enter number of the element: ');

readln (j);

del (pn, j);

end;

3: begin

veiw (pn);

end;

4: begin

writeln ('Enter number of elements: ');

readln (j);

spec (pn, j);

end;

end; { case }

end;

end.