#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
//данные хранятся в виде массива структур из указателя и ключа
//структура элемента таблицы
typedef struct Item
{
int busy; //поле занятости
int key; //ключ
int release; //номер версии
char* info; //поле данных - строка
}Item;
//структура - таблица
typedef struct Table
{
int size; //максимальный размер таблицы
int count; //текущий размер таблицы
Item* val; //массив структур item
}Table;
//меню
int F1_End(Table*); //функция выхода
int F2_Menu(Table*); //меню
int F3_Print(Table*); //вывод элементов
int F4_Generate(Table*); //генерация рандомных значений в таблице
int F5_Input(Table*); //ввод элемента
int F6_DeleteKey(Table*); //удаление элементов по ключу в таблице
int F7_DeleteRelease(Table*); //удаление элемнета по ключу и версии
int F8_FindKey(Table*); //поиск и копирование элемента
int F9_FindRelease(Table*); //поиск версии
//функции работы с таблицей
Table* TableCreate(int size); //функция создания пустой таблицы
void TableDelete(Table* T); //удаление таблицы
void TablePrint(Table* T); //вывод таблицы
int TableAdd(Table* T, int key, char* info); //добавление элемента с ключом в таблицу
void TableZip(Table* T); //сжатие таблицы
int TableFindLast(Table* T, int key); //поиск элемнета последней версии по ключу в таблице (начинается с конца таблицы)
int TableDeleteKey(Table* T, int key); //удаление элементов по ключу
int TableDeleteRelease(Table* T, int key, int release); //удаление элементa по ключу и версии
Table* TableFindKey(Table* T, int key); //поиск и получение копии элемента
char* TableFindRelease(Table* T, int key, int release); //поиск по ключу и версии
int ItemPrint(Item*); //вывод элемента таблицы
//другие функции
int getInt(int*); //чтение целого числа
int getStr(char**); //функция ввода строк
const char *msgs[] = { NULL, "Exit programm", "Show menu", "Print table", "Generate random table",
"Input item", "Delete key", "Delete release", "Find key", "Find release" }; //строки меню
int main()
{
const int SIZE = 10; //максимальны размер таблицы
int ex = 0; //переменые для удобного вывода меню
int menu = 0; //далее до конца - вывод меню
int(*fun[]) (Table*) = { NULL, F1_End, F2_Menu, F3_Print, F4_Generate,
F5_Input, F6_DeleteKey, F7_DeleteRelease, F8_FindKey, F9_FindRelease }; //массив функций
Table* T = TableCreate(SIZE); //создание таблицы
if (T == NULL)
{
puts("out of memory");
return 0;
}
srand((unsigned int)time(NULL)); //задаём зерно генератора
F2_Menu(T); //вывод меню
//выбор пункта меню
while (ex != 1)
{
menu = 0; //пункт меню
while (menu <= 0 || menu >= 10)
getInt(&menu); //чтение номера пункта меню
ex = (*fun[menu])(T);
}
return 0;
}
//интерфейсные функции
//завершение программы
int F1_End(Table* T)
{
TableDelete(T); //удаление таблицы
return 1;
}
//вывод меню
int F2_Menu(Table* T)
{
int i;
for (i = 1; i < 10; ++i)
printf("%d %s\n", i, msgs[i]);//вывод пунктов меню
return 0;
}
//вывод таблицы
int F3_Print(Table* T)
{
puts("Table:");
TablePrint(T); //вывод
return 0;
}
//добавление случайных элементов
int F4_Generate(Table* T)
{
char* str;
int amount = 0; //количество добавляемых элементов
int i, j;
printf("Enter amount: ");
getInt(&amount);
for (i = 0; i < amount; i++)
{ //цикл добавления
str = (char*)calloc(5, sizeof(char));
for (j = 0; j<4; j++) //генерируем случайную строку
str[j] = 'a' + rand() % 26;
if (TableAdd(T, rand() % 1000, str))
{
free(str);
break; //проверка на то, что таблица не переполнена
}
}
printf("Added %d keys.\n", i); //выводим сколько ключей мы смогли добавить
return 0;
}
//добавление ключа
int F5_Input(Table* T)
{
int key = 0;
char* info;
int res;
printf("Enter key: ");
getInt(&key); //читаем ключ
printf("Enter information: ");
res = getStr(&info); //чтение информации
if (res) //проверка на возможность выделить память
{
puts("Memory is out");
TableDelete(T); //удаляем таблицу при нехватке памяти
return 1;
}
if (TableAdd(T, key, info)) //если добавление успешно
puts("Table is full");
else //если не успешно выбираем ошибку
puts("Item added.");
return 0;
}
//удаление элемента
int F6_DeleteKey(Table* T)
{
int key = 0;
printf("Enter key: "); //ввод ключа
getInt(&key);
printf("Deleted %d items.\n", TableDeleteKey(T, key)); //выводим сколько ключей мы удалили
return 0;
}
//удаление элемента по ключу и версии
int F7_DeleteRelease(Table* T)
{
int key = 0;
int release = 0;
printf("Enter key: "); //ввод ключа и версии
getInt(&key);
printf("Enter release: ");
getInt(&release);
if (TableDeleteRelease(T, key, release)) //удаление элемента таблици, если удаление успешно
puts("Items deleted.");
else
puts("Items not found."); //если не успешно
return 0;
}
//поиск в таблице ключа
int F8_FindKey(Table* T)
{
int key = 0;
Table* NewTable;
printf("Enter key: ");
getInt(&key);
NewTable = TableFindKey(T, key); //получаем указатель на ктаблицу с копиями ключа
if (NewTable)
{
puts("Table:");
TablePrint(NewTable); //вывод
TableDelete(NewTable); //и удаление таблицы
}
else
{
puts("Keys not found."); //или выводим сообщение об ошибке
}
return 0;
}
//поиск в таблице ключа и версии
int F9_FindRelease(Table* T)
{
int key = 0;
int release = 0;
char* info;
printf("Enter key: ");
getInt(&key); //ввод ключа
printf("Enter release: ");
getInt(&release); //ввод версии
info = TableFindRelease(T, key, release); //поиск информации по кючу и версии
if (info)
printf("Information: %s.\n", info); //вывод есои нашли
else
puts("Key not found."); //иначе выводим сообщение об ошибке
return 0;
}
//функци работы с таблицей
//создание таблицы, возвращаем указатель на пустую таблицу
Table* TableCreate(int size)
{
Table* T;
if (size < 0)
return NULL;
T = (Table*)malloc(sizeof(Table)); //память под структуру таблицы
if (T == NULL)
return NULL;
T->count = 0;
T->size = size;
T->val = (Item*)calloc(size, sizeof(Item)); //память под массив элементов
if (T->val == NULL)
{
free(T);
return NULL;
}
return T;
}
//удаление таблицы
void TableDelete(Table* T)
{
int i;
for (i = 0; i < T->count; i++)
if (T->val[i].busy)
free(T->val[i].info); //удаление информации
free(T->val); //чистка остальной памяти
free(T);
}
//вывод таблицы
void TablePrint(Table* T)
{
int i;
printf("count = %d, size = %d.\n", T->count, T->size);
printf("%2s %7s %7s %s\n", "i", "key", "release", "string");
if (T->count == 0)
puts("Empty table");
for (i = 0; i < T->size; i++) //проходим по массиву
if (T->val[i].busy)
{
printf("%2d ", i);
ItemPrint(&T->val[i]); //выводим очередной элемент
}
else
{
printf("%2d -----no item-----\n", i); //если элемента нет, то выводим соответствующее сообщение
}
}
//добавление ключа в таблицу
int TableAdd(Table* T, int key, char* info)
{
int ind;
if (T->count == T->size) //проверка на переполнение
TableZip(T); //пытаемся сжать таблицу
if (T->count == T->size) //если не получилось сжать - возвращаем ошибку
return 1;
ind = TableFindLast(T, key); //поиск индекса последней версии ключа
T->val[T->count].busy = 1; //пишем новый элемент в конец таблицы
T->val[T->count].info = info;
T->val[T->count].key = key;
if (ind < 0)
T->val[T->count].release = 1; //пишем правильную версию
else
T->val[T->count].release = T->val[ind].release + 1;
++T->count; //увеличиваем текущее количество элементов в таблице
return 0;
}
//сжатие массива
void TableZip(Table* T)
{
int j = 0;
int i;
for (i = 0; i < T->count; i++)
if (T->val[i].busy) //передвигаем на пустое место наш элемент
{
T->val[j].busy = T->val[i].busy;
T->val[j].info = T->val[i].info;
T->val[j].key = T->val[i].key;
T->val[j].release = T->val[i].release;
++j;
}
T->count = j;
}
//поиск элемента в таблице
int TableFindLast(Table* T, int key)
{
int i;
for (i = T->count - 1; i >= 0; i--) //идём с конца, т.к. версии элемента в силу механизма добавления расположены по возврастанию
if (T->val[i].busy && T->val[i].key == key) //поэтому самое последнее упоминание ключа бужет с самой большой версией
return i;
return -1;
}
//удаление ключа
int TableDeleteKey(Table* T, int key)
{
int count = 0, i;
for (i = 0; i < T->count; i++)
if (T->val[i].busy && T->val[i].key == key) //если ключ совпал и элемент существует
{
T->val[i].busy = 0; //просто меняем поле занятости на 0
free(T->val[i].info); //и очищаем память от информации
++count;
}
return count; //возвращаем число удалённых элементов
}
//удаление элементa по ключу и версии
int TableDeleteRelease(Table* T, int key, int release)
{
int i;
for (i = 0; i < T->count; i++)
if (T->val[i].busy && T->val[i].key == key && T->val[i].release == release) //если ключ и версиясовпали
{
T->val[i].busy = 0; //меняем значение поля занятости
free(T->val[i].info); //очищаем информацию
return 1;
}
return 0;
}
//ищем элемент и создаём таблицу с найденными элементами
Table* TableFindKey(Table* T, int key)
{
Table* NewTable = TableCreate(T->size);
int i, j;
for (i = 0; i < T->count; i++)
if (T->val[i].busy && T->val[i].key == key) //если элемент сущевстует и ключи совпали
{
j = NewTable->count; //пишем в конец нашей новой таблицы
NewTable->val[j].busy = 1;
NewTable->val[j].info = (char*)calloc(strlen(T->val[i].info) + 1, sizeof(char)); //копию найденного элемента
strcpy(NewTable->val[j].info, T->val[i].info);
NewTable->val[j].key = key;
NewTable->val[j].release = T->val[i].release;
++NewTable->count; //увеличиваем размер таблицы
}
NewTable->size = NewTable->count;
if (NewTable->count)
return NewTable;
else
TableDelete(NewTable);
return NULL;
}
//поиск по ключу и версии
char* TableFindRelease(Table* T, int key, int release)
{
int i;
char* info;
for (i = 0; i < T->count; i++)
if (T->val[i].busy && T->val[i].key == key && T->val[i].release == release) //если совпало
{
info = (char*)calloc(strlen(T->val[i].info) + 1, sizeof(char));
strcpy(info, T->val[i].info); //копируем инормацию
return info; //и возвращаем строку
}
return NULL;
}
//вывод элемента
int ItemPrint(Item* I)
{
printf("%7d %7d %s\n", I->key, I->release, I->info);
return 0;
}
//другие функции
//чтение целого числа
int getInt(int *a)
{
int n = scanf("%d", a); //считаем по адресу а - значение символа. сама функция вернёт -1, если конец файла, 0 если символ не корректный
if (!n) // обнаружен некорректный символ - ошибка
printf("%s\n", "Error! All incorrect symbols will be skiped.");
while (n < 0)
{
scanf("%*c");
n = scanf("%d", a);
}
return 1;
}
//получаем строку из входного потока
int getStr(char** s)
{
char buf[21]; //считываем из входного потока строку с помощью этого буфера, кусками по 20 сиволов
int n; //сюда будет записываться результат scanf
int len = 0; //сюда длина результирующей строки
*s = (char *)malloc(1); //указатель на результирующую сткроу
**s = '\0'; //ноль байт, пока строка имеет только конец строки
scanf("%*c");
do {
n = scanf("%20[^\n]", buf); //считываем буфер
if (n < 0)
{ //если ввели конец файла (ctrl+Z), то будет -1
free(*s); //очищаем память, возвращаем пустой указатель
return -1;
}
if (n > 0) { //если буфер не пустой
len += strlen(buf); //увеличиваем результирующую длину
*s = (char *)realloc(*s, len + 1); //добавляем память
if (*s) //если память выделилась
strcat(*s, buf); //копируем строку из буфера в конец нашей строки
else
{ //если память не выделилась
free(*s); //очищаем память
return -2;
}
}
else
scanf("%*c"); //если перенос строки, то очищаем входной поток
} while (n > 0); //пока во входном потоке есть хоть один символ
return 0;
}