Курсовая - Работа Со Стеком и Очередью ПАСКАЛЬ. Работа со стеком и очередью Pascalabc. Net
Скачать 84.91 Kb.
|
ГАОУ ВО “ДАГЕСТАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ НАРОДНОГО ХОЗЯЙСТВА” КУРСОВОЙ ПРОЕКТ ПО ДИСЦИПЛИНЕ “ЯЗЫКИ ПРОГРАММИРОВАНИЯ” ТЕМА: Работа со стеком и очередью PascalABC.NET
РУКОВОДИТЕЛЬ ВЫПОЛНИЛ ШИФР ГРУППЫ
Дата защиты курсового проекта Отметка о защите Рецензия руководителя
Подпись зав. кафедрой Махачкала - 2021 ОглавлениеВведение 3 §1 Общая характеристика среды программирования PascalABC.NET 4 1.1Хронология языка программирования Pascal 4 1.1.1 Pascal 4 1.1.2 Delphi 4 1.1.2 PascalABC.NET 4 1.2 Преимущества PascalABC.NET 5 1.3 Особенности среды программирования PascalABC.NET 6 § 2 Стандартные коллекции. 8 2.1 Стек 8 2.2 Очередь 9 § 3. Реализация Стека и Очереди на языке программирования PascalABC.NET 10 3.1. Стеки в среде программирования PascalABC.NET 10 3.2. Операции для работы со стеком 12 3.3. Примеры использования стека 15 3.5. Операции для работы с очередью 18 3.6. Примеры использования очереди 20 Заключение 23 Список использованной литературы 24 ВведениеКоллекция – это обычный объект, который группирует несколько элементов в единое целое. Иногда коллекцию называют контейнером. Коллекции используют для хранения, извлечения, обработки и передачи агрегированных данных. В общем, они представляют собой элементы данных, которые образуют естественную группу, такую как стопку книг (набор книг), или телефонный справочник (сопоставление имен с телефонными номерами). Коллекции предусмотрены для группировки определенных объектов. Microsoft. NET Framework предоставляет несколько типов коллекций, таких как связанный список, список массивов, стек, очередь или словарь. Объектом исследования в данной курсовой работе является среда программирования PascalABC.NET. Предметом исследования же является стек и очередь. Цель данной работы рассмотреть написать программу с использованием стека и очереди. Для достижения поставленной цели в данной работе необходимо рассмотреть ряд задач исследования: рассмотреть среду программирования PascalABC.NET; разработать программу стека и очереди; Актуальность данной курсовой работы состоит в следующем: стек и очередь в среде программирования очень распространена, а данная курсовая работа поможет прояснить некоторые теоретические и практические вопросы. §1 Общая характеристика среды программирования PascalABC.NET Хронология языка программирования Pascal 1.1.1 Pascal Паскаль – язык компьютерного программирования, разработанным швейцарским профессором в сфере информатики Никлаусом Виртом в 1970г. Паскаль напоминал язык АЛГОЛ, он давал возможность определять типы данных, с помощью которых можно организовать сложную информацию, что выходит за рамки возможностей АЛГОЛА, а также ФОРТРАНА и КОБОЛА. Типы данных, определяемые пользователем, позволяли программисту вводить имена для сложных данных, которые языковой переводчик мог затем проверить на правильность использования перед запуском программы. В конце 1970-х и 80-х годах Паскаль являлся наиболее широко используемых языков для обучения программированию. Он был доступен почти на всех компьютерах. Благодаря своей понятности, ясности и безопасности, его использовали для производственного программного обеспечения, и для обучения. 1.1.2 Delphi Delphi – это объектно-ориентированный, структурированный, статически строго типизированный язык программирования высокого уровня. Основная область использования - написание прикладного программного обеспечения. Ранее этот язык программирования назывался ObjectPascal. ObjectPascal изначально был немного другим языком, который был разработан в Apple в 1987 году в сотрудничестве с командой Ларри Теслера. Однако, начиная с Delphi 7, официальные документы Borland использовали имя Delphi для языка, ранее известного как ObjectPascal. Delphi был выпущен в России в 1995 г. 1.1.2 PascalABC.NETМатематический факультет, механики и компьютерных наук вместе с сотрудниками во главе, который являлся Станислав Станиславович Михалкович в 2002 году в федеральном университете в городе Ростов-на-Дону создали этот язык. PascalABC.NET был создан с главной целью – создание хорошей обучающей среды программирования. В 2005 – 2006 годах Паскаль потерпел ряд сильных изменений: Архитектура полностью меняется. Стал доступен компилятор с поддержкой платформы .NET Ну а вскоре появляется новая версия PascalABC.NET 1.2 С момента создания этого языка программирования, он не переставал улучшаться, во многом обогнав Delphi. По простоте PascalABC.NET сравним с языком Python, и по сравнению с C# его синтаксис является, более компактным, понятным и аккуратным. 1.2 Преимущества PascalABC.NETPascalABC.NET даёт возможность применять многие инструменты, предоставленная платформой .NET: унифицированная система типов, классы, интерфейсы, исключения, делегаты, перегрузка операций, универсальные шаблоны, методы расширения, обширные библиотеки .NET. Было добавлено несколько языковых систем: описание методов в теле класса, наборы произвольных типов, операторы loop и foreach, внутри-блочные переменные. PascalABC.NET – это простая среда разработки, ориентированная на обучение. Одна из важных особенностей интегрированной среды разработки IDE, нацеленная на обучение – это легкость. Интерфейс такой среды не должен выглядеть как интерфейс профессиональных сред программирования или, по крайней мере, должен быть настраиваемым по сложности. Кроме того, среда разработки должна предоставлять специальные инструменты обучения, которые упрощают изучение программирования (например, четкую диагностику ошибок). Помимо языка и среды, PascalABC.NET имеет ряд модулей, предназначенных для обучения. К ним относятся: Модуль растровой графики Graph ABC; Модуль векторной графики ABC Objects; Модуль простых коллекций Collections, модули Robot и Draftsman для школьных исполнителей; Также в PascalABC.NET есть модуль электронной книги задач Programming Taskbook 4 автором, который является Михаил Абрамян. Оно позволяет автоматически выполняет проверку задач, а также и постановку. Также есть модули для учителя, позволяющие создавать задания для исполнителей Робот, Чертежник и электронного задачника. 1.3 Особенности среды программирования PascalABC.NETВыскажем ряд суждений об изучении программирования PascalABC.NET, а также о важности этой концепции. PascalABC.NET - один из тех языков, на которых легко обучать программированию. В основном он предназначен для студентов и школьников, которые хотят быстро выучить современный язык программирования. В этом плане альтернативы PascalABC.NET, на мой взгляд, нет. PascalABC.NET - мощный современный язык программирования, но возможности оболочки направлены в первую очередь на обучение: простота, подсказки по коду. Компилятор PascalABC.NET генерирует код так же быстро, как код C #, но медленнее, чем код Delphi и C ++. PascalABC.NET - один из лучших языков для изучения базового программирования. Суждение о том, что язык Паскаль стал неактуальным и также теряет свои позиции, основано на понятии старого Паскаля и старых сред программирования. Кроме того, это подкрепляется определенной потерей положения системы Delphi, также связанной с неверным суждением о том, что необходимо обучать программированию на «настоящих» промышленных языках, «чтобы потом не пришлось заново учиться». Большая часть нашей учебной литературы с упорством, достойным лучшего приложения, нацелена на устаревший Turbo Pascal со старой консольной оболочкой, плохой графической библиотекой и устаревшими инструментами ООП (объектно-ориентированного программирования). Обучение программированию – это набор алгоритмов, умение структурировать и читать программы, находить в них ошибки. Здесь совершенно не нужны новаторские системы языка. Но, если они на языке и простые, то в этом случае стоит использовать с самого начала обучения, а не откладывать «на потом». PascalABC.NET – это реализация Delphi, в которой отсутствуют особенности языка, специфичные для Delphi, и не имеющая особого значения за пределами среды Delphi. PascalABC.NET основан на платформе .NET и позволяет использовать огромное количество библиотек .NET, включая классы контейнеров, сети, базы данных и т. Д. Кроме того, вы можете просто комбинировать библиотеки, созданные в PascalABC.NET и других .NET. -языки. PascalABC.NET – это развивающийся фреймворк. Он проводит исследования новейших языковых функций, новых библиотек, а также новых языков программирования, которые будут включены в единую область. PascalABC.NET имеет веб-версию WDE PascalABC.NET, которая представляет собой среду разработки на основе браузера. А программы хранятся и компилируются на сервере. § 2 Стандартные коллекции. 2.1 Стек Стек – линейная структура данных, соответствующее механизму L.I.F.O (Last-In-First-Out, зашел последним вышел первым). Объект в стеке, который добавлен последним, она будет удалять его первым. Чтоб добавить или удалить элементы из стека, применяют операции: Push – выполнение операции присвоения элемента на вершину стека Pop – операция вытаскивания элемента из вершины стека Рис 1. Последовательное добавление чисел в стек Проще всего стек можно представлять, как такую стопку книжек. Вы можете положить сверху новую книгу (Рис 1.) или вы можете последнюю книгу, которая лежит на вершине стопки взять. Чтобы получить доступ к самой нижней книге, вам нужно достать самую первую книгу, потом второй и так далее, пока не доберётесь до последнего. По сути стек – это линейный алгоритм, которая хранит данные линейно, то есть как массив один за одним, и вы можете делать только две операции, вы можете добавить сверху стека, и взять элемент из вершины стека. 2.2 ОчередьОчередь – это особый вид типа данных, в которой объекты хранятся в порядке, а основные (или единственные) операции - это добавление объектов в заднюю конечную позицию, и удаление сущностей из передней конечной позиции (Рис 2.). Это делает очередь структурой данных FIFO (First In – First out - «первым пришел - первым вышел»). В структуре данных FIFO первый элемент, добавленный в очередь, будет первым, который будет удален. Очередь – это пример линейной структуры данных или, более абстрактно, последовательной коллекции. Самый простой пример очереди – это типичная очередь, в которой мы все время участвуем. Мы ждем в очереди на просмотр фильма, мы ждем в очереди в продуктовый магазин. Линии очереди очень ограничены, поскольку имеют только один вход и только один выход. Здесь нет прыжков посередине и нет выхода, пока вы не подождали необходимое количество времени, чтобы попасть вперед. Для добавления и удаления из очереди применяют две операции: 1. Enqueue – добавляет элемент в очередь 2. Dequeue – удаляет элемент из очереди Рис 2. Добавляется элементы в очередьивывод элементов из очереди § 3. Реализация Стека и Очереди на языке программирования PascalABC.NET3.1. Стеки в среде программирования PascalABC.NETВ паскале стек создан на основе общей стандартной коллекции System.Collections.Generic.Stack. Стек считается стандартным типом языка, поэтому его можно создать с применением оператора присваивания вида var <имя переменной>:= new Stack <тип данных>; В этой программе реализовано добавление и удаление элементов(чисел) в структуру данных Стек. begin var x := new Stack var i: integer; println('Добавление'); for i := 1 to 5 do begin x.Push(i); println(x); end; println; println('Удаление'); for i := 1 to 5 do begin println(x); x.Pop; end; end. Добавление [1] [2,1] [3,2,1] [4,3,2,1] [5,4,3,2,1] Удаление [5,4,3,2,1] [4,3,2,1] [3,2,1] [2,1] [1] В переменной x в котором присвоен стек будут добавляться цифры от 1 до 5 (из переменной i) в переднюю конечную позицию с помощью операции push. При удалении элемента будут удаляться по порядку из передней конечной позиции с помощью операции pop. Как уже было сказано в теоретической части, в структуре данных конечный элемент LIFO, добавленный в стек, будет удален первым. В качестве типа данных, помещаемых в стек, мы можем заранее определить любой тип, включая наш собственный. Коллекция реализована как контейнер, тип данных, помещаемых в стек, также может быть стеком. Структура предоставляет, объединить создание стека с его заполнением элементами последовательности, указанной в качестве параметра. В данном случае элементы в новом стеке станет противоположным полученным данным. begin var stack1 := new Stack println(stack1); // [13,9,5,1] end. В приведенном примере в стек stack1 поместили элементы последовательности 1, 5, 9, 13 заданной генератором лямбда выражений нечетных чисел. Вывод чисел из стека выполняется, начиная с его вершины, поэтому на мониторе будет показывать значения [13, 9, 5, 1]. В этом и состоит особенность стека: он меняет порядок следования данных на противоположный. 3.2. Операции для работы со стекомДля работы со стеком применяются следующие функции: Count – свойство, возвращающее количество элементов в стеке; Push – метод, помещающий указанный объект на вершину стека; Peek – метод, возвращающий объект, находящийся на вершине стека, при этом сам объект остается на месте. Может вызываться в виде функции; Pop – удаляет элемент на вершине стека. Возвращает удаляемый элемент. Может вызываться в виде функции; Clear – очистка стека; Contains(объект) – метод, котрый возвращает True, если указанный объект находится в стеке и False если такого объекта в стеке нет; ToArray – метод, копирующий содержимое стека в одномерный динамический массив и возвращающий этот массив в качестве результата. Не требует предварительного описания массива; CopyTo(имя массива, индекс) – метод, копирует содержимое стека в существующий одномерный динамический массив, начиная с элемента, указанного индексом. Если данные не помещаются в массиве, возникает исключение; Print – Осуществляет вывод стека, начиная с его вершины. В качестве параметра можно указать символ или строку - разделитель, по умолчанию используется пробел; Println – осуществляется вывод на новую строку В этой программе применение функции стандартных коллекций, для работы со стеком begin var x := new Stack foreach var a in ReadSeqIntegerWhile(p -> p <> 0) do x.Push(a); writeln; println('Элементов: ', x.Count); println('Cодержит ли число 5 в стеке ? - ', x.Contains(5)); println('Число который находится на вершине стека: ', x.Peek); println('Вывод Стека: ', x); println('Очистка Стека: ', x.Clear); end. 1 5 10 15 20 0 Элементов: 5 Содержит ли число 5 в стеке? - True Число который находится на вершине стека: 20 Вывод Стека: [20,15,10,5,1] Очистка Стека: (Void Clear (), [20,15,10,5,1]) 3.3. Примеры использования стекаРассмотрим символьную строку, которая содержит некоторое выражение с круглыми скобками. Требуется определить, верно ли расставлены скобки. Рассмотрим следующий нетрудный алгоритм: Имеем пустой стек. Выполняем последовательный просмотр всех символов строки. Если наш очередной символ является открывающийся круглой скобкой, то заносим символ в стек. Если очередной символ имеет закрывающую круглую скобку, мы проверяем стек. Если он не пустой, то мы удаляем символ с вершины, если пуст – то выводим ошибку. Если после окончания просмотра строки стек не пуст, фиксируем ошибку. begin var St2 := new Stack foreach var x in ReadlnString('Введи выражение') do case x of '(': St2.Push(x); ')': if St2.Count > 0 then St2.Pop else begin write('Скобки неверно расставлены'); Exit end end; if St2.Count = 0 then write('Скобки верно расставлены') else write(' Скобки неверно расставлены') end. Пример выполнения программы Пусть выражение будет: ((2+2) * (3+3) * 2) 'Скобки верно расставлены' А если выражение будет: (2)) (45( 'Скобки неверно расставлены'. 3.4. Очередь в среде программирования PascalABC.NET В Паскале очередь реализована на основе стандартной коллекции System.Collections.Generic.Queue. Очередь является стандартным типом языка, поэтому его можно создать с использованием оператора присваивания вида var <имя переменной> := new Queue <тип данных>; В этой программе реализовано добавление элементов (чисел) в структуру данных очередь. begin var i: integer; var qe := new Queue writeln('Добавление: '); for i := 1 to 5 do begin qe.Enqueue(i); println(qe); end; writeln; writeln('Удаление: '); for i := 1 to 5 do begin println(qe); qe.Dequeue; end; end. Добавление: [1] [1,2] [1,2,3] [1,2,3,4] [1,2,3,4,5] Удаление: [1,2,3,4,5] [2,3,4,5] [3,4,5] [4,5] [5] В переменной qe в котором присвоен очередь, будут добавляться цифры от 1 до 5 (из переменной i) в заднюю конечную позицию с помощью операции enqueue. При удалении элемента будут удаляться по порядку из передней конечной позиции с помощью операции dequeue. Как уже сказано в теоретической части в структуре данных очереди удаление данных возможен только спереди, а добавление данных возможно только сзади. В качестве типа данных, помещаемых в очередь, мы можем заранее определить любой тип, в том числе, предварительно определенный пользователем. Так как коллекция реализована как контейнер, тип данных, помещаемых в очередь, может быть очередью. Структура предоставляет совмещать создание очереди с ее заполненными элементами последовательности, указанной в качестве параметра. begin var x1 := new Queue Println(x1); var x2 := new Queue Println(x2); end. [39,49,41,38,21] [21,38,39,41,49] В приведенном программе в переменной x1 имеется очередь тип данных, который является целые числа и заполняет данные от генератора случайных чисел. В переменной x2 с очередью, было присвоено переменная x1 с сортировкой, который сортируется в порядке возрастания. 3.5. Операции для работы с очередьюДля работы с очередью применяются следующие функции: Count – свойство, возвращающее количество элементов в очереди; Enqueue – помещает указанный элемент в конец очереди; Peek – метод, возвращающий объект, находящийся в начале очереди. Может вызываться в виде функции; Dequeue – удаляет элемент в начале очереди. Возвращает удаляемый элемент. Может вызываться в виде функции; Clear – метод, очищающий очередь; Contains(объект) – метод, возвращающий True, если указанный объект находится в очереди и False если объект отсутствует в очереди; ToArray – метод, копирует содержимое очереди в одномерный динамический массив и возвращающий этот массив в качестве результата. Не требуя предварительного описания массива; CopyTo (имя_массива, индекс) – метод, копирует содержимое очереди в существующий одномерный динамический массив, начиная с элемента, указанного индексом. Если данные не помещаются в массиве, возникает исключение; Print – Осуществляет вывод очереди из передней конечной позиции. В качестве параметра можно указать символ или строку - разделитель, по умолчанию используется пробел; Println – осуществляется вывод на новую строку В этой программе реализовано применение функции стандартных коллекций, для работы с очередью begin var x := new Queue foreach var a in ReadSeqIntegerWhile(p -> p <> 0) do x.enqueue(a); writeln; println('Элементов в Очереди: ', x.Count); println('Cодержит ли число 5 в очереди ? - ', x.Contains(5)); println('Число в передней конечной позиции очереди: ', x.Peek); println('Вывод Очереди: ', x); println('Очистка Очереди: ', x.Clear); end. 1 10 100 250 500 1000 0 Элементов в Очереди: 6 Содержит ли число 5 в очереди? - False Число в передней конечной позиции очереди: 1 Вывод Очереди: [1,10,100,250,500,1000] Очистка Очереди: (Void Clear (), [1,10,100,250,500,1000]) 3.6. Примеры использования очередиМассив, динамический массив, требует указания размера. Для очереди этого не требуется. Из этого следует, что явное превосходство применения очереди в задачках, где количество данных неизвестно, к примеру, когда работаем с файлами или приеме данных с некоторым условием завершения приема. №1. С клавиатуры вводится последовательность натуральных чисел, где число ноль является ограничение. Значение чисел не должно быть больше 999. Вывести значения поступивших чисел по группам: сперва цифры, потом двузначные и в конце трехзначные числа. Порядок следования чисел в каждой группе не должен изменяться по сравнению с порядком ввода чисел. С целью поставленной задачи, требуется создать три очереди, содержимое которых потом выводим. begin var x1 := new Queue var x2 := new Queue var x3 := new Queue foreach var a in ReadSeqIntegerWhile(z -> z <> 0) do if a < 10 then x1.Enqueue(a) else if a < 100 then x2.Enqueue(a) else x3.Enqueue(a); writeln(x1.sorted); writeln(x2.sorted); writeln(x3.sorted); end. Числа которые мы ввели: 9, 4, 3, 5, 1, 44, 32, 54, 11, 122, 111, 0 [1, 3, 4, 5, 9] [11, 32, 44, 54] [111, 122] Задача 2. Очереди x1 и x2 содержатся данные типа integer, отсортированные в порядке возрастания. Выполнить слияние, получив очередь x, содержащую все элементы очередей x1 и x2, расположенные в неубывающем порядке. Тут легче использовать маркер конца, добавляя в хвост очередей x1 и x2 максимально возможное значение integer max value. Оно сделает завершение процесса слияния по присутствию в каждой очереди ровно одного элемента, избавляя от дополнительных ветвлений в алгоритме. begin var x1 := new Queue Println(x1); x1.Enqueue(integer.MaxValue); // маркер конца var x2 := new Queue Println(x2); x2.Enqueue(integer.MaxValue); // маркер конца var x := new Queue while (x1.Count <> 1) or (x2.Count <> 1) do x.Enqueue(x1.Peek < x2.Peek ? x1.Dequeue : x2.Dequeue); Print(x) end. [21,26,43,81,81] [25,43,46,47,51,76,87,99] [21,25,26,43,43,46,47,51,76,81,81,87,99] Выполнения данной задачи теперь с помощью массива. Реализовано значительно короче, однако менее эффективно. Впрочем, при относительно небольших объемах данных это не наблюдается. Практически никаких операции слияния не понадобится и на самом деле не имеет значения, отсортированы ли исходные массивы либо последовательности: они попросту объединяются, а затем полученная последовательность сортируется. begin var x1 := ArrRandom(5, 10, 99); Println(x1); var x2 := ArrRandom(8, 10, 99); Println(x2); var x := (x1 + x2).Sorted.ToArray; // решение в одной строке Println(x) end. ЗаключениеВ данной курсовой работе мы немного ознакомились со средой программирования PascalABC.NET и хронологии его происхождения. Были рассмотрены стандартные коллекции стек и очередь в PascalABC.NET. В большей степени были рассмотрены в практической части. Были применены различные интересные операции в программе, в котором есть только в стандартных коллекциях. Стандартные коллекции представляют собой набор элементов, доступ к которым можно получить, только перебирая все элементы по очереди. В среде программирования PascalABC.NET очень понятно и просто работать со структурными данными. Безусловно, PascalABC.NET – хороший язык, особенно он прекрасно смотрится на фоне старых реализаций. К тому же здесь присутствует очень полезный справочный материал, что помогает в изучении чего-то большего. PascalABC.NET – это прекрасная среда программирования для начального обучения. Список использованной литературыАбрамян M. Э. Структуры данных в PascalABC.NET. Список, множества, словари, стек и очередь. Многомерные структуры. — Ростов н// Д: Изд-во ЮФУ, 2015. — 117 с Водолазов H.H. Михалкович C.C., Ткачук А.В. Опыт разработки учебного языка программирования для платформы .NET // Научно - методическая конференция «Современные ИТ в образовании: Южный Федеральный округ» 27--28 апреля 2006 / Крукиер Л.A., Муратова Г.В. – Ростов-на-Дону: 2006. -- C. 61--63. -- 314 с. -- 264 э. – I.S.B.N 878-5-94353-145-3. Михалкович C. C. Учебная система программирования PascalABC: опыт разработки и использования / Вторая международная научно-практическая конференция «Современные информационные технологии и ИТ-образование»: Сборник трудов -- М., 2005. -- С. 384-401. Осипов А. В. PascalABC.NET введение в современное программирование Интернет – ресурс: Http: //pascalabc.net |