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

Размещено на 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

...