Pascal/С

#endif

8. Стек на ОЛС. Вершина стека - первый элемент ОЛС.

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

unit stack8;

interface

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

const StackOk=ListOk;

StackUnder=ListUnder;

StackOver=ListNotMem;

type stack=list;

procedure InitStack(var s : stack); {инициализация стека}

procedure PutStack(var s : stack; b : basetype);

{поместить элемент в стек}

procedure GetStack(var s : stack; var b : basetype);

{извлечь элемент из стека }

function EmptyStack(s : stack):boolean; {стек пуст}

procedure ReadStack(s:Stack;var b : basetype); {прочитать

элемент из вершины стека}

procedure DoneStack(var s:Stack);{разрушить стек}

var stackerror:byte;

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

#if !defined(__STACK8_H)

#define __STACK8_H

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

const StackOk = ListOk;

const StackUnder = ListUnder;

const StackOver = ListNotMem;

int StackError; // Переменная ошибок

typedef List Stack;

void InitStack(Stack *s); /* Инициализация стека */

void PutStack(Stack *s, BaseType E); /* Поместить элемент в стек */

void GetStack(Stack *s, BaseType *E); /* Извлечь элемент из стека */

int EmptyStack(Stack s); // Проверка: стек пуст?

void ReadStack(Stack s, BaseType *E); /* Прочитать элемент из вершины стека */

void DoneStack(Stack *s); // Уничтожить стек

#endif

9. Стек на ОЛС. Вершина стека - последний элемент ОЛС.

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

unit stack9;

interface

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

const StackOk=ListOk;

StackUnder=ListUnder;

StackOver=ListNotMem;

type stack=list;

procedure InitStack(var s : stack); {инициализация стека}

procedure PutStack(var s : stack; b : basetype);

{поместить элемент в стек}

procedure GetStack(var s : stack; var b : basetype);

{извлечь элемент из стека }

function EmptyStack(s : stack):boolean; {стек пуст}

procedure ReadStack(s:Stack;var b : basetype); {прочитать

элемент из вершины стека}

procedure DoneStack(var s:Stack);{разрушить стек}

var stackerror:byte;

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

#if !defined(__STACK9_H)

#define __STACK9_H

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

const StackOk = ListOk;

const StackUnder = ListUnder;

const StackOver = ListNotMem;

int StackError; // Переменная ошибок

typedef List Stack;

void InitStack(Stack *s); /* Инициализация стека */

void PutStack(Stack *s, BaseType E); /* Поместить элемент в стек */

void GetStack(Stack *s, BaseType *E); /* Извлечь элемент из стека */

int EmptyStack(Stack s); // Проверка: стек пуст?

void ReadStack(Stack s, BaseType *E); /* Прочитать элемент из вершины стека */

void DoneStack(Stack *s); // Уничтожить стек

#endif

10. Стек на ПЛС. Вершина стека - первый элемент ПЛС.

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

unit stack10;

interface

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

const StackOk=ListOk;

StackUnder=ListUnder;

StackOver=ListNotMem;

type stack=list;

procedure InitStack(var s : stack; size : word);

{инициализация стека}

procedure PutStack(var s : stack; var b);

{поместить элемент в стек}

procedure GetStack(var s : stack; var b);

{извлечь элемент из стека }

function EmptyStack(s : stack):boolean; {стек пуст}

procedure ReadStack(s:Stack; var b); {прочитать

элемент из вершины стека}

procedure DoneStack(var s:Stack);{разрушить стек}

var stackerror:byte;

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

#if !defined(__STACK10_H)

#define __STACK10_H

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

const StackOk = ListOk;

const StackUnder = ListUnder;

const StackOver = ListNotMem;

int StackError; // Переменная ошибок

typedef List Stack;

void InitStack(Stack *s, unsigned Size); /* Инициализация стека */

void PutStack(Stack *s, void *E); // Поместить элемент в стек

void GetStack(Stack *s, void *E); // Извлечь элемент из стека

int EmptyStack(Stack s); // Проверка: стек пуст?

void ReadStack(Stack s, void *E); /* Прочитать элемент из вершины стека */

void DoneStack(Stack *s); // Уничтожить стек

#endif

11. Стек на ПЛС. Вершина стека - последний элемент ПЛС.

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

unit stack11;

interface

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

const StackOk=ListOk;

StackUnder=ListUnder;

StackOver=ListNotMem;

type stack=list;

procedure InitStack(var s : stack; SizeMem, SizeEl:Word);

{инициализация стека}

procedure PutStack(var s : stack; var b);

{поместить элемент в стек}

procedure GetStack(var s : stack; var b);

{извлечь элемент из стека }

function EmptyStack(s : stack):boolean; {стек пуст}

procedure ReadStack(s:Stack; var b); {прочитать

элемент из вершины стека}

procedure DoneStack(var s:Stack);{разрушить стек}

var stackerror:byte;

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

#if !defined(__STACK11_H)

#define __STACK11_H

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

const StackOk = ListOk;

const StackUnder = ListUnder;

const StackOver = ListNotMem;

int StackError; // Переменная ошибок

typedef List Stack;

void InitStack(Stack *s, unsigned SizeMem, unsigned SizeEl);

/* Инициализация стека */

void PutStack(Stack *s, void *E); // Поместить элемент в стек

void GetStack(Stack *s, void *E); // Извлечь элемент из стека

int EmptyStack(Stack s); // Проверка: стек пуст?

void ReadStack(Stack s, void *E); /* Прочитать элемент из вершины стека */

void DoneStack(Stack *s); // Уничтожить стек

#endif

Модули для реализации очереди

1. Очередь на ПЛС. «Хвост» очереди -- последний, а «голова» -- первый элемент ПЛС.

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

unit Fifo1;

interface

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

const FifoOk=ListOk;

FifoUnder=ListUnder;

FifokOver=ListNotMem;

type Fifo=list;

procedure InitFifo(var f : fifo; SizeMem, SizeEl:Word);

{инициализация очереди}

procedure PutFifo(var f : fifo; b : basetype);

{поместить элемент в очередь}

procedure GetFifo(var f : fifo; var b : basetype);

{извлечь элемент из очереди}

function EmptyFifo(f : Fifo):boolean; {очередь пуста}

procedure DoneFifo(var f: fifo);{разрушить очередь}

var fifoerror:byte;

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

#if !defined(__FIFO1_H)

#define __FIFO1_H

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

const FifoOk = ListOk;

const FifoUnder = ListUnder;

const FifoOver = ListNotMem;

int FifoError; // Переменная ошибок

typedef List Fifo;

void InitFifo(Fifo *f, unsigned SizeMem, unsigned SizeEl);

// Инициализация очереди

void PutFifo(Fifo *f, BaseType E); /* Поместить элемент в очередь */

void GetFifo(Fifo *f, BaseType *E); /* Извлечь элемент из очереди */

void ReadFifo(Fifo *f, BaseType *E); // Прочитать элемент

int EmptyFifo(Fifo *f); // Проверка, пуста ли очередь?

void DoneFifo(Fifo *f); // Разрушить очередь

#endif

2. Очередь на ПЛС. «Хвост» очереди -- первый, а «голова» -- последний элемент ПЛС.

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

unit Fifo2;

interface

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

const FifoOk=ListOk;

FifoUnder=ListUnder;

FifokOver=ListNotMem;

type Fifo=list;

procedure InitFifo(var f : fifo; Size:Word);

{инициализация очереди}

procedure PutFifo(var f : fifo; b : basetype);

{поместить элемент в очередь}

procedure GetFifo(var f : fifo; var b : basetype);

{извлечь элемент из очереди}

function EmptyFifo(f : Fifo):boolean; {очередь пуста}

procedure DoneFifo(var f: fifo);{разрушить очередь}

var fifoerror:byte;

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

#if !defined(__FIFO2_H)

#define __FIFO2_H

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

const FifoOk = ListOk;

const FifoUnder = ListUnder;

const FifoOver = ListNotMem;

int FifoError; // Переменная ошибок

typedef List Fifo;

void InitFifo(Fifo *f, unsigned Size); /* Инициализация очереди */

void PutFifo(Fifo *f, BaseType E); /* Поместить элемент в очередь */

void GetFifo(Fifo *f, BaseType *E); /* Извлечь элемент из очереди */

void ReadFifo(Fifo *f, BaseType *E); // Прочитать элемент

int EmptyFifo(Fifo *f); // Проверка, пуста ли очередь?

void DoneFifo(Fifo *f); // Разрушить очередь

#endif

3. Очередь на ОЛС. «Хвост» очереди -- последний, а «голова» -- первый элемент ОЛС.

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

unit Fifo3;

interface

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

const FifoOk=ListOk;

FifoUnder=ListUnder;

FifokOver=ListNotMem;

type Fifo=list;

procedure InitFifo(var f : fifo); {инициализация очереди}

procedure PutFifo(var f : fifo; b : basetype);

{поместить элемент в очередь}

procedure GetFifo(var f : fifo; var b : basetype);

{извлечь элемент из очереди}

function EmptyFifo(f : Fifo):boolean; {очередь пуста}

procedure DoneFifo(var s: fifo);{разрушить очередь}

var fifoerror:byte;

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

#if !defined(__FIFO3_H)

#define __FIFO3_H

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

const FifoOk = ListOk;

const FifoUnder = ListUnder;

const FifoOver = ListNotMem;

int FifoError; // Переменная ошибок

typedef List Fifo;

void InitFifo(Fifo *f); // Инициализация очереди

void PutFifo(Fifo *f, BaseType E); /* Поместить элемент в очередь */

void GetFifo(Fifo *f, BaseType *E); /* Извлечь элемент из очереди */

void ReadFifo(Fifo *f, BaseType *E); // Прочитать элемент

int EmptyFifo(Fifo *f); // Проверка, пуста ли очередь?

void DoneFifo(Fifo *f); // Разрушить очередь

#endif

4. Очередь на ОЛС. «Хвост» очереди -- первый, а «голова» -- последний

элемент ОЛС.

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

unit Fifo4;

interface

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

const FifoOk=ListOk;

FifoUnder=ListUnder;

FifokOver=ListNotMem;

type Fifo=list;

procedure InitFifo(var f : fifo); {инициализация очереди}

procedure PutFifo(var f : fifo; b : basetype);

{поместить элемент в очередь}

procedure GetFifo(var f : fifo; var b : basetype);

{извлечь элемент из очереди}

function EmptyFifo(f : Fifo):boolean; {очередь пуста}

procedure DoneFifo(var f: Fifo); {разрушить очередь}

var fifoerror:byte;

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

#if !defined(__FIFO4_H)

#define __FIFO4_H

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

const FifoOk = ListOk;

const FifoUnder = ListUnder;

const FifoOver = ListNotMem;

int FifoError; // Переменная ошибок

typedef List Fifo;

void InitFifo(Fifo *f); // Инициализация очереди

void PutFifo(Fifo *f, BaseType E); /* Поместить элемент в очередь */

void GetFifo(Fifo *f, BaseType *E); /* Извлечь элемент из очереди */

void ReadFifo(Fifo *f, BaseType *E); // Прочитать элемент

int EmptyFifo(Fifo *f); // Проверка, пуста ли очередь?

void DoneFifo(Fifo *f); // Разрушить очередь

#endif

5. Очередь на ОЛС. «Хвост» очереди -- последний, а «голова» -- первыйэлемент ОЛС.

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

unit Fifo5;

interface

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

const FifoOk=ListOk;

FifoUnder=ListUnder;

FifokOver=ListNotMem;

type Fifo=list;

procedure InitFifo(var f : fifo; Size:Word);

{инициализация очереди}

procedure PutFifo(var f : fifo; var b);

{поместить элемент в очередь}

procedure GetFifo(var f : fifo; var b);

{извлечь элемент из очереди}

function EmptyFifo(f : fifo):boolean; {очередь пуста}

procedure DoneFifo(var f: fifo);{разрушить очередь}

var fifoerror:byte;

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

#if !defined(__FIFO5_H)

#define __FIFO5_H

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

const FifoOk = ListOk;

const FifoUnder = ListUnder;

const FifoOver = ListNotMem;

int FifoError; // Переменная ошибок

typedef List Fifo;

void InitFifo(Fifo *f, unsigned Size); /* Инициализация очереди */

void PutFifo(Fifo *f, void *E);// Поместить элемент в очередь

void GetFifo(Fifo *f, void *E); // Извлечь элемент из очереди

void ReadFifo(Fifo *f, void *E); // Прочитать элемент

int EmptyFifo(Fifo *f); // Проверка, пуста ли очередь?

void DoneFifo(Fifo *f); // Разрушить очередь

#endif

6. Очередь на ОЛС. «Хвост» очереди -- первый, а «голова» -- последний элемент ОЛС.

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

unit Fifo6;

interface

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

const FifoOk=ListOk;

FifoUnder=ListUnder;

FifokOver=ListNotMem;

type Fifo=list;

procedure InitFifo(var f : fifo; Size:Word);

{инициализация очереди}

procedure PutFifo(var f : fifo; var b);

{поместить элемент в очередь}

procedure GetFifo(var f : fifo; var b);

{извлечь элемент из очереди}

function EmptyFifo(f : fifo):boolean; {очередь пуста}

procedure DoneFifo(var f: fifo);{разрушить очередь}

var fifoerror:byte;

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

#if !defined(__FIFO6_H)

#define __FIFO6_H

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

const FifoOk = ListOk;

const FifoUnder = ListUnder;

const FifoOver = ListNotMem;

int FifoError; // Переменная ошибок

typedef List Fifo;

void InitFifo(Fifo *f, unsigned Size);//Инициализация очереди

void PutFifo(Fifo *f, void *E);// Поместить элемент в очередь

void GetFifo(Fifo *f, void *E); // Извлечь элемент из очереди

void ReadFifo(Fifo *f, void *E); // Прочитать элемент

int EmptyFifo(Fifo *f); // Проверка, пуста ли очередь?

void DoneFifo(Fifo *f); // Разрушить очередь

#endif

7. Очередь на ОЛС. «Хвост» очереди -- последний, а «голова» -- первый элемент ОЛС.

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

unit Fifo7;

interface

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

const FifoOk=ListOk;

FifoUnder=ListUnder;

FifokOver=ListNotMem;

type Fifo=list;

procedure InitFifo(var f : fifo); {инициализация очереди}

procedure PutFifo(var f : fifo; b : basetype);

{поместить элемент в очередь}

procedure GetFifo(var f : fifo; var b : basetype);

{извлечь элемент из очереди}

function EmptyFifo(f : fifo):boolean; {очередь пуста}

procedure DoneFifo(var f: fifo);{разрушить очередь}

var fifoerror:byte;

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

#if !defined(__FIFO7_H)

#define __FIFO7_H

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

const FifoOk = ListOk;

const FifoUnder = ListUnder;

const FifoOver = ListNotMem;

int FifoError; // Переменная ошибок

typedef List Fifo;

void InitFifo(Fifo *f); // Инициализация очереди

void PutFifo(Fifo *f, BaseType E); /* Поместить элемент в очередь */

void GetFifo(Fifo *f, BaseType *E); /* Извлечь элемент из очереди */

void ReadFifo(Fifo *f, BaseType *E); // Прочитать элемент

int EmptyFifo(Fifo *f); // Проверка, пуста ли очередь?

void DoneFifo(Fifo *f); // Разрушить очередь

#endif

8. Очередь (кольцевая) на массиве в статической памяти.

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

Unit Fifo8;

Interface

Const

FifoSize = 1000;

FifoOk = 0;

FifoOver = 1;

FifoUnder= 2;

var

FifoError:0..2;

Type

Index = 0..FifoSize;

BaseType = . . .; {определить тип элемента очереди}

Fifo = record

Buf: array[Index]of BaseType;

Uk1 : Index; {указывает на “голову” очереди}

Uk2 : Index; {указывает на “хвост” очереди}

end;

procedure InitFifo(var f : fifo); {инициализация очереди}

procedure PutFifo(var f : fifo; var b); {поместить элемент в очередь}

procedure GetFifo(var f : fifo; var b); {извлечь элемент из очереди}

function EmptyFifo(f : fifo):boolean; {очередь пуста}

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

#if !defined(__FIFO8_H)

#define __FIFO8_H

const FifoOk = 0;

const FifoUnder = 1;

const FifoOver = 2;

const FifoSize = 1000;

int FifoError; // Переменная ошибок

typedef ... BaseType; // Определить тип элемента очереди

typedef struct Fifo

{

BaseType Buf[FifoSize];

unsigned Uk1; // Указатель на "голову" очереди

unsigned Uk2; // Указатель на "хвост" очереди

unsigned N; // Количество элементов очереди

};

void InitFifo(Fifo* f); // Инициализация очереди

void PutFifo(Fifo *f, BaseType E); /* Поместить элемент в очередь */

void GetFifo(Fifo *f, BaseType *E); /* Извлечь элемент из очереди */

void ReadFifo(Fifo *f, BaseType *E); // Прочитать элемент

int EmptyFifo(Fifo *f); // Проверка, пуста ли очередь?

#endif

9. Очередь (кольцевая) на массиве в динамической памяти.

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

Unit Fifo9;

Interface

Const

FifoOk = 0;

FifoOver = 1;

FifoUnder= 2;

var FifoError:0..2;

Type

BaseType = . . .; {определить тип элемента очереди}

Const

FifoSize = 65520 div sizeof(BaseType);

Type

Index = 0..FifoSize;

TBuf = array[Index] of BaseType

Fifo = record

PBuf: ^TBuf;

SizeBuf: word; {количество элементов в массиве}

Uk1 : Index; {указывает на “голову” очереди}

Uk2 : Index; {указывает на “хвост” очереди}

end;

procedure InitFifo(var f : fifo; size: word);

{инициализация очереди}

procedure PutFifo(var f : fifo; b : basetype);

{поместить элемент в очередь}

procedure GetFifo(var f : fifo; var b : basetype);

{извлечь элемент из очереди}

function EmptyFifo(f : fifo):boolean; {очередь пуста}

procedure DoneFifo(var f: fifo);{разрушить очередь}

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

#if !defined(__FIFO9_H)

#define __FIFO9_H

const FifoOk = 0;

const FifoUnder = 1;

const FifoOver = 2;

const FifoSize = 1000;

int FifoError; // Переменная ошибок

typedef ... BaseType; // Определить тип элемента очереди

typedef struct Fifo

{

BaseType *Buf;

unsigned SizeBuf; /* Максимальная длина массива, определяющаяся при инициализации */

unsigned Uk1; // Указатель на "голову" очереди

unsigned Uk2; // Указатель на "хвост" очереди

unsigned N; // Количество элементов очереди

};

void InitFifo(Fifo* f, unsigned Size); /* Инициализация очереди */

void PutFifo(Fifo *f, BaseType E); /* Поместить элемент в очередь */

void GetFifo(Fifo *f, BaseType *E); /* Извлечь элемент из очереди */

void ReadFifo(Fifo *f, BaseType *E); // Прочитать элемент

int EmptyFifo(Fifo *f); // Проверка, пуста ли очередь?

void DoneFifo(Fifo *f); // Разрушить очередь

#endif

10. Очередь (кольцевая) на массиве в статической памяти с

элементами в динамической памяти.

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

Unit Fifo10;

Interface

Const

FifoSize = 1000;

FifoOk = 0;

FifoOver = 1;

FifoUnder= 2;

var

FifoError:0..2;

Type

Index = 0..FifoSize;

BaseType = pointer;

Fifo = record

Buf: array[Index]of BaseType;

SizeEl: word; {размер элемента очереди}

Uk1 : Index; {указывает на “голову” очереди}

Uk2 : Index; {указывает на “хвост” очереди}

end;

procedure InitFifo(var f : fifo; size: word);

{инициализация очереди}

procedure PutFifo(var f : fifo; b : basetype);

{поместить элемент в очередь}

procedure GetFifo(var f : fifo; var b : basetype);

{извлечь элемент из очереди}

function EmptyFifo(f : fifo):boolean; {очередь пуста}

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

#if !defined(__FIFO10_H)

#define __FIFO10_H

const FifoOk = 0;

const FifoUnder = 1;

const FifoOver = 2;

const FifoSize = 1000;

int FifoError; // Переменная ошибок

typedef void *BaseType;

typedef struct Fifo

{

BaseType Buf[FifoSize];

unsigned SizeEl; // Размер элемента очереди

unsigned Uk1; // Указатель на "голову" очереди

unsigned Uk2; // Указатель на "хвост" очереди

unsigned N; // Количество элементов очереди

};

void InitFifo(Fifo* f, unsigned Size); /* Инициализация очереди */

void PutFifo(Fifo *f, void *E); /* Поместить элемент в очередь */

void GetFifo(Fifo *f, void *E); // Извлечь элемент из очереди

void ReadFifo(Fifo *f, void *E); // Прочитать элемент

int EmptyFifo(Fifo *f); // Проверка, пуста ли очередь?

void DoneFifo(Fifo *f); // Разрушить очередь

#endif

11. Очередь (кольцевая) на массиве в динамической памяти.

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

Unit Fifo11;

Interface

Const

FifoSize = 65520 div sizeof(pointer);

FifoOk = 0;

FifoOver = 1;

FifoUnder= 2;

var

FifoError:0..2;

Type

Index = 0..FifoSize;

BaseType = pointer;

TBuf = array[Index] of BaseType

Stack = record

PBuf: ^TBuf;

SizeBuf: word; {количество элементов в массиве}

SizeEl: word; {размер элемента очереди}

Uk1 : Index; {указывает на “голову” очереди}

Uk2 : Index; {указывает на “хвост” очереди}

end;

procedure InitFifo(var f : fifo; SizeBuf, SizeEL: word);

{инициализация очереди}

procedure PutFifo(var f : fifo; b : basetype);

{поместить элемент в очередь}

procedure GetFifo(var f : fifo; var b : basetype);

{извлечь элемент из очереди}

function EmptyFifo(f : fifo):boolean; {очередь пуста}

procedure DoneFifo(var f: fifo);{разрушить очередь}

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

#if !defined(__FIFO11_H)

#define __FIFO11_H

const FifoOk = 0;

const FifoUnder = 1;

const FifoOver = 2;

int FifoError; // Переменная ошибок

typedef void *BaseType;

typedef struct Fifo

{

BaseType *Buf;

unsigned SizeBuf; // Максимальная длина очереди

unsigned SizeEl; // Размер элемента очереди

unsigned Uk1; // Указатель на «голову» очереди

unsigned Uk2; // Указатель на «хвост» очереди

unsigned N; // Количество элементов очереди

};

void InitFifo(Fifo* f, unsigned SizeEl, unsigned SizeBuf);

// Инициализация очереди

void PutFifo(Fifo *f, void *E); /* Поместить элемент в очередь */

void GetFifo(Fifo *f, void *E); // Извлечь элемент из очереди

void ReadFifo(Fifo *f, void *E); // Прочитать элемент

int EmptyFifo(Fifo *f); // Проверка, пуста ли очередь?

void DoneFifo(Fifo *f); // Разрушить очередь

#endif

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

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

Цель работы.

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

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

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

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

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

Стек

Стек -- это последовательность элементов, в которой доступ (операции включения, исключения, чтения элемента) осуществляется только с одного конца структуры -- с вершины стека. Стек называют структурой типа LIFO (от англ. Last In, First Out). Иногда стек называют магазином (по аналогии с магазином автомата). Стек -- это динамическая структура.

Над стеком определены следующие основные операции:

1. Инициализация.

2. Включение элемента.

3. Исключение элемента.

4. Чтение элемента.

5. Проверка пустоты стека.

6. Уничтожение стека.

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

CAR(стек) = CAR(BaseType)0 + CAR(BaseType)1 + … + CAR(BaseType)max,

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

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

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

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

1 -- массив (или указатель на массив), на основе которого реализуется стек;

2 -- количество элементов в массиве;

3 -- указатель вершины стека.

Указатель вершины стека может содержать индекс элемента, являющегося вершиной стека (рис.16) или индекс элемента, следующего за вершиной стека (рис.17).

Рис.16. СД типа «стек»

Рис.17. СД типа «стек»

На рис.16 элементы массива с индексами 1..6 являются элементами стека, а на рис.17 элементы стека -- это элементы с индексами 0..5.

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

При чтении элемента стека (см. рис.16) читается элемент массива, индекс которого соответствует указателю вершины стека, а при чтении элемента стека (рис.17) читается элемент массива, индекс которого на единицу меньше указателя вершины стека.

Для исключения элемента стека (см. рис.16, рис.17) достаточно уменьшить указатель вершины стека на единицу.

Теперь рассмотрим реализацию стека на СЛС.

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

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

1 -- массив (или указатель на массив);

2 -- количество элементов в массиве;

3 -- указатель на вершину стека.

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

Очередь

Очередь -- это последовательность элементов, в которой включают элементы с одной стороны («хвост» очереди), а исключают с другой («голова» очереди). Очередь называют структурой типа FIFO (от англ. First In, First Out).

Очередь -- это динамическая структура.

Над очередью определены следующие основные операции:

1. Инициализация.

2. Включение элемента.

3. Исключение элемента.

6. Проверка пустоты очереди.

7. Уничтожение очереди.

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

CAR(FIFO) = CAR(BaseType)0 + CAR(BaseType)1 + … + CAR(BaseType)max,

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

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

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

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

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

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

Операции включения и исключения будут выполняться в одинаковой степени эффективно, если реализовать очередь непосредственно на массиве. В этом случае очереди ставится в соответствие дискриптор, состоящий из 5-ти полей:

1 -- массив (или указатель на массив);

2 -- количество элементов в массиве;

3 -- указатель на «голову» очереди;

4 -- указатель на «хвост» очереди;

5 -- количество элементов в очереди.

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

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

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

В кольцевой очереди, когда указатель «хвоста» достигает последнего элемента массива, элемент включается в очередь, а указатель устанавливается на первый элемент массива. Аналогично, когда указатель «головы» достигает последнего элемента массива, элемент исключается из очереди, а указатель устанавливается на первый элемент массива. На рис.18 и рис.19 показаны возможные состояния кольцевой очереди.

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

1 -- указатель на «голову»;

2 -- указатель на «хвост»;

3 -- количество элементов в очереди.

«голова» «хвост»

Рис.18. СД типа «кольцевая очередь»

«хвост» «голова»



Рис.19. СД типа «кольцевая очередь»

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

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

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

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

3. Определите порядок функции временной сложности операций включения и исключения элемента очереди при ее реализации на последовательном списке.

4. Определите порядок функции временной сложности операций включения и исключения элемента кольцевой очереди.

5. Определите порядок функции временной сложности операций включения и исключения элемента очереди при ее реализации на односвязном списке.

Лабораторная работа №7. Структуры данных «дерево» (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. Реализовать СД «дерево» в соответствии с вариантом индивидуального (табл.17) задания в виде модулей на языках Pascal и С.

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

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

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

Варианты задач

Вариант 1

a) Построить дерево арифметического выражения, заданного в ОПЗ.

Операнды -- целочисленные константы.

Операции -- «+», «-», «*» и «div».

б) Вывести арифметическое выражение в ППЗ.

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

Вариант 2

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

Операции -- «+», «-», «*» и «div».

б) Вывести арифметическое выражение в ОПЗ.

в) Вычислить значение по дереву арифметического выражения и выводит результат выполнения каждой операции в виде:

<операнд><операция><операнд>=<значение>

Вариант 3

а) Построить упорядоченное сбалансированное дерево T.

M -- упорядоченный массив.

б) Вычислить высоту дерева.

в) Вывести дерево по уровням (в i-ю строку вывода -- вершины i-го

уровня).

Вариант 4

а) Построить дерево по его скобочному представлению.

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

в) Вывести листья дерева.

Вариант 5

а) Построить упорядоченное дерево.

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

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

Вариант 6

а) Построить дерево в ширину.

б) Вычислить количество вершин дерева T, имеющих n сыновей.

в) Вывести выводит самый длинный путь от корня до листа.

Вариант 7

а) Построить дерево в глубину.

б) Определить количество вершин в дереве T на n-ом уровне.

в) Вывести выводит все пути от листьев до корня (в i-ю строку вывода -- i-ый путь).

Вариант 8

а) Построить упорядоченное дерево.

б) Вывести упорядоченную по возрастанию последовательность, составленную из элементов дерева, меньших k.

в) Вывести вершины, для которых левое и правое поддерево имеют равное количество вершин.

Вариант 9

а) Построить упорядоченное дерево.

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

в) Вывести количество вершин в левом и в правом поддереве для каждой вершины дерева.

Вариант 10

а) Построить дерево по его скобочному представлению.

б) Создать копию дерева.

в) Сравнить два дерева на равенство.

Модули

1. Дерево в динамической памяти (базовый тип определяется задачей).

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

Unit Tree1;

Interface

Const TreeOk = 0;

TreeNotMem = 1;

TreeUnder = 2;

Type BaseType = …; {определить !!!}

PtrEl = ^Element;

Element = Record Data : BaseType;

LSon,RSon : PtrEl;

End;

Tree= ^PtrEl;

Var TreeError : 0..2;

Procedure InitTree(var T:Tree); {инициализация -- создается элемент, который будет содержать корень дерева}

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,TS:Tree); {перейти к левому сыну, где T -- адрес ячейки, содержащей адрес текущей вершины, TS -- адрес ячейки, содержащей адрес корня левого поддерева(левого сына)}

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

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

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

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

#if !defined(__TREE1_H)

const TreeOk = 0;

const TreeNotMem = 1;

const TreeUnder = 2;

typedef /*определить !!!*/ BaseType;

typedef struct element *ptrel;

typedef struct element{basetype data;

ptrel LSon;

ptrel RSon;}

typedef PtrEl *Tree;

short TreeError;

void InitTree(Tree *T)// инициализация -- создается элемент, который будет содержать корень дерева

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

2. Элементы дерева находятся в массиве MemTree, расположенном в статической памяти. Базовый тип зависит от задачи. «Свободные» элементы массива объединяются в список (ССЭ), на начало которого указывает левый сын первого элемента массива. В массиве MemTree

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

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

Unit Tree2;

Interface

Const TreeOk = 0;

TreeNotMem = 1;

TreeUnder = 2;

SizeMem = 100;

Type BaseType = …; {определить !!!}

Index = 0..SizeMem;

PtrEl = Index;

Element = Record Data : BaseType;

LSon,RSon : PtrEl;

End;

Tree = ^PtrEl;

Var TreeError : 0..2;

MemTree: array[Index] of Element;

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

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,TS:Tree); {перейти к левому сыну, где T -- адрес ячейки, содержащей адрес текущей вершины, TS -- адрес ячейки, содержащей адрес корня левого поддерева(левого сына)}

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

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

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

Implementation

Procedure InitMem; forward; {связывает все элементы массива в

список свободных элементов}

Function EmptyMem: boolean; forward; {возвращает TRUE, если в

массиве нет свободных элементов}

Function NewMem: word; forward; {возвращает номер свободного

элемента и исключает его из ССЭ}

Procedure DisposeMem(n:word); forward; {делает n-й элемент мас-

сива свободным и включает его в ССЭ}

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

#if !defined(__TREE2_H)

#define SizeMem 100

const TreeOk = 0;

const TreeNotMem = 1;

const TreeUnder = 2;

typedef /*определить !!!*/ BaseType;

typedef unsigned char PtrEl;

typedef struct element{basetype data;

ptrel LSon;

ptrel RSon;}

typedef PtrEl *Tree;

short TreeError;

Element MemTree[SizeMem];

void InitTree(Tree *T)// инициализация -- создается элемент, который будет содержать корень дерева

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)//удаление листа

void InitMem() /*связывает все элементы массива в список свободных элементов*/

int EmptyMem() /*возвращает 1, если в массиве нет свободных элементов, 0 -- в противном случае*/

unsigned int NewMem() /*возвращает номер свободного элемента и исключает его из ССЭ*/

void DisposeMem(unsigned n)/*делает n-й элемент массива свободным и включает его в ССЭ*/

#endif

3. Элементы дерева находятся в массиве, расположенном в динамической памяти. Базовый тип зависит от задачи. «Свободные» элементы массива объединяются в список (ССЭ), на начало которого указывает левый сын первого элемента массива. В массиве может

находиться несколько деревьев.

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

Unit Tree3;

Interface

Const TreeOk = 0;

TreeNotMem = 1;

TreeUnder = 2;

Type BaseType = …; {определить !!!}

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

PtrEl = Index;

Element = Record Data : BaseType;

LSon,RSon : PtrEl;

End;

Mem = array[Index] of Element;

Pmem = ^Mem;

Tree = ^Ptr: PtrEl;

Var TreeError : 0..2;

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

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

Procedure InitTree(var T:Tree); {инициализация памяти}

Procedure InitTree(var T:Tree); {инициализация дерева}

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,TS:Tree); {перейти к левому сыну}

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

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

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

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

#if !defined(__TREE3_H)

#define Index 1000

const TreeOk = 0;

const TreeNotMem = 1;

const TreeUnder = 2;

typedef /*определить !!!*/ BaseType;

typedef unsigned char 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; //размер массива

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

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

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

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

Unit Tree4;

Interface

Const TreeOk = 0;

TreeNotMem = 1;

TreeUnder = 2;

Type BaseType = …; {определить !!!}

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;

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(__TREE4_H)

#define Index 1000

const TreeOk = 0;

const TreeNotMem = 1;

const TreeUnder = 2;

typedef /*определить !!!*/ BaseType;

typedef unsigned char 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;

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

5. Дерево в динамической памяти (базовый тип -- произвольный).

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

Unit Tree5;

Interface

Const TreeOk = 0;

TreeNotMem = 1;

TreeUnder = 2;

Type BaseType = pointer;

PtrEl = ^Element;

Element = Record Data : BaseType;

LSon,RSon : PtrEl;

End;

Tree= ^PtrEl;

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(__TREE5_H)

const TreeOk = 0;

const TreeNotMem = 1;

const TreeUnder = 2;

typedef void* BaseType;

typedef struct element *ptrel;

typedef struct element{basetype data;

ptrel LSon;

ptrel RSon;}

typedef PtrEl *Tree;

unsigned Size;

short TreeError;

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

6. Элементы дерева находятся в массиве MemTree, расположенном в статической памяти. Базовый тип -- произвольный. «Свободные» элементы массива объединяются в список (ССЭ), на начало которого указывает левый сын первого элемента массива. В массиве MemTree могут располагаться несколько деревьев.

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

Unit Tree6;

Interface

Const TreeOk = 0;

TreeNotMem = 1;

TreeUnder = 2;

SizeMem = 100;

Type BaseType = pointer;

Index = 0..SizeMem;

PtrEl = Index;

Element = Record Data : BaseType;

LSon,RSon : PtrEl;

End;

Tree= ^PtrEl;

Var TreeError : 0..2;

MemTree: array[Index] of Element;

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);{удаление листа}

Implementation

Procedure InitMem; forward; {связывает все элементы массива в

список свободных элементов}

Function EmptyMem: boolean; forward; {возвращает TRUE, если в

массиве нет свободных элементов}

Function NewMem: word; forward; {возвращает номер свободного

элемента и исключает его из ССЭ}

Procedure DisposeMem(n:word); forward; {делает n-й элемент мас-

сива свободным и включает его в ССЭ}

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

#if !defined(__TREE6_H)

#define Index 1000

const TreeOk = 0;

const TreeNotMem = 1;

const TreeUnder = 2;

typedef void *BaseType;

typedef unsigned char PtrEl;

typedef struct element{basetype data;

ptrel LSon;

ptrel RSon;}

typedef PtrEl *Tree;

unsigned Size;

short TreeError;

Element MemTree[Index];

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)//удаление листа

void InitMem() /*связывает все элементы массива в список свободных элементов*/

int EmptyMem() /*возвращает 1, если в массиве нет свободных элементов,0 -- в противном случае*/

unsigned int NewMem() /*возвращает номер свободного элемента и исключает его из ССЭ*/

void DisposeMem(unsigned n)/*делает n-й элемент массива свободным и включает его в ССЭ*/

#endif

7. Элементы дерева находятся в массиве, расположенном в динамической памяти. Базовый тип - произвольный. «С...