Xreferat.com » Рефераты по информатике и программированию » Структуры Данных и Абстракции Данных

Структуры Данных и Абстракции Данных

Хотя термины тип данных (или просто тип), структура данных и абстрактный тип данных звучат похоже, но имеют они различный смысл. В языках программирования тип данных переменной обозначает множество значений, которые может принимать эта переменная. Например, переменная булевого (логического) типа может принимать только два значения: значение true (истина) и значение false (ложь) и никакие другие. Набор базовых типов данных отличается в разных языках: в языке Pascal это типы целых (integer) и действительных (real) чисел, булев (boolean) тип и символьный (char) тип. Правила конструирования составных типов данных (на основе базовых типов) также различаются в разных языках программирования: Pascal легко и быстро строит такие типы.

Абстрактный тип данных (АТД) – это математическая модель плюс различные операторы, определённые в рамках этой модели. Мы можем разрабатывать алгоритм в терминах АТД, но для реализации алгоритма в конкретном языке программирования необходимо найти способ представления АТД в терминах типов данных и операторов, поддерживаемых данным языком программирования. Для представления АТД используются структуры данных, которые представляют собой набор переменных, возможно, различных типов данных, объединённых определённым образом.

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

В качестве простейшего механизма агрегирования ячеек в Pascal и большинстве других языков программирования можно применять (одномерный) массив, т.е. последовательность ячеек определённого типа. Массив также можно рассматривать как отображение множества индексов (таких как целые числа 1, 2, …, n) в множество ячеек. Ссылка на ячейку обычно состоит из имени массива и значения из множества индексов данного массива. В Pascal множество индексов может быть нечислового типа, например (север, восток, юг, запад), или интервального типа как (1..10).Значения всех ячеек массива должны иметь одинаковый тип данных. Объявление

Имя: array[ТипИндекса] of ТипЯчеек;

задаёт имя для последовательности ячеек, тип для элементов множества индексов и тип содержимого ячеек.

Кстати, Pascal необычайно богат на типы индексов. Многие языки программирования позволяют использовать в качестве индексов только множества последовательных целых чисел. Например, чтобы в языке Fortran в качестве индексов массива можно было использовать буквы, надо всё равно использовать целые индексы, заменяя «А» на 1, «В» на 2, и т.д.

Другим общим механизмом агрегирования ячеек в языке программирования является структура записи. Запись (record) можно рассматривать как ячейку, состоящую из нескольких других ячеек (называемых полями), значения в которых могут быть разных типов. Записи часто группируются в массивы; тип данных определяется совокупностью типов полей записи. Например, в Pascal объявление

var

reclist: array[1..4] of record

data: real;

next: integer;

end

задаёт имя reclist (список записей) 4-элементного массива, значениями которого являются записи с двумя полями: data (данные) и next (следующий).

Третий метод агрегирования ячеек, который можно найти в Pascal и некоторых других языках программирования, - это файл. Файл, как и одномерный массив, является последовательностью значений определённого типа. Однако файл не имеет индексов: его элементы доступны только в том порядке, в каком они были записаны в файл. В отличие от файла, массивы и записи являются структурами с «произвольным доступом», подразумевая под этим, что время доступа к компонентам массива и записи не зависит от значения индекса массива или указателя поля записи. Достоинство агрегирования с помощью файла (частично компенсирующее описанный недостаток) заключается в том, что файл не имеет ограничения на количество составляющих его элементов и это количество может изменяться во время выполнения программы.

Указатели и курсоры

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

В языке Pascal с помощью следующего объявления можно создать переменную – указатель prt, указывающую на ячейку определённого типа, например ТипЯчейки:

var

prt: ТипЯчейки

Постфикс в виде стрелки, направленной вверх, в Pascal используется как оператор разыменования, т.е. выражение prt обозначает значение (типа ТипЯчейки) в ячейке, указанной prt.

Курсор (cursor) – это ячейка с целочисленным значением, используемая для указания на массив. В качестве способа указания курсор работает так же, как и указатель, но курсор можно использовать и в языках (подобных Fortran), которые не имеют явного типа указателя. Интерпретировав целочисленную ячейку как индексное значение для массива, можно эффективно реализовать указания на ячейки массива. К сожалению, этот приём подходит только для ячеек массива и не позволяет организовать указания на ячейки, не являющиеся частью массива.

В схемах структур данных будет рисоваться стрелка из ячейки курсора к ячейке, на которую указывает курсор. Иногда также будет показываться целое число в ячейке курсора, напоминая тем самым, что это не настоящий указатель. Можно заметить, что механизм указателя Pascal разрешает ячейкам массива только «быть указанными» с помощью курсора, но не быть истинным указателем. Другие языки программирования, подобные PL/1 или С, позволяют компонентам массивов быть истинными указателями и, конечно, «быть указанным» с помощью курсора. В отличие от этих языков, в языках Fortran и Algol, где нет типа указателя, можно использовать только курсоры.

Пример1. На рис.1 показана структура данных, состоящая из двух частей. Она имеет цепочку ячеек, содержащих курсоры для массива reclist (список записей), определённого выше. Назначение поля next (следующий) заключается в указании на следующую запись в массиве reclist. Например, reclist[4].next равно 1, поэтому запись 4 предшествует записи 1. полагая первой запись 4, в соответствии со значениями поля next получим следующий порядок записей: 4, 1, 3, 2. Отметим, что значение поля next в записи 2, равное 0, указывает на то, что нет следующей записи. Целесообразно принять соглашение, что число 0 будет обозначать нуль-указатель при использовании курсоров и указателей. Но, чтобы не возникали проблемы при реализации этого соглашения, необходимо также условиться, что массивы, на которые указывают курсоры, индексируются начиная с 1, а не с 0.

4

2

header

    1. 3


3.4 0

5.6 2

7.8 1



1

2

3

4

data next

Рис.1Пример структуры данных.

Ячейки в цепочке 1 имеют тип

type

recordtype = record

cursor: integer;

prt recordtype

end

На цепочку можно ссылаться с помощью переменной header (заголовок), имеющей тип recordtype, header указывает на анонимную запись типа recordtype 1 .Эта запись имеет 4 значения в поле cursor. Рассматривается 4 как индекс массива reclist. Эта запись имеет истинный указатель в поле prt на другую анонимную запись, которая, в свою очередь, указывает на индекс 4 массива reclist и имеет нуль-указатель в поле prt.

Абстрактный тип данных «Список».

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

В математике список представляет собой последовательность элементов определённого типа, который в общем случае будет обозначаться как elementtype (тип элемента). Список будет часто представляться в виде последовательности элементов, разделённых запятыми: a1, a2, …, an, где n > 0 и все ai имеют тип elementtype. Количество элементов n будет называться длиной списка. Если n > 1 ,то а1 называется первым элементом списка. В случае n = 0 список будет называться пустым, т.е. не содержащий элементов.

Важное свойство списка заключается в том, что его элементы можно линейно упорядочить в соответствии с их позицией в списке. Говорится, что элемент аi предшествует аi+1 для i = 1, 2, …, n-1 и аi следует за ai-1 для i = 2, 3, …, n. Говорится также, что элемент аi имеет позицию i. Кроме того, постулируется существование позиции, следующей за последним элементом списка. Функция END(L) будет возвращать позицию, следующую за позицией n в n-элементном списке L. Следует отметить, что позиция END(L), рассматриваемая как расстояние от начала списка, может изменяться при уменьшении или увеличении списка, в то время как другие позиции имеют фиксированное (неизменное) расстояние от начала списка.

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

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

Теперь перейдём к непосредственному определению множества операторов списка. Примем обозначения: L – список объектов типа elementtype, x – объект этого типа, p – позиция элемента в списке. Следует отметить, что «позиция» имеет другой тип данных, чья реализация может быть различной для разных реализаций списков. Обычно позиция понимается как множество целых положительных чисел, но на практике могут встретиться другие представления.

INSERT(x, p, L). Этот оператор вставляет объект х в позицию р и далее в следующую, более высокую позицию. Таким образом, если список L состоит из элементов а1, a2, …,an, то после выполнения этого оператора он будет иметь вид а1, a2, …, ap-1, x, ap, …, an. Если р принимает значение END(L), то будем иметь a1, a2, …, an, x. Если в списке L нет позиции р, то результат выполнения этого оператора не определён.

LOCATE(x, L). Эта функция возвращает позицию объекта х в списке L.если в списке объект х встречается несколько раз, то возвращается позиция первого от начала списка объекта х. Если объекта х нет в списке L, то возвращается END(L).

RETRIEVE(p, L). Эта функция возвращает элемент, который стоит в позиции р в списке L. Результат не определён, если p = END(L) или в списке L нет позиции p. Элементы должны быть одного типа, который в принципе может возвращать функция. Однако на практике мы всегда можем изменить эту функцию так, что она будет возвращать указатель на объект типа elementtype.

DELETE(p, L). этот оператор удаляет элемент в позиции p списка L. Так, если список L состоит из элементов a1, a2, …, an, то после выполнения этого оператора он будет иметь вид a1, a2, …, ap-1, ap+1, …, an. Результат не определён, если в списке L нет позиции p или p = END(L).

NEXT(p, L) и PREVIOUS(p, L). Эти функции возвращают соответственно следующую и предыдущую позиции от позиции p в списке L.если р – последняя позиция в списке L, то NEXT(p, L) = END(L). Функция NEXT не определена, когда p = END(L). Функция PREVIOUS не определена, если p = 1. Обе функции не определены, если в списке L нет позиции p.

MAKENULL(L). Эта функция делает список L пустым и возвращает позицию END(L).

FIRST(L). Эта функция возвращает первую позицию в списке L. Если список пустой, то возвращается позиция END(L).

8. PRINTLIST(L). Печатает элементы списка L в порядке их расположения.

Стеки.

Стек – это специальный тип списка, в котором все вставки и удаления выполняются только на одном конце, называемом вершиной (top). Стеки также иногда называют «магазинами», а в английской литературе для обозначения стеков ещё используется аббревиатура LIFO (last-in-first-out – последний вошел – первый вышел). Интуитивными моделями стека могут служить колода карт на столе при игре в покер, книги, сложенные в стопку, или стопка тарелок на полке буфета; во всех этих моделях взять можно только верхний предмет, а добавить новый объект можно, только положив его на верхний. Абстрактные типы данных семейства STAK (Стек) обычно используют следующие пять операторов.

MAKENULL(S). Делает стек S пустым.

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

POP(S). Удаляет из вершины стека (выталкивает из стека), в терминах операторов списка этот оператор можно записать как DELETE(FIRST(S), S). Иногда этот оператор реализуется в виде функции, возвращающей удаляемый элемент.

PUSH(x, S). Вставляет элемент x в вершину стека S (заталкивает элемент в стек). Элемент, ранее находившийся в вершине стека, становится элементом, следующим за вершиной, и т.д. В терминах общих операторов списка данный оператор можно записать как INSERT(x, FIRST(S), S).

EMPTY(S). Эта функция возвращает значение true (истина), если стек S пустой, и значение false (ложь) в противном случае.

Очереди.

Другой специальный тип списка – очередь (queue), где элементы вставляются с одного конца, называемого задним (rear), а удаляются с другого, переднего (front). Очереди также называют «списками типа FIFO» (аббревиатура FIFO расшифровывается как first-in-first-out: первым вошел – первым вышел). Операторы, выполняемые над очередями, аналогичны операторам стеков. Существенное отличие между ними состоит в том, что вставка новых элементов осуществляется в конец списка, а не в начало, как в стеках. Кроме того, различна устоявшаяся терминология для стеков и очередей. Для работы с очередями будут использоваться следующие операторы.

MAKENULL(Q) очищает очередь Q, делая её пустой.

FRONT(Q) – функция, возвращающая первый элемент очереди Q. Можно реализовать эту функцию с помощью операторов списка как RETRIEVE(FIRST(Q), Q).

ENQUEUE(x, Q) вставляет элемент x в конец очереди Q. С помощью операторов списка этот оператор можно выполнить следующим образом: INSERT(x, END(Q), Q).

DEQUEUE(x, Q) удаляет первый элемент очереди Q. Также реализуем с помощью операторов списка как DELETE(FIRST(Q), Q).

EMPTY(Q) возвращает значение true тогда и только тогда, когда Q является пустой очередью.

Отображения.

Отображение – это функция, определённая на множестве элементов (области определения) одного типа (будет обозначаться domaintype – тип области определения функции) и принимающая значения из множества элементов (области значений) другого типа, этот тип будет обозначаться rangetype – тип области значений (конечно, типы domaintype и rangetype могут совпадать). Тот факт, что отображение М ставит в соответствие элемент d типа domaintype из области определения элементу r типа rangetype из области значений, будет записываться как M(d) = r.

Некоторые отображения, подобные square(i) = i2, легко реализовать с помощью функций и арифметических выражений языка Pascal. Но для многих отображений нет очевидных способов реализации, кроме хранения для каждого d значения M(d). Например, для реализации функции, ставящей в соответствие работникам их недельную зарплату, требуется хранить текущий заработок каждого работника.

Рассмотрим операторы, которые можно выполнить над отображением М. Например, по заданному элементу d типа domaintype мы хотим получить M(d) или узнать, определено ли M(d) (т.е. узнать, принадлежит ли элемент d области определения М). Или хотим добавить новые элементы в текущую область определения М и поставить им в соответствие элементы из области значений. Очевидна также необходимость иметь оператор, который изменял бы значение M(d). Кроме того,
Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: