2015-01-30
935
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. Тема лабораторной работы.
2. Цель работы.
3. Характеристика СД «стек» и «очередь» (п.1 постановки задачи).
4. Индивидуальное задание.
5. Текст модулей для реализации СД «стек» и «очередь» на языках Pascal и С, тексты программ для отладки модулей, тестовые данные и результаты работы программ.
6. Тексты программ на языках 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).
0 1 2 3 4 5 6 7 8 9 10
 |
1 –
2 –
3 –
Рис.16. СД типа «стек»
0 1 2 3 4 5 6 7 8 9 10
1 –
2 –
3 –
Рис.17. СД типа «стек»
На рис.16 элементы массива с индексами 1..6 являются элементами стека, а на рис.17 элементы стека — это элементы с индексами 0..5.
В указатель вершины стека при инициализации стека (см. рис.16) заносится 0, а при инициализации стека (см. рис.17) заносится 1. При включении элемента в стек (см. рис.16) сначала увеличивается указатель вершины стека, а затем в элемент массива с индексом, соответствующем указателю вершины стека, заносится значение включаемого в стек элемента. При включении элемента в стек (см. рис.17) порядок действий изменяется на противоположный.
При чтении элемента стека (см. рис.16) читается элемент массива, индекс которого соответствует указателю вершины стека, а при чтении элемента стека (рис.17) читается элемент массива, индекс которого на единицу меньше указателя вершины стека.
Для исключения элемента стека (см. рис.16, рис.17) достаточно уменьшить указатель вершины стека на единицу.
Теперь рассмотрим реализацию стека на СЛС.
Пусть стек реализуется на основе ОЛС. Если в качестве вершины стека выбрать первый элемент списка, то указатель текущего элемента ОЛС должен указывать на фиктивный элемент. При этом операции чтения, включения и исключения элемента выполняются достаточно быстро, не требуют изменения указателя на текущий элемент и перемещения элементов ОЛС. Если в качестве вершины стека принять последний элемент ОЛС, то при выполнении операций чтения и включения элемента в стек текущим элементом ОЛС должен быть последний элемент ОЛС. При выполнении операции исключения текущим элементом должен быть предпоследний в ОЛС, для поиска которого необходимо стать в начало ОЛС и последовательно пройти по всем элементам до предпоследнего, постоянно переопределяя указатель на текущий элемент, что требует неоправданных вычислений и затрат времени.
Учитывая ограниченный характер доступа к элементам стек можно достаточно эффективно реализовать по принципу ОЛС без фиктивного элемента. Тогда дискриптор стека будет содержать только одно поле (при реализации на связанных элементах, расположенных в динамической памяти), содержащее адрес первого элемента (вершины стека). Если элементами стека будут связанные элементы, расположенные в массиве (в статической или динамической памяти), то дискриптор будет содержать три поля:
1 — массив (или указатель на массив);
2 — количество элементов в массиве;
3 — указатель на вершину стека.
При реализации стека на основе ДЛС выбор элемента, являющегося вершиной стека не имеет значения, т.к. и для первого и для последнего элемента ДЛС операции чтения, включения и исключения эффективны в одинаковой степени.
