Pascal/С

Рассмотрение особенностей встроенных и производных структур данных. Сравнительный анализ методов сортировки, алгоритмов поиска в программе Pascal/С. Характеристика структуры данных "строка", "линейные списки", "стек" и "очередь", "дерево", "таблица".

Рубрика Программирование, компьютеры и кибернетика
Вид лабораторная работа
Язык русский
Дата добавления 27.09.2017
Размер файла 604,2 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

ListUnder = 2;

ListEnd = 3;

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

PtrEl = ^Element;

Element = Record Data : BaseType;

Next : PtrEl;

End;

List = Record

Start,Ptr : PtrEl;

N : Word;

End;

Var ListError : 0..3;

Procedure InitList(var L:List);

Procedure PutList(var L:List; E:Basetype);

Procedure GetList(var L:List; var E:BaseType);

Procedure ReadList(var L:List; var E:BaseType);

Function FullList(var L:List):boolean;

Function EndList(var L:List):boolean;

Function Count(var L:List):Word;

Procedure BeginPtr(var L:List);

Procedure EndPtr(var L:List);

Procedure MovePtr(var L:List);

Procedure MoveTo(var L:List; N:word);

Procedure DoneList(var L:List);

Procedure CopyList(var L1,L2:List);

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

#if !defined(__LIST2_H)

const ListOk = 0;

const ListNotMem = 1;

const ListUnder = 2;

const ListEnd = 3;

typedef < определить > BaseType;

typedef struct element *ptrel;

typedef struct element {basetype data;

ptrel next;};

typedef struct List {ptrel Start;

ptrel ptr;

unsigned int N}

short ListError;

void InitList(List *L);

void PutList(List *L, BaseType E);

void GetList(List *L, BaseType *E);

void ReadList(List *L,BaseType *E);

int FullList(List *L);

int EndList(List *L);

usigned int Count(List *L);

void BeginPtr(List *L);

void EndPtr(List *L);

void MovePtr(List *L);

void MoveTo(List *L, unsigned int n);

void DoneList(List *L);

void CopyList(List *L1,List *L2);

#endif

3. ОЛС в динамической памяти (базовый тип -- pointer). Выделение памяти под информационную часть элемента ОЛС и запись в нее значения происходит при выполнении процедуры PutList. При выполнении процедуры GetList память, занимаемая элементом, освобождается. Размер информационной части элемента задается при инициализации ОЛС и сохраняется в дескрипторе.

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

Unit List3;

Interface

Const ListOk = 0;

ListNotMem = 1;

ListUnder = 2;

ListEnd = 3;

Type BaseType = Pointer;

PtrEl = ^Element;

Element = Record Data : BaseType;

Next : PtrEl;

End;

List = Record

Start,Ptr : PtrEl;

N : Word; { длина списка }

Size : Word { размер информационной}

End; { части элемента }

Var ListError : 0..3;

Procedure InitList(var L:List; Size:Word);

Procedure PutList(var L:List; var E);

Procedure GetList(var L:List; var E);

Procedure ReadList(var L:List; var E);

Function FullList(var L:List):boolean;

Function EndList(var L:List):boolean;

Function Count(var L:List):Word;

Procedure BeginPtr(var L:List);

Procedure EndPtr(var L:List);

Procedure MovePtr(var L:List);

Procedure MoveTo(var L:List; N:word);

Procedure DoneList(var L:List);

Procedure CopyList(var L1,L2:List);

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

#if !defined(__LIST3_H)

const ListOk = 0;

const ListNotMem = 1;

const ListUnder = 2;

const ListEnd = 3;

typedef void* BaseType;

typedef struct element *ptrel;

typedef struct element {basetype data;

ptrel next;};

typedef struct List {ptrel Start;

ptrel ptr;

unsigned int N;//размер списка

unsigned int size;}//размер информационной части элемента

short ListError;

void InitList(List *L);

void PutList(List *L, BaseType E);

void GetList(List *L, BaseType *E);

void ReadList(List *L,BaseType *E);

int FullList(List *L);

int EndList(List *L);

usigned int Count(List *L);

void BeginPtr(List *L);

void EndPtr(List *L);

void MovePtr(List *L);

void MoveTo(List *L, unsigned int n);

void DoneList(List *L);

void CopyList(List *L1,List *L2);

#endif

4. Элементы ОЛС находятся в массиве MemList, расположенном в статической памяти. Базовый тип -- pointer. Каждый элемент массива имеет признак того, является ли он элементом ОЛС или «свободен». Выделение памяти под информационную часть элемента ОЛС и запись в нее значения выполняется до обращения к процедуре PutList. При выполнении процедуры GetList память информационной части элементане освобождается и ее адрес является выходным параметром.

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

Unit List4;

Interface

Const ListOk = 0;

ListNotMem = 1;

ListUnder = 2;

ListEnd = 3;

SizeList = 100;

Type BaseType = Pointer;

Index = 0..SizeList;

PtrEl = Index;

Element = Record Data : BaseType;

Next : PtrEl;

Flag : Boolean {TRUE, если элемент}

{принадлежит ОЛС }

End; {FALSE, если “свободен”}

List = Record

Start,Ptr : PtrEl;

N : Word

End;

Var MemList: array[Index] of Element;

ListError : 0..3;

Procedure InitList(var L:List);

Procedure PutList(var L:List; E:BaseType);

Procedure GetList(var L:List; var E:BaseType);

Function ReadList(var L:List):Pointer;

Function FullList(var L:List):boolean;

Function EndList(var L:List):boolean;

Function Count(var L:List):Word;

Procedure BeginPtr(var L:List);

Procedure EndPtr(var L:List);

Procedure MovePtr(var L:List);

Procedure MoveTo(var L:List; N:word);

Procedure DoneList(var L:List);

Procedure CopyList(var L1,L2:List);

Implementation

Procedure InitMem; forward; {устанавливает Flag каждого элемента в FALSE, вызывается в разделе операторов модуля}

Function EmptyMem: boolean; forward; {возвращает TRUE, если в массиве нет свободных элементов}

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

Procedure DisposeMem(n:word); forward; {делает n-й элемент массива свободным}

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

#if !defined(__LIST4_H)

#define SizeList 100

const ListOk = 0;

const ListNotMem = 1;

const ListUnder = 2;

const ListEnd = 3;

typedef void *BaseType;

typedef unsigned ptrel;

typedef struct element {basetype data;

ptrel next; /*flag=1 если элемент принадлежит ОЛС*/

int flag;}; //flag=0 если свободен

typedef struct List{ptrel Start;

ptrel ptr;

unsigned int N}

element MemList[SizeList];

short ListError;

void InitList(List *L)

void PutList(List *L, BaseType E)

void GetList(List *L, BaseType *E)

void ReadList(List *L,BaseType *E)

int FullList(List *L)

int EndList(List *L)

usigned int Count(List *L)

void BeginPtr(List *L)

void EndPtr(List *L)

void MovePtr(List *L)

void MoveTo(List *L, unsigned int n)

void DoneList(List *L)

void CopyList(List *L1,List *L2)

void InitMem()/*присваивает Flag каждoго элемента в 0*/

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

unsigned NewMem()//возвращает номер свободного элемента

void DisposeMem(unsigned n) /*делает n-й элемент масcива cвободным*/

#endif

5. Элементы ОЛС находятся в массиве MemList, расположенном в статической памяти. Базовый тип зависит от задачи. «Свободные» элементы массива объединяются в список, на начало которого указывает поле-указатель первого элемента массива. Выделение памяти под информационную часть элемента ОЛС и запись в нее значения происходит при выполнении процедуры PutList. При выполнении

процедуры GetList память, занимаемая элементом, освобождается.

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

Unit List5;

Interface

Const ListOk = 0;

ListNotMem = 1;

ListUnder = 2;

ListEnd = 3;

SizeList = 100;

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

Index = 0..SizeList;

PtrEl = Index;

Element = Record Data : BaseType;

Next : PtrEl;

End;

List = Record

Start,Ptr : PtrEl;

N : Word

End;

Var MemList: array[Index] of Element;

ListError : 0..3;

Procedure InitList(var L:List);

Procedure PutList(var L:List; E:BaseType);

Procedure GetList(var L:List; var E:BaseType);

Procedure ReadList(var L:List; var E:BaseType):

Function FullList(var L:List):boolean;

Function EndList(var L:List):boolean;

Function Count(var L:List):Word;

Procedure BeginPtr(var L:List);

Procedure EndPtr(var L:List);

Procedure MovePtr(var L:List);

Procedure MoveTo(var L:List; N:word);

Procedure DoneList(var L:List);

Procedure CopyList(var L1,L2:List);

Implementation

Procedure InitMem; forward; {связывает все элементы массива в список свободных элементов}

Function EmptyMem: boolean; forward; {возвращает TRUE, если в массиве нет свободных элементов}

Function NewMem: word; forward; {возвращает номер свободного элемента и исключает его из ССЭ}

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

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

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

#if !defined(__LIST5_H)

#define SizeList 100

const ListOk = 0;

const ListNotMem = 1;

const ListUnder = 2;

const ListEnd = 3;

typedef <определить> BaseType;

typedef unsigned ptrel;

typedef struct element {basetype data;

ptrel next; };

typedef struct List {ptrel Start;

ptrel ptr;

unsigned int N}

element MemList[SizeList];

short ListError;

void InitList(List *L)

void PutList(List *L, BaseType E)

void GetList(List *L, BaseType *E)

void ReadList(List *L,BaseType *E)

int FullList(List *L)

int EndList(List *L)

usigned int Count(List *L)

void BeginPtr(List *L)

void EndPtr(List *L)

void MovePtr(List *L)

void MoveTo(List *L, unsigned int n)

void DoneList(List *L)

void CopyList(List *L1,List *L2)

void InitMem()/*присваивает Flag каждoго элемента в 0*/

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

unsigned NewMem()//возвращает номер свободного элемента

void DisposeMem(unsigned n) /*делает n-й элемент масcива cвободным*/

#endif

6. ПЛС. Массив, на основе которого реализуется ПЛС, находится в статической памяти (базовый тип элемента -- pointer). Выделение памяти под информационную часть элемента ПЛС и запись в нее значения происходит при выполнении процедуры PutList. При выполнении процедуры GetList память, занимаемая элементом, освобождается. Размер информационной части элемента задается при инициализации ПЛС и сохраняется в дескрипторе.

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

Unit List6;

Interface

Const ListOk = 0;

ListNotMem = 1;

ListUnder = 2;

ListEnd = 3;

Type BaseType = Pointer;

Index = 0..100;

PtrEl = Index;

List = Record

MemList: array[Index] of BaseType;

Ptr : PtrEl;

N : Word; { длина списка }

Size : Word { размер информационной }

End; { части элемента }

Var ListError : 0..3;

Procedure InitList(var L:List; Size:Word);

Procedure PutList(var L:List; var E);

Procedure GetList(var L:List; var E);

Procedure ReadList(var L:List; var E);

Function FullList(var L:List):boolean;

Function EndList(var L:List):boolean;

Function Count(var L:List):Word;

Procedure BeginPtr(var L:List);

Procedure EndPtr(var L:List);

Procedure MovePtr(var L:List);

Procedure MoveTo(var L:List; N:word);

Procedure DoneList(var L:List);

Procedure CopyList(var L1,L2:List);

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

#if !defined(__LIST6_H)

#define SizeList 100

const ListOk = 0;

const ListNotMem = 1;

const ListUnder = 2;

const ListEnd = 3;

typedef void *BaseType;

typedef unsigned ptrel;

typedef struct List {basetype MemList[SizeList];

ptrel ptr;

unsigned int N;

unsigned int Size;};

short ListError;

void InitList(List *L)

void PutList(List *L, BaseType E)

void GetList(List *L, BaseType *E)

void ReadList(List *L,BaseType *E)

int FullList(List *L)

int EndList(List *L)

usigned int Count(List *L)

void BeginPtr(List *L)

void EndPtr(List *L)

void MovePtr(List *L)

void MoveTo(List *L, unsigned int n)

void DoneList(List *L)

void CopyList(List *L1,List *L2)

#endif

7. ПЛС. Массив, на основе которого реализуется ПЛС, находится в динамической памяти (базовый тип элемента определяется задачей). Память под массив выделяется при инициализации ПЛС и количество элементов сохраняется в дескрипторе.

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

Unit List7;

Interface

Const ListOk = 0;

ListNotMem = 1;

ListUnder = 2;

ListEnd = 3;

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

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

TMemList = array[Index] of BaseType;

PtrEl = Index;

List = Record

PMemList: ^TmemList;

Ptr : PtrEl;

N : Word; { длина списка }

SizeМем : Word { размер массива }

End;

Var ListError : 0..3;

Procedure InitList(var L:List; SizeMem:Word);

Procedure PutList(var L:List; var E:BaseType);

Procedure GetList(var L:List; var E:BaseType);

Procedure ReadList(var L:List; var E:BaseType);

Function FullList(var L:List):boolean;

Function EndList(var L:List):boolean;

Function Count(var L:List):Word;

Procedure BeginPtr(var L:List);

Procedure EndPtr(var L:List);

Procedure MovePtr(var L:List);

Procedure MoveTo(var L:List; N:word);

Procedure DoneList(var L:List);

Procedure CopyList(var L1,L2:List);

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

#if !defined(__LIST7_H)

#define Index 1000

const ListOk = 0;

const ListNotMem = 1;

const ListUnder = 2;

const ListEnd = 3;

typedef <определить> BaseType;

typedef basetype TMemList[Index];

typedef unsigned ptrel;

typedef struct List {TMemList* PMemList;

ptrel ptr;

unsigned int N; // длина списка

unsigned int SizeMem;};// размер массива

short ListError;

void InitList(List *L,unsigned SizeMem)

void PutList(List *L, BaseType E)

void GetList(List *L, BaseType *E)

void ReadList(List *L,BaseType *E)

int FullList(List *L)

int EndList(List *L)

usigned int Count(List *L)

void BeginPtr(List *L)

void EndPtr(List *L)

void MovePtr(List *L)

void MoveTo(List *L, unsigned int n)

void DoneList(List *L)

void CopyList(List *L1,List *L2)

#endif

8. ПЛС. Массив, на основе которого реализуется ПЛС, находится в динамической памяти (базовый тип элемента -- Pointer). Память под массив выделяется при инициализации ПЛС и количество элементов сохраняется в дескрипторе. Выделение памяти под информационную часть элемента ПЛС и запись в нее значения происходит при выполнении процедуры PutList. При выполнении процедуры GetList память, занимаемая информационной частью элемента, освобождается. Размер информационной части элемента задается при инициализации ПЛС и сохраняется в дескрипторе.

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

Unit List8;

Interface

Const ListOk = 0;

ListNotMem = 1;

ListUnder = 2;

ListEnd = 3;

Type BaseType = Pointer;

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

TMemList = array[Index] of BaseType;

PtrEl = Index;

List = Record

PMemList: ^TmemList;

Ptr : PtrEl;

N : Word; { длина списка }

SizeМем : Word { размер массива }

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

End;

Var ListError : 0..3;

Procedure InitList(var L:List; SizeMem, SizeEl:Word);

Procedure PutList(var L:List; var E);

Procedure GetList(var L:List; var E);

Procedure ReadList(var L:List; var E);

Function FullList(var L:List):boolean;

Function EndList(var L:List):boolean;

Function Count(var L:List):Word;

Procedure BeginPtr(var L:List);

Procedure EndPtr(var L:List);

Procedure MovePtr(var L:List);

Procedure MoveTo(var L:List; N:word);

Procedure DoneList(var L:List);

Procedure CopyList(var L1,L2:List);

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

#if !defined(__LIST8_H)

#define SizeList 100

#define Index 1000

const ListOk = 0;

const ListNotMem = 1;

const ListUnder = 2;

const ListEnd = 3;

typedef void *BaseType;

typedef basetype TMemList[Index];

typedef unsigned ptrel;

typedef struct List {TMemList* PMemList;

ptrel ptr;

unsigned int N; // длина списка

unsigned int SizeMem;};// размер массива

short ListError;

void InitList(List *L,unsigned SizeMem)

void PutList(List *L, BaseType E)

void GetList(List *L, BaseType *E)

void ReadList(List *L,BaseType *E)

int FullList(List *L)

int EndList(List *L)

usigned int Count(List *L)

void BeginPtr(List *L)

void EndPtr(List *L)

void MovePtr(List *L)

void MoveTo(List *L, unsigned int n)

void DoneList(List *L)

void CopyList(List *L1,List *L2)

#endif

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

InitList -- инициализация списка.

PutList -- включение элемента в список.

GetList -- исключение элемента из списка.

ReadList -- чтение элемента списка.

EmptyList -- проверка: свободен ли список.

EndList -- проверка: является ли элемент последним.

Count -- возвращает количество элементов в списке.

BeginPtr -- устанановка в начало списка.

EndPtr -- устанановка в конец списка.

MovePtr -- переход к следующему элементу.

MoveTo -- переход к n-му элементу.

DoneList -- удаление списка.

CopyList -- копирование списка L1 в список L2.

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

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

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

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

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

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

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

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

Линейный список (ЛС) -- это конечная последовательность однотипных элементов (узлов).

Количество элементов в последовательности называется длиной списка, причем длина в процессе работы программы может изменяться, поэтому ЛС -- динамическая структура.

Над СД ЛС определены следующие основные операции:

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

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

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

4. Чтение текущего элемента.

5. Переход в начало списка.

6. Переход в конец списка.

7. Переход к следующему элементу.

8. Переход к i-му элементу.

9. Определение длины списка.

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

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

CAR(ЛС) = CAR(BaseType)0 + CAR(BaseType)1 +… + CAR(BaseType)max,

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

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

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

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

Рассмотрим некоторые принципы реализации ЛС.

1. Реализация ПЛС

1.1. Последовательному линейному списку можно поставить в соответствие дескриптор, который состоит из 3-х полей:

1 -- массив, на основе которого реализуется ПЛС;

2 -- индекс текущего элемента;

3 -- длина ПЛС.

Дескриптор располагается в статической памяти в виде переменной соответствующего типа. Массив, на основе которого реализуется ПЛС, также располагается в статической памяти.

1.2. Дескриптор ПЛС состоит из 4-х полей:

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

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

3 -- индекс текущего элемента;

4 -- длина ПЛС.

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

Элементы ПЛС могут находиться непосредственно в элементах массива, или в динамической памяти, а их адреса -- в массиве.

2. Реализация ОЛС

2.1. Элементы ОЛС располагаются в динамической памяти. В статической памяти находится дескриптор ОЛС, состоящий из 3-х полей:

1 -- указатель на фиктивный элемент ОЛС;

2 -- указатель на текущий элемент;

3 -- длина ОЛС.

Адрес фиктивного элемента определяется при инициализации.

Элемент ОЛС может содержать либо поле данных, либо адрес данных.

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

В статической памяти находится дескриптор ОЛС, состоящий из трех полей:

1 -- указатель на фиктивный элемент ОЛС;

2 -- указатель на текущий элемент;

3 -- длина ОЛС.

Адрес фиктивного элемента определяется при инициализации.

Элемент ОЛС может содержать либо поле данных, либо адрес данных.

3. Реализация ДЛС

3.1. В статической памяти находится дескриптор ДЛС, состоящий из 3-х полей:

1 -- указатель на первый фиктивный элемент ДЛС;

2 -- указатель на последний фиктивный элемент ДЛС;

3 -- указатель на текущий элемент;

4 -- длина ДЛС.

Адреса фиктивных элементов определяется при инициализации.

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

В заключении выполним сравнительный анализ последовательных и связных списков по эффективности хранения и выполнения операций.

1. СЛС требуют дополнительной памяти для связей.

2. Легко исключить элемент СЛС. Для исключения элемента из ОЛС достаточно лишь установить поле-указатель предшествующего элемента на последующий.

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

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

5. В ПЛС быстрее, чем в СЛС, выполняется обращения к i-му элементу списка, т.к. доступ к элементам ПЛС прямой, а к элементам СЛС -- последовательный.

6. При использовании СЛС упрощается задача объединение двух списков или разбиение списков на части.

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

1. Что такое линейный список?

2. Определите характер изменчивости линейного списка.

3. Назовите основные операции над линейным списком.

4. Что собой представляет линейный список на абстрактном уровне?

5. Чем отличается последовательный линейный список от массива?

6. Что такое односвязный линейный список?

7. Какую структуру имеет элемент односвязного линейного списка?

8. Что такое двусвязный линейный список?

9. Какую структуру имеет элемент двусвязного линейного списка?

10. Как можно реализовать связный линейный список на массиве?

11. Какую структуру может иметь дескриптор линейного списка?

12. Зачем нужны фиктивные элементы в связных линейных списках?

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

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

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

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

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

18. Определите порядок функции временной сложности операции перехода к i-му элементу последовательного и связного линейного списка.

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

20. Какой алгоритм поиска целесообразно использовать в упорядоченном последовательном и связном линейном списке?

21. Предложите различные варианты реализации операции обмена соседних элементов в связном линейном списке.

22. Выполните сравнительный анализ алгоритмов сортировки связных линейных списков.

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

3. Разработать программы на языках Pascal и С, моделирующие вычислительную систему с постоянным шагом по времени (дискретное время) в соответствии с вариантом индивидуального задания (табл.16) с использованием модулей, полученных в результате выполнения пункта 2. Результат работы программ представить в виде таблицы 15. В первом столбце указывается время моделирования 0, 1, 2, …, N. Во втором -- для каждого момента времени указываются имена объектов (очереди -- F1, F2, …, FN; стеки -- S1, S2, …, SM; процессоры -- P1, P2, …, PK), а в третьем -- задачи (имя, время), находящиеся в объектах.

Таблица 15 - Результаты работы программы

Время

Объекты

Задачи

0

F1

(имя,время),(имя,время),. . .,(имя,время)

:

: : :

FN

(имя,время),(имя,время),. . .,(имя,время)

S1

(имя,время),(имя,время),. . .,(имя,время)

:

: : :

SM

(имя,время),(имя,время),. . .,(имя,время)

P1

(имя,время)

:

:

PK

(имя,время)

1

F1

(имя,время),(имя,время),. . .,(имя,время)

:

: : :

FN

(имя,время),(имя,время),. . .,(имя,время)

S1

(имя,время),(имя,время),. . .,(имя,время)

:

: : :

SM

(имя,время),(имя,время),. . ., (имя,время)

P1

(имя,время)

:

:

PK

(имя,время)

:

:

: : :

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

Номер варианта

Номер модуля

для стека

Номер модуля

для очереди

Номер

задачи

1

1

1

1

2

2

2

2

3

3

3

3

4

4

4

4

5

5

5

5

6

6

6

6

7

7

7

7

8

8

8

8

9

9

9

9

10

10

10

10

11

11

10

11

12

1

2

4

13

2

3

5

14

3

4

6

15

4

5

7

16

5

6

8

17

6

7

9

18

7

8

10

19

8

9

11

20

9

10

1

21

10

11

2

22

11

10

3

23

1

3

4

24

2

4

5

25

3

5

6

26

4

6

7

27

5

7

8

28

6

8

9

29

7

9

10

30

8

10

11

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

1. Система состоит из процессора P, трех очередей F0, F1, F2 и стека S (рис.9). В систему поступают запросы. Запрос можно представить записью

на языке Pascal:

Type

TInquiry= record

Name: String[10]; {имя запроса}

Time: Word; {время обслуживания}

P: Byte;{приоритет задачи 0 --высший,

1 -- средний, 2 -- низший}

end;

на языке C:

typedef struct TInquiry

{

char Name[10]; // Имя запроса

unsigned Time; // Время обслуживания

char P; /* Приоритет задачи: 0 -- высший,

1 -- средний, 2 -- низший */

};

Поступающие запросы ставятся в соответствующие приоритетам очереди. Сначала обрабатываются задачи из очереди F0. Если она пуста, можно обрабатывать задачи из очереди F1. Если и она пуста, то можно обрабатывать задачи из очереди F2. Если все очереди пусты, то система находится в ожидании поступающих задач (процессор свободен), либо в режиме обработки предыдущей задачи (процессор занят). Если поступает задача с более высоким приоритетом, чем обрабатываемая в данный момент, то обрабатываемая помещается в стек и может обрабатываться тогда и только тогда, когда все задачи с более высоким приоритетом уже обработаны.

Рис.9. Система задач 1 -- 3

2. Система состоит из процессора P, трех очередей F0, F1, F2 и стека S (см. рис.9). В систему поступают запросы. Запрос можно представить записью

на языке Pascal:

Type

TInquiry= record

Name: String[10]; {имя запроса}

Time: Word; {время обслуживания}

P: Byte;{приоритет задачи 0 -- высший, 1 -- средний, 2 --низший}

end;

на языке C:

typedef struct TInquiry

{

char Name[10]; // имя запроса

unsigned Time; // время обслуживания

char P; /* приоритет задачи: 0 -- высший, 1 -- средний, 2 -- низший */

};

Поступающие запросы ставятся в соответствующие приоритетам очереди. Сначала обрабатываются задачи из очереди F0. Если она пуста, можно обрабатывать задачи из очереди F1. Если и она пуста, то можно обрабатывать задачи из очереди F2. Если все очереди пусты, то система находится в ожидании поступающих задач (процессор свободен), либо в режиме обработки предыдущей задачи (процессор занят). Если обрабатывается задача с низшим приоритетом и поступает задача с более высоким приоритетом, то обрабатываемая помещается в стек и может обрабатываться тогда и только тогда, когда все задачи с более высоким приоритетом уже обработаны.

3. Система состоит из процессора P, трех очередей F0, F1, F2 и стека S (см. рис.9). В систему поступают запросы. Запрос можно представить записью

на языке Pascal:

Type

TInquiry= record

Name: String[10]; {имя запроса}

Time: Word; {время обслуживания}

P: Byte;{приоритет задачи 0 -- высший,

1 -- средний, 2 -- низший}

end;

на языке C:

typedef struct TInquiry

{

char Name[10]; // Имя запроса

unsigned Time; // Время обслуживания

char P; /* Приоритет задачи: 0 -- высший,

1 -- средний, 2 -- низший */

};

Поступающие запросы ставятся в соответствующие приоритетам очереди. Сначала обрабатываются задачи из очереди F0. Если она пуста, можно обрабатывать задачи из очереди F1. Если и она пуста, то можно обрабатывать задачи из очереди F2. Если все очереди пусты, то система находится в ожидании поступающих задач (процессор свободен), либо в режиме обработки предыдущей задачи (процессор занят). Если поступает задача с более высоким приоритетом, чем обрабатываемая в данный момент, то обрабатываемая помещается в стек, если она выполнена менее чем на половину по времени, и может обрабатываться тогда и только тогда, когда все задачи с более высоким приоритетом уже обработаны.

4. Система состоит из двух процессоров P1 и P2, трех очередей F0, F1, F2 и двух стеков S1 и S2 (рис.10).

Рис.10. Система задчи 4

В систему поступают запросы. Запрос можно представить записью

на языке Pascal:

Type

TInquiry= record

Name: String[10]; {имя запроса}

Time: Word; {время обслуживания}

P: Byte;{приоритет задачи 0 -- высший,

1 -- средний, 2 -- низший}

end;

на языке C:

typedef struct TInquiry

{

char Name[10]; // имя запроса

unsigned Time; // время обслуживания

char P; /* приоритет задачи: 0 -- высший,

1 -- средний, 2 -- низший */

};

Поступающие запросы ставятся в соответствующие приоритетам очереди. Сначала обрабатываются задачи из очереди F0. Задача из очереди F0 поступает в свободный процессор P1 или P2, если оба свободны, то в P1. Если очередь F0 пуста, то обрабатываются задачи из очереди F1. Задача из очереди F1 поступает в свободный процессор P1 или P2, если оба свободны, то в P1. Если очереди F0 и F1 пусты, то обрабатываются задачи из очереди F2. Задача из очереди F2 поступает в свободный процессор P1 или P2, если оба свободны, то в P1. Если процессоры заняты и поступает задача с более высоким приоритетом, чем обрабатываемая в одном из процессоров, то задача из процессора помещается в соответствующий стек, а поступающая -- в процессор. Задача из стека помещается в соответствующий процессор, если он свободен, и очереди с задачами более высокого приоритета пусты.

5. Система состоит из трех процессоров P1, P2, P3, очереди F, стека S и распределителя R (рис.11).

Рис.11. Система задач 5 и 6

В систему поступают запросы на выполнение задач трех типов -- Т1, Т2 и Т3, каждая для своего процессора. Запрос можно представить записью

на языке Pascal:

Type

TInquiry= record

Name: String[10]; {имя запроса}

Time: Word; {время обслуживания}

T: Byte;{тип задачи 1 -- Т1, 2 -- Т2, 3 -- Т3}

end;

на языке C:

typedef struct TInquiry

{

char Name[10]; // Имя запроса

unsigned Time; // Время обслуживания

char T; // Тип задачи: 1 -- Т1, 2 -- Т2, 3 -- Т3

};

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

6. Система состоит из трех процессоров P1, P2, P3, очереди F, стека S и распределителя R (рис.11). В систему поступают запросы на выполнение задач трех типов -- Т1, Т2 и Т3, каждая для своего процессора. Запрос можно представить записью

на языке Pascal:

Type

TInquiry= record

Name: String[10]; {имя запроса}

Time: Word; {время обслуживания}

T: Byte;{тип задачи 1 -- Т1, 2 -- Т2, 3 -- Т3}

end;

на языке C:

typedef struct TInquiry

{

char Name[10]; // Имя запроса

unsigned Time; // Время обслуживания

char T; // Тип задачи: 1 -- Т1, 2 -- Т2, 3 -- Т3

};

Поступающие запросы ставятся в очередь. Если в «голове» очереди находится задача Ti и процессор Рi свободен, то распределитель ставит задачу на выполнение в процессор Pi, а если процессор Pi занят, то распределитель отправляет задачу в стек и из очереди извлекается следующая задача. Задача из стека поступает в соответствующий ей свободный процессор только тогда, когда очередь пуста.

7. Система состоит из двух процессоров P1 и P2, трех очередей F1, F2, F3 и стека (рис.12).

Рис.12. Система задач 7 и 10

В систему могут поступать запросы на выполнение задач трех типов -- Т1, Т2, Т3. Задача типа Т1 может выполняться только процессором P1. Задача типа Т2 может выполняться только процессором P2. Задача типа Т3 может выполняться любым процессором. Запрос можно представить записью

на языке Pascal:

Type

TInquiry= record

Name: String[10]; {имя запроса}

Time: Word; {время обслуживания}

T: Byte;{тип задачи 1 -- Т1, 2 -- Т2, 3 -- Т3}

end;

на языке C:

typedef struct TInquiry

{

char Name[10]; // имя запроса

unsigned Time; // время обслуживания

char T; // тип задачи: 1 -- Т1, 2 -- Т2, 3 -- Т3

};

Поступающие запросы ставятся в соответствующие типам задач очереди. Если очередь F1 не пуста и процессор P1 свободен, то задача из очереди F1 поступает на обработку в процессор P1. Если процессор Р1 обрабатывает задачу типа Т3, а процессор Р2 свободен и очередь F2 пуста, то задача из процессора Р1 поступает в процессор Р2, а задача из очереди F1 в процессор Р1, если же процессор Р2 занят или очередь F2 не пуста, то задача из процессора Р1 помещается в стек.

Если очередь F2 не пуста и процессор P2 свободен, то задача из очереди F2 поступает на обработку в процессор P2. Если процессор Р2 обрабатывает задачу типа Т3, а процессор Р1 свободен и очередь F1 пуста, то задача из процессора Р2 поступает в процессор Р1, а задача из очереди F2 -- в процессор Р2, если же процессор Р1 занят или очередь F1 не пуста, то задача из процессора Р1 помещается в стек.

Если очередь F3 не пуста и процессор P1 свободен, и очередь F1 пуста или свободен процессор Р2 и очередь F2 пуста, то задача из очереди F3 поступает на обработку в свободный процессор. Задача из стека поступает на обработку в свободный процессор Р1, если очередь F1 пуста, или в свободный процессора Р2, если очередь F2 пуста.

8. Система состоит из двух процессоров P1 и P2 и двух очередей F1, F2 и стека S (рис.13). В систему могут поступать запросы на выполнение задач двух типов -- Т1 и Т2. Задача типа Т1 может выполняться только процессором P1. Задача типа Т2 может выполняться любым процессором.

Запрос можно представить записью

на языке Pascal:

Type

TInquiry= record

Name: String[10]; {имя запроса}

Time: Word; {время обслуживания}

T: Byte; {тип задачи 1 -- Т1, 2 -- Т2}

end;

на языке C:

typedef struct TInquiry

{

char Name[10]; // имя запроса

unsigned Time; // время обслуживания

char T; // тип задачи 1 -- Т1, 2 -- Т2

};

Рис.13. Система задачи 8

Поступающие запросы ставятся в соответствующие типам задач очереди. Если очередь F1 не пуста и процессор P1 свободен, то задача из очереди F1 поступает на обработку в процессор P1. Если процессор Р1 обрабатывает задачу типа Т2, а процессор Р2 свободен, то задача из процессора Р1 поступает в процессор Р2, а задача из очереди F1 в процессор Р1, если же процессор Р2 занят, то задача из процессора Р1 помещается в стек.

Если очередь F2 не пуста и процессор P2 свободен, то задача из очереди F2 поступает на обработку в процессор P2. Если процессор Р2 занят, а процессор Р1 свободен и очередь F1 пуста, то задача из очереди F2 поступает в процессор Р1, а задача из стека поступает на обработку в свободный процессор Р2, если F2 пуста, или в свободный процессор Р1, если очередь F1 пуста и задачу нельзя поместить в процессор Р2.

9. Система состоит из двух процессоров P1 и P2 и трех очередей F1, F2, F3 и стека (рис.14).

Рис.14. Система задачи 9

В систему могут поступать запросы на выполнение задач двух типов -- Т1 и Т2. Задача типа Т2 обрабатывается процессором P2. Задача типа Т1 сначала обрабатывается процессором P1, затем результат обработки (Т1`) обрабатывается процессором Р2.

Запрос можно представить записью

на языке Pascal:

Type

TInquiry= record

Name: String[10]; {имя запроса}

T: Byte; {тип запроса}

Time1: Word; {время обработки

процессором Р1. Для задач

типа Т2 Time1=0}

Time2: Word; {время обработки

процессором Р2}

end;

на языке C:

typedef struct TInquiry

{

char Name[10]; // имя запроса

char T; // тип запроса

unsigned Time1; /* время обработки

процессором Р1. Для задач

типа Т2 Time1=0 */

unsigned Time2; /* время обработки

процессором Р2 */

};

Поступающие запросы на выполнение задач типа Т1 и Т2 ставятся в соответствующие типам задач очереди. Результат обработки Т1` задачи Т1 процессором Р1 ставится в очередь F3. Если очередь F1 не пуста и процессор P1 свободен, то задача из очереди F1 поступает на обработку в процессор P1.

Если очередь F3 не пуста и процессор P2 свободен, то задача из очереди F3 поступает на обработку в процессор P2. Если процессор Р2 занят выполнением задачи типа Т2, то она помещается в стек, а задача из очереди F3 -- в процессор Р2. Задача из стека возвращается в процессор Р2, если очередь F3 пуста. Задача из очереди F2 поступает на обработку в процессор P2, если он свободен и очередь F3 и стек пусты.

10. Система состоит из двух процессоров P1 и P2 , трех очередей F1, F2, F3 и стека (см. рис.12). В систему поступают запросы. Запрос можно представить записью

на языке Pascal:

Type

TInquiry= record

Name: String[10]; {имя запроса}

Time: Word; {время обслуживания}

P: Byte;{приоритет задачи 0 -- высший,

1 -- средний, 2 -- низший}

end;

на языке C:

typedef struct TInquiry

{

char Name[10]; // имя запроса

unsigned Time; // время обслуживания

char P; /* приоритет задачи: 0 -- высший,

1 -- средний, 2 -- низший */

};

Поступающие запросы ставятся в соответствующие приоритетам очереди. Сначала обрабатываются задачи из очереди F1. Задача из очереди F1 поступает в свободный процессор P1 или P2, если оба свободны, то в P1. Если очередь F1 пуста, то обрабатываются задачи из очереди F2. Задача из очереди F2 поступает в свободный процессор P1 или P2, если оба свободны, то в P1. Если очереди F1 и F2 пусты, то обрабатываются задачи из очереди F3. Задача из очереди F3 поступает в свободный процессор P1 или P2, если оба свободны, то в P2. Если процессоры заняты и поступает задача с более высоким приоритетом, чем обрабатываемая в одном из процессоров, то задача из процессора помещается в стек, а поступающая -- в процессор. Задача из стека поступает в один из освободившихся процессоров, если все задачи с более высоким приоритетом уже обработаны.

11. Система состоит из двух процессоров Р1 и Р2, двух стеков S1 и S2 и четырех очередей F1, F2, F3, F4 (рис.15).

Рис.15. Система задачи 11

В систему могут поступать запросы на выполнение задач двух приоритетов -- высший (1) и низший (2). Задачи сначала обрабатываются процессором P1, затем P2. Запрос можно представить записью

на языке Pascal:

Type

TInquiry= record

Name: String[10]; {имя запроса}

Р: Byte; {приоритет}

Time1: Word; {время выполнения задачи процессором P1}

Time2: Word; {время выполнения задачи процессором P2}

end;

на языке C:

typedef struct TInquiry

{

char Name[10]; // Имя запроса

char Р; // Приоритет

unsigned Time1; /* Время выполнения

задачи процессором P1 */

unsigned Time2; /* Время выполнения

задачи процессором P2 */

};

Запросы на выполнение задач высшего приоритета ставятся в очередь F1, а поступающие с процессора Р1 -- в очередь F3. Запросы на выполнение задач низшего приоритета, поступающие с генератора задач, ставятся в очередь F2, а поступающие с процессора Р1 -- в очередь F4.

Процессор Р1 обрабатывает запросы из очередей F1 и F2, а процессор Р2 -- из очередей F3 и F4. Процессор сначала обрабатывает задачи из очереди задач с высшим приоритетом, затем из очереди задач с низшим приоритетом. Если процессор выполняет задачу с низшим приоритетом и приходит запрос на выполнение задачи с высшим приоритетом, то выполняемая задача помещается в соответствующий процессору стек, а пришедшая задача -- в процессор. Задача из стека возвращается в процессор, если все задачи большего приоритета обработаны.

Модули для реализации стека

1. Стек на массиве в статической памяти.

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

Unit Stack1;

Interface

Const

StackSize = 1000;

StackOk = 0;

StackOver = 1;

StackUnder= 2;

var

StackError:0..2;

Type

Index = 0..StackSize;

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

Stack = record

Buf: array[Index]of BaseType;

Uk: Index; {указывает на элемент, являющийся

вершиной стека}

end;

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

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

procedure PutStack(var s:Stack;El:BaseType); {поместить

элемент в стек}

procedure GetStack(var s:Stack;var El:BaseType);

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

procedure ReadStack(const s:Stack;var El: BaseType;)

{прочитать элемент из вершины стека}

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

#if !defined(__STACK1_H)

#define __STACK1_H

const StackSize = 1000;

const StackOk = 0;

const StackOver = 1;

const StackUnder = 2;

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

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

typedef struct Stack

{

BaseType Buf[StackSize];

unsigned Uk; /* Указывает на элемент, являющийся

вершиной стека */

};

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

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

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

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

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

#endif

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

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

Unit Stack2;

Interface

Const

StackOk = 0;

StackOver = 1;

StackUnder= 2;

var StackError:0..2;

Type

Index = 0..StackSize;

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

Const

StackSize = 65520 div sizeof(BaseType);

Type

Index = 0..StackSize;

TBuf = array[Index]of BaseType;

Pbuf = ^Tbuf;

Stack = record

Buf: PBuf;

Kbuf: word; {количество элементов в массиве, запол-

няется при инициализации}

Uk : Index; {указывает на элемент, следующий за

вершиной стека}

end;

procedure InitStack(var s:Stack; var SizeBuf:word);

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

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

procedure PutStack(var s:Stack;El:BaseType); {поместить

элемент в стек}

procedure GetStack(var s:Stack;var El:BaseType);

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

procedure ReadStack(const s:Stack;var El: BaseType;)

{прочитать элемент из вершины стека}

procedure DoneStack(Var S:Stack); {уничтожить стек}

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

#if !defined(__STACK2_H)

#define __STACK2_H

const StackOk = 0;

const StackOver = 1;

const StackUnder = 2;

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

typedef ... BaseType; // Oпределить тип элемента стека

typedef struct Stack

{

BaseType *Buf; // Массив элементов базового типа

unsigned Kbuf; /* Количество элементов в массиве, заполняется при инициализации */

unsigned Uk; /* Указывает на элемент, следующий за

вершиной стека */

};

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

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

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

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

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

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

#endif

3. Стек на массиве в статической памяти, элементы стека - в

динамической.

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

Unit Stack3;

Interface

Const

StackSize = 1000;

StackOk = 0;

StackOver = 1;

StackUnder= 2;

var

StackError:0..2;

Type

Index = 0..StackSize;

BaseType = Pointer;

Stack = record

Buf: array[Index]of BaseType;

SizeEl: word; {размер элемента стека, определяется

при инициализации}

Uk : Index; {указывает на элемент, являющийся

вершиной стека}

end;

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

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

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

procedure PutStack(var s:Stack; var El); {поместить

элемент в стек}

procedure GetStack(var s:Stack;var El); {извлечь элемент

из стека}

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

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

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

#if !defined(__STACK3_H)

#define __STACK3_H

const StackSize = 1000;

const StackOk = 0;

const StackOver = 1;

const StackUnder = 2;

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

typedef void *BaseType;

typedef struct Stack

{

BaseType Buf[StackSize];

unsigned SizeEl; /* Размер элемента стека, определяющийся при инициализации */

unsigned Uk; /* Указывает на элемент, являющийся вершиной стека */

};

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

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

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

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

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

#endif

4. Стек в динамической памяти (связанная схема).

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

Unit Stack4;

Interface

Const

StackOk = 0;

StackOver = 1;

StackUnder= 2;

var

StackError:0..2;

Type

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

PtrEl = ^Element;

Element = Record Data : BaseType;

Next : PtrEl;

End;

Stack = PtrEl; {указывает на первый элемент в ОЛС,

являющийся вершиной стека}

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

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

procedure PutStack(var s:Stack;El:BaseType); {поместить

элемент в стек}

procedure GetStack(var s:Stack;var El:BaseType);

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

procedure ReadStack(const s:Stack;var El: BaseType;)

{прочитать элемент из вершины стека}

procedure DoneStack(Var S:Stack); {уничтожить стек}

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

#if !defined(__STACK4_H)

#define __STACK4_H

const StackOk = 0;

const StackOver = 1;

const StackUnder = 2;

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

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

typedef struct Element

{

BaseType Data;

unsigned SizeEl; /* Размер элемента стека, определяющийся

при инициализации */

Element *Next;

};

typedef Element *Stack; /* Указывает на первый элемент в ОЛС,

являющийся вершиной стека */

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

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

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

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

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

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

#endif

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

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

unit stack5;

interface

uses list1; {см лаб.раб. №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); {прочитать

элемент...


Подобные документы

  • Рассмотрение правил записи, способов ввода и вывода, использования функций обработки символьных данных в Pascal. Описание алгоритмизации и программирования файловых структур данных, проектирования структуры файла. Ознакомление с работой данных массива.

    курсовая работа [336,2 K], добавлен 27.06.2015

  • Средства создания динамических структур данных. Формат описания ссылочного типа. Структура памяти во время выполнения программы. Линейные списки, стек, очередь. Организация списков в динамической памяти. Пример создания списка в обратном порядке.

    лабораторная работа [788,2 K], добавлен 14.06.2009

  • Анализ эффективности методов сортировки данных в языке Turbo Pascal. Разработка эскизного и технического проекта программы. Сортировка без и с использованием дополнительной памяти, за исключением небольшого стека (массива). Сортировка связанных списков.

    курсовая работа [359,0 K], добавлен 23.05.2012

  • Проблемы с организацией данных. Определение и классификация динамических структур данных. Линейные односвязные, двухсвязные, кольцевые списки. Очередь, стеки. Описание основных типов данных и функции для работы с ними. Листинг программы, пример ее работы.

    контрольная работа [290,6 K], добавлен 17.07.2012

  • Краткая характеристика интегрированной среды Turbo Pascal. Принципы программирования разветвляющихся алгоритмов, циклических структур, задач обработки символьных данных, множеств. Правила записи данных в текстовый файл. Понятие явной и косвенной рекурсии.

    учебное пособие [1,5 M], добавлен 10.12.2010

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

    курсовая работа [451,1 K], добавлен 19.10.2013

  • Методы реализации алгоритмов сортировки и алгоритмов поиска на языках программирования высокого уровня. Программирование алгоритмов сортировки и поиска в рамках создаваемого программного средства на языке Delphi. Создание руководства пользователя.

    курсовая работа [1,7 M], добавлен 16.04.2012

  • Разработка алгоритмов методом пошаговой детализации. Типы данных и операции в Turbo-Pascal. Организация работы с подпрограммами. Составление алгоритмов и программ задач с использованием конечных сумм. Организация работы с динамическими переменными.

    учебное пособие [1,4 M], добавлен 26.03.2014

  • Характеристика вычислительной системы и инструментов разработки. Программирование на языке Pascal в среде Turbo Pascal и на языке Object Pascal в среде Delphi. Использование процедур, функций, массивов, бинарного поиска. Создание базы данных в виде файла.

    отчет по практике [2,1 M], добавлен 02.05.2014

  • Изучение функций и возможностей среды разработки языка программирования Pascal. Рассмотрение работы с одномерными и двумерными массивами, со строками и числами. Математическая формулировка задач. Разработка алгоритмов, описание структуры программ.

    курсовая работа [879,8 K], добавлен 11.02.2016

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

    курсовая работа [747,2 K], добавлен 09.06.2013

  • Создание программы для обработки структуры данных. Возможность ввода и записи данных на персональном компьютере. Прикладное программирование на языке Turbo Pascal. Свободное редактирование записанных данных с помощью программы, написанной на Turbo Pascal.

    лабораторная работа [11,4 K], добавлен 13.05.2011

  • Разработка программ на языке Turbo Pascal на основе использования массивов данных. Особенности хранения данных, способы объявления переменных, действия над элементами массивов, их ввод и вывод. Практическое применение одномерных и многомерных массивов.

    методичка [17,8 K], добавлен 25.11.2010

  • При помощи Turbo Pascal достаточно не просто создать программу, которая бы демонстрировала работу с базами данных. Для этого существует огромное количество специализированных программ. Основа и сущность формирования базы данных при помощи Turbo Pascal.

    курсовая работа [479,7 K], добавлен 04.07.2008

  • Проектирование программ в среде Рascal с интерфейсом типа "Меню". Разработка и отладка программы сортировки массива данных. Освоение методов проектирования Pascal-программ с использованием графических процедур и функций из стандартного модуля Graph.

    контрольная работа [581,1 K], добавлен 16.01.2015

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

    курсовая работа [364,1 K], добавлен 06.04.2014

  • Создание таблицы, содержащей сведения о книгах (фамилия автора, название, год издательства, тираж, цена) с применением встроенных функций сортировки, поиска данных и их замены, автофильтра, расширенного фильтра, баз данных, диаграмм и графиков в MS Excel.

    курсовая работа [3,3 M], добавлен 16.05.2010

  • Исследование основных особенностей алгоритмов быстрой и поразрядной сортировки данных. Построение графиков зависимости времени сортировки от количества элементов в файле и от степени перемешенности элементов. Описания сортировки чисел и строковых данных.

    лабораторная работа [1,2 M], добавлен 23.07.2012

  • Условие задачи: составление программы на языке Pascal для определения оптимального маршрута с ближайшим временем отправления, меньшим пребыванием в пути. Решение методом последовательного испытания. Формы представления данных, набора тестов. Результаты.

    курсовая работа [22,0 K], добавлен 07.11.2009

  • Общая характеристика организации массива в виде двоичного дерева. Особенности линейного и двоичного поиска заданного элемента массива. Методика упорядочения массива методом сортировки деревом. Инструкции и текст программы для нечисленной обработки данных.

    курсовая работа [242,3 K], добавлен 12.11.2010

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.