Операции над множествами

Пусть S1, S2, S3 : set of byte , Над этими множествами определены следующие специфические операции:

1) Объединение множеств: S2+S3. Результатом является множество, содержащее элементы обоих исходных множеств. 2) Пересечение множеств: S2*S3. Результатом является множество, содержащее общие элементы обоих исходных множеств. 3) Проверка на вхождение элемента в множество: a in S1. Результатом этой операции является значение логического типа - true, если элемент a входит в множество S1, false - в противном случае.

Операции над строками

Базовыми операциями над строками являются:

определение длины строки; присваивание строк; конкатенация (сцепление) строк; выделение подстроки; поиск вхождения.

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

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

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

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

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

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

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

Главное заключается в том, что независимо от используемого языка программирования, имеющиеся в программе структуры данных не появляются "из ничего", а явно или неявно объявляются операторами создания структур. В результате этого всем экземплярам структур в программе выделяется память для их размещения.

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

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

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

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

Операции над указателями.

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

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

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

Операция выборки - одноместная, ее операндом является типизированный (обязательно!) указатель, результат - данные, выбранные из памяти по адресу, заданному операндом. Тип результата определяется типом указателя-операнда.

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

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

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

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

Операции адресной арифметики выполняются только над типизированными указателями. Единицей измерения в адресной арифметике является размер объекта, который указателем адресуется. Так, если переменная ipt определена как указатель на целое число (int *ipt), то выражение ipt+1 даст адрес, больший не на 1, а на количество байт в целом числе (в MS DOS - 2). Вычитание указателей также дает в результате не количество байт, а количество объектов данного типа, помещающихся в памяти между двумя адресами. Это справедливо как для указателей на простые типы, так и для указателей на сложные объекты, размеры которых составляют десятки, сотни и более байт.

В связи с имеющимися в языке C расширенными средствами работы с указателями, следует упомянуть и о разных представлениях указателей в этом языке. В C указатели любого типа могут быть ближними (near) и дальними (far) или (huge). Эта дифференциация связана с физической структурой адреса в i8086, которая была рассмотрена выше. Ближние указатели представляют собой смещение в текущем сегменте, для представления такого указателя достаточно одного 16-разрядного слова. Дальние указатели представляются двумя 16-разрядными словами - сегментом и смещением. Разница между far или huge указателями состоит в том, что для первых адресная арифметика работает только со смещением, не затрагивая сегментную часть адреса, таким образом, операции адресной арифметики могут изменять адрес в диапазоне не более 64 Кбайт; для вторых - в адресной арифметике участвует и сегментная часть, таким образом, предел изменения адреса - 1 Мбайт.

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

Операции над записями

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

< имя переменной-записи >.< имя поля >

Так, для записи, описанной в начале п.3.5.1, конструкции: stud1.num и stud1.math будут обеспечивать обращения к полям num и math соответственно.

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

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

Операции обработки списков

Базовыми операциями при обработке списков являются операции (функции): car, cdr, cons и atom.

Операция car в качестве аргумента получает список (указатель на начало списка). Ее возвращаемым значением является первый элемент этого списка (указатель на первый элемент). Например:

если X - список (2,6,4,7), то car(X) - атом 2; если X - список ((1,2),6), то car(X) - список (1,2); если X - атом то car(X) не имеет смысла и в действительности не определено.

Операция cdr в качестве аргумента также получает список. Ее возвращаемым значением является остаток списка - указатель на список после удаления из него первого элемента. Например:

если X - (2,6,4), то cdr(X) - (6,4); если X - ((1,2),6,5), то cdr(X) - (6,5); если список X содержит один элемент, то cdr(X) равно nil.

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

если X - 2, а Y - (6,4,7), то cons(X,Y) - (2,6,4,7); если X - (1,2), Y - (6,4,7), то cons(X,Y) - ((1,2),6,4,7).

Операция atom выполняет проверку типа элемента списка. Она должна возвращать логическое значение: true - если ее аргумент является атомом или false - если ее аргумент является подсписком.

В программном примере 5.11 приведена реализация описанных операций как функций языка PASCAL. Структура элемента списка, обрабатываемого функциями этого модуля определена в нем как тип litem и полностью соответствует рис.5.16. Помимо описанных операций в модуле определены также функции выделения памяти для дескриптора данных - NewAtom и для элемента списка - NewNode. Реали- зация операций настолько проста, что не требует дополнительных пояснений.

{==== Программный пример 5.11 ====} { Элементарные операции для работы со списками } Unit ListWork; Interface type lpt = ^litem; { указатель на элемент списка } litem = record typeflg : char; { Char(0) - узел, иначе - код типа } down : pointer; { указатель на данные или на подсписок } next: lpt; { указатель на текущем уровне } end; Function NewAtom(d: pointer; t : char) : lpt; Function NewNode(d: lpt) : lpt; Function Atom(l : lpt) : boolean; Function Cdr(l : lpt) : lpt; Function Car(l : lpt) : lpt; Function Cons(l1, l : lpt) : lpt; Function Append(l1,l : lpt) : lpt; Implementation {*** создание дескриптора для атома } Function NewAtom(d: pointer; t : char) : lpt; var l : lpt; begin New(l); l^.typeflg:=t; { тип данных атома } l^.down:=d; { указатель на данные } l^.next:=nil; NewAtom:=l; end; {*** создание элемента списка для подсписка } Function NewNode(d: lpt) : lpt; var l : lpt; begin New(l); l^.typeflg:=Chr(0); { признак подсписка } l^.down:=d; { указатель на начало подсписка } l^.next:=nil; NewNode:=l; end; {*** проверка элемента списка: true - атом, false - подсписок } Function Atom(l : lpt) : boolean; begin { проверка поля типа } if l^.typeflg=Chr(0) then Atom:=false else Atom:=true; end; Function Car(l : lpt) : lpt; {выборка 1-го элемента из списка } begin Car:=l^.down; { выборка - указатель вниз } end; Function Cdr(l : lpt) : lpt;{исключение 1-го элемента из списка} begin Cdr:=l^.next; { выборка - указатель вправо } end; {*** добавление элемента в начало списка } Function Cons(l1,l : lpt) : lpt; var l2 : lpt; begin l2:=NewNode(l1); { элемент списка для добавляемого } l2^.next:=l; { в начало списка } Cons:=l2; { возвращается новое начало списка } end; {*** добавление элемента в конец списка } Function Append(l1,l : lpt) : lpt; var l2, l3 : lpt; begin l2:=NewNode(l1); { элемент списка для добавляемого } { если список пустой - он будет состоять из одного эл-та } if l=nil then Append:=l2 else begin { выход на последний эл-т списка } l3:=l; while l3^.next <> nil do l3:=l3^.next; l3^.next:=l2; { подключение нового эл-та к последнему } Append:=l; { функция возвращает тот же указатель } end; end; END.

Основные операции над деревьями.

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

1) Поиск узла с заданным ключом ( Find ). 2) Добавление нового узла ( Dob ). 3) Удаление узла ( поддерева ) ( Udal ). 4) Обход дерева в определенном порядке:

Нисходящий обход ( процедура Preorder , рекурсивная процедура r_Preoder); Смешанный обход (процедура Inorder, рекурсивная процедура r_Inorder); Восходящий обход ( процедура Postorder, рекурсивная процедура r_Postorder).

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

процедура включения в стек при нисходящем обходе (Push_st); функция извлечения из стека при нисходящем обходе (Pop_st); процедура включения в стек при восходящем и смешанном обходе (S_Push); функция извлечения из стека при восходящем и смешанном обходе (S_Pop).

Для прошитых деревьев:

функция нахождения сына данного узла ( Inson ); функция нахождения отца данного узла ( Inp ); процедура включения в дерево узла слева от данного (leftIn);

ПОИСК ЗАПИСИ В ДЕРЕВЕ( Find ).

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

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

1) найдена вершина, содержащая ключ, равный ключу X; 2) в дереве отсутствует вершина, к которой нужно перейти для выполнения очередного шага поиска.

В первом случае возвращается указатель на найденную вершину. Во втором - указатель на звено, где остановился поиск, (что удобно для построения дерева ).
Реализация функции Find приведена в программном примере 6.2.

{=== Программный пример 6.2. Поиск звена по ключу === } Function Find(k:KeyType;d:TreePtr;var rez:TreePtr):bollean; { где k - ключ, d - корень дерева, rez - результат } Var p,g: TreePtr; b: boolean; Begin b:=false; p:=d; { ключ не найден } if d <> NIL then repeat q: =p; if p^.key = k then b:=true { ключ найден } else begin q:=p; { указатель на отца } if k < p^.key then p:=p^.left { поиск влево } else p:=p^.right { поиск вправо} end; until b or (p=NIL); Find:=b; rez:=q; End; { Find }

ДОБАВЛЕНИЕ НОВОГО УЗЛА ( Dop ).

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

Алгоритм поиска нужной вершины, вообще говоря, тот же самый, что и при поиске вершины с заданным ключом. Эта вершина будет найдена в тот момент, когда в качестве очередного указателя, определяющего ветвь дерева, в которой надо продолжить поиск, окажется указатель NIL ( случай 2 функции Find ). Тогда процедура вставки записывается так, как в программном примере 6.3.

{=== Программный пример 6.3. Добавление звена ===} Procedure Dob (k:KeyType; var d:TreePtr; zap:data); { k - ключ, d - узел дерева, zap - запись } Var r,s: TreePtr; t: DataPtr; Begin if not Find(k,d,r) then begin (* Занесение в новое звено текста записи *) new(t); t^:=zap; new(s); s^.key:=k; s^.ssil:=t; s^.left:=NIL; s^.right:=NIL; if d = NIL then d:=s (* Вставка нового звена *) else if k < r^.key then r^.left:=s else r^.right:=s; end; End; { Dop }

ОБХОД ДЕРЕВА.

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

Бинарное дерево можно обходить тремя основными способами: нисходящим, смешанным и восходящим ( возможны также обратный нисходящий, обратный смешанный и обратный восходящий обходы).


Принятые выше названия методов обхода связаны с временем обработки корневой вершины: До того как обработаны оба ее поддерева (Preorder), после того как обработано левое поддерево, но до того как обработано правое (Inorder), после того как обработаны оба поддерева (Postorder). Используемые в переводе названия методов отражают направление обхода в дереве: от корневой вершины вниз к листьям - нисходящий обход; от листьев вверх к корню - восходящий обход, и смешанный обход - от самого левого листа дерева через корень к самому правому листу.

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

1. В качестве очередной вершины взять корень дерева. Перейти к пункту 2. 2. Произвести обработку очередной вершины в соответствии с требованиями задачи. Перейти к пункту 3. 3.а) Если очередная вершина имеет обе ветви, то в качестве новой вершины выбрать ту вершину, на которую ссылается левая ветвь, а вершину, на которую ссылается правая ветвь, занести в стек; перейти к пункту 2; 3.б) если очередная вершина является конечной, то выбрать в качестве новой очередной вершины вершину из стека, если он не пуст, и перейти к пункту 2; если же стек пуст, то это означает, что обход всего дерева окончен, перейти к пункту 4; 3.в) если очередная вершина имеет только одну ветвь, то в качестве очередной вершины выбрать ту вершину, на которую эта ветвь указывает, перейти к пункту 2. 4. Конец алгоритма.

Для примера рассмотрим возможные варианты обхода дерева (рис.6.26).

При обходе дерева представленного на рис.6.26 этими тремя методами мыполучим следующие последовательности: ABCDEFG ( нисходящий ); CBAFEDG ( смешанный ); CBFEGDA ( восходящий ).

Основные определения

Дерево - это граф, который характеризуется следующими свойствами:

1. Cуществует единственный элемент (узел или вершина), на который не ссылается никакой другой элемент - и который называется КОРНЕМ (рис. 6.8, 6.9 - A,G,M - корни). 2. Начиная с корня и следуя по определенной цепочке указателей, содержащихся в элементах, можно осуществить доступ к любому элементу структуры. 3. На каждый элемент, кроме корня, имеется единственная ссылка, т.е. каждый элемент адресуется единственным указателем.

Название "дерево" проистекает из логической эквивалентности древовидной структуры абстрактному дереву в теории графов. Линия связи между парой узлов дерева называется обычно ВЕТВЬЮ. Те узлы, которые не ссылаются ни на какие другие узлы дерева, называются ЛИСТЬЯМИ (или терминальными вершинами)(рис. 6.8, 6.9 - b,k,l,h - листья). Узел, не являющийся листом или корнем, считается промежуточным или узлом ветвления (нетерминальной или внутренней вершиной).

Для ориентированного графа число ребер, исходящих из некоторой начальной вершины V, называется ПОЛУСТЕПЕНЬЮ ИСХОДА этой вершины. Число ребер, для которых вершина V является конечной, называется ПОЛУСТЕПЕНЬЮ ЗАХОДА вершины V, а сумма полустепеней исхода и захода вершины V называется ПОЛНОЙ СТЕПЕНЬЮ этой вершины.

рис. 6.8. Дерево

рис. 6.9. Лес

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

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

Основные понятия

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

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

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

(a,(b,c,d),e,(f,g)) ( ) ((a))

Первый список содержит четыре элемента: атом a, список (b,c,d) (содержащий в свою очередь атомы b,c,d), атом e и список (f,g), элементами которого являются атомы f и g. Второй список не содержит элементов, тем не менее нулевой список, в соответствии с нашим определением является действительным списком. Третий список состоит из одного элемента: списка (a), который в свою очередь содержит атом а.

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

Рис.5.12. Схематическое представление разветвленного списка

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

Порядок. Над элементами списка задано транзитивное отношение, определяемое последовательностью, в которой элементы появляются внутри списка. В списке (x,y,z) атом x предшествует y, а y предшествует z.
При этом подразумевается, что x предшествует z. Данный список не эквивалентен списку (y,z,x). При представлении списков графическими схемами порядок определяется горизонтальными стрелками. Горизонтальные стрелки истолковываются следующим образом: элемент из которого исходит стрелка,предшествует элементу, на который она указывает.

Глубина. Это максимальный уровень, приписываемый элементам внутри списка или внутри любого подсписка в списке. Уровень элемента предписывается вложенностью подсписков внутри списка, т.е.числом пар круглых скобок, окаймляющих элемент. В списке, изображенном на рис.5.12), элементы a и e находятся на уровне 1, в то время как оставшиеся элементы - b, c, d, f и g имеют уровень 2. Глубина входного списка равна 2. При представлении списков схемами концепции глубины и уровня облегчаются для понимания, если каждому атомарному или списковому узлу приписать некоторое число l. Значение l для элемента x, обозначаемое как l(x), является числом вертикальных стрелок, которое необходимо пройти для того, чтобы достичь данный элемент из первого элемента списка. На рис.5.12 l(a)=0, l(b)=1 и т.д. Глубина списка является максимальным значением уровня среди уровней всех атомов списка.

Длина - это число элементов уровня 1 в списке. Например, длина списка на рис.5.12 равна 3.

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

< операнд 1 > < знак операции > < операнд 2 >

Перечислимый тип

Логическая структура.

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

type color=(red,blue,green); work_day=(mo,tu,we,th,fr); winter_day=(december,january,february);

Машинное представление.

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

var B,С:color; begin B:=bluе; (* B=1 *) C:=green; (* С=2 *) Write(ord(B):4,ord(C):4); end.

После выполнения данного фрагмента программы на экран будут выданы цифры 1 и 2. Содержимое памяти для переменных B И C при этом следующее:

В - 00000001; С - 00000010.

Операции.

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

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

Перевод чисел из одной системы счисления в другую

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

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

Например,

1) перевести дробное число 0.243 из десятичной системы счисления в двоичную.

0.243(10) ---> 0.0011111(2). Проверка: 0.0011111 = 0*2^(-1) + 0*2^(-2)+1*2^(-3) + 1*2^(-4)+1*2^(-5) + +1*2^(-6)+1*2*(-7) = 0,2421875

2) перевести целое число 164 из десятичной системы счисления в двоичную систему.

164(10) ---> 10100100(2) Проверка: 10100100 = 1*2^7 + 0*2^6 + 1*2^5 + 0*2^4 + 0*2^3 + 1*2^2 + 0*2^1 + 0*2^0 = 128+32+4=164

При переводе смешанных чисел целая и дробная части числа переводятся отдельно.

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

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

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

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

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

Для последовательного поиска в среднем требуется (N+1)/2 сравнений. Таким образом, порядок алгоритма - линейный - O(N).

Программная иллюстрация линейного поиска в неупорядоченном массиве приведена в следующем примере, где a - исходный массив, key - ключ, который ищется; функция возвращает индекс найденного элемента или EMPTY - если элементт отсутствует в массиве.

{===== Программный пример 3.4 =====} Function LinSearch( a : SEQ; key : integer) : integer; var i : integer; for i:=1 to N do { перебор эл-тов массива } if a[i]=key then begin { ключ найден - возврат индекса } LinSearch:=i; Exit; end; LinSearch:=EMPTY; {просмотрен весь массив, но ключ не найден } end;

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

В позиционной системе счисления используется конечное число 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. В каждом узле оставить только ветвь к старшему сыну (вертикальное соединение); 2. Соединить горизонтальными ребрами всех братьев одного отца; 3. Таким образом перестроить дерево по правилу:

левый сын - вершина, расположенная под данной; правый сын - вершина, расположенная справа от данной (т.е. на одном ярусе с ней).

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

В результате преобразования любого дерева в бинарное получается дерево в виде левого поддерева, подвешенного к корневой вершине.

В процессе преобразования правый указатель каждого узла бинарного дерева будет указывать на соседа по уровню. Если такового нет, то правый указатель NIL. Левый указатель будет указывать на вершину следующего уровня. Если таковой нет, то указатель устанавливается на NIL.

Рис.6.14. Исходное дерево

Рис.6.15 Промежуточный результат перестройки дерева

Рис. 6.16. Представление дерева в виде бинарного

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

Правило построения бинарного дерева из леса: корни всех поддеревьев леса соединить горизонтальными связями. В полученном дереве узлы в данном примере будут располагаться на трех уровнях. Далее перестраивать по ранее рассмотренному плану: в начале поддерево с корнем А, затем В и затем Н. В результате преобразования упорядоченного леса в бинарное дерево получается полное бинарное дерево с левым и правым поддеревом.

рис.6.17. Упорядоченный лес

Рис.6.18. Промежуточный результат перестройки леса

Рис. 6.19. Представление леса в виде 2-го дерева

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

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

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

Рис.5.14. Структура элемента разветвленного списка

Элементы списка могут быть двух видов: атомы - содержащие данные и узлы - содержащие указатели на подсписки. В атомах не используется поле down элемента списка, а в узлах - поле data. Поэтому логичным является совмещение этих двух полей в одно, как показано на рис.5.15.

Рис.5.15. Структура элемента разветвленного списка

Поле type содержат признак атом/узел, оно может быть 1-битовым. Такой формат элемента удобен для списков, атомарная информация которых занимает небольшой объем памяти. В этом случае теряется незначительный объем памяти в элементах списка, для которых не требуется поля data. В более общем случае для атомарной информации необходим относительно большой объем памяти. Наиболее распространенный в данной ситуации формат структуры узла представленный на рис.5.16.

Рис. 5.16. Структура элемента разветвленного списка

В этом случае указатель down указывает на данные или на подсписок. Поскольку списки могут составляться из данных различных типов, целесообразно адресовать указателем down не непосредственно данные, а их дескриптор, в котором может быть описан тип данных, их длина и т.п. Само описание того, является ли адресуемый указателем данных объект атомом или узлом также может находиться в этом дескрипторе. Удобно сделать размер дескриптора данных таким же, как и элемента списка. В этом случае размер поля type может быть расширен, например, до 1 байта и это поле может индицировать не только атом/подсписок, но и тип атомарных данных, поле next в дескрипторе данных может использоваться для представления еще какой-то описательной информации, например, размера атома. На рис.5.17 показано представление элементами такого формата списка: (КОВАЛЬ,(12,7,53),d). Первая (верхняя) строка на рисунке представляет элементы списка, вторая - элементы подсписка, третья - дескрипторы данных, четвертая - сами данные. В поле type каждого элемента мы использовали коды: n - узел, S - атом, тип STRING, I - атом, тип INTEGER, C - атом, тип CHAR.

Рис.5.17. Пример представления списка элементами одного формата

Представление строк в памяти.

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

ВЕКТОРНОЕ ПРЕДСТАВЛЕНИЕ СТРОК.

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

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

На рис.4.3 приведена схема, на которой показано представление двух строк: 'ABCD' и 'PQRSTUVW' в виде вектора постоянной длины на шесть символов.

Рис. 4.3. Представление строк векторами постоянной длины

ПРЕДСТАВЛЕНИЕ СТРОК ВЕКТОРОМ ПЕРЕМЕННОЙ ДЛИНЫ С ПРИЗНАКОМ КОНЦА.

Этот и все последующие за ним методы учитывают переменную длину строк. Признак конца - это особый символ, принадлежащий алфавиту (таким образом, полезный алфавит оказывается меньше на один символ), и занимает то же количество разрядов, что и все остальные символы.
Издержки памяти при этом способе составляют 1 символ на строку. Такое представление строки показано на рис.4.4. Специальный символ-маркер конца строки обозначен здесь 'eos'. В языке C, например, в качестве маркера конца строки используется символ с кодом 0.

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

В программе на языке высокого уровня указатели могут быть типизированными и нетипизированными. При объявлении типизированного указателя определяется и тип объекта в памяти, адресуемого этим указателем. Так например, объявления в языке PASCAL:

Var ipt : ^integer; cpt : ^char;

или в языке C:

int *ipt; char *cpt;

означают, что переменная ipt представляет собой адрес области памяти, в которой хранится целое число, а cpt - адрес области памяти, в которой хранится символ. Хотя физическая структура адреса не зависит от типа и значения данных, хранящихся по этому адресу, компилятор считает указатели ipt и cpt имеющими разный тип, и в Pascal оператор:

cpt := ipt;

будет расценен компилятором как ошибочный (компилятор C для аналогичного оператора присваивания ограничится предупреждением). Таким образом, когда речь идет об указателях типизированных, правильнее говорить не о едином типе данных "указатель", а о целом семействе типов: "указатель на целое", "указатель на символ" и т.д. Могут быть указатели и на более сложные, интегрированные структуры данных, и указатели на указатели.

Нетипизированный указатель - тип pointer в Pascal или void * в C - служит для представления адреса, по которому содержатся данные неизвестного типа. Работа с нетипизированными указателями существенно ограничена, они могут использоваться только для сохранения адреса, обращение по адресу, задаваемому нетипизированным указателем, невозможно.

Приложения деревьев.

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

Применение линейных списков

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

В программном примере 5.8 показана организация стека на односвязном линейном списке. Это пример функционально аналогичен примеру 4.1 с той существенной разницей, что размер стека здесь практически неограничен.

Стек представляется как линейный список, в котором включение элементов всегда производятся в начала списка, а исключение - также из начала. Для представления его нам достаточно иметь один указатель - top, который всегда указывает на последний записанный в стек элемент. В исходном состоянии (при пустом стеке) указатель top - пустой. Процедуры StackPush и StackPop сводятся к включению и исключению элемента в начало списка. Обратите внимание, что при включении элемента для него выделяется память, а при исключении - освобождается. Перед включением элемента проверяется доступный объем памяти, и если он не позволяет выделить память для нового элемента, стек считается заполненным. При очистке стека последовательно просматривается весь список и уничтожаются его элементы. При списковом представлении стека оказывается непросто определить размер стека. Эта операция могла бы потребовать перебора всего списка с подсчета числа элементов. Чтобы избежать последовательного перебора всего списка мы ввели дополнительную переменную stsize, которая отражает текущее число элементов в стеке и корректируется при каждом включении/исключении.

{==== Программный пример 5.8 ====} { Стек на 1-связном линейном списке } unit Stack; Interface type data = ...; { эл-ты могут иметь любой тип } Procedure StackInit; Procedure StackClr; Function StackPush(a : data) : boolean; Function StackPop(Var a : data) : boolean; Function StackSize : integer; Implementation type stptr = ^stit; { указатель на эл-т списка } stit = record { элемент списка } inf : data; { данные } next: stptr; { указатель на следующий эл-т } end; Var top : stptr; { указатель на вершину стека } stsize : longint; { размер стека } {** инициализация - список пустой } Procedure StackInit; begin top:=nil; stsize:=0; end; { StackInit } {** очистка - освобождение всей памяти } Procedure StackClr; var x : stptr; begin { перебор эл-тов до конца списка и их уничтожение } while top<>nil do begin x:=top; top:=top^.next; Dispose(x); end; stsize:=0; end; { StackClr } Function StackPush(a: data) : boolean; { занесение в стек } var x : stptr; begin { если нет больше свободной памяти - отказ } if MaxAvail < SizeOf(stit) then StackPush:=false else { выделение памяти для эл-та и заполнение инф.части } begin New(x); x^.inf:=a; { новый эл-т помещается в голову списка } x^.next:=top; top:=x; stsize:=stsize+1; { коррекция размера } StackPush:=true; end; end; { StackPush } Function StackPop(var a: data) : boolean; { выборка из стека } var x : stptr; begin { список пуст - стек пуст } if top=nil then StackPop:=false else begin a:=top^.inf; { выборка информации из 1-го эл-та списка } { 1-й эл-т исключается из списка, освобождается память } x:=top; top:=top^.next; Dispose(top); stsize:=stsize-1; { коррекция размера } StackPop:=true; end; end; { StackPop } Function StackSize : integer; { определение размера стека } begin StackSize:=stsize; end; { StackSize } END.

Природа информации

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

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

n H = - СУММА ( p(i) * log2 (p(i)) ). i=1

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

ПРОСТЫЕ СТРУКТУРЫ ДАННЫХ

Простые структуры данных называют также примитивными или базовыми структурами. Эти структуры служат основой для построения более сложных структур. В языках программирования простые структуры описываются простыми (базовыми) типами. К таким типам относятся: числовые, битовые, логические, символьные, перечисляемые, интервальные, указатели. В дальнейшем изложении мы ориентируемся в основном на язык PASCAL и его реализации в среде MS DOS. Структура простых типов PASCAL приведена на рис 2.1 (через запятую указан размер памяти в байтах, требуемый для размещения данных соответствующего типа). В других языках программирования набор простых типов может несколько отличаться от указанного. Размер же памяти, необходимый для данных того или иного типа, может быть разным не только в разных языках программирования, но и в разных реализациях одного и того же языка.

Рис. 2.1. Структура простых типов PASCAL.

Реализация операций над связными линейными списками

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

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

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

любая структура информационной части списка:

type data = ...; элемент односвязного списка (sll - single linked list):

type sllptr = ^slltype; { указатель в односвязном списке } slltype = record { элемент односвязного списка } inf : data; { информационная часть } next : sllptr; { указатель на следующий элемент } end;

элемент двухсвязного списка (dll - double linked list):

type dllptr = ^dlltype; { указатель в двухсвязном списке } dlltype = record { элемент односвязного списка } inf : data; { информационная часть } next : sllptr; { указатель на следующий элемент (вперед) } prev : sllptr; { указатель на предыдущий элемент (назад) } end;

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

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

Перебор элементов списка.

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

Сбалансированные деревья

ОПРЕДЕЛЕНИЯ.

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

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

Одно из определений сбалансированности было дано Адельсоном-Вельским и Ландисом:

Дерево является СБАЛАНСИРОВАННЫМ тогда и только тогда, когда для каждого узла высота его двух поддеревьев различается не более чем на 1.

Поэтому деревья, удовлетворяющие этому условию, часто называют "АВЛ-деревьями" (по фамилиям их изобретателей).

Операции выполняемые над сбалансированным деревом: поиск, вставка, удаление элемента.

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

1) вставить новый элемент; 2) удалить заданный элемент; 3) поиск заданного элемента.

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

левое - узел левоперевешивающий, если самый длинный путь по ее левому поддереву на единицу больше самого длинного пути по ее правому поддереву;

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

правое - узел правоперевешивающий, если самый длинный путь по ее правому поддереву на единицу больше самого длинного пути по ее левому поддереву;

Символьные множества

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

Например, S : set of char; S:=['A','C'];

В этом случае представление множества S в памяти выглядит следующим образом :

@S+0 - 00000000 . . . . . . . . . . . . @S+31 - 00000000 @S+8 - 00001010

Символьный тип

Значением символьного типа char являются символы из некоторого предопределенного множества. В большинстве современных персональных ЭВМ этим множеством является ASCII (American Standard Code for Information Intechange - американский стандартный код для обмена информацией). Это множество состоит из 256 разных символов, упорядоченных определенным образом и содержит символы заг- лавных и строчных букв, цифр и других символов, включая специальные управляющие символы. Допускается некоторые отклонения от стандарта ASCII, в частности, при наличии соответствующей системной поддержки это множество может содержать буквы русского алфавита. Порядковые номера ( кодировку) можно узнать в соответствующих разделах технических описаний.

Значение символьного типа char занимает в памяти 1 байт. Код от 0 до 255 в этом байте задает один из 256 возможных символов ASCII таблицы.

Например: символ "1" имеет ASCII код 49, следовательно машинное представление будет выглядеть следующим образом: 00110001.

ASCII, однако, не является единственно возможным множеством. Другим достаточно широко используемым множеством является код EBCDIC (Extended Binary Coded Decimal Interchange Code - расширенный двоично-кодированный десятичный код обмена), применяемый в системах IBM средней и большой мощности. В EBCDIC код символа также занимает один байт, но с иной кодировкой, чем в ASCII.

И ASCII, и EBCDIC включают в себя буквенные символы только латинского алфавита. Символы национальных алфавитов занимают "свободные места" в таблицах кодов и, таким образом, одна таблица может поддерживать только один национальный алфавит. Этот недостаток преодолен во множестве UNICODE, которое находит все большее распространение прежде всего в UNIX-ориентированных системах. В UNICODE каждый символ кодируется двумя байтами, что обеспечивает более 64 тыс. возможных кодовых комбинаций и дает возможность иметь единую таблицу кодов, включающую в себя все национальные алфавиты. UNICODE, безусловно, является перспективным, однако, повсеместный переход к двухбайтным кодам символов может вызвать необходимость переделки значительной части существующего программного обеспечения.

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

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

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

Сортировки распределением.

Поразрядная цифровая сортировка.

Алгоритм требует представления ключей сортируемой последовательности в виде чисел в некоторой системе счисления P. Число проходов сортировка равно максимальному числу значащих цифр в числе - D. В каждом проходе анализируется значащая цифра в очередном разряде ключа, начиная с младшего разряда. Все ключи с одинаковым значением этой цифры объединяются в одну группу. Ключи в группе располагаются в порядке их поступления. После того, как вся исходная последовательность распределена по группам, группы располагаются в порядке возрастания связанных с группами цифр. Процесс повторяется для второй цифры и т.д., пока не будут исчерпаны значащие цифры в ключе. Основание системы счисления P может быть любым, в частном случае 2 или 10. Для системы счисления с основанием P требуется P групп.

Порядок алгоритма качественно линейный - O(N), для сортировки требуется D*N операций анализа цифры. Однако, в такой оценке порядка не учитывается ряд обстоятельств.

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

Во-вторых, в оценке алгоритма не учитываются расходы времени и памяти на создание и ведение групп. Размещение групп в статической рабочей памяти потребует памяти для P*N элементов, так как в предельном случае все элементы могут попасть в какую-то одну группу. Если же формировать группы внутри той же последовательности по принципу обменных алгоритмов, то возникает необходимость перераспределения последовательности между группами и все проблемы и недостатки, присущие алгоритмам включения. Наиболее рациональным является формирование групп в виде связных списков с динамическим выделением памяти.

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

Сортировки слиянием.

Алгоритмы сортировки слиянием, как правило, имеют порядок O(N*log2(N)), но отличаются от других алгоритмов большей сложностью и требуют большого числа пересылок. Алгоритмы слияния применяются в основном, как составная часть внеш- ней сортировки, которая более подробно будет рассматриваться нами во втором томе нашего пособия. Здесь же для понимания принципа слияния мы приводим простейший алгоритм слияния в оперативной памяти.

Сортировка попарным слиянием.

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

Важнейшей частью алгоритма является слияние двух упорядоченных множеств. Эту часть алгоритма мы опишем строго.

1. [Начальные установки]. Определить длины первого и второго исходных множеств - l1 и l2 соответственно. Установить индексы текущих элементов в исходных множествах i1 и i2 в 1. Установить индекс в выходном множестве j=1. 2. [Цикл слияния]. Выполнять шаг 3 до тех пор, пока i13. [Сравнение]. Сравнить ключ i1-го элемента из 1-го исходного множества с ключом i2-го элемента из второго исходного множества. Если ключ элемента из 1-го множества меньше, то записать i1-ый элемент из 1-го множества на j-ое место в выходное множество и увеличить i1 на 1. Иначе - записать i2-ой элемент из 2-го множества на j-ое место в выходное множество и увеличить i2 на 1. Увеличить j на 1. 4. [Вывод остатка]. Если i1

Программный пример 3.17 иллюстрирует сортировку попарным слиянием в ее обменном варианте - выходные множества формируются на месте входных.

{===== Программный пример 3.17 =====} { Сортировка слиянием } Procedure Sort(var a :Seq); Var i0,j0,i,j,si,sj,k,ke,t,m : integer; begin si:=1; { начальный размер одного множества } while si < N do begin { цикл пока одно множество не составит весь массив } i0:=1; { нач.
индекс 1-го множества пары } while i0 < N do begin { цикл пока не пересмотрим весь массив } j0:=i0+si; { нач. индекс 2-го множества пары } i:=i0; j:=j0; { размер 2-го множества пары может ограничиваться концом массива } if si > N-j0+1 then sj:=N-j0+1 else sj:=si; if sj > 0 then begin k:=i0; { нач. индекс слитого множества } while (i < i0+si+sj) and (j a[j] then begin { если эл-т 1-го a[j] } k:=k+1; { вых. множество увеличилось } i:=i+1; { если был перенос - за счет сдвига, если не было - за счет перехода эл-та в вых. } end; { while } end; { if sj > 0 } i0:=i0+si*2; { начало следующей пары } end; { while i0 < N } si:=si*2; { размер эл-тов пары увеличивается вдвое } end; { while si < N } end;

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

Сортировки включением

Сортировка простыми вставками.

Этот метод - "дословная" реализации стратегии включения. Порядок алгоритма сортировки простыми вставками - O(N^2), если учитывать только операции сравнения. Но сортировка требует еще и в среднем N^2/4 перемещений, что де- лает ее в таком варианте значительно менее эффективной, чем сортировка выборкой.

Алгоритм сортировки простыми вставками иллюстрируется программным примером 3.11.

{===== Программный пример 3.11 =====} Procedure Sort(a : Seq; var b : Seq); Var i, j, k : integer; begin for i:=1 to N do begin { перебор входного массива } { поиск места для a[i] в выходном массиве } j:=1; while (j < i) and (b[j]

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

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

Пузырьковая сортировка вставками.

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

{===== Программный пример 3.12 =====} Procedure Sort (var a : Seq); Var i, j, k, t : integer; begin for i:=2 to N do begin { перебор входного массива } {*** вх.множество - [i..N], вых.множество - [1..i] } t:=a[i]; { запоминается значение нового эл-та } j:=i-1; {поиск места для эл-та в вых. множестве со сдвигом} { цикл закончится при достижении начала или, когда будет встречен эл-т, меньший нового } while (j >= 1) and (a[j] > t) do begin a[j+1]:=a[j]; { все эл-ты, большие нового сдвигаются } j:=j-1; { цикл от конца к началу выходного множества } end; a[j+1]:=t; { новый эл-т ставится на свое место } end; end;

Результаты трассировки программного примера 3.11 представлены в таблице 3.8.

Сортировки выборкой

Сортировка простой выборкой.

Данный метод реализует практически "дословно" сформулированную выше стратегию выборки. Порядок алгоритма простой выборки - O(N^2). Количество пересылок - N.

Алгоритм сортировки простой выборкой иллюстрируется программным примером 3.7.

В программной реализации алгоритма возникает проблема значения ключа "пусто". Довольно часто программисты используют в качестве такового некоторое заведомо отсутствующее во входной последовательности значение ключа, например, максимальное из теоретически возможных значений. Другой, более строгий подход - создание отдельного вектора, каждый элемент которого имеет логический тип и отражает состояние соответствующего элемента входного множества ("истина" - "непусто", "ложь" - "пусто"). Именно такой подход реализован в нашем программном примере. Роль входной последовательности здесь выполняет параметр a, роль выходной - параметр b, роль вектора состояний - массив c. Алгоритм несколько усложняется за счет того, что для установки начального значения при поиске минимума приходится отбрасывать уже "пустые" элементы.

{===== Программный пример 3.7 =====} Procedure Sort( a : SEQ; var b : SEQ); Var i, j, m : integer; c: array[1..N] of boolean; {состояние эл-тов вх.множества} begin for i:=1 to N do c[i]:=true; { сброс отметок} for i:=1 to N do {поиск 1-го невыбранного эл. во вх.множестве} begin j:=1; while not c[j] do j:=j+1; m:=j; { поиск минимального элемент а} for j:=2 to N do if c[j] and (a[j] < a[m]) then m:=j; b[i]:=a[m]; { запись в выходное множество} c[m]:=false; { во входное множество - "пусто" } end; end;

Обменная сортировка простой выборкой.

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

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

{===== Программный пример 3.8 =====} Procedure Sort(var a : SEQ); Var x, i, j, m : integer; begin for i:=1 to N-1 do { перебор элементов выходного множества} { входное множество - [i:N]; выходное - [1:i-1] } begin m:=i; for j:=i+1 to N do { поиск минимума во входном множестве } if (a[j] < a[m]) then m:=j; { обмен 1-го элемента вх. множества с минимальным } if i<>m then begin x:=a[i]; a[i]:=a[m]; a[m]:=x; end;end; end;

Результаты трассировки программного примера 3.8 представлены в таблице 3.5. Двоеточием показана граница между входным и выходным множествами.

Специальные массивы

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

Симметричные массивы.

Двумерный массив, в котором количество строк равно количеству столбцов называется квадратной матрицей. Квадратная матрица, у которой элементы, расположенные симметрично относительно главной диагонали, попарно равны друг другу, называется симметричной. Если матрица порядка n симметрична, то в ее физической структуре достаточно отобразить не n^2, а лишь n*(n+1)/2 еЯ элементов. Иными словами, в памяти необходимо представить только верхний (включая и диагональ) треугольник квадратной логической структуры. Доступ к треугольному массиву организуется таким образом, чтобы можно было обращаться к любому элементу исходной логической структуры, в том числе и к элементам, значения которых хотя и не представлены в памяти, но могут быть определены на основе значений симметричных им элементов.

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

а) преобразования индексов матрицы в индекс вектора,

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

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

В приложении приведен пример программы для работы с симметричной матрицей.

Разреженные массивы.

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

Различают два типа разреженных массивов:

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

СТАТИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ

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

Каждую структуру данных характеризуют еЯ логическим и физическим представлениями. Очень часто говоря о той или иной структуре данных, имеют в виду еЯ логическое представление. Физическое представление обычно не соответствует логическому, и кроме того, может существенно различаться в разных программных системах. Нередко физической структуре ставится в соответствие дескриптор, или заголовок, который содержит общие сведения о физической структуре. Дескриптор необходим, например, в том случае, когда граничные значения индексов элементов массива неизвестны на этапе компиляции, и, следовательно, выделение памяти для массива может быть выполнено только на этапе выполнения программы (как в языке PL/1, ALGOL-60). Дескриптор хранится как и сама физическая структура, в памяти и состоит из полей, характер, число и размеры которых зависят от той структуры, которую он описывает и от приня- тых способов ее обработки. В ряде случаев дескриптор является совершенно необходимым, так как выполнение операции доступа к структуре требует обязательного знания каких-то ее параметров, и эти параметры хранятся в дескрипторе. Другие хранимые в дескрипторе параметры не являются совершенно необходимыми, но их использование позволяет сократить время доступа или обеспечить контроль правильности доступа к структуре. Дескриптор структуры данных, поддерживаемый языками программирования, является "невидимым" для программиста; он создается компилятором и компилятор же, формируя объектные коды для доступа к структуре, включает в эти коды команды, обращающиеся к дескриптору.

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

Стеки в вычислительных системах

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

Предположим, имеется процедура A, которая вызывает процедуру B, а та в свою очередь - процедуру C. Когда выполнение процедуры A дойдет до вызова B, процедура A приостанавливается и управление передается на входную точку процедуры B. Когда B доходит до вызова C, приостанавливается B и управление передается на процедуру C. Когда заканчивается выполнение процедуры C, управление должно быть возвращено в B, причем в точку, следующую за вызовом C. При завершении B управление должно возвращаться в A, в точку, следующую за вызовом B. Правильную последовательность возвратов легко обеспечить, если при каждом вызове процедуры записывать адрес возврата в стек. Так, когда процедура A вызывает процедуру B, в стек заносится адрес возврата в A; когда B вызывает C, в стек заносится адрес возврата в B. Когда C заканчивается, адрес возврата выбирается из вершины стека - а это адрес возврата в B. Когда заканчивается B, в вершине стека находится адрес возврата в A, и возврат из B произойдет в A.

В микропроцессорах семейства Intel, как и в большинстве современных процессорных архитектур, поддерживается аппаратный стек. Аппаратный стек расположен в ОЗУ, указатель стека содержится в паре специальных регистров - SS:SP, доступных для программиста. Аппаратный стек расширяется в сторону уменьшения адресов, указатель его адресует первый свободный элемент. Выполнение команд CALL и INT, а также аппаратных прерываний включает в себя запись в аппаратный стек адреса возврата. Выполнение команд RET и IRET включает в себя выборку из аппаратного стека адреса возврата и передачу управления по этому адресу. Пара команд - PUSH и POP - обеспечивает использование аппаратного стека для программного решения других задач.

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

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

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

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

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


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

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

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

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



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

Связное представление данных в памяти

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

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

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

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

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

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

Вместе с тем связное представление не лишено и недостатков, основные из которых:

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

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

Связные линейные списки

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

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

Таблицы

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

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

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

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

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

Управление динамически выделяемой памятью

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

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

В общем случае при распределении памяти должны быть решены следующие вопросы:

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

В распоряжении программы обычно имеется адресное пространство, которое может рассматриваться как последовательность ячеек памяти с адресами, линейно возрастающими от 0 до N. Какие-то части этого адресного пространства обычно заняты системными программами и данными, какие-то - кодами и статическими данными самой программы, оставшаяся часть доступна для динамического распределения. Обычно доступная для распределения память представляет собой непрерывный участок пространства с адресными границами от n1 до n2. В управлении памятью при каждом запросе на память необходимо решать, по каким адресам внутри доступного участка будет располагаться выделяемая память.

Векторы

Логическая структура.

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

Машинное представление. Адресация элементов структур.

Элементы вектора размещаются в памяти в подряд расположенных ячейках памяти. Под элемент вектора выделяется количество байт памяти, определяемое базовым типом элемента этого вектора. Необходимое число байтов памяти для хранения одного элемента вектора называется слотом. Размер памяти для хранения вектора определяется произведением длины слота на число элементов.

В языках программирования вектор представляется одномерным массивом с синтаксисом описания вида (PASCAL):

< Имя > : array [n..k] of < тип >;

где n-номер первого элемента, k-номер последнего элемента. Представление в памяти вектора будет такое, как показано на рис. 3.1.

Рис. 3.1. Представление вектора в памяти

где @ Имя -адрес вектора или, что тоже самое, адрес первого элемента вектора,

Sizeof(тип)-размер слота (количество байтов памяти для записи одного элемента вектора), (k-n)*Sizeof(тип) - относительный адрес элемента с номером k, или, что тоже самое, смещение элемента с номером k.

Например: var m1:array[-2..2] of real;

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

Рис. 3.2. Представление вектора m1 в памяти

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

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

ByteSise = ( k - n + 1 ) * Sizeof (тип)

Обращение к i-тому элементу вектора выполняется по адресу вектора плюс смещение к данному элементу.
Смещение i- ого элемента вектора определяется по формуле:

ByteNumer = ( i- n ) * Sizeof (тип), а адрес его: @ ByteNumber = @ имя + ByteNumber.

где @ имя - адрес первого элемента вектора.

Например: var МAS: array [ 5..10 ] of word.

Базовый тип элемента вектора - Word требует 2 байта, поэтому на каждый элемент вектора выделяется по два байта. Тогда таблица 3.1 смещений элементов вектора относительно @Mas выглядит так:

Вещественные типы

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

Представление вещественных чисел в памяти.

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

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

Рис. 2.5. Формат представления вещественных чисел

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

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

Они служат базовыми элементами любой

Записи с вариантами

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

Для задач подобного рода развитые языки программирования (C, PASCAL) предоставляют в распоряжение программиста записи с вариантами. Запись с вариантами состоит из двух частей. В первой части описываются поля, общие для всех групп объектов, моделируемых записью. Среди этих полей обычно бывает поле, значение которого позволяет идентифицировать группу, к которой данный объект принадлежит и, следовательно, какой из вариантов второй части записи должен быть использован при обработке. Вторая часть записи содержит описания непересекающихся свойств - для каждого подмножества таких свойств - отдельное описание. Язык программирования может требовать, чтобы имена полей-свойств не повторялись в разных вариантах (PASCAL), или же требовать именования каждого варианта (C). В первом случае идентификация поля, находящегося в вариантной части записи при обращении к нему ничем не отличается от случая простой записи:

< имя переменной-записи >.< имя поля >

Во втором случае идентификация немного усложняется:

< имя переменной-записи >.< имя варианта >.< имя поля >

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

Запись с вариантами для такой задачи в языке PASCAL выглядит, как:

type figure = record fig_type : char; { тип фигуры } x0, y0 : word; { координаты опорной точки } color : byte; { цвет } case fig_t : char of 'C': ( radius : word); { радиус окружности } 'R': (len1, len2 : word); { длины сторон прямоугольника } 'T': (x1,y1,x2,y2 : word); { координаты двух вершин } end;

а в языке C, как:

typedef struct { char fig_type; /* тип фигуры */ unsigned int x0, y0; /* координаты опорной точки */ unsigned char color; /* цвет */ union { struct { unsigned int radius; /* радиус окружности */ } cyrcle; struct { unsigned int len1, len2; /* длины сторон прямоугольника */ } rectangle; struct { unsigned int x1,y1,x2,y2; /* координаты двух вершин */ } triangle; } fig_t; } figure;

И если в программе определена переменная fig1 типа figure, в которой хранится описание окружности, то обращение к радиусу этой окружности в языке PASCAL будет иметь вид: fig1.radius, а в C: fig1.circle.radius

Поле с именем fig_type введено для представления идентификатора вида фигуры, который, например, может кодироваться символами: "C"- окружность или "R"- прямоугольник, или "T"- треугольник.

Выделение памяти для записи с вариантами показано на рис.3.12.