Структуры и типы данных языка программирования. Трансляция, компиляция, интерпретация

Цель информационного программирования; алгоритмический язык как система обозначений и правил для единообразной и точной записи алгоритмов и их исполнения. Языки программирования низкого и высокого уровня; классификация и использование структуры данных.

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

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

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

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

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

Содержание

Введение

1. Алгоритм

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

3. Типы данных

4. Структура данных

5. Список структур данных

6. Статистические структуры данных

7. Полустатистические структуры данных

8. Динамические структуры данных

9. Нелинейные структуры данных

Заключение

Список использованной литературы

Введение

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

Все выше сказанное обусловило цель работы: исследовать основные типа и структуры данных различных языков программирования. Однако для этого необходимо понять, что такое программирование и что такое алгоритм.

1. Алгоритм

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

Любой алгоритм представляет собой описание некоторой упорядоченной совокупности действий над определенными объектами. Объектами действий для вычислительных алгоритмов являются данные - числа, слова, тексты, хранящиеся в памяти ЭВМ или поступающие через устройства ввода-вывода информации.

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

В общем виде алгоритм на алгоритмическом языке записывается так:

алг имя алгоритма

дано условия применимости алгоритма

надо цель выполнения алгоритма

нач начало алгоритма

тело алгоритма (последовательность команд)

кон конец алгоритма

Примерами вычислительных алгоритмов служат стандартные методы решения математических, физических задач, задач теории вероятности и др. Вообще само слово «алгоритм» происходит от algorithmi - латинской формы написания имени великого математика IX века аль-Хорезми, сформулировавшего правила выполнения арифметических действий. Поэтому первоначально под алгоритмами понимали только правила выполнения четырех арифметических действий над числами. В дальнейшем это понятие стали использовать для обозначения действий, приводящих к решению поставленной задачи.

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

Линейными являются алгоритмы, состоящие из одной серии простых команд.

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

При разработке алгоритмов необходимо соблюдать определенные требования:

1. Конечность. Работа алгоритма должна заканчиваться за конечное число шагов.

2. Определенность. Все предписания алгоритма должны допускать однозначную трактовку и быть понятны исполнителю алгоритма.

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

4. Вывод. Алгоритм должен давать результат.

5. Эффективность. Общее время работы алгоритма должно быть в разумных пределах.

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

Процесс разработки алгоритма включает в себя следующие этапы:

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

2. Построение математической модели исходной задачи (описание исходной задачи с использованием математических формул).

3. Анализ возможностей системы, Реализующей алгоритмический процесс (способна ли система по своим техническим характеристикам решить задачу).

В качестве исполнителей вычислительных алгоритмов выступают ЭВМ. Для того чтобы алгоритм был выполнен на ЭВМ, он прежде всего, должен быть записан с помощью специального языка - языка программирования. Процесс записи алгоритма на выбранном языке в форме, доступной для обработки на ЭВМ, называется программированием, а результат записи алгоритма на этом языке называется программой. Иными словами, программа это набор предписаний (инструкций) дл ЭВМ.

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

Программирование возникло задолго до появления компьютеров. Первым программистом считается дочь известного поэта лорда Байрона Ада Лавлейс - ученица английского математика Чарльза Бэббиджа, разработавшего в XIX веке проект вычислительной машины. В честь Ады Лавлейс один из языков программирования был назван в ее имением, впоследствии широко применяемый в Министерстве обороны Соединенных Штатов Америки.

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

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

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

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

· Задача: язык программирования отличается от естественных языков тем, что предназначен для передачи команд и данных от человека компьютеру, в то время, как естественные языки используются для общения людей между собой. В принципе, можно обобщить определение «языков программирования» -- это способ передачи команд, приказов, чёткого руководства к действию; тогда как человеческие языки служат также для обмена информацией.

· Исполнение: язык программирования может использовать специальные конструкции для определения и манипулирования структурами данных и управления процессом вычислений.

В настоящее время языков программирования несколько десятков, а то и сотен. Я рассмотрела лишь некоторые из них.

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

Язык программирования низкого уровня - это язык программирования, структура команд которого определяется форматом команд и данных машинного языка, а также архитектурой ЭВМ.

Ярким представителем языка программирования низкого уровня является Ассемблер (Assembler), который был разработан в 50-е годы прошлого века и позволяет писать программы с использованием специальных обозначений машинных кодов - мнемоники. Ассемблер широко применяется в программах, где необходимо высокое быстродействие.

Однако составлять программы на таком языке - дело очень хлопотное и неблагодарное. Поэтому были созданы языки программирования высокого уровня.

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

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

Языки программирования высокого уровня освобождают пользователя от программирования в машинных кодах. Однако такую программу не понимает ЭВМ, ей доступен только машинный язык. Поэтому для трансляции (перевода) программ с языка высокого уровня в машинные коды используются программы компиляции или интерпретации. При этом отличие компилятора от интерпретатора заключается в том, что компилятор вначале переводит все команды исходной программы, записанной на языке высокого уровня, в машинные инструкции, а затем выполняет ее, а интерпретатор осуществляет покомандную обработку и исполнение исходной программы.

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

Ада (Ada) - назван в честь Августы Ады Байрон, графини Лавлейс, дочери лорда Байрона, которая была сотрудницей Чарльза Бэббиджа, изобретателя аналитической машины, и написала для нее практически законченную программу вычисления коэффициентов Бернулли. Кроме того она ввела многие понятия (цикл, условный оператор), которые теперь составляют базу программирования. Сам язык Ада является универсальным языком программирования, поддерживающим методологии разработки снизу вверх и сверху вниз, раздельную компиляцию, настраиваемые пакеты, абстрактные типы данных, параллельное программирование и работу в реальном времени, средства для низкоуровневого программирования, контролируемую точность вычислений, возможность гибкой настройки на конкретную платформу и многое другое. В настоящее время Ада является основным языком программирования Министерства обороны США.

Алгол (Algorithmic Language - алгоритмический язык) - универсальный язык для программирования вычислительных задач. Ему свойственна близость к математической символике.

Бейсик (Beginer All-Purpose Symbolic Code - универсальный символический код для начинающих) - язык для создания программ и их решения ЭВМ в режиме диалога. Он был разработан в середине 60-х годов профессорами Дармутского колледжа Джоном Кемени и Томасом Курцом. Бейсик является одним из самых простых и распространенных в мире языков программирования. В середине 80-х годов фирмой Microsoft был реализован язык QuickBasic (последняя версия 4.5). Это полностью компилируемый язык, с нормальными структурными конструкциями, пользовательскими типами данных, причем еще и совместимый со старыми версиями. С появлением Windows и моды на визуальные средства разработки изменился и Basic. Его новая версия, названная Visual Basic, была отлично приспособлена для написания несложных программ с развитым пользовательским интерфейсом. Visual Basic на равнее с Visual C является весьма популярным средством разработки под Windows.

Делфи (Delphi) оказался одним из первых продуктов, который сделал процесс программирования простым и понятным даже начинающим разработчикам. Это было связано с появлением в начале 90-х операционных систем со встроенным графическим интерфейсом. Действительно, процесс разработки программы в Delphi предельно упрощен. В первую очередь это относится к созданию интерфейса, на который уходит 80% времени разработки программы. Вы просто помещаете нужные компоненты на поверхность Windows-окна (в Delphi оно называется формой) и настраиваете их свойства с помощью специального инструмента (Object Inspector). С его помощью можно связать события этих компонентов (нажатие на кнопку, выбор мышью элемента в списке и т.д.) с кодом его обработки - и простое приложение готово. При этом разработчик получает в свое распоряжение мощные средства отладки (вплоть до пошагового выполнения команд процессора), удобную контекстную справочную систему, средства коллективной работы над проектом и т.д. - всего не перечислить.

Паскаль (Philips Automatic Sequence Calculator). Этот язык был разработан швейцарским ученым Никлаусом Виртом в 1969 году как учебный язык, но спустя некоторое время приобрел популярность как отличный инструмент для решения серьезных задач. Программирование на Паскале обеспечивает высокую надежность программ. Программы на паскале понятны любому программисту и в то же время они легко транслируются в эффективные машинные коды. Паскаль, наряду с Бейсиком, считается так же учебным языком; он принят во многих учебных заведениях как базовый язык для изучения программирования. Так, в США с 1983 года Паскаль введен в учебные курсы всех средних школ для учащихся, специализирующихся в области информатики. По мере своего развития язык Паскаль постоянно совершенствовался и приобретал новые свойства и сейчас более известен язык Турбо Паскаль, разработанный фирмой Borland.

Си (C) - язык, специально разработанный для написания системных программ и переноса записи программного обеспечения с одной ЭВМ на другую. Этот язык был создан сотрудником фирмы Ball Labs Денисом Ритчи в 1972 году и послужил главным инструментом для создания операционных систем UNIX и MS-DOS. Как и все языки, язык C постепенно совершенствовался. Уже в начале 80-х годов Бьерн Страуструп в AT&T Bell Labs стал разрабатывать расширение языка C под условным названием «C с классами», дающий возможности определять и использовать новые типы данных. Первый коммерческий транслятор нового языка, получившего название C++, появился в 1983 году. Он представлял собой препроцессор, транслировавший программу в код на C. Однако фактически рождением языка можно считать выход в 1985 году книги Страуструпа «The C++ Programming Language». Именно с этого момента C++ начинает набирать всемирную популярность.

Главным достоинством C++ является возможность создания и использования в программе своих собственных полноценных типов данных, «настроенных» на конкретную задачу. Например, работая в среде Turbo C++, программист может использовать такие концепции: окно редактора или отладчика; текст в текущем окне; меню команд; режим компиляции. Над ними могут выполняться, например, такие действия: открыть новое окно или закрыть ненужное; выбрать другое текущее окно; переместить окно или изменить его размер; выполнить вертикальный сдвиг текста в окне; упорядочить расположение окон на экране; выбрать нужную команду меню с помощью мыши; изменить режим компиляции; сохранить текущий режим компиляции.

Фортран (Formula Translator - переводчик формул) был разработан в середине 50-х годов программистами фирмы IBM. В основном он используется для программ, выполняющих естественнонаучные и математические расчеты.

Ява (Java) - язык для программирования Internet, позволяющий создать безопасные, переносимые, надежные, объектно-ориентированные интерактивные программы с параллельно выполняющимися подпроцессорами. Язык Ява жестко связан с Internet, потому что первой серьезной программой, написанной на этом языке, был браузер Всемирной паутины.

3. Типы данных

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

Необходимость использования типов данных

Типы данных различаются начиная с нижних уровней системы. Так, например, даже в Ассемблере х86 различаются типы «целое число» и «вещественное число». Это объясняется тем, что для чисел рассматриваемых типов отводятся различные объёмы памяти, используются различные регистры микропроцессора, а для операций с ними применяются различные команды Ассемблера и различные ядра микропроцессора.

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

Практическое применение

Как правило, типы языков программирования не всегда строго соответствуют подобным математическим типам. Например, тип «целое число» большинства языков программирования не соответствует принятому в математике типу «целое число», так как в математике указанный тип не имеет ограничений ни сверху, ни снизу, а в языках программирования эти ограничения есть. Как правило, в языках и системах имеется множество целых типов, отличающихся допустимым диапазоном значений (определяемым объёмом занимаемой памяти). Стоит отметить, что в большинстве реализаций языков и систем выход за границу целого типа (переполнение) не приводит к исключительной ситуации.

Языки без типов

Теоретически не может существовать языков, в которых отсутствуют типы. Это следует из того, что все языки основаны на машине Тьюринга или на лямбда-исчислении. И в том, и в другом случае необходимо оперировать как минимум одним типом данных -- хранящимся на ленте (машина Тьюринга) или передаваемым и возвращаемым из функции (лямбда-исчисление). Ниже перечислены языки программирования по способу определения типов данных:

1) Языки с полиморфным типом данных. Одни языки не связывают переменные, константы, формальные параметры и возвращаемые значения функций с определёнными типами, поддерживая единственный полиморфный тип данных. В чистом виде таких языков не встречается, но близкие примеры -- MS Visual Basic -- тип variant, Пролог, Лисп -- списки. В этих языках переменная может принимать значение любого типа, в параметры функции можно передавать значения любых типов, и вернуть функция также может значение любого типа. Сопоставление типов значений переменных и параметров с применяемыми к ним операциями производится непосредственно при выполнении этих операций. Например, выражение a+b, может трактоваться как сложение чисел, если a и b имеют числовые значения, как конкатенация строк, если a и b имеют строковые значения, и как недопустимая (ошибочная) операция, если типы значений a и b несовместимы. Такой порядок называют «динамической типизацией». Языки, поддерживающие только динамическую типизацию, называют иногда «бестиповыми». Это название не следует понимать как признак отсутствия понятия типов в языке -- типы данных всё равно есть.

2) Языки с неявным определением типов. Казалось бы, BASIC является примером языка без типов. Однако это строго типизированый язык: в нём различаются строковые типы (добавляется символ $), массивы (добавляется []) и числовые типы (ничего не добавляется).

3) Языки с типом, определяемым пользователем. Также хорошо известны языки, в которых типы данных определяются автоматически, а не задаются пользователем. Каждой переменной, параметру, функции приписывается определённый тип данных. В этом случае для любого выражения возможность его выполнения и тип полученного значения могут быть определены без исполнения программы. Такой подход называют «статической типизацией». При этом правила обращения с переменными, выражениями и параметрами разных типов могут быть как очень строгими (С++), так и весьма либеральными (Си). Например, в классическом языке Си практически все типы данных совместимы -- их можно применять совместно в любых выражениях, присваивать значение переменной одного типа переменной другого почти без ограничений. При таких операциях компилятор генерирует код, обеспечивающий преобразование типов, а логическая корректность такого преобразования остаётся на совести программиста. Подобные языки называют «языками со слабой типизацией». Противоположнось им -- «языки с сильной типизацией», такие как Ада. В них каждая операция требует операндов строго заданных типов. Никакие автоматические преобразования типов не поддерживаются -- их можно выполнить только явно, с помощью соответствующих функций и операций. Сильная типизация делает процесс программирования более сложным, но даёт в результате программы, содержащие заметно меньше труднообнаруживаемых ошибок.

На практике языки программирования поддерживают несколько моделей определения типов одновременно.

Базовые типы

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

Преимущества от использования типов данных

· Надёжность. Типы данных защищают от трёх видов ошибок:

1. Некорректное присваивание. Пусть переменная объявлена как имеющая числовой тип. Тогда попытка присвоить ей символьное или какое-либо другое значение в случае статической типизации приведёт к ошибке компиляции и не даст такой программе запуститься. В случае динамической типизации код программы перед выполнением потенциально опасного действия сравнит типы данных переменной и значения и также выдаст ошибку. Всё это позволяет избежать неправильной работы и «падения» программы.

2. Некорректная операция. Позволяет избежать попыток применения выражений вида «Hello world» + 1. Поскольку как уже говорилось, все переменные в памяти хранятся как наборы битов, то при отсутствии типов подобная операция была выполнима (и могла дать результат вроде «ello world?»). С использованием типов (см. далее «Контроль типов») такие ошибки отсекаются опять же на этапе компиляции.

3. Некорректная передача параметров. Если функция «синус» ожидает, что ей будет передан числовой аргумент, то передача ей в качестве параметра строки «Hello world» может иметь непредсказуемые последствия. При помощи контроля типов такие ошибки также отсекаются на этапе компиляции.

· Стандартизация. Благодаря соглашениям о типах, поддерживаемых большинством систем программирования, сложилась ситуация, когда программисты могут быстро менять свои рабочие инструменты, а программы не требуют больших переделок при переносе исходных текстов в другую среду. К сожалению, стандартизации по универсальным типам данных ещё есть куда развиваться.

Классификация типов данных

Типы данных бывают следующие:

· Простые.

o Перечислимый тип. Может хранить только те значения, которые прямо указаны в его описании.

o Числовые. Хранятся числа. Могут применяться обычные арифметические операции.

§ Целочисленные: со знаком, то есть могут принимать как положительные, так и отрицательные значения; и без знака, то есть могут принимать только неотрицательные значения.

§ Вещественные: с запятой (то есть хранятся знак и цифры целой и дробной частей) и с плавающей запятой (то есть число приводится к виду m*be, где m -- мантисса, b -- основание показательной функции, e -- показатель степени (порядок) (в англоязычной литературе экспонента), причём в нормальной форме 0<=m<b, а в нормализованной форме 1<=m<b, e -- целое число и хранятся знак и числа m и e).

§ Числа произвольной точности, обращение с которыми происходит посредством длинной арифметики. Примером языка с встроенной поддержкой таких типов является UBASIC, часто применяемый среди криптографов.

o Символьный тип. Хранит один символ. Могут использоваться различные кодировки.

o Логический тип. Имеет два значения: истина и ложь. Могут применяться логические операции. Используется в операторах ветвления и циклах. В некоторых языках является подтипом числового типа, при этом ложь=0, истина=1.

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

· Составные (сложные).

o Массив. Является индексированным набором элементов одного типа. Одномерный массив -- вектор, двумерный массив -- матрица.

§ Строковый тип. Хранит строку символов. Аналогом сложения в строковой алгебре является конкатенация (прибавление одной строки в конец другой строки). В языках, близких к бинарному представлению данных, чаще рассматривается как массив символов, в языках более высокой абстракции зачастую выделяется в качестве простого.

o Запись (структура). Набор различных элементов (полей записи), хранимый как единое целое. Возможен доступ к отдельным полям записи. Например, struct в C или record в Pascal.

o Файловый тип. Хранит только однотипные значения, доступ к которым осуществляется только последовательно (файл с произвольным доступом, включённый в некоторые системы программирования, фактически является неявным массивом).

o Класс.

· Другие типы данных. Если описанные выше типы данных представляли какие-либо объекты реального мира, то рассматриваемые здесь типы данных представляют объекты компьютерного мира, то есть являются исключительно компьютерными терминами.

o Указатель. Хранит адрес в памяти компьютера, указывающий на какую-либо информацию, как правило -- указатель на переменную.

o Ссылка.

Все эти типы можно отобразить схемой:

Рассмотрим некоторые из них более подробно

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

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

Type

Colors = (red, white, blue);

Соответствие между значениями перечисленного типа и порядковыми номерами этих значений устанавливается очередностью перечисления: первое значение в списке получает номер 0, второе - 1 и т.д. Максимальная мощность перечисленного типа составляет 65536.

К данным перечисленного типа применимы операции отношения.

Целочисленные типы - обозначают множества целых чисел в различных диапазонах. Имеется пять целочисленных типов, различающихся диапазоном допустимых значений и размером занимаемой оперативной памяти. Целочисленные типы обозначаются идентификаторами: Byte, ShortInt, Word, Integer, LongInt; их характеристики приведены в следующей таблице.

Тип

Диапазон

Размер в байтах

Byte

0 ... 255

1

ShortInt

-128 ... 127

1

Word

0 ... 65535

2

Integer

-32768 ... 32767

2

LongInt

-2147483648 ... 2147483647

4

Значения целых типов записываются в программе привычным способом:

123 4 -3 +345 -699

Наличие десятичной точки в записи целого числа недопустимо. Будет ошибкой записать целое число следующим образом:

123.0

Кроме прывычной десятичной формы записи допускается запись целых чисел в шестнадцатиричном формате, используя префикс $, например:

$01AF $FF $1A $F0A1B

Регистр букв A,B, ..., F значения не имеет.

Допустимые операции:

- присваивание;

- все арифметические: +, - ,*, /, div, mod (при обычном делении [/] результат вещественный!);

- сравнение <, >, >=, <=, <>, =.

Логический тип (Boolean) - состоит всего из двух значений: False (ложно) и True (истинно). Слова False и True определены в языке и являются, по сути, логическими константами. Регистр букв в их написании несущественен: FALSE = false. Значения этого типа являются результатом вычислений условных и логических выражений и участвуют во всевозможных условных операторах языка.

Допустимые операции:

- присваивание;

- сравнение: <, >, >=, <=, <>, =;

- логические операции: NOT, OR, AND, XOR

Символьный тип (Char) - это тип данных, состоящих из одного символа (знака, буквы, кода). Значением типа Char может быть любой символ из набора ASCII (7-битная кодировка для представления десятичных цифр, латинского и национального алфавитов, знаков препинания и управляющих символов). Если символ имеет графическое представление, то в программе он записывается заключенным в одиночные кавычки (апострофы), например:

'ж' 's' '.' '*' ' '-(пробел)

Для представления самого апострофа его изображение удваивается: ''''. Если же символ не имеет графического представления, например, символ табуляции или символ возрата каретки, то можно воспользоваться эквивалентной формой записи символьного значения, состоящего из префикса # и ASCII-кода символа:

#9 #32 #13

Допустимые операции:

- присваивание;

- сравнение: <, >, >=, <=, <>, =.

Большим считается тот символ, который имеет больший ASCII-номер.

Строковый тип (String, String[n]) - этот тип данных определяет последовательности символов - строки. Параметр n определяет максимальное количество символов в строке. Если он не задан, подразумевается n=255. Значение типа "строка" в программе запиывается как последовательность символов, заключенных в одиночные кавычки (апострофы), например

'Это текстовая строка' 'This is a string''1234' - это тоже строка, не число'' - пустая строка

Допустимые операции:

- присваивание;

- сложение (конкатенация, слияние);

например, S := 'Зима'+' '+'пришла!'

;- сравнение: <, >, >=, <=, <>, =.

Строки считаются равными, если имеют одинаковую длину и посимвольно эквивалентны.

Вещественные типы - обозначают множества вещественных чисел в различных диапазонах. Имеется пять вещественных типов, различающихся диапазоном допустимых значений и размером занимаемой оперативной памяти. Вещественные типы обозначаются идентификаторами: Real, Single, Double, Extended, Comp; их характеристики приведены в следующей таблице.

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

Тип

Диапазон

Размер в байтах

Real

2.9·10-39 ... 1.7·1038

6

Single

1.5·10-45 ... 3.4·1038

4

Double

5.0·10-324 ... 1.7·10308

8

Extended

3.4·10-4932 ... 1.1·10-4932

10

Comp

-2·1063 ... +2·1063-1

8

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

Значения вещественных типов могут записываться в программе несколькими способами:

1.456

0.000134

-120.0

65432

+345

0

-45

127E+12

-1.5E-5

-1.6E+12

5E4

0.002E-6

Будет ошибкой записать вещественное число следующим образом:

.5 (правильно 0.5)12. (правильно 12.0 или 12)

Вещественное число в форме с плавающей точкой (экспоненциальная форма) записывается как пара

<мантисса> Е <порядок>

Такое обозначение понимается как "мантисса, умноженная на десять в степени, равном порядку". Например,

-1.6E+12 сответствует -1.6·1012

Допустимые операции: - присваивание;

- все арифметические: +,

- ,*, / ;- сравнение: <, >, >=, <=, <>, =.

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

Диапазон или (ограниченный тип) не является предопределенным типом языка (таким как, например, Integer или Char) и поэтому ему не соответствует никакой идентификатор. Этот тип является вводимм пользователем. Используя его мы можем определить новый тип, который будет содержать значения только из ограниченного поддиапазона некоего базового типа. Базовым типом может быть только целочисленный тип, тип Char (символьный) и любой из введенных программистом перечислимых типов.

Для введения нового типа - диапазона - нужно в блоке описания типов TYPE указать имя вводимого типа и границы диапазона через специальный символ диапазона ".." (две точки подряд):

TYPE Century = 1..21; { поддиапазон цилочисленного типа } CapsLetters = 'А'..'Я'; { поддиапазон из типа Char }

4. Cтруктура данных

Cтруктура данных -- программная единица, позволяющая хранить и обрабатывать множество однотипных и/или логически связанных данных в вычислительной технике. Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих её интерфейс. Структура данных часто является реализацией какого-либо абстрактного типа данных.

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

Хорошо спроектированное хранилище данных оптимизирует использование ресурсов (таких как время выполнения операций, используемый объём оперативной памяти, число обращений к дисковым накопителям), требуемых для выполнения наиболее критичных операций.

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

Различные виды структур данных подходят для различных приложений; некоторые из них имеют узкую специализацию для определённых задач. Например, B-деревья обычно подходят для создания баз данных, в то время как хеш-таблицы используются повсеместно для создания различного рода словарей, например, для отображения доменных имён в интернет-адреса компьютеров.

При разработке программного обеспечения сложность реализации и качество работы программ существенно зависит от правильного выбора структур данных. Это понимание дало начало формальным методам разработки и языкам программирования, в которых именно структуры данных, а не алгоритмы, ставятся во главу архитектуры программного средства. Большая часть таких языков обладает определённым типом модульности, позволяющим структурам данных безопасно переиспользоваться в различных приложениях. Объектно-ориентированные языки, такие как Java, C# и C++, являются примерами такого подхода.

Многие классические структуры данных представлены в стандартных библиотеках языков программирования или непосредственно встроены в языки программирования. Например, структура данных хэш-таблица встроена в языки программирования Lua, Perl, Python, Ruby, Tcl и др. Широко используется стандартная библиотека шаблонов STL языка C++.

Фундаментальными строительными блоками для большей части структур данных являются массивы, записи (см. конструкцию struct в языке Си и конструкцию record в языке Паскаль), размеченные объединения (см. конструкцию union в языке Си) и ссылки. Например, структура данных двусвязный список, может быть построена с помощью записей и зануляемых ссылок, а именно, каждая запись будет предоставлять блок данных (узел, node), содержащий ссылки на «левый» и «правый» узлы, а также сами хранимые данные.

5. Список структур данных

· Линейные структуры данных (Linear data structures)

o Список (List)

§ Массив (Array)

§ Битовые поля (Bitmaps)

§ Изображения (Images)

§ Поля высот (Heightfields)

§ Фильтр Блума (Bloom filter)

§ Параллельный массив (Parallel array)

§ Дерево Фенвика

§ Разреженная таблица

§ Связный список (Linked list)

§ Список с пропусками (Skip list)

§ Развёрнутый связный список (Unrolled linked list)

§ XOR-связный список (Xor linked list)

§ V-список (VList)

o Ассоциативный массив (Associative array a.k.a. dictionary or map) -- также известен как словарь или карта

o Хеш-таблица (Hash table)

o Стек (Stack a.k.a. LIFO Last in, first out) -- также известен как ЛИФО

o Очередь (Queue a.k.a. FIFO First in, first out) -- также известен как ФИФО

§ Очередь с приоритетом (Priority queue), одна из реализаций -- Двоичная куча, см. ниже

o Дек (Deque) -- двусвязная очередь

o Буферное окно (Buffer gap)

· Граф (Graph)

o Список рёбер (Adjacency list)

o Представление графа в разорванном виде (Disjoint-set data structure)

o Представление графа в виде стеков (Graph-structured stack)

o Сценограф (Scene graph)

o Деревья

§ 2-3 дерево

§ Дерево отрезков

§ Красно-чёрное дерево

§ BSP дерево

§ M-Way Tree

§ B-дерево

§ Двоичное дерево поиска (Binary search tree)

§ Самобалансирующееся дерево поиска (Self-balancing binary search tree)

§ АВЛ-дерево (AVL tree)

§ Дерево Фибоначчи

§ Красно-чёрное дерево (Red-black tree)

§ Дерево со штрафами (Scapegoat tree)

§ Расширяющееся дерево (Splay tree)

§ Дерево ван Емде Боаса (van Emde Boas tree)

§ Дерево остатков (Radix tree)

§ Интервальное дерево (Interval tree)

§ Куча (Heap)

§ Двоичная куча (Binary heap)

§ Биномиальная куча (Binomial heap)

§ Фибоначчиева куча (Fibonacci heap)

§ Сливаемая куча (Mergable heap)

§ 2-3-куча (2-3 heap)

§ Мягкая куча (Soft heap)

§ Дерево разбора (Parse tree)

§ Квад-дерево (Quadtree) и Окт-дерево (Octree)

§ Суффиксное дерево (Suffix tree)

§ Префиксное дерево (Trie)

§ Патриция (дерево) (Patricia trie)

· Другие структуры данных

o Помеченное объединение (Tagged union)

o Объединение (Union)

o Таблица (Table)

Попытка классификации некоторых из них на основании особенностей:

Структура

Упорядоченная

Уникальная

Данных на вершину

Сумка

нет

нет

1

Множество

нет

да

1

Список

да

нет

1

Ассоциативный массив

нет

да

2

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

6. Статические структуры данных

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

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

Векторы. Вектор (одномерный массив) - структура данных с фиксированным числом элементов одного и того же типа. Каждый элемент вектора имеет уникальный в рамках заданного вектора номер. Обращение к элементу вектора выполняется по имени вектора и номеру требуемого элемента.

Массивы. Логическая структура: массив - такая структура данных, которая характеризуется: фиксированным набором элементов одного и того же типа; каждый элемент имеет уникальный набор значений индексов; количество индексов определяют мерность массива (два индекса - двумерный массив, три индекса - трехмерный массив, один индекс - одномерный массив или вектор); обращение к элементу массива выполняется по имени массива и значениям индексов для данного элемента. Другими словами, массив - это вектор, каждый элемент которого - вектор.

Тип массив определяется конструкцией:

Array [диапазон] of ТипЭлементов;

Диапазон в квадратных скобках указывает значения индексов первого и последнего элемента в стурктуре. Примеры объявления типов и переменных:

TYPE Vector = array[1..10] of Real;VAR V1 : Vector; V2 : array[0..5] of

Byte;

Здесь переменная V1 определяется с использованием описанного выше типа Vector; тип переменной V2 конструируется непостредственно на этапе ее описания.

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

VAR M1 : array[1..3] of array[1..3] of Byte;

Это же самое можно записать гораздо компактнее:

VAR M2 : array[1..3, 1..3] of Byte;

Здесь массивы M1 и M2 имеют совершенно одинаковую структуру - квадратной матрицы размером 3x3.

Доступ к элемента массива осуществляется путем указания его индекса, например:

writeln( V1[1] ); {вывод на экран первого элемента массива V1}readln(

M2[2,3] );{ввод третьего элемента второй строки матрицы М2}

Физическая структура - это размещение элементов массива в памяти ЭВМ. Многомерные массивы хранятся в непрерывной области памяти. Размер слота определяется базовым типом элемента массива. Количество элементов массива и размер слота определяют размер памяти для хранения массива. Принцип распределения элементов массива в памяти определен языком программирования. Так в FORTRAN элементы распределяются по столбцам - так, что быстрее меняется левые индексы, в PASCAL - по строкам - изменение индексов выполняется в направлении справа налево.

Специальные массивы. На практике встречаются массивы, которые в силу определенных причин могут записываться в память не полностью, а частично. Это особенно актуально для массивов настолько больших размеров, что для их хранения в полном объёме памяти может быть недостаточно. К таким массивам относятся симметричные и разреженные массивы.

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

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

1) массивы, в которых местоположения элементов со значениями отличными от фонового, могут быть математически описаны;

2) массивы со случайным расположением элементов.

Множества. Логическая структура: Множество - такая структура, которая представляет собой набор неповторяющихся данных одного и того же типа. Множество может принимать все значения базового типа. Базовый тип не должен превышать 256 возможных значений. Поэтому базовым типом множества могут быть byte, char и производные от них типы.

Физическая структура: Множество в памяти хранится как массив битов, в котором каждый бит указывает является ли элемент принадлежащим объявленному множеству или нет. Т.о. максимальное число элементов множества 256, а данные типа множество могут занимать не более 32-ух байт.

Числовые множества. Стандартный числовой тип, который может быть базовым для формирования множества - тип byte.

Символьные множества. Символьные множества хранятся в памяти также как и числовые множества. Разница лишь в том, что хранятся не числа, а коды ASCII символов.

Множество из элементов перечислимого типа. Множество, базовым типом которого есть перечислимый тип, хранится также, как множество, базовым типом которого является тип byte. Но, в памяти занимает место, которое зависит от количества элементов в перечислимом типе.

Множество от интервального типа. Множество, базовым типом которого есть интервальный тип, хранится также, как множество, базовым типом которого является тип byte. В памяти занимает место, которое зависит от количества элементов, входящих в объявленный интервал.

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

Таблицы. Таблица - сложная интегрированная структура. С физической точки зрения таблица представляет собой вектор, элементами которого являются записи. Логической особенностью таблиц является то, что доступ к элементам таблицы производится не по номеру (индексу), а по ключу - по значению одного из свойств объекта, описываемого записью-элементом таблицы. Ключ - это свойство, идентифицирующее данную запись во множестве однотипных записей. Ключ может включаться в состав записи и быть одним из её полей, но может и не включаться в запись, а вычисляться по положению записи. Таблица может иметь один или несколько ключей. Основной операцией при работе с таблицами является операция доступа к записи по ключу. Она реализуется процедурой поиска. Поскольку поиск может быть значительно более эффективным в таблицах, упорядоченных по значениям ключей, довольно часто над таблицами необходимо выполнять операции сортировки.

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

7. Полустатические структуры данных

Полустатические структуры данных характеризуются следующими признаками: они имеют переменную длину и простые процедуры её изменения; изменение длины структуры происходит в определенных пределах, не превышая какого-то максимального (предельного) значения.

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

Стеки. Стек - такой последовательный список с переменной длиной, включение и исключение элементов из которого выполняются только с одной стороны списка, называемого вершиной стека. Применяются и другие названия стека - магазин и очередь, функционирующая по принципу LIFO (Last - In - First- Out - "последним пришёл - первым вышел").

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

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

а) пустого;

б, в, г) после последовательного включения в него элементов с именами 'A', 'B', 'C';

д, е) после последовательного удаления из стека элементов 'C' и 'B';

ж) после включения в стек элемента 'D'.

Рис. 1.3 - Включение и исключение элементов из стека

Как видно из рис. 1.3., стек можно представить, например, в виде стопки книг (элементов), лежащей на столе. Присвоим каждой книге свое название, например A,B,C,D... Тогда в момент времени, когда на столе книг нет, про стек аналогично можно сказать, что он пуст, т.е. не содержит ни одного элемента. Если же мы начнем последовательно класть книги одну на другую, то получим стопку книг (допустим, из n книг), или получим стек, в котором содержится n элементов, причем вершиной его будет являться элемент n+1. Удаление элементов из стека осуществляется аналогичным образом т. е. удаляется последовательно по одному элементу, начиная с вершины, или по одной книге из стопки.

Очереди FIFO. Очередью FIFO (First - In - First- Out - "первым пришел - первым вышел") называется такой последовательный список с переменной длиной, в котором включение элементов выполняется только с одной стороны списка (эту сторону часто называют концом или хвостом очереди), а исключение - с другой стороны (называемой началом или головой очереди). Основные операции над очередью - те же, что и над стеком - включение, исключение, определение размера, очистка, неразрушающее чтение.


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

  • Основные сведения о языках программирования и их состав. Программа для компьютера. Использование компилятора и операторы. Языки программирования высокого уровня. Концепции объектно-ориентированного программирования. Языки искусственного интеллекта.

    презентация [6,3 M], добавлен 14.08.2013

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

    реферат [35,2 K], добавлен 24.07.2010

  • Классификация языков программирования. Использование циклических конструкций и выполнение итерационных процессов. Алгоритмические структуры циклов языков C, C++, Java, C#. Особенности современных языков программирования высокого уровня и их применение.

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

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

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

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

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

  • Машинные коды и ассемблер. Первые языки программирования высокого уровня. Язык программирования FORTRAN. Достоинства и недостатки ALGOL. Научные и бухгалтерские программы. Основные принципы, которые соблюдались при создании языка программирования Basic.

    курсовая работа [407,4 K], добавлен 21.06.2014

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

    контрольная работа [19,6 K], добавлен 11.12.2011

  • Этапы развития, особенности и возможности языка программирования Java; происхождение названия. Приложения Sun Microsystems: идеи, примитивные типы. Python - высокоуровневый язык программирования общего назначения: структуры данных, синтаксис и семантика.

    реферат [79,0 K], добавлен 23.06.2012

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

    презентация [1,2 M], добавлен 19.02.2014

  • Эволюция языков программирования от низкого уровня до современности. Языки программирования второго поколения - ассемблер. Императивные, функциональные, логические и объектно-ориентированные языки. Машинная независимость. Парадигмы программирования.

    презентация [353,5 K], добавлен 14.10.2013

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