Оглавление
Введение
Глава 1. Языки программирования высокого уровня (ЯПВУ)
1.1. Понятие и классификация языков программирования высокого уровня
1.2. Наиболее распространенные языки программирования
1.3. Обоснование выбора языка Паскаль
Глава 2. Основные принципы построения динамических списочных структур данных
2.1. Однонаправленные списки
2.2. Двунаправленные списки
2.3. Циклические списки
2.4. Мультисписки
2.5. Очередь и дек
2.6. Стек
Глава 3. Практическая часть
3.1. Постановка задачи
3.2. Решение поставленной задачи
Заключение
Список используемой литературы
ВВЕДЕНИЕ
Объектом исследования данной курсовой работы являются языки программирования высокого уровня.
Предмет исследования – динамические структуры данных, а именно список, в программировании высокого уровня.
Цель курсовой работы – изучить динамические структуры данных на конкретном примере списков, научиться создавать их и проводить другие операция добавления или удаления элементов списка.
Актуальность темы заключается прежде всего в том, что сегодня написание функциональных программ, не используя динамические структуры данных, практически невозможно, Также нужно уметь оперировать с такими структурами, используя правильный подход к выбору метода решения назначенной задачи. Поэтому изучение данного вопроса является необходимым, и в теории и в практике.
При помощи линейного списка может быть реализован абстрактный тип данных, то есть такой тип данных, который предоставляет определенный набор функций для работы с элементами. Такие типы данных впервые были описаны в книге «Искусство программирования», автором которой является Дональд Эрвин Кнут.
Дональд Эрвин Кнут – американский ученый, почетный профессор преподаватель и идеолог программирования. Он является автором всемирно известной серии книг, посвященной основным алгоритмам и методам вычислительной математики.
В этой книге он рассматривает информационные структуры, описывает так называемые структуры данных, которые определяет, как способы организации данных непосредственно внутри программы. Также описывает такие типы данных как списки, стеки, деки, очереди и так далее.
Такие типы данных позволяют нам достичь модульности программных решений и иметь несколько альтернативных взаимозаменяемых вариантом отдельного модуля.
Исходя из всего вышесказанного, перед собой я поставил задачу рассмотреть основные языки программирования, языки программирования высокого уровня, типы данных и так далее, а именно:
• что такое язык программирования;
• классификация языков программирования;
• обосновать выбор языка Паскаль;
• рассмотреть основные понятия и определения;
• ознакомиться с общими понятиями списка в Паскале;
• рассмотреть основные операции работы со списками.
Глава 1. Языки программирования высокого уровня (ЯПВУ)
1.1. Понятие и классификация языков программирования высокого уровня
Язык программирования — машинно-независимые языки, которые согласно ГОСТ 19781-90, используют понятия и структуры удобные для восприятия человеком.
Язык программирования высокого уровня предназначены прежде всего для удобства и быстроты написания программ программистом. Высокоуровневые языки программирования стремятся не только облегчить решение тех или иных задач, но и упростить возможность использования программного обеспечения на различных платформах. Использование разнообразных интерпретаторов и трансляторов обеспечивает связь программ с различным оборудованием и операционными системами, при этом исходный код не подвергается изменениям.
К недостатку программ, написанных на языке высокого уровня, можно отнести избыточный код, к которому привела компиляция. Код содержит в себе различные подпрограммы, а также комментарии к тем или иным участкам кода. Программы, для написания которых использовались высокоуровневые языки, проще для понимания, но менее эффективны, чем их аналоги, написанные на низкоуровневом (машинном) языке.
Процедурные (Procedural languages) – языки программирования, в которых все действия над данными описаны последовательностями определенных команд. Написанная на процедурном языке программа является последовательностью команд, которые определяют алгоритм решения задачи. Главная идея данного программирования заключается в том, что память используется не для хранения данных, а основной командой является операция присвоения. С ее помощью определяется и меняется память ЭВМ. Программа производит преобразование содержимого памяти, изменяя его, тем самым из исходного состояния переходит к результирующему.
Объектно-ориентированные (Object-oriented languages) – языки программирования, которые в построении программы используют совокупности объектов, состоящих из данных и операций над ними, и классов объектов. Они в свою очередь могут обращаться (вызывать) друг друга для дальнейшего выполнения тех или иных операция.
Функциональные (Functional languages) – языки программирования, в которых действия c данными выражаются в виде терминов последовательности команд. Программа, написанная на функциональном языке программирования, является совокупностью описаний функций и выражений необходимые для вычисления. Вычисления производятся с помощью редукции, то есть серии упрощений. В функциональных языках программирования не используется память как хранилище значений переменных, а операторы присваивания отсутствуют, вследствие чего переменные обозначают объекты программы, а не области памяти.
Логические (Logical languages) – языки программирования, используемые для построения программ в виде совокупности логических правил с заранее определенными алгоритмами, которые служат для обработки данных. При использовании логических языков программирования необходимо только специфицировать факты, которые лежат в основе алгоритма, а не определять шаги, требуемые для выполнения.
1.2. Наиболее распространенные языки программирования
Наиболее распространёнными языками программирования высокого уровня можно назвать:
• Ассемблер;
• Си;
• Бейсик;
• Фортран;
• Паскаль.
Рассмотрим каждый из упомянутых выше языков.
Ассемблер (Assembler) – язык программирования, расширенный использованием конструкций высокоуровневых языков программирования. К достоинствам языка ассемблера можно отнести, безусловно, самый компактный код, какой возможен для процессора; на Ассемблере можно писать программы, которые работают на микроуровне, то есть вне операционной системы, например, «прошивка» BIOS или драйвера. Но в силу машинной ориентации человеку сложнее дается чтение и понимание такого кода программы, соответственно усложняется сам процесс программирования и отладки. Также является невозможным перенос программы на компьютеры с другой архитектурой и набором команд.
Си (C) зачастую называют средне уровневым языком или даже языком программирования низкого уровня, по причине работы «близкой» к машинным устройствам. Однако, в строгой классификации, он безусловно является языком программирования высокого уровня. Создавался же этот язык с целью сделать написание больших программ более простым, с минимальным числом ошибок по правилам процедурного программирования, тем самым не добавляя в итоговый код лишнего для компилятора, как это всегда делают языки высокого уровня, например Бейсик. Но многие элементы Си являются потенциально опасными, а последствия неправильного их использования оказываются непредсказуемыми. Керниган в своей книге говорит: «Си — инструмент, острый, как бритва: с его помощью можно создать и элегантную программу, и кровавое месиво». Многие случаи некорректного использования подобных элементов не обнаруживаются ни при компиляции, ни во время исполнения. Это зачастую приводит к дальнейшему непредсказуемому поведению программы. В результате неверного использования элементов языка Си появляются «дыры» в системе безопасности.
Бейсик (BASIC) предназначался для обучения программированию и получил распространение, прежде всего, как язык для домашних компьютеров. Название языка, BASIC, является аббревиатурным сокращением – Beginner’s All-purpose Sybmolic Instruction Code, что в переводе звучит как универсальный код символических инструкций для начинающих. Синтаксис Бейсика напоминает Фортран, а многие элементы явно заимствованы. Так как язык задумывался для обучения, его конструкции очень просты – ключевые слова, используемые в синтаксисе, взяты из английского языка. Простота использования Бейсика оборачивалась трудностями структурирования. Особенно это было видно в ранних версиях языка. Также Бейсик не допускал использование рекурсии, позволяющей писать короткие, но в то же время эффективные программы. В будущих версиях, например Visual Basic, многие недостатки были устранены.
Фортран. Фортран (Fоrtran) является первым высокоуровневым языком, который имеет транслятор. Этот язык используется в первую очередь в разных научных и инженерных вычислениях. В себе Фортран несет жесткие стандарты, поэтому он легко портируется на другие платформы. Многие крупные научно-технические программы написаны на Фортране потому, что он обладает, помимо наличия встроенных математических и тригонометрических функций, важными факторами – переносимостью и устойчивость. Также неотъемлемой частью любой программы, написанной на Фортране, является графическая библиотека, которая позволяет использовать графические данные и другие изображения. Главное назначение Фортрана - это быстрый счет в различных научно-технических приложениях. Это та область, в которой у Фортрана нет конкурентов.
Язык программирования Паскаль (Pascal) является одним из первых языков, который отличался строгой типизацией и наличием средств структурного (процедурного) программирования. Этот язык представляет собой процедурный язык, включает в себя множество структур и конструкций наподобие if, then, while, еlsе и так далее. Но также Паскаль содержит достаточно большое количество возможностей для структурирования абстракций и информации (записи, указатели, множества, определение типов и перечисления). Паскаль представляет удобную среду разработки, включающую функциональный отладчик, который доступен программисту в любой момент, обладает высокой скоростью компиляции, а также высокой скоростью выполнения откомпилированных программ, имеет встроенную возможность использовать вставки на языке ассемблера.
1.3. Обоснование выбора языка Паскаль
Выбор Паскаля, как языка программирования в дальнейшем исследовании и построении данных списочных структур, прежде всего, основывается на следующих факторах:
Паскаль используется для обучения программированию и является базой для многих других языков программирования;
Учитывая строгую типизацию языка, Паскаль способствует дисциплинированному программированию;
Имеется поддержка указателей, что позволяет использовать косвенную адресацию (экономия памяти, чтение файла из памяти, а не загрузка его в ОЗУ) и динамически управлять памятью;
Паскаль является языком структурного программирования, в основе которого лежит представление программы в виде иерархической структуры. Это дает гарантии того, что при внесении ряда изменений или исправлений ошибок в одном блоке не выйдет из строя какая-либо уже отлаженная часть.