Pascal/С

Function IsEmptyTree(var T:Tree):boolean;{пустое дерево ?}

Procedure DelTree(var T:Tree);{удаление листа}

Спецификация СД на языке C:

#if !defined(__TREE7_H)

#define Index 1000

const TreeOk = 0;

const TreeNotMem = 1;

const TreeUnder = 2;

typedef void *BaseType;

typedef unsigned PtrEl;

typedef struct element{basetype data;

ptrel LSon;

ptrel RSon;}

typedef Element Mem[Index];

typedef Mem *Pmem;

typedef PtrEl *Tree;

short TreeError;

Pmem Pbuf; //указатель на массив

unsigned Size; //размер массива

unsigned SizeEl;

void InitTree(Tree *T,unsigned size)// инициализация дерева

void CreateRoot(Tree *T) //создание корня

void WriteDataTree(Tree *T, BaseType E) //запись данных

void ReadDataTree(Tree *T,BaseType *E)//чтение

int IsLSon(Tree *T)//1 -- есть левый сын, 0 -- нет

int IsRSon(Tree *T)//1 -- есть правый сын, 0 -- нет

void MoveToLSon(Tree *T, Tree *TS)// перейти к левому сыну, где T -- адрес ячейки, содержащей адрес текущей вершины, TS -- адрес ячейки, содержащей адрес корня левого поддерева(левого сына)

void MoveToRSon(Tree *T, Tree *TS)//перейти к правому сыну

int IsEmptyTree(Tree *T)//1 -- пустое дерево,0 -- не пустое

void DelTree(Tree *T)//удаление листа

#endif

8. Элементы дерева находятся в массиве, расположенном в динамической памяти. Базовый тип - произвольный. Каждый элемент массива имеет признак того, является ли он элементом дерева или «свободен». Корень дерева находится в первом элементе массива. Для вершины дерева, расположенной в n-м элементе массива, LSon будет находиться в (2*n)-м элементе, а RSon -- в (2*n + 1)-м.

Спецификация СД на языке Pascal:

Unit Tree8;

Interface

Const TreeOk = 0;

TreeNotMem = 1;

TreeUnder = 2;

Type BaseType = pointer;

Index = 0..65520 div sizeof(BaseType);

PtrEl = Index;

Element = Record Data : BaseType;

Flag : Boolean;{FALSE - элемент свободен}

{TRUE - элемент дерева }

End;

Mem = array[Index] of Element;

Pmem= ^Mem;

Tree= record

Pbuf: Pmem; {указатель на массив}

Size: word; {размер массива}

Ptr: PtrEl

end;

Var TreeError : 0..2;

SizeEl: word; {размер элемента}

Procedure InitTree(var T:Tree; Size: word); {инициализация}

Procedure CreateRoot(var T:Tree); {создание корня}

Procedure WriteDataTree(var T:Tree; E:BaseType);{запись данных}

Procedure ReadDataTree(var T:Tree;var E:BaseType);{чтение}

Function IsLSon(var T:Tree):boolean;{есть левый сын ?}

Function IsRSon(var T:Tree):boolean;{есть правый сын ?}

Procedure MoveToLSon(var T:Tree); {перейти к левому сыну}

Procedure MoveToRSon(var T:Tree); {перейти к правому сыну}

Function IsEmptyTree(var T:Tree):boolean;{пустое дерево ?}

Procedure DelTree(var T:Tree);{удаление листа}

Спецификация СД на языке C:

#if !defined(__TREE8_H)

#define Index 1000

const TreeOk = 0;

const TreeNotMem = 1;

const TreeUnder = 2;

typedef void *BaseType;

typedef unsigned PtrEl;

typedef struct element{basetype data;

short flag;};//0 -- элемент занят

//1 -- элемент свободен

typedef Element Mem[Index];

typedef Mem *Pmem;

typedef struct Tree{Pmem Pbuf; //указатель на массив

unsigned Size; //размер массива

PtrEl Ptr;};

short TreeError;

unsigned SizeEl;//размер элемента

void InitTree(Tree *T,unsigned size)// инициализация дерева

void CreateRoot(Tree *T) //создание корня

void WriteDataTree(Tree *T, BaseType E) //запись данных

void ReadDataTree(Tree *T,BaseType *E)//чтение

int IsLSon(Tree *T)//1 -- есть левый сын, 0 -- нет

int IsRSon(Tree *T)//1 -- есть правый сын, 0 -- нет

void MoveToLSon(Tree *T, Tree *TS)// перейти к левому сыну, где T -- адрес ячейки, содержащей адрес текущей вершины, TS -- адрес ячейки, содержащей адрес корня левого поддерева(левого сына)

void MoveToRSon(Tree *T, Tree *TS)//перейти к правому сыну

int IsEmptyTree(Tree *T)//1 -- пустое дерево,0 -- не пустое

void DelTree(Tree *T)//удаление листа

#endif

Назначение процедур и функций:

InitTree -- инициализация дерева;

CreateRoot -- создание корня;

WriteDataTree -- запись данных в дерево;

ReadDataTree -- чтение элемента дерева;

IsLSon -- проверка на наличие левого сына;

IsRSon -- проверка на наличие правого сына;

MoveToLSon -- переход к левому сыну;

MoveToRSon -- переход к правому сыну;

IsEmptyTree -- проверка: дерево пусто или нет;

DelTree -- удаление листа.

Содержание отчета

1. Тема лабораторной работы.

2. Цель работы.

3. Характеристика СД «дерево» (п.1 задания).

4. Индивидуальное задание.

5. Тексты модулей на языках Pascal и С для реализации СД «дерево», тексты программ для отладки модулей, тестовые данные и результат работы программ.

6. Тексты программ на языках Pascal и С для решения задачи с использованием модулей, тестовые данные, результаты работы программ.

Теоретические сведения

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

1) Имеется одна специально обозначенная вершина, называемая корнем данного дерева.

2) Остальные вершины (исключая корень) содержатся в m 0 попарно непересекающихся множествах Т1, Т2, …, Тm, каждое из которых в свою очередь является деревом. Деревья Т1, Т2, …, Тm называются поддеревьями данного корня.

Наиболее наглядным способом представления дерева является графический (рис.20), в котором вершины изображаются окружностями с вписанной в них информацией и корень дерева соединяется с корнями поддеревьев Т1, Т2, …, Тm, дугой (линией).

Рис.20. Графический способ представления дерева

Если подмножества Т1, Т2, …, Тm упорядочены, то дерево называют упорядоченным. Если два дерева считаются равными и тогда, когда они отличаются порядком подмножеств Т1, Т2, …, Тm, то такие деревья называются ориентированными деревьями. Конечное множество непересекающихся деревьев называется лесом.

Количество подмножеств для данной вершины называется степенью вершины. Если такое количество равно нулю, то вершина является листом. Максимальная степень вершины в дереве -- степень дерева. Уровень вершины -- длина пути от корня до вершины. Максимальная длина пути от корня до вершины определяет высоту дерева (количество уровней в дереве).

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

Рис.21. Графическое представление БД

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

Кардинальное число СД БД определяется по формуле

CAR(БД) = ((2i)! / ((i + 1)(i!)2))·CAR(BaseType) + 1 ,i=1…max,

где CAR(BaseType) -- кардинальное число элемента БД типа BaseType, max -- максимальное количество элементов в БД (не всегда определено, т.к. может зависеть от объема свободной динамической памяти).

На абстрактном уровне БД представляет собой иерархическую структуру -- дерево.

На физическом уровне БД реализуется связной схемой хранения. Располагаться БД может в статической или динамической памяти.

Принципы размещения бинарного дерева в памяти ЭВМ

1. БД располагается в динамической памяти. Каждая вершина БД представляет собой СД типа «запись», содержащую информационную часть и адреса сыновей. Память под вершину БД выделяется по мере надобности при построении БД и освобождается при исключении вершины. Адрес корня дерева находится в специальной ячейке динамической памяти, адрес которой хранится в статической памяти. БД (см. рис.21)может быть представлено в памяти так, как показано на рис.22.

2. Для хранения вершин БД используется СД типа «массив». Массив может располагаться в статической или динамической памяти. Элементы массива представляют собой СД типа «запись», содержащую информационную часть и адреса сыновей вершины БД. Индекс элемента массива, содержащего корень дерева, находится в специальной ячейке динамической памяти, адрес которой хранится в статической памяти. Элементы массива, не являющиеся вершинами БД, объединяются в список свободных элементов (ССЭ), на первый элемент которого указывает правый сын первого элемента массива. При включении элемента в БД берется первый элемент ССЭ, а исключаемый элемент заносится в начало ССЭ. БД (рис.21) может быть представлено в памяти так, как показано на рис.23. При таком способе в одном массиве может быть размещено несколько БД.

3. Для хранения вершин БД используется СД типа «массив». Массив может располагаться в статической или динамической памяти. Элементы массива представляют собой СД типа «запись», содержащую информационную часть вершны БД и признак использования элемента массива -- 1 -- если элемент содержит вершину БД, 0 -- если элемент свободен. Корнем дерева является элемент массива с индексом 1, индекс левого сына вычисляется по формуле i*2, где i -- индекс отца, а правый сын располагается в следующем (i*2 + 1) элементе массива. БД (см. рис.21) может быть представлено в памяти так, как показано на рис.24.

Статическая адрес ячейки, содержащей

память адрес корня дерева

адрес корня дерева

Динамическая

память

Рис.22. Представление БД в памяти

Рис.7.4



Рис.24. Представление БД в памяти

Алгоритмы обхода бинарного дерева

Пусть в памяти ЭВМ находится БД. Задача обхода БД состоит в том, чтобы вывести информационную часть каждой вершины БД. Порядок прохождения вершин определяет алгоритм обхода БД. Рассмотрим некоторые алгоритмы обхода БД.

Обход бинарного дерева «в глубину» (в прямом порядке)

Чтобы пройти БД в прямом порядке нужно выполнить следующие три операции:

1. Попасть в корень.

2. Пройти в прямом порядке левое поддерево.

3. Пройти в прямом порядке правое поддерево.

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

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

Итеративный алгоритм прохождения БД «в глубину»:

1. Инициализировать стек.

2. Пройти корень T и включить его адрес в стек.

3. Если стек пуст, то перейти к п.5. Если есть левый сын вершины T, то пройти его и занести его адрес в стек, иначе извлечь из стека адрес вершины Т и если у нее есть правый сын, то пройти его и занести в стек.

4. Перейти к п.3.

5. Конец алгоритма.

Обход бинарного дерева «в ширину» (по уровням)

В этом обходе сначала выписывается корень, затем вершины первого уровня, второго и т.д. до последнего. Выполнив обход БД на рис.21, получим последовательность: ABGCFHDEIJ.

В алгоритме обхода БД «в ширину» будем использовать очередь, в которую будут помещаться адреса вершин в порядке обхода.

Алгоритм прохождения БД «в ширину»:

1. Инициализировать очередь.

2. Занести адрес корня T в очередь.

3. Если очередь пуста, то перейти к п.5. Извлечь из очереди адрес вершины T и пройти ее. Если у нее есть левый сын, то занести его адрес в очередь. Если у нее есть правый сын, то занести его адрес в очередь.

4. Перейти к п.3.

5. Конец алгоритма.

Обход бинарного дерева в симметричном порядке

Для прохождения БД в симметричном порядке нужно выполнить следующие действия:

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

2. Попасть в корень.

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

Выполнив обход в симметричном порядке БД на рис.21, получим последовательность: DCEBFAGIHJ.

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

Итеративный алгоритм прохождения БД в симметричном порядке:

1. Инициализировать стек.

2. Адрес корня T включить в стек.

3. Если стек пуст, то перейти к п.5. Если есть левый сын вершины T, то занести его адрес в стек, иначе извлечь из стека адрес вершины Т, пройти ее и если у нее есть правый сын, то занести его в стек.

4. Перейти к п.3.

5. Конец алгоритма.

Обход бинарного дерева в обратном порядке

Для прохождения БД в обратном порядке нужно выполнить следующие действия:

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

2. Пройти в обратном порядке правое поддерево.

3. Попасть в корень.

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

Алгоритмы формирования бинарного дерева

Для того, чтобы сформировать в памяти ЭВМ БД, необходимо представить его в виде последовательности информационных частей вершин БД. Такую последовательность можно получить в результате обхода БД. Последовательность, полученная в результате обхода, неоднозначно определяет БД, т.к. не содержит информации о наличии сыновей у вершин БД. Чтобы получить такую информацию, введем в БД фиктивные вершины (с символом «.» в информационной части). Такие вершины соответствуют несуществующим сыновьям вершин БД. БД (см. рис.21) с фиктивными вершинами представлено на рис.25.



Рис.25. БД с фиктивными вершинами

При обходе БД (см. рис.25) в прямом порядке получим последовательность: ABCD..E..F..G.HI..J.. Из полученной последовательности следует, что вершины A,B,C,D и H имеют по два сына, причем левый сын записан непосредственно за отцом, вершины D,E,F,I и J -- листья (за ними следуют две точки), вершина G не имеет левого сына (одна точка за этой вершиной), а правый сын -- H.

Сформировать БД исходя из данной последовательности можно рекурсивным и итеративным способом, причем БД будет строиться «в глубину».

Рекурсивный алгоритм формирования бинарного дерева «в глубину»

1. Прочитать очередной символ последовательности.

2. Если прочитанный символ точка, то БД пустое, иначе создать корень, записать в него символ, построить левое поддерево, построить правое поддерево.

Итеративный алгоритм формирования бинарного дерева «в глубину»

1. Инициализировать стек.

2. Прочитать очередной символ последовательности.

3. Если прочитанный символ точка, то БД пустое, иначе создать корень, записать в него символ, корень поместить в стек.

4. Пока стек не пуст, выполнять п.5.

5. Прочитать символ, извлечь вершину из стека. Если для вершины левое поддерево не построено, то построить его в соответствии с п.6, если не построено правое поддерево, то построить его в соответствии с п.7.

6. Если символ точка, то левое поддерево пустое, вернуть вершину в стек, иначе создать корень левого поддерева, записать в него символ, вернуть в стек вершину, созданный корень поместить в стек.

7. Если символ точка, то правое поддерево пустое, иначе создать корень правого поддерева, записать в него символ, созданный корень поместить в стек.

Если при прохождении БД (см. рис.21) в прямом порядке сначала дерево, а потом все поддеревья заключать в скобки, то получим скобочное представление БД:

(A(B(C(D()())(E()()))(F()()))(G()(H(I()())(J()())))

Скобочное представление БД можно использовать в качестве исходных данных для формирования БД «в глубину», если пару символов `()' считать точкой, а остальные скобки игнорировать.

При обходе БД (см. рис.25) «в ширину» получим последовательность: ABGCF.HDE..IJ. . . . . . . .

Используя эту последовательность в качестве исходных данных можно сформировать БД, применив алгоритм формирования БД «в ширину».

Алгоритм формирования бинарного дерева «в ширину»

1. Инициализировать очередь.

2. Прочитать очередной символ последовательности.

3. Если прочитанный символ точка, то БД пустое, иначе создать корень, записать в него символ, корень поместить в очередь.

4. Пока очередь не пуста, выполнять п.5.

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

При обходе БД (см. рис.25) в обратном порядке получим последовательность: ..D..EC..FB...I..JHGA

Если ограничить эту последовательность концевым маркером, то ее можно будет использовать в качестве исходных данных для формирования БД «снизу вверх».

Алгоритм формирования бинарного дерева «снизу вверх»

1. Инициализировать очередь.

2. Последовательно обрабатывать символы последовательности, пока не достигнут концевой маркер.

3. Если прочитанный символ точка, то поместить в очередь пустое БД, иначе создать корень, записать в него символ, взять из очереди его левое, затем правое поддерево, полученное БД поместить в очередь.

4. Если по окончании работы алгоритма очередь окажется пустой, то сформировано пустое БД, иначе очередь будет содержать единственный элемент -- корень сформированного дерева.

При обходе БД (см. рис.25) в симметричном порядке получим последовательность: .D.C.E.B.F.A.G.I.H.J.

Такую же последовательность получим при обходе в симметричном порядке БД на рис.26, поэтому она неоднозначно определяет БД и не может быть использована в качестве исходных данных для формирования БД.

Рис.26. Бинарное дерево

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

Рекурсивный алгоритм формирования бинарного дерева

1. Прочитать элемент последовательности.

2. Если БД пустое, то создать корень и записать в него значение элемента, иначе включить элемент в левое поддерево, если его значение меньше значения корня, или включить в правое поддерево, если значение элемента больше значения корня.

Итеративный алгоритм формирования бинарного дерева

1. Пока в последовательности неповторяющихся значений есть элементы, читать и включать их в дерево в соответствии с п.2 или п.3.

2. Если БД пустое, то создать корень, записать в него значение.

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

Применив рассмотренные алгоритмы к последовательности целых чисел 20, 15, 23, 10, 5, 12, 30, 18, 44, 25 получим БД на рис.27.

Рис.27. БД, построенное по итеративному алгоритму

Если последовательность будет упорядоченной, то БД вырождается в последовательность.

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

Алгоритм формирования бинарного дерева минимальной высоты

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

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

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

Итеративный алгоритм формирования сбалансированного бинарного дерева

1. Создать корень, занести в него значение среднего элемента последовательности. Адрес корня, границы правой и левой части последовательности занести в стек.

2. Пока стек не пуст, извлечь из стека границы левой, правой части последовательности и адрес корня.

Если левой части нет, то нет левого поддерева для корня, иначе создать корень левого поддерева (левого сына), записать в него значение среднего элемента левой части, адрес левого сына и границы левой и правой части занести в стек.

Если правой части нет, то нет правого поддерева для корня, иначе создать корень правого поддерева (правого сына), записать в него значение среднего элемента правой части, адрес правого сына и границы левой и правой части занести в стек.

3. Конец алгоритма.

Представление алгебраических выражений бинарными деревьями

Любое алгебраическое выражение, которое содержит переменные, константы, знаки операций и скобки можно представить в виде бинарного дерева, в котором знак операции помещается в корне, первый операнд -- в левом поддереве, а второй операнд -- в правом. Скобки при этом опускаются. В результате все константы и переменные окажутся в листьях, а знаки операций -- во внутренних вершинах. БД алгебраического выражения a + 5 * b * (3 + c * d) представлено на рис.28.

Рис.28. БД алгебраического выражения a+5*b*(3+c*d)

Если выполнить обход БД (рис.28) в прямом порядке, то получим прямую польскую запись (ППЗ) алгебраического выражения:

+ a * * 5 b + 3 * c d

Используя ППЗ можно сформировать БД алгебраического выражения.

Алгоритм формирования бинарного дерева по прямой польской записи

1. Прочитать элемент ППЗ, создать корень, занести в него значение элемента.

2. Если прочитанный элемент -- знак операции, то для корня построить левое, затем правое поддерево, иначе левое и правое поддеревья пустые.

Поддеревья строятся точно также, как и БД в целом.

Если выполнить обход БД (см. рис.28) в обратном порядке, то получим обратную польскую запись (ОПЗ) алгебраического выражения:

a 5 b * 3 c d * + * +

Используя ОПЗ можно сформировать БД алгебраического выражения.

Алгоритм формирования бинарного дерева по обратной польской записи

1. Пока в ОПЗ есть элементы, прочитать очередной элемент, создать корень, занести в него значение элемента.

2. Если прочитанный элемент -- знак операции, то извлечь из стека адреса правого и левого поддеревьев корня.

3. Адрес корня занести в стек.

По окончании работы алгоритма стек будет содержать единственный элемент -- адрес корня БД.

Контрольные вопросы

1. Что такое бинарное дерево? Какие операции определены над бинарным деревом?

2. Как можно разместить бинарное дерево в памяти ЭВМ?

3. В чем заключается задача обхода бинарного дерева?

4. Опишите алгоритмы обхода бинарных деревьев.

5. Опишите алгоритмы формирования бинарных деревьев.

6. Разработайте алгоритм сортировки массива с использованием бинарного дерева. Определите порядок функции временной сложности алгоритма сортировки.

7. Опишите алгоритм поиска элемента в бинарном дереве. Определите порядок функции временной сложности алгоритма поиска.

Лабораторная работа №8. Структуры данных «таблица» (Pascal/С)

Цель работы: изучить СД «таблица», научиться их программно реализовывать и использовать.

Задание

1. Для СД «таблица» определить:

1.1. Абстрактный уровень представления СД:

1.1.1. Характер организованности и изменчивости.

1.1.2. Набор допустимых операций.

1.2. Физический уровень представления СД:

1.2.1. Схему хранения.

1.2.2. Объем памяти, занимаемый экземпляром СД.

1.2.3. Формат внутреннего представления СД и способ

его интерпретации.

1.2.4. Характеристику допустимых значений.

1.2.5. Тип доступа к элементам.

1. 3. Логический уровень представления СД:

Способ описания СД и экземпляра СД на языке программирования.

2. Реализовать СД «таблица» в соответствии с вариантом индивидуального задания (табл.18) в виде модулей на языках Pascal и С.

3. Разработать программы на языках Pascal и С для решения задачи в соответствии с вариантом индивидуального задания (см. табл.18) с использованием модулей, полученных в результате выполнения пункта 2 задания.

Таблица 18 - Варианты индивидуальных заданий

Номер варианта	Номер модуля	Задача
1	1	1
2	2	2
3	3	3
4	4	4
5	5	5
6	6	6
7	7	7
8	8	8
9	9	9
10	10	10
11	11	9
12	11	8
13	10	7
14	9	6
15	8	5
16	7	4
17	6	3
18	5	2
19	4	1
20	3	2
21	2	3
22	1	4
23	11	5
24	10	6
25	9	7
26	8	8
27	7	9
28	6	10
29	5	1
30	4	2

Задачи

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

Исходные данные: текстовые файлы, содержащие

а) текст программы;

б) символы-разделители;

в) служебные слова.

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

2. Текст программы на некотором алгоритмическом языке может содержать символы-разделители, служебные слова, числовые константы и идентификаторы (слова, начинающиеся не с цифры и не являющиеся служебными). Все идентификаторы, используемые в программе, должны быть описаны до первого появления в тексте программы служебного слова «BEGIN». Идентификатор считать описанным, если он встречается в тексте программы до первого слова «BEGIN», причем только один раз. Вывести все идентификаторы, которые описаны более одного раза и неописанные идентификаторы.

Исходные данные: текстовые файлы, содержащие

а) текст программы;

б) символы-разделители;

в) служебные слова.

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

3. Текст программы на некотором алгоритмическом языке может содержать символы-разделители, служебные слова, числовые константы и идентификаторы (слова, начинающиеся не с цифры и не являющиеся служебными). Проверить ошибки в записи идентификаторов и констант, парность служебных слов: «BEGIN» и «END», «IF» и «THEN», «FOR» и «DO», и скобок: «(» и «)», «[» и «]». Проверку констант выполнить с помощью стандартной процедуры VAL. Для проверки парности служебных слов и символов-разделителей использовать динамический массив из KP целочисленных элементов, где KP -- количество парных служебных слов и символов-разделителей. Сначала все элементы массива обнуляются. Если встречается первое слово i-й пары, то i-й элемент массива увеличивается на единицу, а если второе слово -- уменьшается. После обработки текста программы все элементы массива должны быть нулевыми. Парные служебные слова и символы-разделители хранить в таблице. Ключ элемента таблицы -- парное служебное слово, информационная часть содержит +i для первого слова i-й пары и -i для второго слова. Информацию о символах-разделителях и парных служебных словах прочитать из текстовых файлов.

4. Текст программы на некотором алгоритмическом языке может содержать символы-разделители, служебные слова, числовые константы и идентификаторы (слова, начинающиеся не с цифры и не являющиеся служебными). Проверить ошибки в записи идентификаторов и констант и сочетаемость рядом стоящих служебных слов, символов-разделителей, числовых констант и идентификаторов. Например, пары «BEGIN x» и «ELSE BEGIN» -- сочетаемы, а пары «x BEGIN» и «BEGIN ELSE» -- несочетаемы. Проверку констант выполнить с помощью стандартной процедуры VAL. Проверку сочетаемости -- с помощью таблицы сочетаемости. Ключ элемента таблицы -- служебное слово или символ-разделитель, информационная часть -- код служебного слова или символа-разделителя и множество кодов слов, которые могут непосредственно следовать за ключевым словом. Код константы -- 0, идентификатора -- 1. Для констант и идентификаторов также сформировать множества кодов слов, которые могут следовать за ними. Информацию для таблицы сочетаемости прочитать из файла.

5. Вычислить алгебраическое выражение, заданное ОПЗ. Выражение может содержать константы, вещественные переменные, знаки операций: «+», «-», «*», «/» и функции «sin(x)», «cos(x)», «arctan(x)», «abs(x)», «exp(x)», «ln(x)», «sqr(x)» и «sqrt(x)». Для хранения значений переменных использовать таблицу. Ключ элемента таблицы -- имя переменной, информационная часть -- значение переменной. Если текущей переменной нет в таблице, то ввести значение и включить ее в таблицу. Для вычисления значения выражения использовать стек.

ОПЗ выражения b·a + 5·(b + sin(sqr(a)) имеет вид:

b a · 5 b a sqr sin + * +

6. Написать интерпретатор языка вычисления арифметических вещественных выражений, заданных ОПЗ. В языке три оператора:

1) <оператор ввода> ::= <переменная> Read

2) <оператор вывода> ::= <переменная> Write

3) <оператор присваивания> ::= <переменная> = <ОПЗ>

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

Пример текста программы на языке вычисления арифметических вещественных выражений:

a Read

b Read

c Read

d = a b * 3.5 +

e = d d * c * a + 2 /

d = a b + 2 d * e - *

d Write

e Write

7. Написать интерпретатор языка арифметических вычислений. Язык содержит команды ввода и вывода значений вещественных переменных, команду пересылки константы или значения переменной в другую переменную, арифметические команды сложения, вычитания, умножения и деления. Команды ввода (IN) и вывода (OUT) имеют один операнд, команда пересылки (MOV) -- два операнда, первый из которых -- имя переменной, в которую пересылается второй операнд, арифметические команды (ADD, SUB, MUL, DIV) -- два операнда, в первом сохраняется результат. В каждой строке программы -- одна команда. Команды и операнды разделяются пробелами. Текст программы находится в текстовом файле. Значения переменных хранятся в таблице. Ключ элемента таблицы -- имя переменной, информационная часть -- значение переменной. Если операнда команды ввода или первого операнда арифметических команд и команды пересылки нет в таблице, то определить его значение и занести в таблицу. Если операнда команды вывода или второго операнда арифметических команд и команды пересылки нет в таблице, то выдать сообщение об ошибке.

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

IN a

IN b

IN c

MOV d a

MUL d b

DIV c a

SUB b c

MUL b 3.7

ADD d b

OUT d

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

Получил триста двадцать пять рублей пятнадцать копеек.

преобразовать в файл:

Получил 325 рублей 15 копеек.

Для преобразования чисел использовать таблицу. Ключ элемента -- словесное название числа («один», «два»,..., «десять», «одиннадцать»,..., «двадцать»,..., «девяносто», «сто», «двести», «триста»,..., «девятьсот»), информационная часть -- числовое значение ключа. Информацию в таблицу загрузить из текстового файла.

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

Получил 325 рублей 15 копеек.

преобразовать в файл:

Получил триста двадцать пять рублей пятнадцать копеек.

Для преобразования чисел использовать таблицу. Ключ элемента -- числовое значение числа («1», «2»,..., «10», «11»,..., «12»,..., «20»,..., «90», «100», «200», «300»,..., «900»), информационная часть -- словесное название ключа. Информацию в таблицу загрузить из текстового файла.

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

H2O , HCl , O2 , H2SO4 , O4H2S , NaCl .

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

Модули

1. Неупорядоченная таблица на последовательном линейном списке.

Спецификация СД на языке Pascal:

Unit Table1;

Interface

uses list8; {см лаб.раб. №5}

Const TableOk = 0;

TableNotMem = 1;

TableUnder = 2;

Type Table=list;

Func=function(var A,B: pointer):shortint; {Сравнивает ключи элементов таблицы, адреса которых находятся в параметрах A и B. Возвращает -1, если ключ элемента по адресу A меньше ключа элемента по адресу B, 0 -- если ключи равны и +1 -- если ключ элемента по адресу A больше ключа элемента по адресу B.}

Var TableError : 0..2;

Procedure InitTable(var T:Table; SizeMem, SizeEl:Word);

Function EmptyTable(var T:Table):boolean; {Возвращает TRUE , если таблица пуста, иначе -- FALSE}

Function PutTable(var T:Table; El:Element;

var F: Func):boolean; {Включение элемента в таблицу. Возвращает TRUE , если элемент включен в таблицу, иначе -- FALSE (если в таблице уже есть элемент с заданным ключем или нехватает памяти).}

Function GetTable(var T:Table; var El:Element; Key:T_Key;

var F: Func):boolean; {Исключение элемента. Возвращает TRUE , если элемент с ключем Key был в таблице, иначе -- FALSE}

Function ReadTable(var T:Table; var El:Element; Key:T_Key;

var F: Func):boolean; {Чтение элемента. Возвращает TRUE , если элемент с ключем Key есть в таблице, иначе -- FALSE}

Function WriteTable(var T:Table; var El:Element; Key:T_Key;

var F: Func):boolean; {Изменение элемента. Возвращает TRUE , если элемент с ключем Key есть в таблице, иначе -- FALSE}

Procedure DoneTable(var T:Table); {Уничтожение таблицы}

Спецификация СД на языке C:

#if !defined(__TABLE1_H)

#define __TABLE1_H

#include "list8.h" // Cмотреть лаб.раб. №5

const TableOk = 0;

const TableNotMem = 1;

const TableUnder = 2;

typedef List Table;

typedef ... T_Key; // Определить тип ключа

typedef int (* func)(void*, void*); /* Сравнивает ключи элементов таблицы, адреса которых находятся в параметрах a и b. Возвращает -1, если ключ элемента по адресу a меньше ключа элемента по адресу b, 0 -- если ключи равны и +1 -- если ключ элемента по адресу a больше ключа элемента по адресу b */

int TableError; // 0..2

void InitTable(Table *T, unsigned SizeMem, unsigned SizeEl);

inline int EmptyTable(Table *T); /* Возвращает 1 , если таблица пуста, иначе -- 0 */

int PutTable(Table *T, void *E, func f); /* Включение элемента в таблицу. Возвращает 1 , если элемент включен в таблицу, иначе -- 0 (если в таблице уже есть элемент с заданным ключем или нехватает памяти) */

int GetTable(Table *T, void *E, T_Key Key, func f); /* Исключение элемента. Возвращает 1 , если элемент с ключем Key был в таблице, иначе -- 0 */

int ReadTable(Table *T, void *E, T_Key Key, func f); /* Чтение элемента. Возвращает 1 , если элемент с ключем Key есть в таблице, иначе -- 0 */

int WriteTable(Table *T, void *E, T_Key Key, func f); /* Изменение элемента. Возвращает 1 , если элемент с ключем Key есть в таблице, иначе -- 0 */

void DoneTable(Table *T);/*Удаление таблицы из динамической памяти */

#endif

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

Спецификация СД на языке Pascal:

Unit Table2;

Interface

uses list3; {см лаб.раб. №5}

Const TableOk = 0;

TableNotMem = 1;

TableUnder = 2;

Type Table=list;

Func=function(var A,B: pointer):shortint; {Сравнивает ключи элементов таблицы, адреса которых находятся в параметрах A и B. Возвращает -1, если ключ элемента по адресу A меньше ключа элемента по адресу B, 0 -- если ключи равны и +1 -- если ключ элемента по адресу A больше ключа элемента по адресу B.}

Var TableError : 0..2;

Procedure InitTable(var T:Table; SizeMem, SizeEl:Word);

Function EmptyTable(var T:Table):boolean; {Возвращает TRUE -- если таблица пуста, иначе FALSE}

Function PutTable(var T:Table; El:Element; var F: Func):boolean; {Включение элемента в таблицу. Возвращает TRUE , если элемент включен в таблицу, иначе -- FALSE (если в таблице уже есть элемент с заданным ключем или нехватает памяти).}

Function GetTable(var T:Table; var El:Element; Key:T_Key;

var F: Func):boolean; {Исключение элемента. Возвращает TRUE , если элемент с ключем Key был в таблице, иначе -- FALSE}

Function ReadTable(var T:Table; var El:Element; Key:T_Key;

var F: Func):boolean; {Чтение элемента. Возвращает TRUE , если элемент с ключем Key есть в таблице, иначе -- FALSE}

Function WriteTable(var T:Table; var El:Element; Key:T_Key;

var F: Func):boolean; {Изменение элемента. Возвращает TRUE , если элемент с ключем Key есть в таблице, иначе -- FALSE}

Procedure DoneTable(var T:Table); {Уничтожение таблицы}

Спецификация СД на языке C:

#if !defined(__TABLE1_H)

#define __TABLE1_H

#include "list3.h" // Cмотреть лаб.раб. №5

const TableOk = 0;

const TableNotMem = 1;

const TableUnder = 2;

typedef List Table;

typedef ... T_Key; // Определить тип ключа

typedef int (* func)(void*, void*); /* Сравнивает ключи элементов таблицы, адреса которых находятся в параметрах a и b. Возвращает -1, если ключ элемента по адресу a меньше ключа элемента по адресу b, 0 -- если ключи равны и +1 -- если ключ элемента по адресу a больше ключа элемента по адресу b */

int TableError; // 0..2

void InitTable(Table *T, unsigned SizeMem, unsigned SizeEl);

inline int EmptyTable(Table *T); /* Возвращает 1 , если таблица пуста, иначе -- 0 */

int PutTable(Table *T, void *E, func f); /* Включение элемента в таблицу. Возвращает 1 , если элемент включен в таблицу, иначе -- 0 (если в таблице уже есть элемент с заданным ключем или нехватает памяти) */

int GetTable(Table *T, void *E, T_Key Key, func f); /* Исключение элемента. Возвращает 1 , если элемент с ключем Key был в таблице, иначе -- 0 */

int ReadTable(Table *T, void *E, T_Key Key, func f); /* Чтение элемента. Возвращает 1 , если элемент с ключем Key есть в таблице, иначе -- 0 */

int WriteTable(Table *T, void *E, T_Key Key, func f); /* Изменение элемента. Возвращает 1 , если элемент с ключем Key есть в таблице, иначе -- 0 */

void DoneTable(Table *T); //Удаление таблицы из динамической памяти

#endif

3. Упорядоченная таблица на последовательном линейном списке. Использовать алгоритм блочного поиска (см лаб.раб.№4).

Спецификация СД на языке Pascal:

Unit Table3;

Interface

uses list8; {см лаб.раб. №5}

Const TableOk = 0;

TableNotMem = 1;

TableUnder = 2;

Type Table=list;

Func=function(var A,B: pointer):shortint; {Сравнивает ключи элементов таблицы, адреса которых находятся в параметрах A и B. Возвращает -1, если ключ элемента по адресу A меньше ключа элемента по адресу B, 0 -- если ключи равны и +1 -- если ключ элемента по адресу A больше ключа элемента по адресу B.}

Var TableError : 0..2;

Procedure InitTable(var T:Table; SizeMem, SizeEl:Word);

Function EmptyTable(var T:Table):boolean; {Возвращает TRUE , если таблица пуста, иначе -- FALSE}

Function PutTable(var T:Table; El:Element; var F: Func):boolean; {Включение элемента в таблицу. Возвращает TRUE , если элемент включен в таблицу, иначе -- FALSE (если в таблице уже есть элемент с заданным ключем или нехватает памяти).}

Function GetTable(var T:Table; var El:Element; Key:T_Key;

var F: Func):boolean; {Исключение элемента. Возвращает TRUE , если элемент с ключем Key был в таблице, иначе -- FALSE}

Function ReadTable(var T:Table; var El:Element; Key:T_Key;

var F: Func):boolean; {Чтение элемента. Возвращает TRUE , если элемент с ключем Key есть в таблице, иначе -- FALSE}

Function WriteTable(var T:Table; var El:Element; Key:T_Key;

var F: Func):boolean; {Изменение элемента. Возвращает TRUE , если элемент с ключем Key есть в таблице, иначе -- FALSE}

Procedure DoneTable(var T:Table); {Уничтожение таблицы}

Спецификация СД на языке C:

#if !defined(__TABLE1_H)

#define __TABLE1_H

#include "list8.h" // Cмотреть лаб.раб. №5

const TableOk = 0;

const TableNotMem = 1;

const TableUnder = 2;

typedef List Table;

typedef ... T_Key; // Определить тип ключа

typedef int (* func)(void*, void*); /* Сравнивает ключи элементов таблицы, адреса которых находятся в параметрах a и b. Возвращает -1, если ключ элемента по адресу a меньше ключа элемента по адресу b, 0 -- если ключи равны и +1 -- если ключ элемента по адресу a больше ключа элемента по адресу b */

int TableError; // 0..2

void InitTable(Table *T, unsigned SizeMem, unsigned SizeEl);

inline int EmptyTable(Table *T); /* Возвращает 1 , если таблица пуста, иначе -- 0 */

int PutTable(Table *T, void *E, func f); /* Включение элемента в таблицу. Возвращает 1 , если элемент включен в таблицу, иначе -- 0 (если в таблице уже есть элемент с заданным ключем или нехватает памяти) */

int GetTable(Table *T, void *E, T_Key Key, func f); /* Исключение элемента. Возвращает 1 , если элемент с ключем Key был в таблице, иначе -- 0 */

int ReadTable(Table *T, void *E, T_Key Key, func f); /* Чтение элемента. Возвращает 1 , если элемент с ключем Key есть в таблице, иначе -- 0 */

int WriteTable(Table *T, void *E, T_Key Key, func f); /* Изменение элемента. Возвращает 1 , если элемент с ключем Key есть в таблице, иначе -- 0 */

void DoneTable(Table *T); //Удаление таблицы из динамической памяти

#endif

4. Упорядоченная таблица на последовательном линейном списке. Использовать алгоритм бинарного поиска(см лаб.раб.№4).

Спецификация СД на языке Pascal:

Unit Table4;

Interface

uses list6; {см лаб.раб. №5}

Const TableOk = 0;

TableNotMem = 1;

TableUnder = 2;

Type Table=list;

Func=function(var A,B: pointer):shortint; {Сравнивает ключи элементов таблицы, адреса которых находятся в параметрах A и B. Возвращает -1, если ключ элемента по адресу A меньше ключа элемента по адресу B, 0 -- если ключи равны и +1 -- если ключ элемента по адресу A больше ключа элемента по адресу B.}

Var TableError : 0..2;

Procedure InitTable(var T:Table; SizeMem, SizeEl:Word);

Function EmptyTable(var T:Table):boolean; {Возвращает TRUE , если таблица пуста, иначе -- FALSE}

Function PutTable(var T:Table; El:Element;

var F: Func):boolean; {Включение элемента в таблицу. Возвращает TRUE , если элемент включен в таблицу, иначе -- FALSE (если в таблице уже есть элемент с заданным ключем или нехватает памяти).}

Function GetTable(var T:Table; var El:Element; Key:T_Key;

var F: Func):boolean; {Исключение элемента. Возвращает TRUE , если элемент с ключем Key был в таблице, иначе -- FALSE}

Function ReadTable(var T:Table; var El:Element; Key:T_Key;

var F: Func):boolean; {Чтение элемента. Возвращает TRUE , если элемент с ключем Key есть в таблице, иначе -- FALSE}

Function WriteTable(var T:Table; var El:Element; Key:T_Key;

var F: Func):boolean; {Изменение элемента. Возвращает TRUE , если элемент с ключем Key есть в таблице, иначе -- FALSE}

Procedure DoneTable(var T:Table); {Уничтожение таблицы}

Спецификация СД на языке C:

#if !defined(__TABLE1_H)

#define __TABLE1_H

#include "list6.h" // Cмотреть лаб.раб. №5

const TableOk = 0;

const TableNotMem = 1;

const TableUnder = 2;

typedef List Table;

typedef ... T_Key; // Определить тип ключа

typedef int (* func)(void*, void*); /* Сравнивает ключи элементов таблицы, адреса которых находятся в параметрах a и b. Возвращает -1, если ключ элемента по адресу a меньше ключа элемента по адресу b, 0 -- если ключи равны и +1 -- если ключ элемента по адресу a больше ключа элемента по адресу b */

int TableError; // 0..2

void InitTable(Table *T, unsigned SizeMem, unsigned SizeEl);

inline int EmptyTable(Table *T); /* Возвращает 1 , если таблица пуста, иначе -- 0 */

int PutTable(Table *T, void *E, func f); /* Включение элемента в таблицу. Возвращает 1 , если элемент включен в таблицу, иначе -- 0 (если в таблице уже есть элемент с заданным ключем или нехватает памяти) */

int GetTable(Table *T, void *E, T_Key Key, func f); /* Исключение элемента. Возвращает 1 , если элемент с ключем Key был в таблице, иначе -- 0 */

int ReadTable(Table *T, void *E, T_Key Key, func f); /* Чтение элемента. Возвращает 1 , если элемент с ключем Key есть в таблице, иначе -- 0 */

int WriteTable(Table *T, void *E, T_Key Key, func f); /* Изменение элемента. Возвращает 1 , если элемент с ключем Key есть в таблице, иначе -- 0 */

void DoneTable(Table *T); //Удаление таблицы из динамической памяти

#endif

5. Упорядоченная таблица на односвязном линейном списке.

Спецификация СД на языке Pascal:

Unit Table5;

Interface

uses list2; {см лаб.раб. №5}

Const TableOk = 0;

TableNotMem = 1;

TableUnder = 2;

Type Table=list;

Var TableError : 0..2;

Procedure InitTable(var T:Table; SizeMem, SizeEl:Word);

Function EmptyTable(var T:Table):boolean; {Возвращает TRUE , если таблица пуста, иначе -- FALSE}

Function PutTable(var T:Table; El:Element; var F: Func):boolean; {Включение элемента в таблицу. Возвращает TRUE , если элемент включен в таблицу, иначе -- FALSE (если в таблице уже есть элемент с заданным ключем или нехватает памяти).}

Function GetTable(var T:Table; var El:Element; Key:T_Key;

var F: Func):boolean; {Исключение элемента. Возвращает TRUE , если элемент с ключем Key был в таблице, иначе -- FALSE}

Function ReadTable(var T:Table; var El:Element; Key:T_Key;

var F: Func):boolean; {Чтение элемента. Возвращает TRUE , если элемент с ключем Key есть в таблице, иначе -- FALSE}

Function WriteTable(var T:Table; var El:Element; Key:T_Key;

var F: Func):boolean; {Изменение элемента. Возвращает TRUE , если элемент с ключем Key есть в таблице, иначе -- FALSE}

Procedure DoneTable(var T:Table); {Уничтожение таблицы}

Спецификация СД на языке C:

#if !defined(__TABLE5_H)

#define __TABLE5_H

#include "list2.h" // Cмотреть лаб.раб. №5

const TableOk = 0;

const TableNotMem = 1;

const TableUnder = 2;

typedef List Table;

typedef ... T_Key; // Определить тип ключа

int TableError; // 0..2

void InitTable(Table *T);

int EmptyTable(Table *T); // Возвращает 1 , если таблица пуста, иначе -- 0

int PutTable(Table *T, BaseType E); /* Включение элемента в таблицу. Возвращает 1 , если элемент включен в таблицу, иначе -- 0 (если в таблице уже есть элемент с заданным ключем или нехватает памяти) */

int GetTable(Table *T, BaseType *E, T_Key Key); /* Исключение элемента. Возвращает 1 , если элемент с ключем Key был в таблице, иначе -- 0 */

int ReadTable(Table *T, BaseType *E, T_Key Key); /* Чтение элемента. Возвращает 1 , если элемент с ключем Key есть в таблице, иначе -- 0 */

int WriteTable(Table *T, BaseType *E, T_Key Key); /* Изменение элемента. Возвращает 1 , если элемент с ключем Key есть в таблице, иначе -- 0 */

void DoneTable(Table *T); // Уничтожение таблицы

#endif

6. Упорядоченная таблица на бинарном дереве.

Спецификация СД на языке Pascal:

Unit Table6;

Interface

uses Tree1; {см лаб.раб. №7}

Const TableOk = 0;

TableNotMem = 1;

TableUnder = 2;

Type Table=tree;

Var TableError : 0..2;

Procedure InitTable(var T:Table; SizeMem, SizeEl:Word);

Function EmptyTable(var T:Table):boolean; {Возвращает TRUE , если таблица пуста, иначе -- FALSE}

Function PutTable(var T:Table; El:Element; var F: Func):boolean; {Включение элемента в таблицу. Возвращает TRUE , если элемент включен в таблицу, иначе -- FALSE (если в таблице уже есть элемент с заданным ключем или нехватает памяти).}

Function GetTable(var T:Table; var El:Element; Key:T_Key;

var F: Func):boolean; {Исключение элемента. Возвращает TRUE , если элемент с ключем Key был в таблице, иначе -- FALSE}

Function ReadTable(var T:Table; var El:Element; Key:T_Key;

var F: Func):boolean; {Чтение элемента. Возвращает TRUE , если элемент с ключем Key есть в таблице, иначе -- FALSE}

Function WriteTable(var T:Table; var El:Element; Key:T_Key;

var F: Func):boolean; {Изменение элемента. Возвращает TRUE , если элемент с ключем Key есть в таблице, иначе -- FALSE}

Procedure DoneTable(var T:Table); {Уничтожение таблицы}

Спецификация СД на языке C:

#if !defined(__TABLE6_H)

#define __TABLE6_H

#include " tree1.h " // Cмотреть лаб.раб. №5

const TableOk = 0;

const TableNotMem = 1;

const TableUnder = 2;

typedef List Table;

typedef ... T_Key; // Определить тип ключа

int TableError; // 0..2

void InitTable(Table *T);

int EmptyTable(Table *T); // Возвращает 1 , если таблица пуста, иначе -- 0

int PutTable(Table *T, BaseType E); /* Включение элемента в таблицу. Возвращает 1 , если элемент включен в таблицу, иначе -- 0 (если в таблице уже есть элемент с заданным ключем или нехватает памяти) */

int GetTable(Table *T, BaseType *E, T_Key Key); /* Исключение элемента. Возвращает 1 , если элемент с ключем Key был в таблице, иначе -- 0 */

int ReadTable(Table *T, BaseType *E, T_Key Key); /* Чтение элемента. Возвращает 1 , если элемент с ключем Key есть в таблице, иначе -- 0 */

int WriteTable(Table *T, BaseType *E, T_Key Key); /* Изменение элемента. Возвращает 1 , если элемент с ключем Key есть в таблице, иначе -- 0 */

void DoneTable(Table *T); // Уничтожение таблицы

#endif

7. Упорядоченная таблица на бинарном дереве.

Спецификация СД на языке Pascal:

Unit Table7;

Interface

uses Tree6; {см лаб.раб. №7}

Const TableOk = 0;

TableNotMem = 1;

TableUnder = 2;

Type Table=Tree;

Func=function(var A,B: pointer):shortint; {Сравнивает ключи элементов таблицы, адреса которых находятся в параметрах A и B. Возвращает -1, если ключ элемента по адресу A меньше ключа элемента по адресу B, 0 -- если ключи равны и +1 -- если ключ элемента по адресу A больше ключа элемента по адресу B.}

Var TableError : 0..2;

Procedure InitTable(var T:Table; SizeMem, SizeEl:Word);

Function EmptyTable(var T:Table):boolean; {Возвращает TRUE , если таблица пуста, иначе -- FALSE}

Function PutTable(var T:Table; El:Element; var F: Func):boolean; {Включение элемента в таблицу. Возвращает TRUE , если элемент включен в таблицу, иначе -- FALSE (если в таблице уже есть элемент с заданным ключем или нехватает памяти).}

Function GetTable(var T:Table; var El:Element; Key:T_Key;

var F: Func):boolean; {Исключение элемента. Возвращает TRUE , если элемент с ключем Key был в таблице, иначе -- FALSE}

Function ReadTable(var T:Table; var El:Element; Key:T_Key;

var F: Func):boolean; {Чтение элемента. Возвращает TRUE , если элемент с ключем Key есть в таблице, иначе -- FALSE}

Function WriteTable(var T:Table; var El:Element; Key:T_Key;

var F: Func):boolean; {Изменение элемента. Возвращает TRUE , если элемент с ключем Key есть в таблице, иначе -- FALSE}

Procedure DoneTable(var T:Table); {Уничтожение таблицы}

Спецификация СД на языке C:

#if !defined(__TABLE7_H)

#define __TABLE7_H

#include " tree6.h " // Cмотреть лаб.раб. №5

const TableOk = 0;

const TableNotMem = 1;

const TableUnder = 2;

typedef List Table;

typedef ... T_Key; // Определить тип ключа

typedef int (* func)(void*, void*); /* Сравнивает ключи элементов таблицы, адреса которых находятся в параметрах a и b. Возвращает -1, если ключ элемента по адресу a меньше ключа элемента по адресу b, 0 -- если ключи равны и +1 -- если ключ элемента по адресу a больше ключа элемента по адресу b */

...