ЛОЙКО В И СТРУКТУРЫ И АЛГОРИТМЫ ОБРАБОТКИ ДАННЫХ КРАСНОДАР 2004 261 С 2

  TYPE = (Красный, Зеленый, Синий)     Операции те же, что и для символьного типа.   1.6.2 Диапазонный или интервальный   В любом порядковом типе можно выделить подмножество значений, определяемое минимальным и максимальным значениями, в которое входят все значения исходного типа, находящиеся в этих границах, включая сами границы. Такое подмножество определяет диапазонный тип. Он задаётся указанием минимального и максимального значений, разделенных двумя точками.     TYPE T=[ MIN..MAX ]

  TYPE =[1..60]     Минимальное значение при определении такого типа не должно быть больше максимального.     Контрольные вопросы:  1. Каковы основные характеристики структур данных?  2. Какие типы данных вы знаете ?  3. Какие из них относятся к стандартным, а какие к пользовательским ?  4. Как представляются вещественные числа ?  5. Что представляют собой данные логического типа ?  6. Какие типы данных относятся к стандартным пользовательским ?  7. Какому условию должны удовлетворять допустимые числа типа INTEGER ?  8. Какие операции можно производить над целыми числами ?  9. Перечислите булевские операции.  10. Какова структура типа CHAR ?  11. Какие операции возможны над данными этого типа ?  12. Что можно вычислить с помощью данных указательного типа ?  13. Что представляет собой перечисляемый тип данных?  14. Как задается диапазонный тип ?    2. СТАТИЧЕСКИЕ И ПОЛУСТАТИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ     Структуры данных — это совокупность элементов данных и отношений между ними. При этом под элементами данных может подразумеваться как простое данное так и структура данных. Под отношениями между данными понимают функциональные связи между ними и указатели на то, где находятся эти данные.   Графическое представление элемента структуры данных.             Элемент отношений — это совокупность всех связей элемента с другими элементами данных, рассматриваемой структуры.   S:=(D,R)   Где S — структура данных, D — данные и R — отношения.   Как бы сложна ни была структура данных, в конечном итоге она состоит из простых данных (см. рис. 2.2, 2.3).               2.1 Уровни представления данных     Внутренний мир ЭВМ далеко не так прост, как мы думаем. Память машины состоит из миллионов триггеров, которые обрабатывают поступающую информацию   Мы, занося информацию в компьютер, представляем ее в каком-то виде, который на наш взгляд упорядочивает данные и придает им смысл. Машина отводит поле для поступающей информации и задает ей какой-то адрес. Таким образом получается, что мы обрабатываем данные на логическом уровне, как бы абстрактно, а машина делает это на физическом уровне.         Последовательность переходов от логической организации к физической показана на рис. 2.4.    2.2 Классификация структур данных     Структуры данных классифицируются:   1. По связанности данных в структуре:   — если данные в структуре связаны очень слабо, то такие структуры называются несвязанными (вектор, массив, строки, стеки)   — если данные в структуре связаны, то такие структуры называются связанными (связанные списки)   2. По изменчивости структуры во времени или в процессе выполнения программы:   — статические структуры — структуры, неменяющиеся до конца выполнения программы (записи, массивы, строки, вектора)   — полустатические структуры (стеки, деки, очереди)   — динамические структуры — происходит полное изменение при выполнении программы   3. По упорядоченности структуры:   — линейные (вектора, массивы, стеки, деки, записи)   — нелинейные (многосвязные списки, древовидные структуры, графы)   Наиболее важной характеристикой является изменчивость структуры во времени.     2.3 Статические структуры данных     2.3.1 Векторы   Самая простая статическая структура — это вектор. Вектор — это чисто линейная упорядоченная структура, где отношение между ее элементами есть строго выраженная последовательность элементов структуры (рис. 2.5).       Каждый элемент вектора имеет свой индекс, определяющий положение данного элемента в векторе. Поскольку индексы являются целыми числами, над ними можно производить операции и, таким образом, вычислять положение элемента в структуре на логическом уровне доступа. Для доступа к элементу вектора, достаточно просто указать имя вектора (элемента) и его индекс .   Для доступа к этому элементу используется функция адресации, которая формирует из значения индекса адрес слота, где находится значение исходного элемента. Для объявления в программе вектора необходимо указать его имя, количество элементов и их тип (тип данных)   Пример:   var   M1: Array [1..100] of integer;   M2: Array [1..10] of real;     Вектор состоит из совершенно однотипных данных и количество их строго определено.     2.3.2 Массивы   В общем случае элемент массива — это есть элемент вектора, который сам по себе тоже является элементом структуры (рис. 2.6).         Для доступа к элементу двумерного массива необходимы значения пары индексов (номер строки и номер столбца, на пересечении которых находится элемент). На физическом уровне двумерный массив выглядит также, как и одномерный (вектор), причем трансляторы представляют массивы либо в виде строк, либо в виде столбцов.     2.3.3 Записи   Запись представляет из себя структуру данных последовательного типа, где элементы структуры расположены один за другим как в логическом, так и в физическом представлении. Запись предполагает множество элементов разного типа. Элементы данных в записи часто называют полями записи.   Пример:       Логическая структура записи может быть представлена как в графическом виде, так и в табличном.               Элемент записи может включать в себя записи. В этом случае возникает сложная иерархическая структура данных.     Пример:   Необходимо заполнить запись о студенте, содержащую следующую информацию: N — порядковый номер студента; Имя студента, в составе которого должны быть: Фамилия, Имя, Отчество; Анкетные данные студента: год рождения, место рождения, родители: мать, отец; Факультет; Группа; Оценки, полученные в сессию: по английскому языку и микропроцессорам.   Ниже приведены два логических представления структуры этой записи.         Получена четырехуровневая иерархическая структура данных. Информация содержится в листьях, остальные узлы служат для указания пути к листьям.   1-ый уровень Студент = запись   2-ой уровень Номер   2-ой уровень Имя = запись   3-ий уровень Фамилия   3-ий уровень Имя   3-ий уровень Отчество   2-ой уровень Анкетные данные = запись   3-ий уровень Место рождения   3-ий уровень Год рождения   3-ий уровень Родители = запись   4-ый уровень Мать   4-ый уровень Отец   2-ой уровень Факультет   2-ой уровень Группа   2-ой уровень Оценки = запись   3-ий уровень Английский   3-ий уровень Физика     Эта структура называется вложенной записью.     Операции над записями:  1. Прочтение содержимого поля записи.  2. Занесение информации в поле записи.  3. Все операции, которые разрешаются над полем записи, соответствующего типа.     2.3.4 Таблицы   Таблица — это конечный набор записей (рис. 2.11).         При задании таблицы указывается количество содержащихся в ней записей.     Пример:     Type ST = Record   Num: Integer;   Name: String[15];   Fak: String[5];   Group: String[10];   Angl: Integer;   Physic: Integer;     var   Table: Array [1..19] of St;     Элементом данных таблицы является запись. Поэтому операции, которые производятся с таблицей — это операции, производимые с записью.     Операции с таблицами:   1. Поиск записи по заданному ключу.   2. Занесение новой записи в таблицу.     Ключ — это идентификатор записи. Для хранения этого идентификатора отводится специальное поле.   Составной ключ — ключ, содержащий более двух полей.     2.4 Полустатические структуры данных     К полустатическим структурам данных относят стеки, деки и очереди.   Списки   Это набор связанных элементов данных, которые в общем случае могут быть разного типа.   Пример списка:   E1, E2, …….., En,… n > 1 и не зафиксировано.   Количество элементов списка может меняться в процессе выполнения программы. Различают 2 вида списков:   1) Несвязные   2) Связные   В несвязных списках связь между элементами данных выражена неявно. В связных списках в элемент данных заносится указатель связи с последующим или предыдущим элементом списка.   Стеки, деки и очереди — это несвязные списки. Кроме того они относятся к последовательным спискам, в которых неявная связь отображается их последовательностью.     2.4.1 Стеки   Очередь вида LIFO (Last In First Out — Последним пришел, первым ушел ), при которой на обслуживание первым выбирается тот элемент очереди, который поступил в нее последним, называется стеком. Это одна из наиболее употребляемых структур данных, которая оказывается весьма удобной при решении различных задач.   В силу указанной дисциплины обслуживания, в стеке доступна единственая его позиция, которая называется вершиной стека- это позиция, в которой находится последний по времени поступления в стек элемент. Когда мы заносим новый элемент в стек, то он помещается поверх прежней вершины и теперь уже сам находится в вершине стека. Выбрать элемент можно только из вершины стека; при этом выбранный элемент исключается из стека, а в его вершине оказывается элемент, который был занесен в стек перед выбранным из него элементом (структура с ограниченным доступом к данным).   Графически стек можно представить следующим образом:         Первый элемент заносится вниз стека . Выборка из стека осуществляется с вершины, поэтому стек является структурой с ограниченным доступом.     Операции, производимые над стеками:     1. Занесение элемента в стек.   Push(S,I), где S — идентификатор стека, I — заносимый элемент.   2. Выборка элемента из стека.   Pop(S)   3. Определение пустоты стека.   Empty(S)   4. Прочтение элемента без его выборки из стека.   StackTop(S)     Пример реализации стека на Паскале с использованием одномерного массива:     type   Stack = Array[1..10] of Integer; {стек вместимостью 10 элементов типа Integer}     var   StackCount: Integer; {Переменная — указатель на вершину стека, ее начальное значение должно быть равно 0}   S: Stack; {Объявление стека}     Procedure Push(I: Integer; var S: Stack);   begin   Inc(StackCount);   S[StackCount]:=I;   end;     Procedure Pop(var I: Integer; S: Stack);   begin   I:=S[StackCount];   Dec(StackCount);   end;     Function Empty: Boolean;   begin   If I = 0 then Empty:=True Else Empty:=False;   end;     При выполнении операции выборки из стека сначала необходимо осуществить проверку на пустоту стека. Если он пуст, то Empty возвращает значение True. Если Empty возвращает False, то это означает, что стек не пуст и из него еще можно выбирать элементы.     Procedure StackTop(var I: Integer; S: Stack);   begin   I:=S[StackCount];   end;     2.4.2 Очередь   Понятие очереди всем хорошо известно из повседневной жизни. Элементами очереди в общем случае являются заказы на то или иное обслуживание.   В программировании имеется структура данных, которая называется очередью. Эта структура данных используется, например, для моделирования реальных очередей с целью определения их характеристик при данном законе поступления заказов и дисциплине их обслуживания. По своему существу очередь является полустатической структурой- с течением времени и длина очереди, и состав могут изменяться.   На рис. 2. 13 приведена очередь, содержащая четыре элемента — А, В, С и D. Элемент А расположен в начале очереди, а элемент D — в ее конце. Элементы могут удаляться только из начала очереди, то есть первый помещаемый в очередь элемент удаляется первым. По этой причине очередь часто называют списком, организованным по принципу «первый размещенный первым удаляется» в противоположность принципу стековой организации — «последний размещенный первым удаляется».   Дисциплину обслуживания, в которой заказ, поступивший в очередь первым, выбирается первым для обслуживания (и удаляется из очереди), называется FIFO (First In First Out — Первым пришел, первым ушел). Очередь открыта с обеих сторон.   Таким образом, изъятие компонент происходит из начала очереди, а запись- в конец. В этом случае вводят два указателя: один — на начало очереди, второй- на ее конец.   Реальная очередь создается в памяти ЭВМ в виде одномерного массива с конечным числом элементов, при этом необходимо указать тип элементов очереди, а также необходима переменная в работе с очередью.         Физически очередь занимает сплошную область памяти и элементы следуют друг за другом, как в последовательном списке.     Операции, производимые над очередью:   Для очереди определены три примитивные операции. Операция insert (q,x) помещает элемент х в конец очереди q. Операция remove(q) удаляет элемент из начала очереди q и присваивает его значение переменной х. Третья операция, empty (q), возвращает значение true или false в зависимости от того, является ли данная очередь пустой или нет. Кроме того. Учитывая то, что полустатическая очередь реализуется на одномерном массиве, необходимо следить за возможностью его переполнения. Сэтой целью вводится опнрация full(q).   Операция insert может быть выполнена всегда, поскольку на количество элементов, которые может содержать очередь, никаких ограничений не накладывается. Операция remove, однако, применима только к непустой очереди, поскольку невозможно удалить элемент из очереди, не содержащей элементов. Результатом попытки удалить элемент из пустой очереди является возникновение исключительной ситуации потеря значимости. Операция empty, разумеется, выполнима всегда.     Пример реализации очереди в виде одномерного массива на Паскале:   const   MaxQ = …

Пролистать наверх