Файл Stack_Array.h
Федеральное агентство по образованию РФ
Государственное образовательное учреждение высшего профессионального образования
Белгородский Государственный Технологический Университет им. В. Г. Шухова.
Кафедра программного обеспечения вычислительной техники и
автоматизированных систем.
Расчётно-графическое задание по дисциплине
«Алгоритмы и структуры данных»
Выполнил
студент группы КБ-21
Биньковский Борис
Белгород 2014
Стек на массиве.
Файл Stack_Array.h
##ifndef _STACK_ARRAY_H_
#define _STACK_ARRAY_H_
/*Размер стека*/
#define SIZE_STACK_ARRAY 100
/*Описание исключительных ситуаций*/
const int okStackArray = 0; // Все нормально
const int fullStackArray = 1; // Стек переполнен
const int emptyStackArray = 2; // Стек пуст
/*********************************/
/*Переменная ошибок*/
extern int errorStackArray;
/*Базовый тип стека*/
typedef int stackArrayBaseType;
/*Дескриптор стека*/
typedef struct {
stackArrayBaseType buf[SIZE_STACK_ARRAY]; // Буфер стека
unsigned uk; // Указатель
} StackArray;
/*Функции работы со стеком*/
void initStackArray(StackArray *S); // Инициализация стека
void putStackArray(StackArray *S, stackArrayBaseType E); // Включение в стек
void getStackArray(StackArray *S, stackArrayBaseType *E); // Исключение из стека
int isFullStackArray(StackArray *S); // Предикат: полон ли стек
int isEmptyStackArray(StackArray *S); // Предикат: пуст ли стек
#endif
Файл Stack_Array.c
#include <stdio.h>
#include "Stack_Array.h"
/*Переменная ошибок*/
int errorStackArray;
/*Инициализация стека*/
void initStackArray(StackArray *S) {
S->uk = 0;
errorStackArray = okStackArray;
}
/*Включение в стек*/
void putStackArray(StackArray *S, stackArrayBaseType E) {
/*Если стек переполнен*/
if (isFullStackArray(S)) {
return;
}
/*Иначе*/
S->buf[S->uk] = E; // Включение элемента
S->uk++; // Сдвиг указателя
}
/*Исключение из стека*/
void getStackArray(StackArray *S, stackArrayBaseType *E) {
/*Если стек пуст*/
if (isEmptyStackArray(S)) {
return;
}
/*Иначе*/
*E = S->buf[S->uk - 1]; // Считывание элемента в переменную
S->uk--; // Сдвиг указателя
}
/*Предикат: полон ли стек*/
int isFullStackArray(StackArray *S) {
if (S->uk == SIZE_STACK_ARRAY) {
errorStackArray = fullStackArray;
return 1;
}
return 0;
}
/*Предикат: пуст ли стек*/
int isEmptyStackArray(StackArray *S) {
if (S->uk == 0) {
errorStackArray = emptyStackArray;
return 1;
}
return 0;
}
Модуль стека как отображение на ОЛС :
StackList.h
#ifndef _STACK_LIST_H_
#define _STACK_LIST_H_
#include "List_One.h"
/*Описание исключительных ситуаций*/
const int stackListOk = listOneOK;
const int stackListEmpty = listOneEmpty;
const int stackListNoMem = listOneNoMem;
/*Переменная ошибок*/
extern int listOneError;
/*Базовый тип стека на списке*/
typedef listOneBaseType stackListBaseType;
/*Тип стека на списке*/
typedef ListOne StackList;
/*Функции работы со стеком*/
void initStackList(StackList *S); // Инициализация стека
void putStackList(StackList *S, stackListBaseType E); // Включение в стек
void getStackList(StackList *S, stackListBaseType *E); // Исключение из стека
void doneStackList(StackList *L); // Удаление стека
int isEmptyStackList(StackList *S); // Предикат: пуст ли стек
/**************************/
#endif
StackList.h
#include "Stack_List.h"
#include "List_One.h"
/*Инициализация стека*/
void initStackList(StackList *S) {
initListOne(S);
listOneError = stackListOk;
}
/*Включение в стек*/
void putStackList(StackList *S, stackListBaseType E) {
putListOne(S, E);
listOneError= listOneNoMem;
}
/*Исключение из стека*/
void getStackList(StackList *S, stackListBaseType *E) {
getListOne(S, E);
listOneError= listOneEmpty;
}
/*Удаление стека*/
void doneStackList(StackList *L) {
doneListOne(L);
}
/*Предикат: пуст ли стек*/
int isEmptyStackList(StackList *S) {
return isEmptyListOne(S);
}
Модуль очереди как отображение на массив:
Queue_Array.h
##ifndef _QUEUE_ARRAY_H_
#define _QUEUE_ARRAY_H_
/*Размер очереди*/
#define SIZE_QUEUE_ARRAY 3
/*Описание исключительных ситуаций*/
const int okQueueArray = 0; // Все нормально
const int fullQueueArray = 1; // Очередь переполнена
const int emptyQueueArray = 2; // Очередь пуста
/*Переменная ошибок*/
extern int errorQueueArray;
/*Базовый тип очереди*/
typedef int queueArrayBaseType;
/*Дескриптор очереди*/
typedef struct {
queueArrayBaseType buf[SIZE_QUEUE_ARRAY]; // Буфер очереди
unsigned ukEnd; // Указатель на хвост (по нему включают)
unsigned ukBegin; // Указатель на голову (по нему исключают)
unsigned len; // Количество элементов в очереди
} QueueArray;
/*Функции работы с очередью*/
void initQueueArray(QueueArray *F); // Инициализация очереди
void putQueueArray(QueueArray *F, queueArrayBaseType E); // Включение в очередь
void getQueueArray(QueueArray *F, queueArrayBaseType *E); // Исключение из очереди
int isFullQueueArray(QueueArray *F); // Предикат: полна ли очередь
int isEmptyQueueArray(QueueArray *F); // Предикат: пуста ли очередь
#endif
Queue_Array.h
#include <stdio.h>
#include "Queue_Array.h"
/*Переменная ошибок*/
int errorQueueArray;
/*Инициализация очереди*/
void initQueueArray(QueueArray *F) {
F->ukBegin = 0;
F->ukEnd = 0;
F->len = 0;
errorQueueArray = okQueueArray;
}
/*Включение в очередь*/
void putQueueArray(QueueArray *F, queueArrayBaseType E) {
/*Если очередь переполнена*/
if (isFullQueueArray(F)) {
return;
}
/*Иначе*/
F->buf[F->ukEnd] = E; // Включение элемента
F->ukEnd = (F->ukEnd + 1) % SIZE_QUEUE_ARRAY; // Сдвиг указателя
F->len++; // Увеличение количества элементов очереди
}
/*Исключение из очереди*/
void getQueueArray(QueueArray *F, queueArrayBaseType *E) {
/*Если очередь пуста*/
if (isEmptyQueueArray(F)) {
return;
}
/*Иначе*/
*E = F->buf[F->ukBegin]; // Запись элемента в переменную
F->ukBegin = (F->ukBegin + 1) % SIZE_QUEUE_ARRAY; // Сдвиг указателя
F->len--; // Уменьшение длины
}
/*Предикат: полна ли очередь*/
int isFullQueueArray(QueueArray *F) {
if (F->len == SIZE_QUEUE_ARRAY) {
errorQueueArray = fullQueueArray;
return 1;
}
return 0;
}
/*Предикат: пуста ли очередь*/
int isEmptyQueueArray(QueueArray *F) {
if (F->len == 0) {
errorQueueArray = emptyQueueArray;
return 1;
}
return 0;
}
Модуль очереди как отображение на ОЛС :
Queue_List.h
#ifndef _QUEUE_LIST_H_
#define _QUEUE_LIST_H_
#include "List_One.h"
/*Описание исключительных ситуаций*/
const int queueListOk = listOneOK;
const int queueListEmpty = listOneEmpty;
const int queueListNoMem = listOneNoMem;
\
/*Переменная ошибок*/
extern int listOneError;
/*Базовый тип очереди на списке*/
typedef listOneBaseType QueueListBaseType;
/*Тип очереди на списке*/
typedef ListOne QueueList;
/*Функции работы со очередью*/
void initQueueList(QueueList *S); // Инициализация очереди
void putQueueList(QueueList *S, QueueListBaseType E); // Включение в очередь
void getQueueList(QueueList *S, QueueListBaseType *E); // Исключение из очереди
void doneQueueList(QueueList *L); // Удаление очереди
int isEmptyQueueList(QueueList *S); // Предикат: пуста ли очередь
#endif
Queue_List.h
#include "Queue_List.h"
/*Инициализация очереди*/
void initQueueList(QueueList *S) {
initListOne(S);
listOneError = queueListOk;
}
/*Включение в очередь*/
void putQueueList(QueueList *S, QueueListBaseType E) {
endPtrListOne(S);
putListOne(S, E);
listOneError = queueListNoMem;
}
/*Исключение из очереди*/
void getQueueList(QueueList *S, QueueListBaseType *E) {
beginPtrListOne(S);
getListOne(S, E);
listOneError = listOneEmpty;
}
/*Удаление очереди*/
void doneQueueList(QueueList *L) {
doneListOne(L);
}
/*Предикат: пуста ли очередь*/
int isEmptyQueueList(QueueList *S) {
return isEmptyListOne(S);
}
Модуль очереди с приоритетом:
QueuePriority.h
#ifndef _QUEUE_PRIORITY_H_
#define _QUEUE_PRIORITY_H_
/*Размер очереди*/
#define SIZE_QUEUE_PRIORITY 5
/*Описание исключительных ситуаций*/
const int okQueuePriority = 0; // Все нормально
const int fullQueuePriority = 1; // Очередь переполнена
const int emptyQueuePriority = 2; // Очередь пуста
/*Переменная ошибок*/
extern int errorQueuePriority;
/*Базовый тип очереди*/
typedef struct {
int data; // Данные
int priority; // Приоритет
} queuePriorityBaseType;
/*Дескриптор очереди*/
typedef struct {
queuePriorityBaseType buf[SIZE_QUEUE_PRIORITY]; // Буфер очереди
unsigned uk; // Указатель на хвост
} QueuePriority;
/*Функции работы с очередью*/
void initQueuePriority(QueuePriority *F); // Инициализация очереди
void putQueuePriority(QueuePriority *F, queuePriorityBaseType E); // Включение в очередь
void getQueuePriority(QueuePriority *F, queuePriorityBaseType *E); // Исключение из очереди
int isFullQueuePriority(QueuePriority *F); // Предикат: полна ли очередь
int isEmptyQueuePriority(QueuePriority *F); // Предикат: пуста ли очередь
#endif
QueuePriority. с
#include <stdio.h>
#include "QueuePriority.h"
/*Переменная ошибок*/
int errorQueuePriority;
/*Инициализация очереди*/
void initQueuePriority(QueuePriority *F) {
F->uk = 0;
errorQueuePriority = okQueuePriority;
}
/*Включение в очередь*/
void putQueuePriority(QueuePriority *F, queuePriorityBaseType E) {
/*Если очередь переполнена*/
if (isFullQueuePriority(F)) {
return;
}
/*Иначе*/
F->buf[F->uk] = E;
F->uk++;
}
/*Исключение из очереди*/
void getQueuePriority(QueuePriority *F, queuePriorityBaseType *E) {
/*Если очередь пуста*/
if (isEmptyQueuePriority(F)) {
return;
}
/*Иначе поиск элемента с максимальным приоритетом*/
queuePriorityBaseType max = F->buf[0]; // Максимальным примем 1-й элемент
int maxPos = 0; // Позиция элемента в макс. приоритетом
for (unsigned i = 1; i < F->uk; i++) { // Для всех элементов начиная со второго выполнить
if (F->buf[i].priority > max.priority) { // поиск элемента с максимальным приоритетом
max = F->buf[i];
maxPos = i;
}
}
/*Максимальный найден. Производим исключение*/
*E = max; // Запись данных в переменную
F->buf[maxPos] = F->buf[--F->uk]; // Установка на позицию исключаемого элемента последнего
// Уменьшение длины очереди
}
/*Предикат: полна ли очередь*/
int isFullQueuePriority(QueuePriority *F) {
if (F->uk == SIZE_QUEUE_PRIORITY) {
errorQueuePriority = fullQueuePriority;
return 1;
}
return 0;
}
/*Предикат: пуста ли очередь*/
int isEmptyQueuePriority(QueuePriority *F) {
if (F->uk == 0) {
errorQueuePriority = emptyQueuePriority;
return 1;
}
return 0;
}
Модуль ОЛС, расположенного в динамической памяти:
List .h
#if !defined(LIST. H)
const ListOk = 0;
const ListNotMem =1 ;
const ListUnder = 2;
const ListEnd = 3;
typedef int *BaseType;
typedef struct element *ptrel;
typedef struct element {basetype data;
ptr link;};
typedef struct List {ptrel Start;
ptrel ptr;
unsigned int N}
extern short ListError;
void InitList(List *L);
void PutList(List *L, BaseType E);
void GetList(List *L, BaseType *E);
int FullList(List *L);
void BeginPtr(List *L);
void EndPtr(List *L);
void MovePtr(List *L);
void DoneList(List *L);
#endif
List . c
#include <stdio.h>
#include “List.h”
short ListError;
void InitList(List *L);
L->start = (ptrEl) malloc(sizeof(element));
if (!L->start) {
listError = ListNotMem;
return;
}
L->ptr = L->start;
L->ptr->link = NULL;
}
void PutList(List *L, BaseType E);
// Выделение памяти под новый элемент
ptrel temp = (ptrel) malloc(sizeof(element));
if (temp==NULL) {
listError = ListNotMem;
return;
}
temp->data = E;
temp->link = L->ptr->link;
L->ptr->link = temp;
}
void GetList(List *L, BaseType *E);
{
if (FullList(L))
{
return;
}
/* рабочий указатель указывает на последний элемент*/
if ((L->ptr!=L->start)&&(!L->ptr->link))
{
listError = ListEnd;
return;
}
ptrel pntr = L->ptr->link;
L->ptr->link = pntr->link;
*E = pntr->data;
pntr->link = NULL;
free((void *) pntr);
}
int FullList(List *L);
{
if ((L->ptr!=L->start)&&(!L->ptr->link))
{
listError = ListUnder;
return 1;
}
return 0;
}
void MovePtr(List *L);
{
/* рабочий указатель указывает на последний элемент*/
if ((L->ptr!=L->start)&&(!L->ptr->link))
{
listError = ListEnd;
return;
}
L->ptr = L->ptr->link;
}
void BeginPtr(List *L);
{
L->ptr = L->start;
}
void EndPtr(List *L);
{
while (L->ptr->link)
{
movePtr (L);
}
}
int EmptyList(List *L)
{
if (L->start->next==NULL) {
ListError = ListEmpty;
return 1;
}
return 0;
}
int EndList(List *L)
{
if (L->ptr->next==NULL && L->ptr!=L->start) {
ListError = ListEnd;
return 1;
}
return 0;
}
void DoneList(List *L);
{
BeginPtr (L);
ListBaseType temp;
while (!FullList(L)) {
GetList(L, &temp);
}
free((void *) L->ptr);
}
Модуль ДЛС, расположенного в динамической памяти:
ListTwo.h
#ifndef _LIST_TWO_H_
#define _LIST_TWO_H_
const int ListTwoOk = 0;
const int ListTwoEmpty = 1;
const int ListTwoNoMem = 2;
const int ListTwoEnd = 3;
const int ListTwoBegin = 4;
extern int ListTwoError;
typedef int listTwoBaseType;
struct elementTwo {
listTwoBaseType data;
elementTwo *pred;
elementTwo *next;
};
typedef struct ListTwo {
elementTwo *Start;
elementTwo *End;
elementTwo *ptr;
};
void InitListTwo(ListTwo *L);
void PredPut(ListTwo *L, listTwoBaseType E);
void PostPut(ListTwo *L, listTwoBaseType E);
void PredGet(ListTwo *L, listTwoBaseType *E);
void postGet(ListTwo *L, listTwoBaseType *E);
void MovePtrListTwoLeft(ListTwo *L);
void MovePtrListTwoRight(ListTwo *L);
void BeginPtrListTwo(ListTwo *L);
void EndPtrListTwo(ListTwo *L);
void DoneListTwo(ListTwo *L);
int EmptyListTwo(ListTwo *L);
#endif
ListTwo.c
#include <stdio.h>
#include <stdlib.h>
#include "ListTwo.h"
int ListTwoError;
void initListTwo(ListTwo *L)
{
L->Start = (elementTwo *) malloc(sizeof(elementTwo));
if (!L->Start)
{
listTwoError = listTwoNoMem;
return;
}
L->End = (elementTwo *) malloc(sizeof(elementTwo));
if (!L->End)
{
listTwoError = listTwoNoMem;
free((void *) L->Start);
L->Start = NULL;
return;
}
L->Start->next = L->End;
L->Start->pred = NULL;
L->End->nextLink = NULL;
L->End->predLink = L->Start;
L->ptr = L->Start;
listTwoError = listTwoOk;
}
void PredPut(ListTwo *L, listTwoBaseType E)
{
if (L->ptr == L->Start)
{
listTwoError = listTwoBegin;
return;
}
ElementTwo *pntr = (elementTwo *) malloc(sizeof(elementTwo));
if (!pntr)
{
listTwoError = listTwoNoMem;
return;
}
pntr->data = E;
pntr->pred = L->ptr->pred;
pntr->next = L->ptr;
L->ptr->pred->next = pntr;
L->ptr->post= pntr; // Текущий эл-т указывает слева на новый
}
void postPut(ListTwo *L, listTwoBaseType E)
{
if (L->ptr == L->End)
{
listTwoError = listTwoEnd;
return;
}
elementTwo *pntr = (elementTwo *) malloc(sizeof(elementTwo));
if (!pntr)
{
listTwoError = listTwoNoMem;
return;
}
pntr->data = E;
pntr->next = L->ptr->next;
pntr->pred = L->ptr;
L->ptr->next->pred = pntr;
L->ptr->next = pntr;
}
void PredGet(ListTwo *L, listTwoBaseType *E)
{
if (EmptyListTwo(L))
{
return;
}
if (L->ptr == L->Start)
{
listTwoError = listTwoBegin;
return;
}
*E = L->ptr->predLink->data;
elementTwo *pntr = L->ptr->pred;
L->ptr->predLink = pntr->predLink;
pntr->predLink->nextLink = L->ptr;
free((void *) pntr);
}
void postGet(ListTwo *L, listTwoBaseType *E)
{
if (EmptyListTwo(L)) {
return;
}
if (L->ptr == L->End)
{
listTwoError = listTwoEnd;
return;
}
*E = L->ptr->next->data;
elementTwo *pntr = L->ptr->next;
L->ptr->next= pntr->next;
pntr->next->pred = L->ptr;
free((void *) pntr);
}
void movePtrListTwoLeft(ListTwo *L)
{
if (L->ptr == L->Start)
{
listTwoError = listTwoBegin;
return;
}
L->ptr = L->ptr->predLink;
}
void movePtrListTwoRight(ListTwo *L)
{
if (L->ptr == L->End)
{
listTwoError = listTwoEnd;
return;
}
L->ptr = L->ptr->nextLink;
}
void BeginPtrListTwo(ListTwo *L)
{
while (L->ptr != L->Start) {
movePtrListTwoLeft(L);
}
}
void EndPtrListTwo(ListTwo *L)
{
while (L->ptr != L->End)
{
movePtrListTwoRight(L);
}
}
void doneListTwo(ListTwo *L)
{
BeginPtrListTwo(L);
ListTwoBaseType E; // Создание временного элемента
while (!EmptyListTwo(L))
{
PostGet(L, &E);
}
free((void *) L->Start);
free((void *) L->End);
}
int EmptyListTwo(ListTwo *L)
{
if (L->Start->next == L->End)
{
listTwoError = listTwoEmpty;
return 1;
}
return 0;
}
Модуль дека на отображение на ДЛС :
DeckListTwo.h
#ifndef _DECK_LIST_TWO_H_
#define _DECK_LIST_TWO_H_
#include "ListTwo.h"
const int DeckOk = listTwoOk;
const int DeckNoMem = listTwoNoMem;
const int DeckEmpty = listTwoEmpty;
extern int ListTwoError;
typedef listTwoBaseType BaseType;
typedef ListTwo Deck;
void InitDeck(Deck *D);
void PutDeckLeft(Deck *D, BaseType E);
void GetDeckLeft(Deck *D, BaseType *E);
void PutDeckRight(Deck *D, BaseType E);
void GetDeckRight(Deck *D, BaseType *E);
void DoneDeck(Deck *D);
int DeckEmpty(Deck *D);
#endif
DeckListTwo.c
#include<stdio.h>
#include "DeckListTwo.h"
void InitDeck(Deck *D) {
InitListTwo(D);
ListTwoError = DeckOk;
}
void PutDeckLeft(Deck *D, BaseType E)
{
BeginPtrListTwo(D);
PostPut(D, E);
ListTwoError = DeckEmpty;
}
void GetDeckLeft(Deck *D, BaseType *E)
{
BeginPtrListTwo(D);
PostGet(D, E);
ListTwoError = DeckNoMem;
}
void PutDeckRight(Deck *D, BaseType E)
{
EndPtrListTwo(D);
PredPut(D, E);
ListTwoError = DeckEmpty;
}
void GetDeckRight(Deck *D, BaseType *E)
{
EndPtrListTwo(D);
PredGet(D, E);
ListTwoError = DeckNoMem;
}
int DeckEmpty(Deck *D) {
return EmptyListTwo(D);
}
Модуль упорядоченной таблицы как отображения на массив:
Tabl е .h
#ifndef TABL_H
#define TABL_H
const int Tabl_Size 50
const int TableOk = 0;
const int TableEmpty = 1;
const int TableFull = 2;
const int TableNoKey = 3;
extern int TablError;
typedef struct Element{
int data;
int key;
};
typedef struct Table {
int buf[Table_Size];
unsigned uk;
};
void InitTable (Table *T);
void PutTable (Table *T, Element E);
void OutTable (Table *T, element *E, int key);
int SearchKey(Table *T, int key);
int EmptyTabl (Table *T);
int FullTabl (Tabl *T);
#endif
Table.c
#include <stdio.h>
#include "Table.h"
int TablError;
void InitTabl(Table *T)
{
T->uk = 0;
TablError = TableOk;
}
int SearchKey(Table *T, int key)
{
unsigned i;
for (i = 0; i < T->uk && T->buf[i].key != key;) { i++;}
if (i == T->uk) {
TableError = TableNoKey;
return -1;
}
return i;
}
void PutTable(Table *T, Element E)
{
if (FullTable(T)==1) { return;}
int posElement;
if ((posElement = SearchKey(T, E.key)) != -1) { T->buf[posElement].date = E.date; }
else {
T->buf[T->uk] = E;
T->uk++
}
}
void OutTable(Table *T, Element *E, int key)
{
if (EmptyTable(T)==1) {return; }
int posElement;
if ((posElement = SearchKey(T, key)) != -1)
{
E->date = T->buf[posElement].date;
E->key = T->buf[posElement].key;
if (posElement != T->uk - 1) {
T->buf[posElement] = T->buf[T->uk - 1];
}
T->uk--;
}
}
int EmptyTable(Table *T)
{
if (T->uk == 0) {
TableError = TableEmpty;
return 1;
}
return 0;
int FullTable(Table *T)
{
if (T->uk == Tabe_Size) {
TablError= TableFull;
return 1;
}
return 0;
}
Модуль неупорядоченной таблицы как отображения на массив:
NTable.h.
#ifndef NTABL_H
#define NTABL_H
const int Tabl_Size 50
const int TableOk = 0;
const int TableEmpty = 1;
const int TableFull = 2;
extern int TablError;
typedef struct Element{
int data;
int key;
}
typedef struct Table {
int buf[Table_Size];
unsigned uk;
}
void InitTable (Table *T);
void PutTable (Table *T, Element E);
void OutTable (Table *T, element *E, int key);
int SearchKey(Table *T, int key);
int EmptyTabl (Table *T);
int FullTabl (Tabl *T);
#endif
NTable.c.
#include <stdio.h>
#include "NTable.h"
int TablError;
void InitTabl(Table *T)
{
T->uk = 0;
TablError = TableOk;
}
int SearchKey(Table *T, int key)
{
unsigned i;
for (i = 0; i < T->uk && T->buf[i].key != key;) { i++;}
if (i == T->uk) {
TableError = TableNoKey;
return -1;
}
return i;
}
void PutTable(Table *T, Element E)
{
if (FullTable(T)==1) { return;}
T->buf[T->uk] = E;
T->uk++;
}
void OutTable(Table *T, Element *E, int key)
{
if (EmptyTable(T)==1) {return; }
int posElement;
if ((posElement = SearchKey(T, key)) != -1)
{
E->date = T->buf[posElement].date;
E->key = T->buf[posElement].key;
if (posElement != T->uk - 1) {
T->buf[posElement] = T->buf[T->uk - 1];
}
T->uk--;
}
}
int EmptyTable(Table *T)
{
if (T->uk == 0) {
TableError = TableEmpty;
return 1;
}
return 0;
int FullTable(Table *T)
{
if (T->uk == Tabe_Size) {
TablError= TableFull;
return 1;
}
return 0;
}
Модуль таблицы как отображения на ОЛС :
TableList.h
#ifndef TABLE_LIST_H_
#define TABLE_LIST_H_
#include "list.h"
const intTableOk = 0;
const intTableNotMem = 1;
const intTableUnder = 3;
int extern TableError;
typedef struct Element {
int key;
int data;
} _Element;
typedef struct Table {
List *Buf;
unsigned n;
unsigned SizeBuf;
unsigned SizeEl;
};
void InitTable(Table *T, unsigned SizeBuf, unsigned SizeEl);
int EmptyTable(Table *T);
int PutTable(Table *T, BaseType E, func f);
int GetTable(Table *T, BaseType E, T_Key Key, func f);
int ReadTable(Table *T, BaseType E, T_Key Key, func f);
int WriteTable(Table *T, BaseType E, T_Key Key, func f);
void DoneTable(Table *T);
#endif
TableList.c
#include<stdio.h>
#include “list.h”
#include “TableList.h”
voidInitTable(Table *T, unsigned SizeBuf, unsigned SizeEl)
{ unsignedi;
T->Buf = (List*)calloc(SizeBuf, sizeof(List));
T->n = 0;
T->SizeBuf = SizeBuf;
T->SizeEl = SizeEl;
for(I = 0; i<SizeBuf; i++) {
InitList(&(T->Buf[i]),SizeEl);
}
TableError = TableOk;
}
intEmptyTable(Table *T) {
return T->n == 0;
}
intSearch_List(List *L, BaseType E, func f) {
_Element temp;
BeginPtr(L);
while (!EndList(L)) {
ReadList(L, &temp);
if (f(&temp, E) == 0) {
return 1;
}
MovePtr(L);
}
return 0;
}
intPutTable(Table *T, BaseType E, func f) {
unsigned index = (unsigned)(((((_Element*)E)->key)*C1 + C2)%T->SizeBuf);
if (Search_List(&(T->Buf[index]), E, f)==1) {
return 0;
}
PutList(&(T->Buf[index]), E);
if (ListError) {
TableError = TableNotMem;
return 0;
}
return 1;
}
intGetTable(Table *T, BaseType E, T_Key Key, func f) {
unsigned index = (unsigned)((Key*C1 + C2) % T->SizeBuf);
if (Search_List(&(T->Buf[index]), E, f)==0) {
return 0;
}
GetList(&(T->Buf[index]), E);
return 1;
}
intReadTable(Table *T, BaseType E, T_Key Key, func f) {
unsigned index = (unsigned)((Key*C1 + C2) % T->SizeBuf);
if (Search_List(&(T->Buf[index]), E, f)==0) {
return 0;
}
ReadList(&(T->Buf[index]), E);
return 1;
}
intWriteTable(Table *T, BaseType E, T_Key Key, func f) {
_Element temp;
if (ReadTable(T, &temp, Key, f)) {
GetTable(T, &temp, Key, f);
PutTable(T, E, f);
return 1;
}
else {
return 0;
}
}
voidDoneTable(Table *T)
{ unsignedi;
for ( I = 0; i< T->SizeBuf; i++) {
DoneList(&(T->Buf[i]));
}
free(T->Buf);
free(T);
}