metod_15.03.04_atppp_oaip_ump_2016 (1016599), страница 17
Текст из файла (страница 17)
Логические данные могут принимать одно из двух значений - О или 1 (0соответствует логическому False, 1 - True, причем, принимается False<True). Для ихзаписи было бы достаточно отвести всего один двоичный разряд. Однако в ОЗУкомпьютера отсутствует доступ к отдельному биту, поэтому для представлениялогических данных выделяется 1 машинное слово, в 0 и 8 разряды которого ипомещаются значения логической величины.15 14 13 12 11 10 9 8 7 6 54 3 2 100000 00010000 00 00Надлогическими данными определены операции: логическое умножение(конъюнкция, ^), логическое сложение (дизъюнкция, v), логическое отрицание ().Примером логических данных может служить тип Boolean в PASCAL'e.Значения элементарных данных формируются в ходе исполнения программы иимеют физическое представление в ОЗУ.
В отличие от них идентификаторы данныхсуществуют только на уровне логического представления - они используются дляобозначения данных в тексте программы, однако при трансляции программы с языкапрограммирования в машинный код имена заменяются номерами ячеек, в которыхданные размещаются. При исполнении такой программы обращение к даннымпроизводится по адресу ячейки, а не идентификатору.
Адреса могут бытьабсолютными - в этом случае они не изменяются при загрузке программы в ОЗУ именно такой способ адресации применяется в исполняемых программных файлах срасширением .соm. Однако в силу некоторых особенностей распределения памятикомпьютера размер таких программ не может превышать 64 Кб. В исполняемыхфайлах с расширением .ехе на этапе трансляции устанавливаются относительныеадреса данных, которые конкретизируются при размещении программы в ОЗУ - этонесколько замедляет начало исполнения, зато снимает указанное выше ограничение наразмер программы.Общие сведения о структурах данныхРабота с большими наборами элементарных данных упрощается, если провести ихупорядочение, т.е.
образовать заданную структуру.Структурированные данные – это упорядоченный набор элементарные данные схарактеристиками и определенными связями между ними.Можно указать ряд причин, поясняющих необходимость и удобство использованияданных, организованных в некоторую структуру:74• отражение в организации данных логики задачи, объективно существующейвзаимосвязи и взаимообусловленности между данными;• оптимизация последовательности обработки данных;• применение при обработке данных циклических конструкций, когда нельзяавтоматически менять имя переменной, однако, можно изменять индексы;• сокращение количества одиночных данных и, следовательно, многих имен.Перечисленные причины приводят к тому, что в современных языках и системахпрограммирования резервируется широкий спектр различных структур данных и,помимо этого, предусматривается возможность создания структур удобных инеобходимых пользователю.При создании любой структуры данных необходимо решить два вопроса - какразделить элементы данных между собой и как разыскивать нужные элементы.Относительно структур данных необходимо сделать следующие общие замечания:• логический уровень организации данных отражается в тексте программы - имопределяется порядок их обработки;• физический уровень представления структур в ОЗУ - последовательные списки исвязные списки; на ВЗУ все структуры представляются в виде файлов;•обработка данных возможна только после их размещения в ОЗУ; с ВЗУопределены только операции записи и чтения;•идентификаторы, как и у одиночных данных, существуют только в текстепрограммы и на этапе трансляции переводятся в адреса ячеек памяти.В зависимости от характера взаимосвязей и отношений между данными в структуреможно выделить несколько классификационных признаков:1.
Отношения порядка. По порядку данных структуры делятся на упорядоченные инеупорядоченные.В упорядоченных структурах элементы размещаются по порядку, т.е. каждыйэлемент имеет свой порядковый номер. При этом если весь набор имеет один общийидентификатор (например, М), то отдельным данным присваиваются собственныеидентификаторы - индексы (например, М5 или Мь).Порядковый номер элемента можно считать внешним признаком, который можетприсваиваться элементу независимо от его значения. Например, регистрационныйномер документа определяется только временем его поступления в учреждение, а неего содержанием.
Помимо нумерации в структурах данных используется упорядочениепо значению некоторого внутреннего признака, например, размещение фамилий валфавитном порядке или группы предприятий в порядке убывания их рентабельности такое упорядочение называется ранжированием.2.
Однородность. Однородные структуры содержат элементарные данные толькоодного типа (массивы, множества, стеки). Неоднородные структуры объединяютданные разных типов (записи).3. Характер отношений между элементами. По взаимной подчиненности элементовструктуры данных подразделяются на линейные и нелинейные.В линейных структурах все элементы равноправны (массив, множество, стек,очередь).В нелинейных структурах между элементами существуют отношенияподчиненности или они могут быть связаны логическими условиями (деревья, графы).75В организованной структуре каждый элемент данных приобретает адрес.
При этомобъем хранимых данных возрастает на число адресов (адреса тоже данные).Основываясь на выделенных классификационных признаках, рассмотрим иохарактеризуем некоторые структуры данных.Массив.Массив - упорядоченная линейная совокупность однородных данных. Другимисловами это пронумерованная, равноправная совокупность данных или массивоводного типа.Если элементами данного массива являются массивы данных, тогда они должныиметь одинаковую структуру и размер.Количество индексов, определяющих положение элемента в массиве,называется мерностью массива.Если индекс единственный (m(i) или m [i]) массив называется одномерным (вектор,строка, столбец).Массив, элементы которого имеют два индекса (G [i, j]) называется двумерным илиматрицей.
Первый индекс является номером строки, а второй индекс - номеромстолбца, на пересечении которых находится данный элемент. Максимальная мерностьмассива может быть ограничена синтаксисом некоторых языков программирования,либо не иметь таких ограничений.Максимальное значение индексов определяет размер массива. Размер массивауказывается в блоке описания программы, т.к.
для хранения элементов массиварезервируется необходимый объем памяти. Если в процессе исполнения программыразмер массива не может быть изменен - это массив фиксированного размера. Еслиизменение размеров массива происходит по ходу работы программы - этодинамический массив.Допустимый набор операций над элементами массива определяется типомэлементарных или структурированных данных, из которых массив сформирован.Особое место занимают символьные массивы - они называются строками илистроковыми данными (например, тип String в PASCAL'e). С ними возможен целыйнабор операций, неопределенных для одиночных символьных данных. В первуюочередь, это операция конкатенации (объединения) строк с формированием новойстроки.
Помимо этого имеются операции замещения части строки, а такжеопределения ее числовых характеристик.Стек, очередь Стек (магазин) и очередь являются упорядоченными, линейными,неоднороднымиструктурами. Реализуются в виде специальным образом организованных областей ОЗУлибо в качестве самостоятельных блоков памяти. Ячейки памяти стека (или регистрыстековой памяти) соединяются друг с другом таким образом, что ввод данныхвозможен только в первую ячейку со сдвигом всех ранее записанных данных.
При считывании - содержимое всех ячеек памяти стека сдвигается и выталкивает содержимоепервой ячейки. Другими словами, вход в стек возможен только через первую ячейку(вершину стека), поэтому извлекаться первой будет та информация, которая былазанесена последней, подобно пассажиру переполненного автобуса.761Ячейки стекааFalse3,14ПустоПустоПустоДно стека11АFalse3,14ПустоПустоаFalse3,14ПустоПустоПустоДно стекаВводданныхВыводданныхОтличие очереди от стека только в том, что извлечение информации производится впорядке «первым вошел - первым вышел», т.е. со дна стека.Таким образом, данные имеют порядок расположения и они равноправны – поэтомуструктура является упорядоченной и линейной.
Однако в общем случае в ячейкахпамяти стека могут содержаться данные разных типов – по этому признаку структураоказывается неоднородной.Дерево Дерево или иерархия является примером нелинейной структуры. В нейэлементкаждого уровня (за исключением самого верхнего) входит в один и только одинэлемент следующего (более высокого) уровня. Элемент самого высокого уровняназывается корнем, а самого нижнего уровня - листьями.Отдельные элементы могут быть однородными или нет. Примером подобной организации служат файловые структуры на внешних запоминающих устройствахкомпьютера.В иерархической структуре адрес каждого элемента определяется путем доступа(маршрутом), ведущим от вершины структуры к данному элементу.Достоинства иерархических структур данных:они не создают проблем с обновлением данных;их легко развивать путем создания новых уровней.Недостатки иерархических структур:- относительная трудоемкость записи адреса элемента данных; упорядочение по форме сложнее, чем линейные и табличные структуры.Часто методы упорядочения в таких структурах основываются на предварительнойиндексации – присвоению каждому элементу данных уникального индекса, которыйможно использовать при поиске, сортировке и т.п.
После такой индексации данныелегко разыскиваются по двоичному коду индекса. Пример, книга имеет иерархическуюструктуру, где каждый уровень и каждый элемент имеет индекс. Оглавление являетсясписком индексов. Поэтому найти нужную страницу можно, не прибегая к просмотрувсего содержимого.Граф77Часто отношения между данными представляются в виде графа - совокупноститочек и линий, в которой каждая линия соединяет две точки. В информатике точкаполучает смысл элемента структуры (системы, данных и пр.), а линии - смыслотношения между элементами.ff12d34aa cee d1452bgcb3а)б)Примеры графов: а) неориентированный; б) ориентированный.По рассмотренной ранее классификации граф является упорядоченной,нелинейной, неоднородной структурой. Понятие графа благодаря его наглядности ивысокой общности в информатике выступает в качестве основного средства описанияструктур данных, систем, порядка выполнения действий.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
