Работа со стеками, деками и очередями

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

Рубрика Программирование, компьютеры и кибернетика
Вид курсовая работа
Язык русский
Дата добавления 11.04.2014
Размер файла 835,8 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http://www.allbest.ru/

Содержание

Аннотация

Введение

1. Содержательная постановка задачи

2. Анализ и пример решения задачи

3. Формальная постановка задачи

4. Спецификация программы

5. Разработка структур данных и алгоритмов

6. Реализация программы

7. Результаты выполнения программы

8. Сравнительный анализ

Заключение

Список литературы

Аннотация

Данная курсовая работа посвящена применению линейных структур данных таких как: стеки, деки и очереди.

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

Введение

Для решения многих практических задач используются структуры данных - массив, запись, множество и так далее. Цель описания типов данных и последующего описания переменных, как относящихся к этому типу, состоит в том, чтобы зафиксировать на время выполнения программы размер значений, которые присваиваются этим переменным и, соответственно, фиксировать размер выделяемой области памяти для них. Такие переменные называются статическими.

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

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

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

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

1. Содержательная (исходная) постановка задачи

Разработать функции для создания , включения и выборки элемента:

1) дека векторной структуры;

2) дека с ограниченным входом векторной структуры;

3) дека с ограниченным выходом векторной структуры;

4) очереди векторной структуры;

5) очереди с приоритетом векторной структуры;

6) стека односвязной списковой структуры;

7) стека двусвязной списковой структуры;

8) очереди двусвязной списковой структуры;

9) очереди с приоритетами односвязной списковой структуры;

10) очереди с приоритетами двусвязной списковой структуры.

Постановка задачи.

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

2. Анализ и пример решения задачи

Анализ задачи. Для изучения данной темы, нам необходимо разработать следующие 10 подпрограмм:

1) Дек векторной структуры.

Дек векторной структуры- это специальный тип списка, где элементы массива вставляются в один конец, называемым хвостом (tail), а удаление и добавление невозможно, так как это вызывает либо переполнение массива, либо его неполноту.

Пример решения задачи

Пусть дан массив а[1..5]=(2,3,4,5,6), и необходимо добавить некоторый элемент n=1.

Мы не сможем добавить его в качестве элемента массива а[i], поэтому мы просто затолкаем его вперед или добавим в конец.

При выводе дека мы получим последовательность: 1 2 3 4 5 6.

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

Пример решения задачи

Пусть дан массив а[1..5]=(2,3,4,5,6), и необходимо добавить некоторый элемент n=1.

Учитывая , что добавление возможно только в конец, то мы получим последовательность вида 2 3 4 5 6 1.

3) Дек с ограниченным выходом векторной структуры.

Её отличие от дека с ограниченным входом векторной структуры состоит в том, что добавление возможно в обоих концах, а удаление только из одного конца.

Пример решения задачи

Пусть дан массив а[1..5]=(2,3,4,5,6), и необходимо добавить некоторый элемент n=1.

Мы можем добавить его в любой конец, например в голову, тогда мы получим последовательность вида 1 2 3 4 5 6 .

4) Очередь векторной структуры- это тип списка, при котором новые данные располагаются следом за существующими в порядке поступления; поступившие первыми данные при этом обрабатываются первыми

Пример решения задачи

Пусть дан массив а[1..5]=(2,3,4,5,6), и необходимо добавить некоторый элемент n=1.

Учитывая , что добавление возможно только в конец, то мы получим последовательность вида 2 3 4 5 6 1.

5) Стек односвязной списковой структуры - это специальный тип списка, в котором все вставки и удаления выполняются только на одном конце, называемом вершиной, (Head).

Пример решения задачи

Пусть с клавиатуры введено пара чисел: 2,3,4,5,6 и необходимо добавить некоторое число n=1.

При организации стека элемент, который мы добавили последним, будет выводиться первым, тогда последовательность примет вид: 1 6 5 4 3 2.

6) Стек двусвязной списковой структуры- это специальный тип списка, в котором все вставки и удаления выполняются на одном конце, называемом вершиной, (Head). Его отличие от стека односвязной списковой структуры в том, что в двусвязном списке связующая часть состоит из двух полей. Одно поле указывает на левого соседа данного элемента списка, другое -- на правого.

Пример решения задачи

Пусть с клавиатуры введено пара чисел: 2 3 4 5 6, и необходимо добавить некоторое число n=1.

При организации стека элемент, который мы добавили последним, будет выводиться первым. Тогда последовательность примет вид: 1 6 5 4 3 2.

7) Очередь односвязной списковой структуры - это специальный тип списка, где элементы вставляются в один конец, называемым хвостом (Tail), а удаляются с другого конца, называемым головой (Head).

Пример решения задачи

Пусть с клавиатуры введено пара чисел: 2 3 4 5 6 , и необходимо добавить некоторое число n=1.

Зная, что добавление в очередь возможно только в конец, то мы получим последовательность вида: 2 3 4 5 6 1.

8) Очередь двусвязной списковой структуры - эта та же очередь односвязной списковой структуры, за исключением того, что связующая часть двусвязного списка состоит из двух полей. Одно поле указывает на левого соседа данного элемента списка, другое -- на правого.

Пример решения задачи

Пусть с клавиатуры введено пара чисел: 2 3 4 5 6 , и необходимо добавить некоторое число n=1.

Зная, что добавление в очередь возможно только в конец, то мы получим последовательность вида: 2 3 4 5 6 1.

9) Очередь с приоритетом односвязной списковой структуры - эта та же очередь, за отличием того, что более приоритетные элементы добавляются в голову, а менее приоритетные добавляются в хвост.

Пример решения задачи

Пусть даны элементы: 2 3 4 5 6 , и необходимо добавить некоторое число n=1.

Будем считать что, самое меньшее число - самое приоритетное. Тогда последовательность примет вид: 1 2 3 4 5 6.

10) Очередь с приоритетом двусвязной списковой структуры.

Его логический смысл такой же, что и в очереди с приоритетом односвязной списковой структуры, но отличие в том , что связующая часть двусвязного списка состоит из двух полей. Одно поле указывает на адрес предыдущего элемента списка, а другое - на следующий.

Пример решения задачи

Пусть даны элементы: 2 3 4 5 6 , и необходимо добавить некоторое число n=1.

Будем считать что, самое меньшее число - самое приоритетное.

Тогда последовательность примет вид: 1 2 3 4 5 6.

3. Формальная подстановка задачи

Исходные данные

1) А - массив последовательности элементов для создания списка векторной структуры.

2) M-элемент создаваемого списка.

3) S - добавляемый элемент.

4) g - элемент выборки.

Ограничения на исходные данные

Данными для задания, не могут быть числа, не соответствующие типу integer.

Результирующие (выходные) данные

Результатом будет последовательность чисел, с соблюдением требований поставленной задачей.

4. Спецификация программы

Исходные данные (ИД)

Перечень и основные характеристики ИД:

1) А - массив последовательности элементов.

2) M -- элемент создаваемого списка. Вводиться с клавиатуры по запросу программы.

3) S - добавляемый элемент. Вводиться с клавиатуры по запросу программы.

4) g - элемент выборки. Вводиться с клавиатуры по запросу программы.

Ограничения на исходные данные:

1)А - массив последовательности элементов. В программе реализован как const.

2) M - элемент создаваемого списка, реализуется типом integer.

3) s - добавляемый элемент, реализуется типом integer.

4) g - элемент выборки. Реализуется типом integer..

Место и форма представления исходных данных:

1)A - уже реализована в тексте программы в форме константы. Представлена в сценарии диалога в наглядной показательной форме.

2) M - вводиться с клавиатуры в процессе диалога, порядок ввода и форма представления описаны в сценарии диалога.

3)s - вводиться с клавиатуры в процессе диалога, порядок ввода и форма представления описаны в сценарии диалога.

4)g - вводиться с клавиатуры в процессе диалога, порядок ввода и форма представления описаны в сценарии диалога.

Функции программы по обработке исключительных ситуаций

Исполняющая система прекращает выполнение программы, выдавая диагностическое сообщение об ошибке в следующих ситуациях:

1) Если при выборе выполняемого действия ведено число i>10.

2) Если добавляемый элемент не принадлежит типу integer.

3) Если в цикле программы окажется, что Head=nil.

Выходные данные

Состав выходных данных:

В состав выходных данных, то есть на экран (в окно OUTPUT) будет выводиться последовательностьA[I], построенная с соблюдением требований, поставленной задачи.

Сценарий диалога.

Общая схема диалога:

1)Сцена 1(Запрос на выполнение функции i=1..10).

2)Если выбрана сцена1, то Сцена 2 (Выполнение функции на включение, добавление и выборки элементов).

При описании сцены 2, мы будем приводить две таблицы:

1. таблица для описания векторной структуры данных;

2.таблица для описания списковой структуры данных

Описание сцен диалога:

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

Таблица 1

Описание сцены 2 приведено в табл. 2

Таблица 2.1

Таблица 2.2

Алгоритм ведения диалога

Сообщения пользователю и его реакция

Ввод запроса

Vvedite colichestvo elementov

Ввод n

<Enter>

ввод запроса

vvedite dobavlaemii element

Ввод m

<Enter>

Ввод запроса

Vvedite dobavlaemii element

Ввод S

dobavlaemii element

ввод запроса

Vvedite neobhodimii element

Ввод g

<Enter>

Если такой элемент имеется, то выводится сообщение

Takoi element imeetsa

5. Разработка структур данных и алгоритмов

алгоритмический линейный стек дек

Алгоритмы.

Алгоритм программы состоит из трёх основных частей:

1)Выбор необходимой задачи;

2) Непосредственная реализация предложенной задачи;

Алгоритм программы:

1.Ввести запрос на выполнение функции (i =1..10);

1.1. Если i=1,то вызываем процедуру создания дека векторной структуры.

1.1.1. Заносим данные массива в память.

Проверяем, пуста ли очередь

ЕСЛИ да, ТО ставим указатель начала очереди на первый созданный элемент ИНАЧЕ, ставим созданный элемент в конец очереди.

Переносим указатель конца очереди на последний элемент

1.1.2. Водим добавляемый элемент и заносим его в голову DOB(head,tail,s).

1.1.3. Водим элемент выборкиg.

ЕСЛИ такой элемент существует, ТО выводится информация о его существовании, ИНАЧЕ, выводится информация о его отсутствии.

1.2. Если i=2,то вызываем процедуру создания дека векторной структуры с ограниченным входом.

1.2.1 Заносим данные массива в память .

Проверяем, пуста ли очередь.

ЕСЛИ да, ТО ставим указатель начала очереди на первый созданный элемент, ИНАЧЕ, ставим созданный элемент в конец очереди.

Переносим указатель конца очереди на последний элемент

2.2. Водим добавляемый элемент и заносим его в хвостDOB(head,tail,s).

1.2.3. Водим элемент выборкиg.

Если такой элемент существует, то выводится информация о его существовании, иначе выводится информация о его отсутствии.

1.3 Если i=3,то вызываем процедуру создания дека векторной структуры с ограниченным выходом.

1.3.1. Заносим данные массива в память.

Проверяем, пуста ли очередь.

ЕСЛИ да, ТО ставим указатель начала очереди на первый созданный элемент, ИНАЧЕ, ставим созданный элемент в конец очереди.

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

1.3.2. Вводим добавляемый элемент и заносим его в голову или в хвостDOB(head,tail,s).

1.3.3. Вводим элемент выборкиg.

Если такой элемент существует, то выводится информация о его существовании, иначе выводится информация о его отсутствии.

1.4. Если i=4,то вызываем процедуру создания очереди векторной структуры .

1.4.1. Заносим данные массива.

Проверяем, пуста ли очередь

ЕСЛИ да, ТО ставим указатель начала очереди на первый созданный элемент

ИНАЧЕ, ставим созданный элемент в конец очереди.

Переносим указатель конца очереди на последний элемент

1.4.2 водим добавляемый элемент и заносим его в хвост DOB(head,tail,s).

1.4.3водим элемент выборки g.

Если такой элемент существует, то выводится информация о его существовании, иначе выводится информация о его отсутствии.

1.5. Если i=5,то вызываем процедуру создания стека односвязной списковой структуры

1.5.1. Заносим вводимый элемент в память, для этого:

Ставим созданный элемент в вершину стека.

Переносим ссылку на вершину стека.

1.5.2 водим добавляемый элемент и заносим его в голову DOB(head,tail,s).

1.5.3 Водим элемент выборкиg.

Если такой элемент существует, то выводится информация о его существовании, иначе выводится информация о его отсутствии.

1.6. Если i=6,то вызываем процедуру создания стека двусвязной списковой структуры. 1.6.1 Заносим вводимый элемент в память, для этого:

1)Устанавливаем ссылку next узла u на голову существующего списка и его ссылку pred в NiL.

2) установить ссылку pred бывшего первого узла (если он существовал) на u

3) установить голову списка на новый узел;

4) если в списке не было ни одного элемента, хвост списка также устанавливается на новый узел.

1.6.2. Водим добавляемый элемент и заносим его в голову

1.6.3. Водим элемент выборки.

Если такой элемент существует, то выводится информация о его существовании, иначе выводится информация о его отсутствии.

1.7. Если i=7,то вызываем процедуру создания очереди односвязной списковой структуры.

1.7.1. Заносим данные, вводимые с клавиатуры, в память, для этого:

Проверяем, пуста ли очередь,

ЕСЛИ да, ТО ставим указатель начала очереди на первый созданный элемент

ИНАЧЕ, ставим созданный элемент в конец очереди.

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

1.4.2. Водим добавляемый элемент и заносим его в хвост.

1.4.3.Водим элемент выборки.

Если такой элемент существует, то выводится информация о его существовании, иначе выводится информация о его отсутствии.

1.8. Если i=8, то вызываем процедуру создания очереди двусвязной списковой структуры.

1.4.1. Заносим данные вводимые с клавиатуры в память, для этого:

1)Устанавливаем ссылку pred узла u на хвост существующего списка и его ссылку Nextв NiL.

2) установить ссылку nextбывшего первого узла (если он существовал) на u

3) установить хвост списка на новый узел;

4) если в списке не было ни одного элемента, голова списка также устанавливается на новый узел.

1.8.2. Водим добавляемый элемент и заносим его в хвост

1.8.3.Водим элемент выборки.

Если такой элемент существует, то выводится информация о его существовании, иначе выводится информация о его отсутствии.

1.9. Если i=9,то вызываем процедуру создания очереди с приорететом односвязной списковой структуры .

1.9.1. Заносим данные вводимые с клавиатуры в память, в неубывающей последовательности, для этого:

Проверяем, пуста ли очередь.

ЕСЛИ да, ТО ставим указатель начала очереди на первый созданный элемент, ИНАЧЕ, ставим созданный элемент в конец очереди.

Переносим указатель конца очереди на последний элемент

1.9.2 Водим добавляемый элемент S.

ЕСЛИ добавляемый элемент меньше Head (головы),

ТО Head:=s,

ИНАЧЕ,

ПОКАHEAD<>nil выполнить

ЕСЛИ предыдущего<S<следующего,

ТО добавление происходит в середину,

ИНАЧЕ,

ЕСЛИ S>предыдущего, а указатель на следующий =nil,

ТО добавление происходит в конец,

ВСЕ ЕСЛИ.

1.9.3. Водим элемент выборки.

Если такой элемент существует, то выводится информация о его существовании, иначе выводится информация о его отсутствии.

1.10. Если i=10,то вызываем процедуру создания очереди с приоритетом односвязной списковой структуры

1.10.1. Заносим данные вводимые с клавиатуры в память, в неубывающем порядке, для этого:

1)Устанавливаем ссылку pred узла u на хвост существующего списка и его ссылку Nextв NiL.

2) установить ссылку nextбывшего первого узла (если он существовал) на u

3) установить хвост списка на новый узел;

4) если в списке не было ни одного элемента, голова списка также устанавливается на новый узел.

1.10.2. Водим добавляемый элемент.

ЕСЛИ добавляемый элемент меньше Head (головы),

ТО Head:=s,

ИНАЧЕ,

ПОКАHEAD<>nil выполнить

ЕСЛИ предыдущего<S<следующего,

ТО добавление происходит в середину,

ИНАЧЕ

ЕСЛИS>предыдущего, а указатель на следующий =nil,

ТО добавление происходит в конец,

ВСЁ ЕСЛИ

1.10.3. Водим элемент выборки.

Если такой элемент существует, то выводится информация о его существовании, иначе выводится информация о его отсутствии.

Модель структуры данных

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

1.Набор операций соответствует линейному списку типа Л1 и Л2 список.

2. Над линейным списком выполняются операции редактирования, значит, для его представления лучше использовать связанную память.

Вывод: для представления последовательности будем использовать Л1 и Л2-списки, реализованные в связной памяти.

Структура программы и интерфейс модулей

type

Link=^st;{тип указатель на узел памяти}

st=record

elem:integer; {поле данных}

next:Link;{указатель на следующий узел}

end;

const a:array[1..5] of integer=(2,3,4,5,6);

proceduredek_1 ;{процедура создания дека векторной структуры}

{процедура создания}

procedure Input(var Head1,Tail1:Link;a:integer);

{процедура добавления}

Procedure dob(Var head1, tail1 : link; c : integer);

{Процедура вывода}

procedure out(Head1:Link);

{Процедура выборки}

procedurepoisk(Head1:Link; b:integer);

vark:integer;

end;

proceduredek_2 ;{процедура создания дека векторной структурыс ограниченным входом}

{процедура создания}

procedure Input(var Head1,Tail1:Link;a:integer);

{процедура добавления}

Procedure dob(Var head1, tail1 : link; c : integer);

{Процедура вывода}

procedure out(Head1:Link);

{Процедура выборки}

procedurepoisk(Head1:Link; b:integer);

vark:integer;

end;

proceduredek_3 ;{процедура создания дека векторной структуры с ограниченным выходом}

{процедура создания}

procedure Input(var Head1,Tail1:Link;a:integer);

{процедура добавления}

Procedure dob(Var head1, tail1 : link; c : integer);

{Процедура вывода}

procedure out(Head1:Link);

{Процедура выборки}

procedurepoisk(Head1:Link; b:integer);

vark:integer;

end;

procedureoch_vec;{процедура создания очереди векторной структуры}

{процедурас оздания}

procedure Input(var Head1,Tail1:Link;a:integer);

{процедура добавления}

Procedure dob(Var head1, tail1 : link; c : integer);

{Процедура вывода}

procedure out(Head1:Link);

{Процедура выборки}

procedurepoisk(Head1:Link; b:integer);

vark:integer;

end;

procedurestek1;{процедура создания стека односвязной списковой структуры}

{процедура создания}

procedure Input(var Head1:Link;a:integer);

{процедура добавления}

Procedure dob(Var head1, : link; c : integer);

{Процедура вывода}

procedure out(Head1:Link);

{Процедура выборки}

procedurepoisk(Head1:Link; b:integer);

vark:integer;

end;

procedure ;{процедура создания стека двусвязной списковой структуры }

{процедура создания}

procedure Input(var Head1:Link;a:integer);

{процедура добавления}

Procedure dob(Var head1 : link; c : integer);

{Процедура вывода}

procedure out(Head1:Link);

{Процедура выборки}

procedurepoisk(Head1:Link; b:integer);

vark:integer;

end;

procedureoch_1;{процедура создания очереди односвязной списковой структуры}

{процедура создания}

procedure Input(var Head1,Tail1:Link;a:integer);

{процедура добавления}

Procedure dob(Var head1, tail1 : link; c : integer);

{Процедура вывода}

procedure out(Head1:Link);

{Процедура выборки}

procedurepoisk(Head1:Link; b:integer);

vark:integer;

end;

procedureoch_2;{процедура создания очереди двусвязной списковой структуры}

{процедура создания}

procedure Input(var Head1,Tail1:Link;a:integer);

{процедура добавления}

Procedure dob(Var head1, tail1 : link; c : integer);

{Процедура вывода}

procedure out(Head1:Link);

{Процедура выборки}

procedurepoisk(Head1:Link; b:integer);

vark:integer;

end;

procedureoch_prio;{процедура создания очереди с приоритетом односвязной списковой структуры}

{процедура создания}

procedure Input(var Head1,Tail1:Link;a:integer);

{процедура добавления}

Procedure dob(Var head1, tail1 : link; c : integer);

{Процедура вывода}

procedure out(Head1:Link);

{Процедура выборки}

procedurepoisk(Head1:Link; b:integer);

vark:integer;

end;

procedureoch_prio2;{процедура создания очереди с приоритетом двусвязной списковой структуры}

{процедура создания}

procedure Input(var Head1,Tail1:Link;a:integer);

{процедура добавления}

Procedure dob(Var head1, tail1 : link; c : integer);

{Процедура вывода}

procedure out(Head1:Link);

{Процедура выборки}

procedurepoisk(Head1:Link; b:integer);

vark:integer;

end;

6. Программа на языке ТУРБО ПАСКАЛЬ

uses crt;

type

Link=^st;

st=record

elem:integer;

next,pred:Link;

end;

const a:array[1..5] of integer=(2,3,4,7,8);

var

i,s,g,m,n:integer;

Head,Tail:Link;

procedure dek_1 ;

procedure Input(var Head1,Tail1:Link;a:integer);

var

tmp:Link;

begin

New(tmp);

tmp^.next:=nil;

tmp^.elem:=a;

if Tail1 <> nil then

Tail1^.next:=tmp;

Tail1:=tmp;

if Head1=nil then

Head1:=Tail1;

end;

{процедура добавления}

Procedure dob(Var head1, tail1 : link; c : integer);

Var

u : link;

Begin

new(u);

u^.elem := c;

u^.Next := head1;

head1:= u;

tail1:=head1;

End;

{Процедуравывода}

procedure out(Head1:Link);

begin

if Head1=nil thenbegin

writeln('ocheredpusta!');

exit;end;

while Head1 <> nil dobegin

write(Head1^.elem:4);

Head1:=Head1^.next;

end;end;

{Процедуравыборки}

procedure poisk(Head1:Link; b:integer);

var k:integer;

begin

if Head1=nil then

begin

writeln('ochered pusta!');

exit;

end;

k:=0;

while Head1 <> nil do

begin

if Head1^.elem=b then

inc(k);

Head1:=Head1^.next;

end;

if k>0 then

writeln('takoi element imeetca')

else

writeln('takogo elementa net');

end;

begin

Head:=nil; Tail:=nil;

for i:=1 to 5 dobegin

Input(Head,Tail,a[i]);

end;

writeln('vivod ocheredi');

out(Head);

writeln;

writeln('vveditedobavlaemiy element');

readln(s);

dob(Head,Tail,s);

out(Head);

writeln;

writeln('vedite neobodimii element');

readln(g) ;

poisk(head,g);

readkey;

end;

procedure dek_2 ;

procedure Input(var Head1,Tail1:Link;a:integer);

var

tmp:Link;

begin

New(tmp);

tmp^.next:=nil;

tmp^.elem:=a;

if Tail1 <> nil then

Tail1^.next:=tmp;

Tail1:=tmp;

if Head1=nil then

Head1:=Tail1;

end;

{процедура добавления}

Procedure dob(Var head1, tail1 : link; c : integer);

Var

u : link;

Begin

new(u);

u^.elem := c;

u^.Next := Nil;

if head =Nil {проверяем пуста ли очередь}

then

head := u {ставим указатель начала очереди на первый созданный элемент}

else

tail^.Next := u; {ставим созданный элемент в конец очереди}

tail := u; {переносим указатель конца очереди на последний элемент}

End;

{Процедуравыборки}

procedure poisk(Head1:Link; b:integer);

var k:integer;

begin

if Head1=nil then begin

writeln('ochered pusta!');

exit;

end;

k:=0;

while Head1 <> nil do

begin

if Head1^.elem=b then

inc(k);

Head1:=Head1^.next;

end;

if k>0 then

writeln('takoi element imeetca')

else

writeln('takogo elementa net');

end;

{Процедуравывода}

procedure out(Head1:Link);

begin

if Head1=nil then begin

writeln('Очередьпуста!');

exit; end;

while Head1 <> nil do begin

write(Head1^.elem:4);

Head1:=Head1^.next;

end;end;

begin

Head:=nil; Tail:=nil;

for i:=1 to 5 do begin

Input(Head,Tail,a[i]);

end;

writeln('vivod ocheredi');

out(Head);

writeln('vvedite dobavlaemii element');

readln(s);

Input(Head,Tail,s);

out(Head);

writeln;

writeln('vedite neobodimii element');

readln(g) ;

poisk(head,g);

end;

procedure dek_3;

procedure Input(var Head1,Tail1:Link;a:integer);

var

tmp:Link;

begin

New(tmp);

tmp^.next:=nil;

tmp^.elem:=a;

if Tail1 <> nil then

Tail1^.next:=tmp;

Tail1:=tmp;

if Head1=nil then

Head1:=Tail1;

end;

{процедура добавления}

Procedure dob(Var head1, tail1 : link; c : integer);

Var

u : link;

Begin

new(u);

u^.elem := c;

u^.Next := head1;

head1:= u;

tail1:=head1;

End;

{Процедуравывода}

procedure out(Head1:Link);

begin

if Head1=nil thenbegin

writeln('ocheredpusta!');

exit;end;

while Head1 <> nil dobegin

write(Head1^.elem:4);

Head1:=Head1^.next;

end;end;

{Процедуравыборки}

procedure poisk(Head1:Link; b:integer);

var k:integer;

begin

if Head1=nil then begin

writeln('ochered pusta!');

exit;

end;

k:=0;

while Head1 <> nil do begin

if Head1^.elem=b then

inc(k);

Head1:=Head1^.next;

end;

if k>0 then

writeln('takoi element imeetca')

else

writeln('takogo elementa net');

end;

begin

Head:=nil; Tail:=nil;

for i:=1 to 5 dobegin

Input(Head,Tail,a[i]);

end;

writeln('vivod ocheredi');

out(Head);

writeln;

writeln('vveditedobavlaemiy element');

readln(s);

dob(Head,Tail,s);

out(Head);

writeln;

writeln('vedite neobodimii element');

readln(g) ;

poisk(head,g);

readkey;

end;

procedure och_vec;

procedure Input(var Head1,Tail1:Link;a:integer);

var

tmp:Link;

begin

New(tmp);

tmp^.next:=nil;

tmp^.elem:=a;

if Tail1 <> nil then

Tail1^.next:=tmp;

Tail1:=tmp;

if Head1=nil then

Head1:=Tail1;

end;

{процедура добавления}

Procedure dob(Var head1, tail1 : link; c : integer);

Var

u : link;

Begin

new(u);

u^.elem := c;

u^.Next := Nil;

if head1 =Nil {проверяем пуста ли очередь}

then

head1 := u {ставим указатель начала очереди на первый созданный элемент}

else

tail1^.Next := u; {ставим созданный элемент в конец очереди}

tail1:= u; {переносим указатель конца очереди на последний элемент}

End;

{Процедуравыборки}

procedure poisk(Head1:Link; b:integer);

var k:integer;

begin

if Head1=nil then begin

writeln('ochered pusta!');

exit;

end;

k:=0;

while Head1 <> nil do

begin

if Head1^.elem=b then

inc(k);

Head1:=Head1^.next;

end;

if k>0 then

writeln('takoi element imeetca')

else

writeln('takogo elementa net');

end;

{Процедуравывода}

procedure out(Head1:Link);

begin

if Head1=nil then begin

writeln('Очередь пуста!');

exit;

end;

while Head1 <> nil do begin

write(Head1^.elem:4);

Head1:=Head1^.next;

end;end;

begin

Head:=nil; Tail:=nil;

for i:=1 to 5 do begin

Input(Head,Tail,a[i]);

end;

writeln('vvivod oheredi');

out(Head);

writeln('dobavlaemii element');

readln(m);

Input(Head,Tail,m);

out(Head);

writeln('vvedite neobhod element');

readln(g);

poisk(head,g);

end;

procedure stek1;

var head,beg,t,q:link;

m,n,i,a:integer;

procedure input(var head1: link; a: byte);

var

tmp: link;

begin

new(tmp);

tmp^.elem := a;

tmp^.Next := head1;

head1 := tmp;

end;

procedure dob(var head1:link; n:integer);

var u,q:link;

begin

new(u);

u^.elem:=n;

u^.next:=head1;

head1:=u;

end;

{Процедура выборки}

procedure poisk(Head1:Link; b:integer);

var k:integer;

beg:link;

begin

head1:=beg;

k:=0;

while Head1 <> nil do

begin

if Head1^.elem=b then

inc(k);

Head1:=Head1^.next;

end;

if k>0 then

writeln('takoi element imeetca')

else

writeln('takogo elementa net');

end;

{Процедуравывода}

procedure out(Head1:Link);

begin

if Head1=nil then begin

writeln('Очередьпуста!');

exit; end;

while Head1 <> nil do

begin

write(Head1^.elem:4);

Head1:=Head1^.next;

end;end;

begin

head:=nil;

writeln('vvedite kolichestvo elementov');

readln(n);

for i:=1 to n do begin

writeln('vvedite element');

readln(a);

input(head, a);

end;

out(head); writeln;

writeln('vvedite dobavlaemiy element');

readln(s);

dob(head,s);

out(head);

readkey;

end;

procedure stek2;

type

Link=^st;

st=record

elem:integer;

next:Link;

pred:link;

end;

var head,tail:link;

procedure input(var head1: link; a: byte);

var

u: link;

begin

new(u);

u^.elem := a;

if head=nil then begin

u^.pred:=nil;

u^.Next := head1;

head1 := u;

endelse

u^.pred:=head1;

head1^.next:= u;

head1:=u; end;

procedure dob(var head1:link; n:integer);

var u,q:link;

begin

new(u);

u^.elem:=n;

u^.next:=nil;

u^.pred:=head1;

head1:=u;

end;

procedure out(Head1:Link);

begin

if Head1=nil then begin

writeln('Очередь пуста!');

exit;end;

while Head1 <> nil do begin

write(Head1^.elem:4);

Head1:=Head1^.pred;

end;end;

{Процедуравыборки}

procedure poisk(Head1:Link; g:integer);

var k:integer;

beg:link;

begin

k:=0;

while Head1 <> nil do

begin

if Head1^.elem=g then

inc(k);

Head1:=Head1^.pred;

end;

if k>0 then

writeln('takoi element imeetca')

else

writeln('takogo elementa net');

end;

begin

Head:=nil;

writeln('vvedite colichestvo elementov');

readln(n);

for i:=1 to n do begin

writeln('vvedite element');

readln(m);

Input(Head,m);

end;

writeln('vvivod ocheredi');

out(Head);

writeln;

writeln('vvedite dobavlaemiy element');

readln(s);

dob(Head,s);

out(Head);

writeln;

writeln('vedite neobhodimiy element');

read(g);

poisk(Head,g);

readkey;

end;

procedure och_1;

{Процедураввода}

procedure Input(var Head1,Tail1:Link;a:integer);

var

tmp:Link;

begin

New(tmp);

tmp^.next:=nil;

tmp^.elem:=a;

if Tail1 <> nil then

Tail1^.next:=tmp;

Tail1:=tmp;

if Head1=nil then

Head1:=Tail1;

end;

{процедура добавления}

Procedure dob(Var head1, tail1 : link; c : integer);

Var

u : link;

Begin

new(u);

u^.elem := c;

u^.Next := Nil;

if head =Nil {проверяем пуста ли очередь}

then

head := u {ставим указатель начала очереди на первый созданный элемент}

else

tail^.Next := u; {ставим созданный элемент в конец очереди}

tail := u; {переносим указатель конца очереди на последний элемент}

End;

{Процедуравыборки}

procedure poisk(Head1:Link; b:integer);

var k:integer;

begin

if Head1=nil then begin

writeln('ochered pusta!');

exit;end;

k:=0;

while Head1 <> nil do

begin

if Head1^.elem=b then

inc(k);

Head1:=Head1^.next;

end;

if k>0 then

writeln('takoi element imeetca')

else

writeln('takogo elementa net');

end;

{Процедуравывода}

procedure out(Head1:Link);

begin

if Head1=nil then begin

writeln('Очередь пуста!');

exit;end;

while Head1 <> nil do begin

write(Head1^.elem:4);

Head1:=Head1^.next;

end;end;

begin

Head:=nil; Tail:=nil;

writeln('vvedite colichestvo elementov');

readln(n);

for i:=1 to n do begin

writeln('vvedite element');

readln(m);

Input(Head,Tail,m);

end;

writeln('vvivod ocheredi');

out(Head);

writeln;

writeln('vvedite dobavlaemiy element');

readln(s);

dob(Head,Tail,s);

out(Head);

writeln;

writeln('vedite neobhodimiy element');

read(g);

poisk(Head,g);

readkey;

end;

procedure och_2;

type

Link=^st;

st=record

elem:integer;

next:Link;

pred:link;

end;

var head,tail:link;

procedure Input(var Head1,Tail1:Link;a:integer);

var

tmp,t:Link;

begin

New(tmp);

tmp^.next:=nil;

tmp^.pred:=tail1;

tmp^.elem:=a;

if Tail1 <> nil then

Tail1^.next:=tmp;

Tail1:=tmp;

if Head1=nil then

Head1:=Tail1;

end;

{процедура добавления}

Procedure dob(Var head1, tail1 : link; c : integer);

Var

u : link;

Begin

new(u);

u^.elem := c;

u^.Next := Nil;

u^.pred := tail1;

if head1 =Nil {проверяем пуста ли очередь}

then

head1 := u {ставим указатель начала очереди на первый созданный элемент}

else

tail1^.Next := u; {ставим созданный элемент в конец очереди}

tail1 := u;

End;

{Процедура выборки}

procedure poisk(Head1:Link; b:integer);

var k:integer;

begin

if Head1=nil then begin

writeln('ochered pusta!');

exit; end;

k:=0;

while Head1 <> nil do

begin

if Head1^.elem=b then

inc(k);

Head1:=Head1^.next;

end;

if k>0 then

writeln('takoi element imeetca')

else

writeln('takogo elementa net');

end;

{Процедура вывода}

procedure out(Head1:Link);

begin

if Head1=nil then begin

writeln('ochered pusta!');

exit;end;

while Head1 <> nil do begin

write(Head1^.elem:4);

Head1:=Head1^.pred;

end;end;

begin

Head:=nil; Tail:=nil;

writeln('vvedite colichestvo elementov');

readln(n);

for i:=1 to n do begin

writeln('vvedite element');

readln(m);

Input(Head,Tail,m);

end;

writeln('vvivod ocheredi');

out(tail);

writeln;

writeln('vvedite dobavlaemiy element');

readln(s);

dob(Head,Tail,s);

out(tail);

writeln;

writeln('vedite neobhodimiy element');

read(g);

poisk(Head,g);

readkey;

end;

procedure och_prio;

{Процедураввода}

procedure Input(var Head1,Tail1:Link;a:integer);

var

tmp:Link;

begin

New(tmp);

tmp^.next:=nil;

tmp^.elem:=a;

if Tail1 <> nil then

Tail1^.next:=tmp;

Tail1:=tmp;

if Head1=nil then

Head1:=Tail1;

end;

{процедура добавления}

Procedure dob(var head1, tail1 : link; c : integer);

Var

u,t: link;

Begin

t:=head1;

if c<=t^.elem then begin

new(u);

u^.elem := c;

u^.Next := t;

u^.pred := nil;

t:= u;

endelse

while Head1 <> nil do

begin

if (head1^.elem<c) and (head1^.next^.elem>c)

then begin

new(u);

u^.elem := c;

u^.Next := head1^.next;

head1^.next:=u;

endelse

if (head1^.elem<c) and (head1^.next=tail1) then begin

new(u);

u^.elem := c;

u^.Next := nil;

if head1=nil

then head1:=tail1;

end;

Head1:=head1^.next;

end;

head1:=t;

End;

procedure out(Head1:Link);

begin

if Head1=nil thenbegin

writeln('ochered pusta!');

exit;end;

while Head1 <> nil do

begin

write(Head1^.elem:4);

Head1:=Head1^.next;

end;end;

{Процедуравыборки}

procedure poisk(Head1:Link; b:integer);

var k:integer;

begin

if Head1=nil then begin

writeln('ochered pusta!');

exit; end;

k:=0;

while Head1 <> nil do

begin

if Head1^.elem=b then

inc(k);

Head1:=Head1^.next;

end;

if k>0 then

writeln('takoi element imeetca')

else

writeln('takogo elementa net');

end;

begin

Head:=nil; Tail:=nil;

writeln('vvedite colichestvo elementov');

readln(n);

for i:=1 to n do

begin

writeln('vvedite element');

readln(m);

Input(Head,Tail,m);

end;

writeln('vvivod ocheredi');

out(Head);

writeln;

writeln('vvedite dobavlaemiy element');

readln(s);

dob(Head,Tail,s);

out(Head);

writeln;

writeln('vedite neobhodimiy element');

read(g);

poisk(Head,g);

readkey;

end;

procedure och_prio2;

{Процедураввода}

procedure Input(var Head1,Tail1:Link;a:integer);

var

tmp:Link;

begin

New(tmp);

tmp^.next:=nil;

tmp^.pred:=tail1;

tmp^.elem:=a;

if Tail1 <> nil then

Tail1^.next:=tmp;

Tail1:=tmp;

if Head1=nil then

Head1:=Tail1;

end;

{процедура добавления}

Procedure dob(var head1, tail1 : link; c : integer);

Var

u,nach,t: link;

Begin

t:=head1;

if c<=t^.elem then begin

new(u);

u^.elem := c;

u^.Next := t;

u^.pred := nil;

t:= u;

tail1:=t;

endelse

while Head1 <> nil do begin

if (head1^.elem<c) and (head1^.next^.elem>c)

thenbegin

new(u);

u^.elem := c;

u^.Next := head1^.next;

head1^.next:=u;

u^.pred := tail1^.pred;

tail1^.pred:=u;

end else

if (head1^.elem<c) and (head1^.next=tail1) then begin

new(u);

u^.elem := c;

u^.Next := tail1;

u^.pred :=nil;

end;

Head1:=head1^.next;

end;

head1:=t;

End;

procedure out(Head1:Link);

begin

if Head1=nil thenbegin

writeln('ochered pusta!');

exit;end;

while Head1 <> nil dobegin

write(Head1^.elem:4);

Head1:=Head1^.next;

end;end;

{Процедуравыборки}

procedure poisk(Head1:Link; b:integer);

var k:integer;

begin

if Head1=nil then

begin

writeln('ochered pusta!');

exit; end;

k:=0;

while Head1 <> nil do begin

if Head1^.elem=b then

inc(k);

Head1:=Head1^.next;

end;

if k>0 then

writeln('takoi element imeetca')

else

writeln('takogo elementa net');

end;

begin

Head:=nil; Tail:=nil;

writeln('vvedite colichestvo elementov');

readln(n);

for i:=1 to n do

begin

writeln('vvedite element');

readln(m);

Input(Head,Tail,m);

end;

writeln('vvivod ocheredi');

out(head);

writeln;

writeln('vvedite dobavlaemiy element');

readln(s);

dob(Head,Tail,s);

out(head);

writeln;

writeln('vedite neobhodimiy element');

read(g);

poisk(Head,g);

readkey;end;

begin

clrscr;

writeln('1-deq vectornoy structuri');

writeln('2-deq ogranichenim vhodom;');

writeln('3-deq ogranichenim vihodom;');

writeln('4-ochered vectornoi structuri');

writeln('5-odnosniy stek');

writeln('6-dvusvasniy stek');

writeln('7-odnosvasnaya ochered;');

writeln('8-dvusvasnaya ochered');

writeln('9-odnosvasnaya ochered c prioretetom');

writeln('10-dvusvasnaya ochered c prioriteom');

writeln('vedite neobh deistvie:');

readln(i);

case i of

1:dek_1;

2:dek_2;

3:dek_3;

4:och_vec;

5:stek1;

6:stek2;

7:och_1;

8:och_2;

9:och_prio;

10:och_prio2;else

writeln('chislo vedeno nepravilno');

end;

end.

7. Результаты тестирования программы

при i=1

при i=2

при i=3

при i=4

при i=5

при i=6

при i=7

при i=8

при i=9

при i=10

8. Анализ результатов

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

Заключение

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

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

Список литературы

1.Хусаинов Б. С. Структуры и алгоритмы обработки данных. Примеры на языке Си: Учебное пособие. - М.: Финансы и статистика, 2004.-464 с.

2.Ильясов Э.Э. Методические указания по выполнению курсовой работы по дисциплине «Структура и алгоритмы обработки данных». Махачкала, РИО, ДГТУ, 2007. -20 с.

Размещено на Allbest.ru

...

Подобные документы

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

    курсовая работа [254,3 K], добавлен 20.05.2013

  • Использование класса статических массивов структур и базы данных "ODER" при создании программы на языке С++. Основные формы выдачи результатов. Технические и программные средства. Тесты для проверки работоспособности алгоритма создания программы.

    курсовая работа [1,1 M], добавлен 17.03.2015

  • Изучение категории типов данных, видов выражений и операций, работа на языке Си. Составление программы вычисления значения функции у(х) при произвольном значении х. Блок-схема алгоритма. Описание текста программы и рассмотрение контрольного примера.

    лабораторная работа [124,7 K], добавлен 09.01.2012

  • Разработка программы обработки типизированных файлов с кодом на языке Object Pascal, с использованием компонентов Delphi для ввода и вывода данных. Разработка экранных форм и алгоритма программы. Описание программных модулей и инструкция оператору.

    курсовая работа [1,5 M], добавлен 08.02.2011

  • Анализ функции и разработка алгоритма по ее вычислению. Программирование отдельных блоков и структур алгоритма. Структура Паскаль-программы. Раздел описаний, подпрограммы, тело программы. Полная Паскаль-программа в соответствии с разработанным алгоритмом.

    курсовая работа [241,8 K], добавлен 30.01.2016

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

    курсовая работа [1,2 M], добавлен 19.02.2015

  • Понятие класса как собрания информации, которая включает в себя данные и функции. Создание класса "Дек". Реализация методов: добавления элемента в начало и в конец дека, удаление элемента из начала и конца дека, проверка дека на наличие в нем элементов.

    курсовая работа [568,9 K], добавлен 08.09.2010

  • Оценка погрешности и точности в математике. Составление программы и алгоритма для численного дифференцирования с заданной допустимой погрешностью на алгоритмическом языке Turbo Pascal 7.0. Составление алгоритма и программы аппроксимации функции.

    курсовая работа [810,6 K], добавлен 24.03.2012

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

    курсовая работа [1,6 M], добавлен 12.12.2011

  • Программирование на алгоритмическом языке Turbo Pascal на примере разработки алгоритма и программы расчета временной функции. Выбор, обоснование методов решения. Схемы алгоритмов основной программы и подпрограмм. Распечатка исходных и вычисленных величин.

    реферат [154,8 K], добавлен 15.03.2012

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

    курсовая работа [2,1 M], добавлен 21.04.2012

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

    контрольная работа [52,9 K], добавлен 03.10.2010

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

    курсовая работа [3,5 M], добавлен 22.06.2012

  • Разработка программы реализации линейного алгоритма приема исходных данных со стандартного внешнего устройства и вывода на дисплей. Нахождение первого отрицательного элемента в одномерном массиве, содержащем положительные, отрицательные элементы и нули.

    курсовая работа [184,3 K], добавлен 09.06.2011

  • Особенности проектирования программы на языке С++ для обработки данных из таблиц базы данных. Основные функции программы, создание концептуальной модели базы данных и диаграммы классов, разработка интерфейса пользователя и запросов к базе данных.

    курсовая работа [2,1 M], добавлен 08.06.2012

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

    курсовая работа [41,5 K], добавлен 15.03.2012

  • Разработка линейной программы на языке С++. Разработка программ с разветвленной структурой. Составление по заданному варианту схемы алгоритма и программы вычисления тригонометрической функции с абсолютной погрешностью с использованием разложения в ряд.

    лабораторная работа [1,2 M], добавлен 12.01.2011

  • Разработка алгоритма решения задачи численного интегрирования методом трапеции. Словесное описание и блок-схема разработанного алгоритма программы. Описание интерфейса, главного окна и основных форм программы. Проверка работоспособности программы.

    курсовая работа [1,4 M], добавлен 16.03.2012

  • Анализ заданной сложной функции и разработка структурной схемы алгоритма по её вычислению. Программирование отдельных блоков и структур алгоритма решаемой задачи на языке Паскаль. Полная программа в соответствии с алгоритмом. Результаты расчётов на ПК.

    курсовая работа [59,2 K], добавлен 09.04.2012

  • Основные приёмы и возможности алгоритмических языков программирования Fortran. Табуляция функции на языке Fortran, ее графический вид и блок-схема алгоритма. Выполнение расчетов на алгоритмическом языке Фортран. Текст (листинг) Fortran-программы.

    курсовая работа [31,9 K], добавлен 15.02.2011

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.