#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
//данные хранятся в виде массива структур из указателя и ключа
//структура элемента таблицы
typedef struct Item
{
int key; //ключ
int release; //номер версии
char* info; //поле данных - строка
}Item;
//структура - таблица
typedef struct Table
{
int size; //максимальный размер таблицы
int count; //текущий размер таблицы
Item* val; //массив структур item
}Table;
const int SIZE = 10; //максимальны размер таблицы
//меню
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_FindKey(Table*); //поиск и копирование элемента
int F8_FindRelease(Table*); //поиск версии
//функции работы с таблицей
Table* TableCreate(int size); //функция создания пустой таблицы
void TableDelete(Table* T); //удаление таблицы
void TablePrint(Table* T); //вывод таблицы
int TableAdd(Table* T, int key, char* info); //добавление элемента с ключом в таблицу
int TableFindLast(Table* T, int key); //поиск элемнета последней версии по ключу в таблице (начинается с конца таблицы)
Table* TableFindKey(Table* T, int key); //поиск и получение копии элемента
char* TableFindRelease(Table* T, int key, int release); //поиск по ключу и версии
int TableDeleteRelease(Table* T); //удаление предыдущих версий
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 releases", "Find key", "Find release" }; //строки меню
int main()
{
int ex = 0; //переменые для удобного вывода меню
int menu = 0; //далее до конца - вывод меню
int(*fun[]) (Table*) = { NULL, F1_End, F2_Menu, F3_Print, F4_Generate,
F5_Input, F6_DeleteKey, F7_FindKey, F8_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 >= 9)
{
printf("Enter number menu (2 for enter menu): ");
getInt(&menu); //чтение номера пункта меню
if (menu <= 0 || menu >= 9) { // обнаружен неверный номер - ошибка
printf("%s\n", "Error! Wrong symbol.");
scanf("%*c");
}
}
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 < 9; ++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)
{
printf("Deleted %d items.\n", TableDeleteRelease(T)); //выводим сколько ключей мы удалили
return 0;
}
//поиск в таблице ключа
int F7_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 F8_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++)
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");
else
{
for (i = 0; i < T->count; i++) {
//проходим по массиву
printf("%2d ", i); //выводим очередной элемент
ItemPrint(&T->val[i]);
}
}
}
//добавление ключа в таблицу
int TableAdd(Table* T, int key, char* info)
{
int ind;
if (T->count == T->size) //проверка на переполнение
return 1;
ind = TableFindLast(T, key); //поиск индекса последней версии ключа
//пишем новый элемент в конец таблицы
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;
}
//поиск последней версии элемента в таблице
int TableFindLast(Table* T, int key)
{
int i;
for (i = T->count - 1; i >= 0; i--) //идём с конца, т.к. версии элемента в силу механизма добавления расположены по возврастанию
if (T->val[i].key == key) //поэтому самое последнее упоминание ключа бужет с самой большой версией
return i;
return -1;
}
//сжатие массива
int TableZip(Table* T, int key, int release)
{
int j = T->count; //переменная для хранения текущего размера
int i = 0;
while (i < j)
{
if (T->val[i].key == key and T->val[i].release != release) //если у текущего элемента тот же ключ, но другая версия
{
free(T->val[i].info); //удаляем строку
for (int k = i; k < j - 1; k++) { //сдвигаем все элементы в массиве на один влево
T->val[k].info = T->val[k + 1].info;
T->val[k].key = T->val[k + 1].key;
T->val[k].release = T->val[k + 1].release;
}
--j; //уменьшаем текущий размер на один
}
else {
i++;
}
}
int count = 0; //переменная для посчета числа удаленных элементов
for (i = j; i < T->count; i++) {
T->val[i].info = NULL; //удаление лишней информации
count++;
}
T->count = j; //запоминаем новый размер
return count;
}
//удаление старых весий элементов
int TableDeleteRelease(Table* T)
{
int i = 0;
int count = 0;
while (i < T->count) { //проходимся по всем элемнтам
int ver = TableFindLast(T, T->val[i].key); //получаем номер последней версии текущего элемента
if (T->val[ver].release == T->val[i].release) { //если текущий элемент самая новая версия
i++; //переходим к следующему элементу
}
else {
count += TableZip(T, T->val[i].key, T->val[ver].release); //удаляем все старые версии
}
}
return count;
}
//ищем элемент и создаём таблицу с найденными элементами
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].key == key) //если элемент сущевстует и ключи совпали
{
j = NewTable->count; //пишем в конец нашей новой таблицы
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].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 = 0;
do
{
n = scanf("%d", a); //считаем по адресу а - значение символа. сама функция вернёт -1, если конец файла, 0 если символ не корректный
if (n <= 0) // обнаружен некорректный символ - ошибка
printf("%s\n", "Error! Wrong symbol.");
scanf("%*c");
} while (n <= 0);
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;
}