Структуры данных «линейные списки» (Pascal/С)

6 7 8 9 10 11 12

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

З а д а н и е

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

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

Таблица 14

Варианты индивидуальных заданий

Номер варианта	Номер модуля	Задача

Окончание табл.14

Задачи

1. Многочлен P(x)=a_nxⁿ+ a_n_-1xⁿ^-1+... + a₁x + a₀ с целыми коэффициентами можно представить в виде списка, причем если a_i = 0, то соответствующее звено не включать в список. Определить логическую функцию РАВНО(p, q), проверяющие на равенство многочлены p и q.

2. Дано натуральное число n целые числа a₁,a₂,...,a_n. Требуется получить последовательность x_1,y₁;x_2,y_2;...;x_k,y_k, где x₁,...,x_k — взятые в порядке следования (слева на право) четные члены последовательности a₁,...,a_n, a y₁,...,y_k — нечетные члены, к = min(m,l).

3. Дано натуральное число n и целые числа a₁,a₂,...,a_n. Вычислить , где среднее арифметическое чисел a₁,...,a_n.

4. Даны натуральные числа k,m,n, последовательности символов s₁,...,s_k,t₁,...,t_m,u₁,...,u_n. Получить по одному разу те символы, которые входят во все три последовательности.

5. Многочлен P(x)=a_nxⁿ+ a_n_-1xⁿ^{- 1}+... + a₁x + a₀ с целыми коэффициентами можно представить в виде списка, причем если a_i=0, то соответствующее звено не включать в список. Определить функцию, вычисляющую значения многочлена в точке х.

6. Даны натуральное число n, символы s₁,...,s_n. Получить символы, принадлежащие последовательности s₁,...,s_n, которые входят в нее по одному разу.

7. Многочлен P(x) = a_nxⁿ+ a_n_-1xⁿ^{- 1}+... + a₁x + a₀ с целыми коэффициентами можно представить в виде списка, причем если a_i = 0, то соответствующее звено не включать в список. Определить процедуру, которая стоит многочлен p — сумму многочленов q и r;

8. Многочлен P(x) = a_nxⁿ+ a_n_-1xⁿ^-1+... + a₁x + a₀с целыми коэффициентами можно представить в виде списка, причем если a_i = 0, то соответствующее звено не включать в список. Определить процедуру ВЫВОД(p,y), которая печатает многочлен р как многочлен от переменной, однобуквенное имя которой является значением литерного параметра y.

9. Многочлен P(x) = a_nxⁿ+ a_n_-1xⁿ^-1+... + a₁x + a₀с целыми коэффициентами можно представить в виде списка, причем если a_i = 0, то соответствующее звено не включать в список. Определить процедуру, которая строит многочлен р — произведение многочленов q и r.

10. Проверить, удовлетворяют ли элементы списка (базовый тип integer) закону x = f(х₀,h), где х — элемент списка,h — шаг, x₀ — начальный элемент списка.

Пример: x₀= 5, h = 1. x₁= 6, x₂= 7, x₃= 8... Элементы списка удовлетворяют закону х = f(5,1).

11. Многочлен P(x) = a_nxⁿ+ a_n_-1xⁿ^-1+... + a₁x + a₀ с целыми коэффициентами можно представить в виде списка, причем если a_i = 0, то соответствующее звено не включать в список. Построить многочлен p, являющийся производной многочлена q.

Модули

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

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

Unit List1;

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

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(__LIST1_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}

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

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

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

Unit List2;

Interface

Const ListOk = 0;

ListNotMem = 1;

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