Организация данных в программировании

Данные в программировании

Да́нные (калька от лат. data ) — это представление фактов и идей в формализованном виде, пригодном для передачи и обработки в некотором информационном процессе.

Содержание

В обществе

В информатике

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

Контроль за доступом к данным в современных компьютерах осуществляется аппаратно.

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

Типы данных

Традиционно выделяют два типа данных — двоичные (бинарные) и текстовые.

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

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

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

Данные в ООП

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

Данные в языках разметки

Имеют различное отображение в зависимости от выбранного способа представления.

Данные в XML

В теории множеств

В отличие от операций над элементами множества, представляют собой множество (название и элементы множества)

В лингвистике

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

Метаданные

Множество данных может иметь надмножество, называемое метаданными.

Примечания

См. также

Ссылки

Wikimedia Foundation . 2010 .

Смотреть что такое «Данные в программировании» в других словарях:

Данные (вычислительная техника) — В вычислительной технике данные обычно отличают от программ. Программа является набором инструкций, которые детализируют вычисление или задачу, которая производится компьютером. Данными же традиционно называется всё, что не выступает в роли… … Википедия

Данные — (калька от англ. data[источник не указан 101 день]) представление фактов и идей в формализованном виде, пригодном для передачи и обработки в некотором информационном процессе. Изначально данные величины, то… … Википедия

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

Парадигма — (Paradigm) Определение парадигмы, история возникновения парадигмы Информация об определении парадигмы, история возникновения парадигмы Содержание Содержание История возникновения Частные случаи (лингвистика) Управленческая парадигма Парадигма… … Энциклопедия инвестора

Функциональное программирование — Парадигмы программирования Агентно ориентированная Компонентно ориентированная Конкатенативная Декларативная (контрастирует с Императивной) Ограничениями Функциональная Потоком данных Таблично ориентированная (электронные таблицы) Реактивная … Википедия

Model-View-Controller — Шаблон проектирования Model View Controller Кон … Википедия

Антипаттерн — Возможно, эта статья содержит оригинальное исследование. Добавьте ссылки на источники, в противном случае она может быть выставлена на удаление. Дополнительные сведения могут быть на странице обсуждения. (25 мая 2011) … Википедия

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

Битовые операции — Не следует путать с булевой функцией. Битовая операция в программировании некоторые операции над цепочками битов. В программировании, как правило, рассматриваются лишь некоторые виды этих операций: логические побитовые операции и… … Википедия

Рекурсия — У этого термина существуют и другие значения, см. Рекурсия (значения). Визуальная форма рекурсии (эффект Дросте) … Википедия

Организация данных в программировании

1. Какие бывают данные и их структуры?

2. Как задаются структуры данных?

… Лучше, чтобы в 100 функциях

использовалась одна структура данных,

чем в 10 функциях — 10 структур

А. Дж. Перлис

Всякая программа, предназначенная для реализации на ЭВМ, представляет собой формальное описание алгоритма решения той или иной задачи. Действия, выполняемые программой в соответствии с этим алгоритмом, направлены на преобразование некоторых объектов, определяющих текущее состояние процесса решения задачи. Такие внутренние объекты программы мы и называем данными. Основная цель любой программы состоит в обработке данных. Данные различных типов хранятся в памяти компьютера и обрабатываются по-разному. Согласно концепции типов данных, каждый тип данных однозначно определяет: множество значений, которые может принимать переменная заданного типа; операции и функции, которые можно применять к этой переменной; внутреннее представление переменной в памяти компьютера. Напомним, что память выделяется не для типа данных, а для размещения переменных или констант определенных типов.

Будем исходить из того представления, что структура данных – программная единица, позволяющая хранить и обрабатывать множество однотипных или логически связанных данных в вычислительной технике (https://ru.wikipedia.org/wiki/Структура_данных). Она формируется с помощью типов данных, ссылок и операций над ними в выбранном языке программирования.

3.1 Классификация структур данных

В языке Си различают следующие категории типов данных : базовые (или простые, основные, стандартные) типы данных и производные (или сложные, составные) типы данных. Основные типы данных представлены на рис. 3.1.

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

Рисунок 3.1 — Основные типы данных, применяемые в программировании

Указание типа данных четко определяет:

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

В си несколько основных базовых типов. Разделим их на две группы — целые и числа с плавающей точкой.

• char — размер 1 байт. Всегда! Это нужно запомнить.
• short — размер 2 байта
• int — размер 4 байта
• long — размер 4 байта
• long long — размер 8 байт.

Здесь следует сделать замечание. Размер переменных в си не определён явно, как размер в байтах. В стандарте только указано, что

Список.

Двунаправленный список.

Рисунок 3.4 – Структуры данных «Однонаправленный и двунаправленный список»

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

Рисунок 3.5 – Структура данных «Связанный список»

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

struct spis *next; >; // Указатель на структуру

Здесь при описании указателя используем ещё не описанный объект struct spis *next , который будет служить ссылкой на последующий элемент списка. Самая последняя структура в списке никуда не указывает, т.е. поле next должно иметь значение NULL. Адрес начала (головы) списка хранится в переменной типа указатель *head. На текущую структуру будет указывать *p.

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

3.2.3 Стек

Стек – это динамическая линейная структура данных, представляющая собой список элементов, организованных по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»).

Часто сравнивают стек со стопкой тарелок. Чтобы достать следующую тарелку, необходимо снять предыдущие. Вершина стека – это вершина стопки тарелок.

Пример задания стека :

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

Рисунок 3.6 – Структура данных «стек»

Рисунок 3.7 — Последовательное выполнение операций push 3, push 5, push 7, pop, pop, pop

3.2.4 Очередь

О́чередь — структура данных с дисциплиной доступа к элементам «первый пришёл — первый вышел» (FIFO, First In — First Out). Добавление элемента (принято обозначать словом enqueue — поставить в очередь) возможно лишь в конец очереди, выборка — только из начала очереди (что принято называть словом dequeue — убрать из очереди), при этом выбранный элемент из очереди удаляется.

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

Рисунок 3.8 – Структура данных «Очередь»

Очереди очень часто встречаются в реальной жизни, например, около банков или ресторанов быстрого обслуживания. Чтобы представить себе работу очереди, давайте введем две функции: qstore() и qretrieve() (от «store»— «сохранять», «retrieve» — «получать»). Функция qstore() помещает элемент в конец очереди, а функция qretrieve() удаляет элемент из начала очереди и возвращает его значение.

3.2.5 Дек

Дек – структура данных одновременно работает по двум способам организации данных: FIFO и LIFO. Поэтому ее допустимо отнести к отдельной программной единице, полученной в результате суммирования двух предыдущих видов структур данных.

Рисунок 3.9 – Структура данных «дек»

3.2.6 Хэш-таблица

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

Рисунок 3.10 – Структура данных «хэш – таблица»

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

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

Рисунок 3.11 — Телефонная книга на примере хэш-таблицы

3.2.7 Иерархические структуры данных

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

Деревья

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

Деревья – динамическая иерархическая структура данных, представленная единственным корневым узлом и его потомками. Максимальное количество потомков каждого узла и определяет размерность дерева. Отдельно выделяют двоичные или бинарные деревья, поскольку они используются в алгоритмах сортировки и поиска: каждый узел двоичного дерева поиска соответствует элементу из некоторого отсортированного набора, все его “левые” потомки – меньшим элементам, а все его “правые” потомки – большим элементам. Каждый узел в дереве однозначно идентифицируется последовательностью неповторяющихся узлов от корня и до него – путем. Длина пути и является уровнем узла в иерархии дерева. Для двоичных или бинарных деревьев выделяют следующие виды рекурсивного обхода всех его элементов (в фигурных скобках указан порядок посещения элементов каждого узла, начиная с корня): прямой или префиксный <узел, левое поддерево, правое поддерево>; обратный или постфиксный <левое поддерево, правое поддерево, узел>; симметричный или инфиксный
<левое поддерево, узел, правое поддерево>.

Пример представления дерева:

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

Рисунок 3.12 – Структура данных «дерево»

Иерархический список

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

Рисунок 3.13 – Структура данных «Иерархический список»

Примеры применения структур данных

Пример 3.1. Применения структуры массив. Дан одномерный массив. Необходимо, заполнить одномерный массив, сделать вывод одномерного массива. Определить среднее арифметическое значение элементов массива.

Пример 3.2. Пример создания и просмотра односвязного списка (http://c.guti.ru/dstruktury.asp ).

Пример 3.3. Пример реализации структуры данных «стек».

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

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

В 1976 году швейцарец Никлаус Вирт опубликовал книгу «Алгоритмы и структуры данных». Несмотря на то, что после публикации этой книги уже прошло более 40 лет, работа Вирта «Алгоритмы и структуры данных» до сих чрезвычайно актуальна. Это обусловлено тем, что любой разработчик ПО должен прекрасно теоретические основы структур данных. Косвенно это подтверждается тем, что практически на любом ИТ-собеседовании возникает вопрос на данную тематику.

Учитывая этот факт, изучение теоретических основ данной темы имеет важнейшее значение для тех, кто планирует найти новую более престижную работу.

Структура базы данных представляет собой контейнер для хранения информация в заданной форме. Такая «компоновка» позволяет этой информации быть эффективной при выполнении одних операций и абсолютно бесполезной для решения других заданий. Главной задачей разработчика считается выбор наилучшего варианта структуры данных для решения определенной задачи.

Назначение структур данных

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

Самые востребованные структуры данных

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

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

Массивы

Массивы считаются самой простой и востребованной структурой. Ниже приведен пример одномерного массива, состоящего из четырех элементов (1, 2, 3, 4).

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

Выше указан одномерный массив, но также существует его многомерный аналог. Простыми словами его можно назвать массивы массивов.

Разработчики имеют возможность осуществлять с массивами самые разные операции, но все-таки чаще всего эта структура данных предусматривает выполнение:

• вставки;
• извлечения нужного элемента по индексу;
• удаления;
• определения количества элементов в массиве.

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

• Как найти минимальный элемент?
• Как объединить 2 отсортированных массива?
• Как поменять местами положительные и отрицательные значения?

Стеки

В любой современной программе есть опция «Отменить». Она считается одной из самых востребованных среди пользователей. Но далеко не все пользователи понимают, как работает эта опция.

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

Для понимания работы стека стоит привести самый тривиальный пример. Предположим, на столе одна на одной лежит куча тетрадок. Чтобы взять тетрадку из середины, необходимо удалить тетрадки, которые лежат сверху. Таким образом работаем принцип «последним пришел – первым ушел. В среде разработчиков этот принцип называется LIFO (Last In First Out).

Ниже приведен пример стека.

Элемент со значением «3» находится в самом верху. Следовательно, он будет удален первым.

Если говорить об операциях со стеками, то прежде всего нужно отметить:

• вставку элемента в топ;
• извлечение и последующее удаление верхнего элемента;
• проверку на пустоту стека;
• извлечение первого элемента.

На ИТ-собеседованиях программисту стоит быть готовым к таким вопросам:

• Как отсортировать стек?
• Как проверить соответствие скобок в выражении?

Очереди

Очередь – линейная структура данных, хранящая элементы в определенной последовательности. В очереди используется принцип «первым пришел – первым ушел» (FIFO).

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

Ниже приведен пример очереди, состоящей из 4 элементов.

В этом примере элемент со значением «1» находится в начале очереди. Следовательно, именно этот элемент первым выйдет из очереди.

К основным действиям с queue стоит отнести:

• вставку в конец;
• удаление первого элемента;
• проверку на пустоту очереди;
• извлечение первого элемента.

На собеседовании разработчика могут попросить:

• создать стек посредством очереди;
• сгенерировать двоичные числа посредством очереди.

Связный список

Создание структуры базы данных также предусматривает использование связных списков. Эта структура очень схожа с массивом. Но все-таки она отличается:

• организацией;
• принципом распределения памяти;
• принцип выполнения операций Insert и Delete.

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

Главной задачей связных списков является систем хранения файлов. Ниже приведен пример этой структуры:

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

• вставка в начало или конец;
• удаление первого или выбранного элемента;
• поиск определенного элемента;
• проверка на пустоту списка.

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

• удалить дубликаты
• развернуть список
• получить заданный узел с конца списка.

Графы

Графы – это набор узлов, соединенных в виде сети. Пара узлов называется ребром, указывающим на то, что вершина одного узла соединена с вершиной другого.

Графы делятся на два типа – ориентированные и неориентированные. В программировании эта структура данных представлена в виде матрицы или списка смежности. Обход графов может осуществляться как в ширину, так и в длину.

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

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

Дерево

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

Именно эта структура используется для создания интеллектуальных машин.

Ниже приведен пример простого дерева:

Стоит добавить, что в программирование существует несколько видов деревьев:

• N-арное;
• сбалансированное;
• бинарное;
• AVL;
• красно-черное;
• 2-3;
• бинарное дерево поиска.

К наиболее часто задаваемым вопросам по деревьям стоит отнести:

• определение высоты дерева;
• поиск максимального значения;
• поиск предков определенного узла.

Префиксное дерево

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

Ниже приведен пример префиксного дерева.

Объекты поиска указываются сверху вниз. Зеленым цветом выделены элементы, которые показывают конец каждого объекта поиска.

На ИТ-собеседованиях разработчику могут задать такие задания, связанные с префиксными деревьями:

• создание словаря Т9;
• определение общего количества элементов;
• сортировка массива.

Хэш-таблица

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

Производительность хэш-таблиц зависит от следующих нюансов:

• хеширования;
• размера;
• способа обработки коллекций.

Ниже приведен пример, в котором хэш отображается в массиве:

На ИТ-собеседовании разработчику могут быть заданы такие задания:

• поиск симметричных пар;
• определение того является ли определенный массив подмножеством другого;
• проверка массивов на пересекаемость.

Резюмируя, стоит сказать, что вышеописанные 8 структур данных должен знать любой разработчик, желающий успешно пройти IT-собеседование.

Размещено на реф.рф
Никакая дополнительная информация о членах семьи не изменит общую логическую структуру семьи:

семья =отец, мать, ребенок .

отец = имя, возраст, профессия

мать = имя, возраст, девичья фамилия,

ребенок = имя, возраст, пол

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

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

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

Организация данных — понятие и виды. Классификация и особенности категории «Организация данных» 2017, 2018.

Читайте также

Программное обеспечение ПК Основные характеристики современных ПК Устройства, характеристики и программное обеспечение ПК ПК состоит из системного блока и внешних устройств. Системный блоквключает микропроцессор, выполняющий. [читать подробнее].

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

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

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

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

Сравнение методов организации данных В табл. 3 собраны все оценки методов организации дан­ных, что позволяет сделать ряд выводов. Таблица 3. Сравнение методов организации данных Критерии оценки Методы организации данных Лучший метод . [читать подробнее].

Сравнение методов организации данных В табл. 3 собраны все оценки методов организации дан­ных, что позволяет сделать ряд выводов. Таблица 3. Сравнение методов организации данных Критерии оценки Методы организации данных Лучший метод . [читать подробнее].

Древовидной организацией данных (деревом) называется множество записей, расположенных по уровням следующим образом: — на 1-м уровне расположена только одна запись (корень дерева), — к любой записи i-го уровня ведет адрес связи только от одной записи уровня i-1. Количество. [читать подробнее].

Технология программирования Последовательное распределение С вычислительной точки зрения простейшим представлением [11] конечной последовательности является список ее членов, расположенных по порядку в последовательных ячейках памяти. ¬ d ® . [читать подробнее].

Рис.15 Рис.14 Семантические сети — модели данных, созданы исполнителями, работавшими над проблемами искусственного интеллекта. Базовые структуры в этих моделях могут быть представлены графом, множество дуг которого образуют сеть, предназначенную для. [читать подробнее].

Организация данных в ЭВМ и основы программирования

Описание файла

Документ из архива «Организация данных в ЭВМ и основы программирования», который расположен в категории «лекции и семинары». Всё это находится в предмете «информатика» из первого семестра, которые можно найти в файловом архиве РТУ МИРЭА. Не смотря на прямую связь этого архива с РТУ МИРЭА, его также можно найти и в других разделах. Архив можно найти в разделе «лекции и семинары», в предмете «информатика» в общих файлах.

Текст из документа «Организация данных в ЭВМ и основы программирования»

Министерство образования Российской Федерации

Московская Государственная академия приборостроения и информатики

Конспект лекций по информатике

для специальностей 2102, 0718

Автор доц., к.т.н. Каширская Е.Н.

ОРГАНИЗАЦИЯ ДАННЫХ В ЭВМ И ОСНОВЫ ПРОГРАММИРОВАНИЯ

1. ОСНОВНЫЕ ПОНЯТИЯ ЯЗЫКА ПРОГРАММИРОВАНИЯ ПАСКАЛЬ

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

1.1. Структурное программирование

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

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

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

записи с вариантами,

указатели, а также развитые средства построения из них новых типов данных.

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

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

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

Основная цель структурного программирования — создать программу с минимальными взаимосвязями между ее модулями. В ИДЕАЛЕ каждый модуль должен иметь один вход и один выход.

Опыт использования методов структурного программирования позволяет сделать следующие выводы:

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

2) использование модулей небольших размеров позволяет упростить и ускорить процессы их отладки;

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

4) структурное программирование является хорошей базой автоматизации разработки модульных программ.

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

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

1.2. Основные символы языка

Алфавит языка. Основными символами языка являются:

— буквы A,B,C, . Z — заглавные,

— буквы a,b,c, . z — строчные

— знаки + — * / = ( ) _ “пробел”,

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

Максимальная длина программной строки ограничена 126 символами.

Следующие слова зарезервированы и, следовательно, не могут быть использованы иначе как служебные (они зарезервированы):

AND — логическое умножение

CASE — в случае (выбор)

CONSTRUCTOR — создать объект

DIV — целочисленное деление

DO — делать (в цикле)

DOWNTO — шаг в уменьшении

EXTERNAL — внешняя процедура

FILE — описание файла

FORWARD — опережающее описание

IMPLEMENTATION — правило выполнения модулей

INLINE — включение в строку

INTERFACE — связь модулей

MOD — остаток от целочисленного деления

OBJECT — переменная типа “типа”

OR — логическое сложение

UNIT — программный модуль

UNTIL — до тех пор, пока

VIRTUAL — внутренняя переменная

1.3. Элементы языка

Идентификатор — начинается с буквы или “_” (символа подчеркивания) и состоит из букв, цифр и “_”. Длина идентификатора ограничена длинной программной строки, т.е. 126 символами, но при этом компилятор различает только первые 63 символа. Большие и маленькие буквы не различаются.

Пример. MYVAR три различных написания

myvar одной и той же

Числа в Паскаль — программе — это константы целого или действительного типа. Целые константы представляются в десятичной или шестнадцатеричной системе счисления. Признаком шестнадцатеричной системы является предшествующий символ $. Целые константы должны принадлежать диапазону от -2147483648 до 2147483647.

65535 целого типа

Строки — последовательность символов, заключенных в апострофы (в одиночные кавычки). Максимальная длина строковой константы — 255 символов.

Пример. ‘TURBO PASCAL 6.0’

Комментарий в Паскале — любой текст, ограниченный (*. *) или <. >. Вложенность компонентов допускается лишь двумя способами:

1.4. Интегрированная среда TURBO PASCAL

Система программирования TURBO PASCAL представляет собой интегрированную среду, включающую в себя экранный редактор, компилятор, редактор связей (Linker), отладчик.

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

1.5. Структура программы в TURBO PASCAL

Program — заголовок программы

Label — описание меток

Const — описание констант

Type — описание типов

Var — описание переменных

Procedure — описание процедур

Function – описание функций

Заголовок программы выполняет чисто декоративные функции и служит для удовлетворения эстетических запросов программиста. Заголовок программы компилятором игнорируется.

Раздел “описание” состоит из пяти секций.

Описание меток. Переход по метке выполняется оператором GOTO. Все метки должны быть описаны. Метки могут быть целочисленными от 0 до 9999 или идентификаторами. Каждая описанная метка должна появиться в программе.

Пример. Label X1, Finish, 4444;

Описание констант. Общий вид:

Const идентификатор = выражение (или число).

Пример.Const Limit = 256

Error = ‘Ошибка’; — символьная константа;

Err1 = Error + ‘Повторите ввод’;

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

ABS — абсолютная величина

CHR — символическая переменная типа порядковый номер

HI — старший байт (хай)

LENGTH — длина строковой переменной

LO — младший байт

ORD – порядковый номер

PRED — предыдущее значение

PTR — указатель (пойнтер)

SIZEOF — размер переменной

SWAP — перестановка байтов

TRUNC – отбрасывание дробной части числа

BOOLEAN — логическая переменная

LONGINT — длинное целое

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

В данном примере сначала определяется идентификатор константы L, который затем используется при определении константы Н.

В качестве констант в языке Паскаль разрешается использовать целые и вещественные значения, а также строки.

1.6. Определение типов

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

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

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

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