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

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ
1.Языки программирования высокого уровня
1.1.Основные понятия и определения
1.2.Наиболее распространенные языки программирования
1.3.Обоснование выбора языка Паскаль
2.Основные понятия, связанные со списками в языке Паскаль
2.1.Общее представление о типах данных в языке Паскаль
2.2.Указатели
2.3.Динамические структуры данных
3.Списки в Паскале
3.1.Основные понятия списка в языке Паскаль
3.2.Виды списков
3.3.Операции над списками
3.3.1.Создание списка
3.3.2.Добавление элементов
3.3.3.Удаление элементов
3.3.4.Поиск элемента
3.3.5.Создание ведущего (заглавного) звена
4.Практическая реализация создания списка в Паскаль
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
ПРИЛОЖЕНИЕ 1

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

поиск данных в списке;
создание ведущего (заглавного) звена (при необходимости);
обращение (реверсирование) списка, т.е. перестановка всех его звеньев в обратном порядке.
Рассмотрим основные из перечисленных операций.
3.3.1. Создание списка
Описание списка для демонстрации операций со списками будет выглядеть следующим способом (смотри рисунок 8) [19,20]:
Рис. 8. Создание списка
Для формирования списка (смотри рисунок 9) используются пять переменных типа указатель. pBegin - указатель начала списка, pEnd - указатель конца списка, pCKey, pPreComp, pAux - вспомогательные указатели. [20]
Рис. 9. Структура списка
Создание циклического списка приведено на рисунке 10.
Рис.10. Создание циклического списка
3.3.2. Добавление элементов
Для просмотра или вставки нового элемента по ключу необходимо осуществить поиск элемента по ключу. Key - ключ, тип которого совпадает с типом данных элемента списка. После выполнения вставки или просмотра указатель pСKey будет определять элемент с заданным ключом или такой элемент не будет найден (смотри рисунок 11, рисунок 12). [20]
Рис. 11. Схема добавления нового элемента в список
Рис. 12. Описание процедуры добавления элемента
3.3.3. Удаление элементов
При удалении элемента с заданным ключом надо при поиске нужного элемента помнить адрес предыдущего элемента. pCKey определяет элемент с заданным ключом, pPreComp содержит адрес предыдущего элемента (смотри рисунок 13, рисунок 14). [20]
Рис.13. Схема удаление элемента списка
Рис. 14. Описание процедуры удаления элемента списка
Удаление элемента из циклического списка представлено на рисунке 15.
Рис.15. Процедура удаления в циклическом списке
3.3.4. Поиск элемента
Операция поиска схожа с операцией просмотра списка отличается только тем, что на каждом шаге проверяется значение текущего элемента с искомым. В случае если искомые данные найдены, перемещение по списку заканчивается.
Пример процедуры реализующей поиск элемента по ключу (смотри рисунок 16)[19,20]
Рис. 16. Описание процедуры поиска
Функция поиска в циклическом списке представлена на рисунке 17.
Рис.17. Функция поиска в циклическом списке
3.3.5. Создание ведущего (заглавного) звена
Заглавное звено это первое звено в котором не обязательно должны храниться данные.
Заглавное звено в односвязном списке можно создать следующем образом (смотри рисунок 18).
Рис.18. Создание заглавного звена в односвязном списке
Создание заглавного звена в двухсвязном циклическом списке изображено на рисунке 19.
Рис.19. Создание заглавного звена в циклическом списке
4. Практическая реализация создания списка в Паскаль
Постановка задачи: составим и протестируем программу на Pascal для создания списка. Список линейный однонаправленный. Программа должна позволять создавать список, добавлять элементы, удалять элементы, удалять из списка первые k элементов, в том случае если задается удалить, элементов больше чем их есть в списке, то не менять список и выводить сообщение об ошибке.
Программа включает три процедуры реализации линейного списка: добавление нового элемента на указанное место в списке, удаление элемента с указанным номером из списка, просмотр содержимого списка. Специальное действие также реализовано с помощью отдельной процедуры.
Процедура добавления: процедуре по ссылке передается ссылка на начало списка. Также передается номер, на котором должен оказаться новый элемент, и значение элемента. Создается новый элемент, его значением становится передаваемый процедуре аргумент. Если ссылка на начало равна nil или передаваемый номер элемента равен единице, тогда элемент вставляется на первое место. В противном случае список проходится в цикле либо до нахождения нужного номера, либо до конца списка. Элемент вставляется на найденное место с соответствующей модификацией ссылок.
Процедура удаления: процедуре передается номер удаляемого элемента и (по ссылке) ссылка на начало списка. Если список не пуст, то выполняются следующие действия. Если номер удаляемого равен 1, то модифицируется ссылка на начало, если нет, то список проходится в цикле, либо до нахождения соответствующего номера, либо до конца списка. Если номер удаляемого находится в пределах списка, то соответствующий элемент удаляется с высвобождением памяти и модификацией ссылки на этот элемент.
Процедура просмотра: Список просто проходится в цикле до конца с выводом каждого элемента.
Специальная процедура: сначала список проходится в цикле с подсчетом количества элементов. Если размер списка меньше чем переданное процедуре количество удаляемых элементов, то ничего не происходит, если меньше, то опять в цикле происходит последовательное удаление элементов с высвобождением памяти, ссылка на начало после этого будет указывать на (k+1) элемент.
Основная программа: реализуется в виде меню. В цикле предлагается ввести число, соответствующее вышеперечисленным процедурам. Цикл завершается, если введен ноль, означающий конец программы. Вначале программа создает список, т.е. присваивает ссылке на начало значение nil.
Описание основных переменных и констант приведено в таблице 1.
Таблица 1
Описание основных переменных и констант
Имя
Тип
Назначение
Основная программа:
pn
link
Ссылка на начало списка.
arg
integer
Значение нового элемента.
m
integer
Переменная меню.
Подпрограммы:
Neo, ind
link
Ссылочные переменные употребляются для прохода списка.
i
integer
Счетчик цикла.
Входными и выходными данными являются целые значения элементов.
Тестовые примеры: программа протестирована на всевозможные действия над списком, в том числе и некорректные, например, удаление элемента из пустого списка или с номером, превышающим размер списка (смотри рисунок 20).
Рис. 20. Тестирование программы
ЗАКЛЮЧЕНИЕ
При выполнении работы были получены теоретические знания и практические навыки по работе со списками.
На первом этапе выполнения работы был проведен обзор литературных источников по теме работы: «Создание списков в Паскаль». Основными изученными изданиями были книги, написанные Немнюгиным С.А., Поповым В. и Павловской Т.А. Книги описывают программирование на языке высокого уровня Паскаль. Содержат подробное изложение языка программирования. Описание списков содержится в главах посвященных динамическим структурам данных языка Паскаль. Изучение литературы позволило сформировать структуру работы (план изложения материала), выделить основные главы, определить этапы изучения вопроса создания списков в Паскаль.
Список это динамическая структура. В практике программирования вместо любой статической структуры можно использовать динамическую структуру, но делать это нужно осторожно. Переменные простых типов занимают меньше памяти, чем указатель на них. При динамическом распределении памяти увеличивается объем текста программы, снижается наглядность и быстродействие.
Однако в ряде случаев использование динамических структур оказывается более эффективным, чем статических, а иногда и единственно возможной реализацией поставленной задачи. Обработка больших массивов данных с неопределенным размером вот пример такой задачи. Или сортировка большого объема информации тоже окажется более эффективной с использованием динамических структур.
Правильный выбор способа организации данных во многом определяет быстродействие программы, расход памяти, что характеризует качество программного продукта. Поэтому данному вопросу программист уделяет особое внимание.
Для того чтобы создать список в Паскаль, был изучен синтаксис языка, структура написания программы на языке Паскаль, изучены основные типы данных используемые в языке. В первой главе работы были определены основные понятия, связанные со списками в Паскаль.
Изучение типов данных позволило представить иерархию типов данных в структурированном виде. Более подробно описан специфический тип указатели. Определен синтаксис описания, особенности данного типа. Данный тип используется при создании списков.
В работе описаны основные понятия, связанные с динамическими структурами данных. Выявлены основные особенности такого рода организации данных. Определены основные цели использования такой организации данных. Определено что список является динамической структурой или как еще его называют в некоторых изданиях абстрактный тип данных. Приведен синтаксис описания динамической структуры. Определены виды динамических структур. Определены основные направления использования динамических структур.
В литературе и электронных ресурсах приведено большое количество примеров использования списков, операции со списками для решения разного рода задач. Отдельная глава работы посвящена описанию основных приемов работы со списками: создание списков, добавление элемента, удаление элементов, поиск элемента. В графическом виде продемонстрированы некоторые операции. В работе продемонстрированы фрагменты кодов реализации этих операций. На основе этого материала была создана программа, описанная в главе практической реализации.
Теоретические знания по теме списков позволили реализовать программу с создание списка в Паскаль. Результат работы программы это создание списка, добавление в него элементов, удаление из него элементов, удаление сразу нескольких элементов. Написанная программа протестирована на весь функционал. При выполнении практической части произошло полезное ознакомление с механизмом работы динамических структур, которые позволяют создавать структуры данных, ограниченных по размеру только объемом оперативной памяти. Полезно было бы дополнить эту работу реализацией процедуры сохранения списков в файлах и их обратного преобразования в динамику.
Выполнение работы было интересным и полезным. Полученные знания будут обязательно использованы в практике программирования на языка Паскаль для решения разного рода задач.
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
1. Андреева Т. А Программирование на языке Pascal. – М.: Бином. Лаборатория знаний, 2006. – 240 с.
2. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы / Пер. с англ. – М.: Вильямс, 2001.- 384 с.
3. Вирт Н. Алгоритмы и структуры данных. - 2-е изд. - СПб: “Невский Диалект”, 2001. - 352 с.
4. Климова Л. М. Pascal 7.0.Практическое программирование. Решение типовых задач. Изд. 4-е,доп. М: КУДИЦ-ОБРАЗ, 2003. - 528 с.
5. Культин Н. Turbo Pascal в задачах и примерах. - СПб.: БХВ-Петербург, 2006. - 256 с.
6. Малыхина М. П. Программирование на языке высокого уровня Turbo Pascal. - СПб.: БХВ-Петербург, 2006. - 544 с.
7. Моргун А. Н. Программирование на языке Паскаль (Pascal). Основы обработки структур данных. — М.: Диалектика, 2005. - 576 с.
8. Немнюгин С.А. Turbo Pascal. – СПб.: Питер, 2000. - 496 с.
9. Павловская Т.А. Паскаль. Программирование на языке высокого уровня: Учебник для вузов. – СПб.: Питер, 2007. - 393 с.
10. Попов В.Б. Паскаль и Дельфи. Самоучитель. – СПб.: Питер, 2004. - 544 с.
11. Рапаков Г. Г. Программирование на языке Pascal. - СПб.: БХВ-Петербург, 2004. - 480 с.
12. Стивене Р. Delphi. Готовые алгоритмы. - 2-е изд., стер.: Пер. с англ. Мерещука П. А. - М.: ДМК Пресс ; - СПб.: Питер, 2004. - 384 с.
13. Сухарев М. Turbo Pascal 7.0. Теория и практика программирования. – СПб.: Наука и техника, 2006. - 544 с.
14. Фаронов В.В. Delphi: Программирование на языке высокого уровня: Учебник для вузов. - СПб.: Питер, 2007. - 640 с.
15. Фаронов В.В. Turbo Pascal. - СПб.: БХВ-Петербург, 2004. - 1056 с.
16. Федоренко Ю. Алгоритмы и программы на Turbo Pascal. Учебный курс.. – СПб.: Питер, 2001. - 240 с.
17. Домнин Ф. А. Язык программирования Паскаль(Turbo Pascal). Обучающие уроки – 2009. – 28 декабря [Электронный ресурс]. URL: http://www.life-prog.ru/view_zam.php?id=32&cat=1&page=2 (дата обращения: 16.05.2012).
18. Васильев Н.А. Краткая справка по языку программирования Turbo Pascal. – 2004. [Электронный ресурс]. URL: http://forprogrammer.narod.ru/pascal/index.htm (дата обращения: 16.05.2012).
19. Язык Паскаль. Динамические структуры данных. – 2011. – 2 июля [Электронный ресурс]. URL: http://pas1.ru/dynamicstructures (дата обращения: 16.05.2012).
20. Динамические структуры данных в Паскаль. – 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);