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

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

Термин «структура данных» может  иметь несколько близких, но тем не менее различных значений:

• Абстрактный тип данных;
• Реализация какого-либо абстрактного типа данных;
• Экземпляр типа данных, например, конкретный список;
• В контексте функционального программирования — уникальная единица (англ. unique identity), сохранящаяся при изменениях. О ней неформально говорят как об одной структуре данных, несмотря на возможное наличие различных версий.

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

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

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

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

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

Сравнение структур данных в функциональном и императивном программировани

Проектировать структуры данных для  функциональных языков более сложно, чем для императивных, как минимум  по двум причинам^[1]:

1. Почти все структуры данных интенсивно используют присваивание, которое в чисто функциональном стиле не используется;
2. Функциональные структуры данных являются более гибкими, и поэтому там, где в императивном программировании старая версия теряется, просто заменяясь новой, в функциональном она автоматически продолжает существовать. Другими словами, в императивном программировании (если не принять особых мер, могущих серьёзно усложнить программу) структуры данных являются эфемерными (англ. ephemeral), а в функциональных программах они как правило постоянные (англ. Persistent)

 

 

ВВЕДЕНИЕ

 

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

Представление и преобразование информации в ЭВМ описано в  первой части.

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

 
 

1. ПРЕДСТАВЛЕНИЕ  И ПРЕОБРАЗОВАНИЕ ИНФОРМАЦИИ  В ЭВМ

 

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

Существуют позиционные  и непозиционные системы счисления.

В непозиционных системах вес цифры (т.е. тот вклад, который  она вносит в значение числа) не зависит  от ее позиции в записи числа. Так, в римской системе счисления  в числе ХХХII (тридцать два) вес цифры Х в любой позиции равен просто десяти.

В позиционных системах счисления  вес каждой цифры изменяется в  зависимости от ее положения (позиции) в последовательности цифр, изображающих число. Например, в числе 757,7 первая семерка означает 7 сотен, вторая - 7 единиц, а третья - 7 десятых долей  единицы.

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

При переводе чисел из десятичной системы счисления в систему  с основанием P > 1 обычно используют следующий алгоритм:

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

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

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

Несмотря на то, что десятичная СС имеет широкое распространение, ЭВМ строятся на двоичных (цифровых) элементах, так как реализовать  элементы с десятью четко различными состояниями сложно.

В двоичной системе счисления  используются только две цифры 0 и 1. И значит, имеется только два однозначных  числа.

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

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

2.   Представление информации посредством только двух состояний надёжно и помехоустойчиво;

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

4.   Двоичная арифметика намного проще десятичной.

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

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

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

Задача перевода из одной  системы счисления в другую часто  встречается при программировании и особенно часто - при программировании на языке Ассемблера.

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

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

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

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

В ЭВМ применяются две  формы представления чисел: с  фиксированной (ффт) и плавающей (фпт) точкой. В случае ффт положение точки фиксируется в определенном месте относительно разрядов числа, как правило, перед старшим или после младшего; в первом случае представляются числа N<1, во втором - только целые числа.

По традиции нумерация  бинарных разрядов (битов) в ЭВМ общего назначения ведется слева направо. Знаковый разряд является, как правило, крайним слева. В случае использования  прямого кода диапазон представления  чисел составляет 1N 2 -1; дополнительный код позволяет использовать числа  в диапазоне -2 N2 -1, что при n=32 примерно соответствует диапазону десятичных целых чисел 1N 10. Для других рассмотренных  кодов установление диапазонов представимости чисел оставляем читателю. В настоящее время форма фиксации точки перед старшим разрядом используется для представления целых чисел с фиксацией точки после младшего разряда. Если точка фиксируется справа от младшего разряда, то регистром целых чисел со знаком можно представлять нуль, положительные и отрицательные целые бинарные числа. В зависимости от модели ЭВМ используются два формата ффт представления целых чисел: со знаком и без; в последнем случае все разряды регистра служат для представления модуля числа. Форматы чисел с ффт используются в качестве основных только в ограниченных по возможностям ЭВМ, ориентированных на работу в системах передачи данных, управлении технологическими процессами и работы в режиме реального времени. Остальные типы ЭВМ используют эти форматы, главным образом, для работы с целыми числами.

В ЭВМ общего (универсального) назначения основной является форма  представления чисел с плавающей  точкой (фпт), не требующая масштабирования данных. Но и в таких ЭВМ часто используется рассмотренная выше ффт, ибо операции с целыми числами в таких форматах выполняются быстрее; сюда же относятся и операции индексной арифметики над кодами адресов (обеспечение адресации). В общем случае представление N-числа в фпт имеет следующий вид: N=AM, где M - мантисса; А - основание характеристики и р - ее порядок. Как правило, величина Ар представляет целую степень двух. Мантисса (М; является дробью со знаком) и порядок (р; целое со знаком) представляются в А-с. с. в соответствующей бинарно-кодированной форме. Знак N-числа совпадает со знаком М-мантиссы; р-порядок определяет положение точки в представлении N-числа.

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

Так как под мантиссу отводится  фиксированное число битов, то для  получения максимальной точности используются нормализованные числа, для которых  выполняется условие А М<1. В некоторых ЭВМ используется другое условие нормализации - 1М<A, т.е. старший бит мантиссы в А-с. с. отличен от нуля. Если в процессе вычислений получается ненормализованное число, оно, как правило, автоматически нормализуется: если d старших битов мантиссы нулевые, то производится ее сдвиг на d битов влево (младшие биты обнуляются) с одновременным уменьшением порядка числа на d единиц (при нулевой мантиссе нормализации не производится). В различных ЭВМ используются фпт при А=2 (m=1,3,4,...); при этом, р-порядок представляется целым числом, а М-мантисса - бинарным числом, состоящим из групп по m битов, изображающих цифры мантиссы в А-с. с. Наиболее распространенными являются основания A{2,8,16}. Использование небинарного А-основания несколько уменьшает точность вычислений, но позволяет увеличивать диапазон представимых чисел и скорость выполнения ряда операций, уменьшая вероятность появления ненормализованных чисел. Диапазон представимых чисел в фпт зависит от А-с. с. и числа битов, отведенных под р-порядок; тогда как точность вычислений определяется числом битов М-мантиссы. С увеличением разрядности мантиссы растет точность вычислений, но уменьшается скорость выполнения арифметических операций. Ввиду различных требований, предъявляемых к точности вычислений, многие ЭВМ используют несколько форматов для представления чисел в фпт (разные разрядности мантиссы). В первую очередь, это относится к сопроцессорам ПК и микро-ЭВМ. Такое архитектурное решение позволяет более гибко организовывать вычислительный ход.