Файл: Динамические структуры данных. Списки (Понятие и классификация языков программирования высокого уровня).pdf

ВВЕДЕНИЕ

Объект исследования данной курсовой работы – языки программирования высокого уровня.

Предметом исследования являются динамические структуры данных, а именно списки, в программировании на языках высокого уровня.

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

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

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

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

Эти типы данных помогают достичь модульность программных продуктов и иметь несколько альтернативных взаимозаменяемых вариантов отдельных модулей.

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

• определение языка программирования;
• рассмотреть классификации языков программирования;
• обоснование выбора языка Паскаль;
• рассмотреть основные понятия и определения;
• познакомиться с общими понятиями списов в Паскале;
• рассмотреть основные операции работы со списками.

Глава 1. Языки программирования высокого уровня (ЯПВУ)

1.1 Понятие и классификация языков программирования высокого уровня

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

Языки программирования высокого уровня предназначаются прежде всего для удобства и быстроты в написании программ программистами. Высокоуровневые языки программирования стремятся не только облегчать решение каких-либо задач, но и упрощать возможности использования программного обеспечения на разных платформах. Использование различных интерпретаторов и трансляторов обеспечивает связь программы с различным оборудованием и операционной системой, при этом исходный код не изменяется [1].

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

Языки программирования высокого уровня разделяются на (рис. 1):

• процедурные;
• объектно-ориентированные;
• функциональные;
• логические.

Языки программирования

Процедурные

Объектно-ориентированные

Функциональные

Логические

Рисунок 1. Классификация языков программирования высокого уровня

Процедурным языком программирования (Procedural languages) называется язык, в котором все действия над данными описаны последовательностями определенных команд. Написанные на процедурном языке программы являются последовательностями команд, определяющими алгоритмы решения задач. Главной идеей данного программирования является то, что память используется не для хранения данных, а основная команда – операция присвоения, с помощью которой определяется и меняется память в ЭВМ. Программой производится преобразование содержимого памяти, изменяется, тем самым из исходного состояния происходит переход к результирующему [2].

Объектно-ориентированные языки программирования (Object-oriented languages) – это языки, которые при построении программ используют совокупность объектов, которые состоят из данных и операций над ними, и классов объекта. Они в свою очередь имеют возможность обращаться (вызывать) друг друга для последующего выполнения тех или иных операций.

Функциональные языки программирования (Functional languages) – это языки, в которых действия c данными выступают в виде терминов последовательностей команд. Программы, написанные на функциональных языках программирования, являются совокупностью описаний функций и выражений необходимых для вычислений.

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

Логические языки программирования (Logical languages) – это языки, используемые при построении программ в виде совокупностей логических правил с ранее определенным алгоритмом, которые служат для обработок данных. При использовании логического языка программирования нужно только специфицировать факты, лежащие в основе алгоритмов, а не определять шаги, которые требуются для выполнения [4].

1.2. Наиболее распространенные языки программирования

К наиболее распространенным языкам программирования высокого уровня можно отнести:

• Ассемблер;
• Си;
• Бейсик;
• Фортран;
• Паскаль.

Рассмотрим каждый из упомянутых выше языков.

Ассемблер (Assembler) – язык программирования, который расширен при помощи использования конструкций высокоуровневых языков программирования. К достоинствам Ассемблера отнесят самый компактный код, какой только возможен для процессора. На Ассемблере можно написать программу, которая работает на микроуровне, то есть вне операционных систем, например, «прошивка» BIOS или драйверов.

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

Си (C) часто называется среднеуровневым языком или даже языком программирования низкого уровня, по причине работы, близкой к машинным устройствам. Тем не менее, в строгой классификации, он непременно является языком программирования высокого уровня. Создавался же этот язык с целью сделать написание программ большого объема более простым, с минимальным числом ошибок с правилами процедурного программирования, тем самым не добавляя в конечный код лишнего для компиляторов, как это всегда делали языки высокого уровня, например Бейсик. Но многие элементы Си относятся к потенциально опасным, а последствия ненадлежащего их использования оказываются непредсказуемы. Керниган в своей книге говорит: «Си – инструмент, острый, как бритва: с его помощью можно создать и элегантную программу, и кровавое месиво». Многие случаи неправильного использования подобных элементов не определяются ни при компиляции, ни во время выполнения. Это часто приводит к дальнейшему непредсказуемому поведению программ. В результате неправильного использования элементов языка Си появляются «дыры» в системах безопасности [6].

Бейсик (BASIC) предназначается для обучения программированию и получил распространение, прежде всего, в качестве языка для домашних компьютеров. Название языка, BASIC, является аббревиатурным сокращением – Beginner’s All-purpose Sybmolic Instruction Code, что в переводе означает универсальный код символических инструкций для начинающих. Синтаксис Бейсика напоминает синтаксис Фортрана, а многие элементы явно заимствованы.

Так как язык задумывался для обучения, его конструкции очень просты – ключевые слова, которые используются в синтаксисе, заимствованы из английского языка. Простота использования Бейсика обернулась трудностями в структурировании. Особенно это видно в ранних версиях языка. Также Бейсик не допускает использования рекурсии, которая позволяет писать короткие, и в то же время довольно эффективные программы. В будущих версиях, например Visual Basic, многие недостатки были устранены [7].

Фортран (Fоrtran) первый высокоуровневый языком, который имеет транслятор. Этот язык используют в первую очередь в различных научных и инженерных вычислениях. Фортран основан на жестких стандартах, поэтому он с легкостью портируется на другие платформы. Многие крупные научно-технические программы написаны на Фортране потому, что он обладает, помимо наличия встроенных математических и тригонометрических функций, важными факторами – переносимость и устойчивост. Также неотъемлемая часть любой программы, которая написана на Фортране, это графическая библиотека, позволяющая использовать графические данные и другие изображения. Главное назначение Фортрана – это быстрый счет в разных научно-технических приложениях. Это та область, в которой Фортран не имеет конкурентов [8].

Язык программирования Паскаль (Pascal) один из первых языков, отличающийся строгой типизацией и наличием средств для структурного (процедурного) программирования. Он представляет собой процедурный язык, который включает в себя большое количество структур и конструкций подобных if, case, while, with и так далее. Но также Паскаль содержит в себе довольно большое количество возможностей для структурирования абстракций и информации (записей, указателей, множеств, определений типов и перечисления).

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

1.3 Обоснование выбора языка Паскаль

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

1. паскаль используется при обучении программированию и является базой для многих других языков программирования;
2. принимая во внимание строгую типизацию языка, Паскаль содействует дисциплинированному программированию;
3. есть поддержка указателей, позволяющая использование косвенной адресации (экономии памяти, чтение файлов из памяти, а не загрузка их в ОЗУ) и динамическое управление памятью;
4. паскаль является языком структурного программирования, в основе которого лежит представления программ в виде иерархических структур. Это дает гарантии того, что при внесении некоторых изменений или исправлений ошибок в одном блоке не выйдет из строя какая-либо уже отлаженная часть программы, оказавшаяся вне поля зрения программиста [10].

Глава 2. Основные принципы построения динамических списочных структур данных

2.1. Однонаправленные списки

Список – упорядоченное множество, которое состоит из n элементов. К элементам списка можно применять такие операции как включение и исключение. Список, элементы которого являются «соседями», имеют последовательность, называется линейным.

Список имеет длину равную количеству элементов в нем. Пустым списком называется список нулевой длины, то есть список, в котором нет элементов. Элементы списков связываются цепочкой с помощью указателей. Каждый элемент списка содержит в себе указатель, указывающий на следующий в списке элемент [11].

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