Основные сведения об информационных структурах данных

ГМУ г. Семей.

 

  
 

СРС 

На тему: Основные сведения об информационных структурах данных

 

  

                                                                                          

                                                                        Кафедра: мед физика информатика

                                                     Зав. кафедрой: Буланова Р.К. 

                                                                         Предмет: информатик

                                                                         Выполнил: Хрулёв А.В. 

                Группа: 133

                Специальность: ОМФ

                проверила: Буланова Р.К. 
 
 

Семей 2011.

ПЛАН 

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

Информация и ее представление в памяти

Хранение информации

Системы счисления

Непозиционные системы  счисления

Позиционные системы  счисления

Позиционные системы  счисления

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

Операции над структурами  данных

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

Список литературы 
 
 
 
 
 
 
 
 
 
 
 
 

CТРУКТУРЫ  ДАННЫХ

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

Структуры данных и  алгоритмы служат теми материалами, из которых строятся программы. Более  того, сам компьютер состоит из структур данных и алгоритмов. Встроенные структуры данных представлены теми регистрами и словами памяти, где  хранятся двоичные величины. Заложенные в конструкцию аппаратуры алгоритмы - это воплощенные в электронных  логических цепях жесткие правила, по которым занесенные в память данные интерпретируются как команды, подлежащие исполнению. Поэтому в основе работы всякого компьютера лежит умение оперировать только с одним видом  данных - с отдельными битами, или  двоичными цифрами. Работает же с  этими данными компьютер только в соответствии с неизменным набором  алгоритмов, которые определяются системой команд центрального процессора. Задачи, которые решаются с помощью компьютера, редко выражаются на языке битов. Как правило, данные имеют форму  чисел, литер, текстов, символов и более  сложных структур типа последовательностей, списков и деревьев. Еще разнообразнее  алгоритмы, применяемые для решения  различных задач; фактически алгоритмов не меньше чем вычислительных задач. Для точного описания абстрактных  структур данных и алгоритмов программ используются такие системы формальных обозначений, называемые языками программирования, в которых смысл всякого предложения  определется точно и однозначно. Среди средств, представляемых почти всеми языками программирования, имеется возможность ссылаться на элемент данных, пользуясь присвоенным ему именем, или, иначе, идентификатором. Одни именованные величины являются константами, которые сохраняют постоянное значение в той части программы, где они определены, другие - переменными, которым с помощью оператора в программе может быть присвоено любое новое значение. Но до тех пор, пока программа не начала выполняться, их значение не определено. Имя константы или переменной помогает программисту, но компьютеру оно ни о чем не говорит. Компилятор же, транслирующий текст программы в двоичный код, связывает каждый идентификатор с определенным адресом памяти. Но для того чтобы компилятор смог это выполнить, нужно сообщить о "типе" каждой именованной величины. Человек, решающий какую-нибудь задачу "вручную", обладает интуитивной способностью быстро разобраться в типах данных и тех операциях, которые для каждого типа справедливы. Так, например, нельзя извлечь квадратный корень из слова или написать число с заглавной буквы. Одна из причин, позволяющих легко провести такое распознавание, состоит в том, что слова, числа и другие обозначения выглядят по-разному. Однако для компьютера все типы данных сводятся в конечном счете к последовательности битов, поэтому различие в типах следует делать явным.  Типы данных, принятые в языках программирования, включают натуральные и целые числа, вещественные (действительные) числа (в виде приближенных десятичных дробей), литеры, строки и т.п.  В некоторых языках программирования тип каждой константы или переменной определяется компилятором по записи присваиваемого значения; наличие десятичной точки, например, может служить признаком вещественного числа. В других языках требуется, чтобы программист явно задал тип каждой переменной, и это дает одно важное преимущество. Хотя при выполнении программы значение переменной может многократно меняться, тип ее меняться не должен никогда; это значит, что компилятор может проверить операции, выполняемые над этой переменной, и убедиться в том, что все они согласуются с описанием типа переменной. Такая проверка может быть проведена путем анализа всего текста программы, и в этом случае она охватит все возможные действия, определяемые данной программой.  В зависимости от назначения языка программирования защита типов, осуществляемая на этапе компиляции, может быть более или менее жесткой. Так, например, язык PASCAL, изначально являвшийся прежде всего инструментом для иллюстрирования структур данных и алгоритмов, сохраняет от своего первоначального назначения весьма строгую защиту типов. PASCAL-компилятор в большинстве случаев расценивает смешение в одном выражении данных разных типов или применение к типу данных несвойственных ему операций как фатальную ошибку. Напротив, язык C, предназначенный прежде всего для системного программирования, является языком с весьма слабой защитой типов. C-компиляторы в таких случаях лишь выдают предупреждения. Отсутствие жесткой защиты типов дает системному программисту, разрабатывающуему программу на языке C, дополнительные возможности, но такой программист сам отвечает за правильность свох действий.  Структура данных относится, по существу, к "пространственным" понятиям: ее можно свести к схеме организации информации в памяти компьютера. Алгоритм же является соответствующим процедурным элементом в структуре программы - он служит рецептом расчета. Первые алгоритмы были придуманы для решения численных задач типа умножения чисел, нахождения наибольшего общего делителя, вычисления тригонометрических функций и других. Сегодня в равной степени важны и нечисленные алгоритмы; они разработаны для таких задач, как, например, поиск в тексте заданного слова, планирование событий, сортировка данных в указанном порядке и т.п. Нечисленные алгоритмы оперируют с данными, которые не обязательно являются числами; более того, не нужны никакие глубокие математические понятия, чтобы их конструировать или понимать. Из этого, однако, вовсе не следует, что в изучении таких алгоритмов математике нет места; напротив, точные, математические методы необходимы при поиске наилучших решений нечисленных задач при доказательстве правильности этих решений. Структуры данных, применяемые в алгоритмах, могут быть чрезвычайно сложными. В результате выбор правильного представления данных часто служит ключом к удачному программированию и может в большей степени сказываться на производительности программы, чем детали используемого алгоритма. Вряд ли когда-нибудь появится общая теория выбора структур данных. Самое лучшее, что можно сделать,- это разобраться во всех базовых "кирпичиках" и в собранных из них структурах. Способность приложить эти знания к конструированию больших систем - это прежде всего дело инженерного мастерства и практики.

Информация  и ее представление  в памяти

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

Хранение  информации

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

Системы счисления

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

Непозиционные системы счисления 

Числа используются для символического представления  количества объектов. Очень простым  методом представления количества является использование одинаковых значков. В такой системе между  значками и пересчитываемыми объектами  устанавливается взаимно однозначное  соответствие. Например, шесть объектов могут быть представлены как ****** или 111111. Такая система становится очень  неудобной, если попытаться с ее помощью  представить большие количества. Системы счисления, подобные римской, обеспечивают частичное решение  проблемы представления большого количества объектов. В римской системе дополнительные символы служат для представления  групп значков. Например, можно принять  что I=*, Y=IIIII, X=YY, L=XXXXX и т.д. Заданная величина представляется с помощью комбинирования символов в соответствии с рядом правил, которые в некоторой степени зависят от положения символа в числе. Недостатком системы, которая с самого начала основывается на группировании некоторого множества символов с целью формирования нового символа, является то обстоятельство, что для представления очень больших количеств требуется очень много уникальных символов.

Позиционные системы счисления 

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

Система счисления  с основанием десять, или десятичная система является позиционной. Рассмотрим, например, число 1303. Его можно представить  в виде:

       1*10^3 + 3*10^2 + 0*10^1 + 3*10^0.

(Здесь и далее  символ ^ используется как знак  операции возведения в степень).

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

       2*10^(-1) + 5*10^(-2).

Другой пример позиционной  системы счисления - двоичная система. Двоичное число 11001.101 представляет то же самое количество, что и десятичное число 26.625. Разложение данного двоичного  числа в соответствии с его  позиционным представлением следующее:

       1*2^4 + 1*2^3 + 0*2^1 + 1*2^0 + 1*2^(-1) + 0*2^(-2) + 1*2^(-3) =

       16 + 8 + 1 + 0.5 + 0.125=26.625.

Наиболее часто  встречаются системы счисления имеющие основание 2,8,10 и 16, которые обычно называют двоичной, восьмеричной, десятичной и шестнадцатеричной системами, соответственно. Вся вычислительная техника работает в двоичной системе счисления, так как базовые элементы вычислительной техники имеют два устойчивых состояния. Восьмеричная и шестнадцатеричная системы используются для удобства работы с большими двоичными числами.

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

Теперь можно дать более конкретное определение данного  на машинном уровне представления информации. Независимо от содержания и сложности  любые данные в памяти ЭВМ представляются последовательностью двоичных разрядов, или битов, а их значениями являются соответствующие двоичные числа. Данные, рассматриваемые в виде последовательности битов, имеют очень простую организацию  или, другими словами, слабо структурированы. Для человека описывать и исследовать  сколько-нибудь сложные данные в  терминах последовательностей битов  весьма неудобно. Более крупные и  содержательные, нежели бит, "строительные блоки" для организации произвольных данных получаются на основе понятия "структуры  данного". Под СТРУКТУРОЙ ДАННЫХ в общем случае понимают множество  элементов данных и множество  связей между ними. Такое определение  охватывает все возможные подходы  к структуризации данных, но в каждой конкретной задаче используются те или  иные его аспекты. Поэтому вводится дополнительная классификация структур данных, направления которой соответствуют  различным аспектам их рассмотрения. Прежде чем приступать к изучению конкретных структур данных, дадим  их общую классификацию по нескольким признакам. Понятие "ФИЗИЧЕСКАЯ структура  данных" отражает способ физического  представления данных в памяти машины и называется еще структурой хранения, внутренней структурой или структурой памяти. Рассмотрение структуры данных без учета ее представления в  машинной памяти называется абстрактной  или ЛОГИЧЕСКОЙ структурой. В общем  случае между логической и соответствующей  ей физической структурами существует различие, степень которого зависит  от самой структуры и особенностей той среды, в которой она должна быть отражена. Вследствие этого различия существуют процедуры, осуществляющие отображение логической структуры  в физическую и, наоборот, физической структуры в логическую. Эти процедуры обеспечивают, кроме того, доступ к физическим структурам и выполнение над ними различных операций, причем каждая операция рассматривается применительно к логической или физической структуре данных. Различаются ПРОСТЫЕ (базовые, примитивные) структуры (типы) данных и ИНТЕГРИРОВАННЫЕ (структурированные, композитные, сложные). Простыми называются такие структуры данных, которые не могут быть расчленены на составные части, большие, чем биты. С точки зрения физической структуры важным является то обстоятельство, что в данной машинной архитектуре, в данной системе программирования мы всегда можем заранее сказать, каков будет размер данного простого типа и какова структура его размещения в памяти. С логической точки зрения простые данные являются неделимыми единицами. Интегрированными называются такие структуры данных, составными частями которых являются другие структуры данных - простые или в свою очередь интегрированные. Интегрированные структуры данных конструируются программистом с использованием средств интеграции данных, предоставляемых языками программирования. В зависимости от отсутствия или наличия явно заданных связей между элементами данных следует различать НЕСВЯЗНЫЕ структуры (векторы, массивы, строки, стеки, очереди) и СВЯЗНЫЕ структуры (связные списки). Весьма важный признак структуры данных - ее изменчивость - изменение числа элементов и (или) связей между элементами структуры. В определении изменчивости структуры не отражен факт изменения значений элементов данных, поскольку в этом случае все структуры данных имели бы свойство изменчивости. По признаку изменчивости различают структуры СТАТИЧЕСКИЕ, ПОЛУСТАТИЧЕСКИЕ, ДИНАМИЧЕСКИЕ. Классификация структур данных по признаку изменчивости приведена на рис. 1.1. Базовые структуры данных, статические, полустатические и динамические характерны для оперативной памяти и часто называются оперативными структурами. Файловые структуры соответствуют структурам данных для внешней памяти. 
 

 

Важный признак  структуры данных - характер упорядоченности  ее элементов. По этому признакуструктуры можно делить на ЛИНЕЙНЫЕ И НЕЛИНЕЙНЫЕ структуры. В зависимости от характера взаимного расположения элементов в памяти линейные структуры можно разделить на структуры с ПОСЛЕДОВАТЕЛЬНЫМ распределением элементов в памяти (векторы, строки, массивы, стеки, очереди) и структуры с ПРОИЗВОЛЬНЫМ СВЯЗНЫМ распределением элементов в памяти ( односвязные, двусвязные списки). Пример нелинейных структур - многосвязные списки, деревья, графы. В языках программирования понятие "структуры данных" тесно связано с понятием "типы данных". Любые данные, т.е. константы, переменные, значения функций или выражения, характеризуются своими типами.

Информация по каждому  типу однозначно определяет :

1) структуру хранения  данных указанного типа, т.е. выделение  памяти и представление данных  в ней, с одной стороны, и  интерпретирование двоичного представления,  с другой;

2) множество допустимых  значений, которые может иметь  тот или иной объект описываемого  типа;

3) множество допустимых  операций, которые применимы к  объекту описываемого типа.

В последующих главах данного пособия рассматриваются  структуры данных и соответствующие  им типы данных. При описании базовых (простых) типов и при конструировании  сложных типов мы ориентировались  в основном на язык PASCAL. Этот язык использовался  и во всех иллюстративных примерах. PASCAL был создан Н.Виртом специально для иллюстрирования структур данных и алгоритмов и традиционно используется для этих целей. Читатель знакомый с любым другим процедурным языком программирования общего назначения (C, FORTRAN, ALGOL, PL/1 и т.д.), без труда найдет аналогичные средства в известном ему языке.

Операции  над структурами  данных

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

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

Например, в PL/1 оператор DECLARE N FIXED DECIMAL приведет к выделению  адресного пространства для переменной N. В FORTRAN ( Integer I ), в PASCAL ( I:integer ), в C ( int I ) в результате описания типа будет выделена память для соответствующих переменных. Для структур данных, объявленных в программе, память выделяется автоматически средствами систем программирования либо на этапе компиляции, либо при активизации процедурного блока, в котором объявляются соответствующие переменные. Программист может и сам выделять память для структур данных, используя имеющиеся в системе программирования процедуры/функции выделения/освобождения памяти. В объектно-ориентированных языках программирования при разработке нового объекта для него должны быть определены процедуры создания и уничтожения.