Lab16,17,18

Lab16.cpp

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <locale.h>
#include <stdlib.h>
#include <string.h>

int hash(char *word)
{
	int i = 0, sum = 0;
	while (word[i] != '\0')
	{
		sum += (int)word[i];
		i++;
	}
	return sum % 10;
}

void main()
{
	setlocale(LC_ALL, "rus");
	char *keys[10] = { "end", "Begin", "var", "word", "Integer0", "IF", "do1", "while", "for)", "Char" };
	char **table = (char**)malloc(10 * sizeof(char*));
	for (int i = 0; i < 10; i++)
	{
		table[i] = NULL;
	}
	while (true)
	{
		char *key = (char*)malloc(256 * sizeof(char));
		printf("Введите одно из ключевых слов:\n");
		for (int i = 0; i < 10; i++)
		{
			puts(keys[i]);
		}
		scanf("%s", key);
			int index = hash(key);
			if (table[index] == NULL)
			{
				table[index] = (char*)malloc(sizeof(key));
				table[index] = key;
				printf("Элемент успешно добавлен.\nХеш-таблица:\n");
				for (int i = 0; i < 10; i++)
				{
					if (table[i] != NULL)
					{
						printf("Индекс: %d. Ключ: %s\n", i, table[i]);
					}
				}
			}
			else
			{
				if (table[index] != NULL)
				{
					printf("Элемент уже существует. Индекс: %d. Ключ: %s.\n", index, table[index]);
				}
			}
		system("pause");
		system("cls");
	}
	system("pause");
}

Lab17.cpp

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <locale.h>
#include <stdlib.h>
#include <string.h>

int hash(char *word, int m)
{
	int i = 0, sum = 0;
	while (word[i] != '\0')
	{
		sum += (int)word[i];
		i++;
	}
	return sum % m;
}
void main()
{
	setlocale(LC_ALL, "rus");
	printf("Введите размер хеш-таблицы.\n");
	int size;
	scanf("%d", &size);
	char **table = (char**)malloc(size * sizeof(char*));
	for (int i = 0; i < size; i++)
	{
		table[i] = NULL;
	}
		while (true)
		{
			int compareCount = 0;
			int select;
			printf("1)Добавить ключ.\n2)Поиск.\n3)Вывод таблицы.\n4)Выход.\n");
			scanf("%d", &select);
			if (select == 1)
			{
				char *key = (char*)malloc(256 * sizeof(char));
				printf("Введите слово.\n");
				scanf("%s", key);
				int index = hash(key, size);
				if (table[index] == NULL)
				{
					table[index] = (char*)malloc(sizeof(key));
					table[index] = key;
					printf("Элемент добавлен: индекс %d, ключ %s.\n", index, table[index]);
				}
				else if (!strcmp(table[index], key))
				{
					printf("Элемент уже существует.\n");
					continue;
				}
				else 
				{
					bool flag = false;
					for (int i = 0; i < size; i++)
					{
						int j = (hash(key, size) + i) % size;
						if (table[j] == NULL)
						{
							table[j] = (char*)malloc(sizeof(key));
							table[j] = key;
							printf("Элемент добавлен: индекс %d, ключ %s.\n", j, table[j]);
							flag = true;
							break;
						}
						else if (table[j] != NULL)
						{
							if (!strcmp(table[j], key))
							{
								printf("Элемент уже существует.\n");
								flag = true;
								break;
							}
						}
					}
					if (!flag)
					{
						printf("Таблица заполнена, добавление невозможно.\n");
					}
				}
			}
			else if(select == 2)
			{
				char *key = (char*)malloc(256 * sizeof(char));
				printf("Введите слово.\n");
				scanf("%s", key);
				int index = hash(key, size);
				if (table[index] != NULL)
				{
					if (!strcmp(table[index], key))
					{
						printf("Элемент уже существует:\nИндекс: %d, Ключ: %s\n", index, table[index]);
						printf("Кол-во сравнений: 1.\n");
						continue;
					}
				}
				bool flag = false;
				for (int i = 0; i < size; i++)
				{
					int j = ((hash(key, size) + i) % size);
					if (table[j] == NULL)
					{
						continue;
					}
					compareCount++;
					if (!strcmp(table[j], key))
					{
						printf("Элемент уже существует:\nИндекс: %d, Ключ: %s\n", j, table[j]);
						printf("Кол-во сравнений: %d.\n", compareCount);
						flag = true;
						break;
					}
				}
				if (!flag)
				{
					printf("Элемент не найден.\n");
				}
			}
			else if (select == 3)
			{
				for (int i = 0; i < size; i++)
				{
					if (table[i] != NULL)
					{
						printf("Индекс: %d, Ключ: %s.\n", i, table[i]);
					}
				}
			}
			else if (select == 4)
			{
				break;
			}
		}
}

Lab18.cpp

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <locale.h>
#include <string.h>

struct QueueItem {
	char *key;
	QueueItem *left;
	QueueItem *right;
};
struct Queue {
	QueueItem *head;
	QueueItem *tail;
};

void addNewKey(Queue **queue, char *key)
{
	if (*queue == NULL)
	{
		*queue = (Queue*)malloc(sizeof(Queue));
		(*queue)->tail = (QueueItem*)malloc(sizeof(QueueItem));
		(*queue)->tail->key = key;
		(*queue)->tail->left = NULL;
		(*queue)->tail->right = NULL;
		(*queue)->head = (*queue)->tail;
	}
	else
	{
		QueueItem *oldTail = (*queue)->tail;
		(*queue)->tail = (QueueItem*)malloc(sizeof(QueueItem));
		(*queue)->tail->key = key;
		(*queue)->tail->left = NULL;
		(*queue)->tail->right = oldTail;
		oldTail->left = (*queue)->tail;
	}
}

int search(Queue *queue, char *key, int index)
{
	if (queue != NULL)
	{
		int compareCount = 0;
		QueueItem *cur = queue->head;
		while (cur != NULL)
		{
			compareCount++;
			if (!strcmp(cur->key, key))
			{
				printf("Индекс: %d.\n", index);
				printf("Ключ: %s.\nПоиск выполнен за %d сравнений.\n", cur->key, compareCount);
				return 1;
			}
			else
			{
				cur = cur->left;
			}
		}
	}
	return 0;
}

void show(Queue *queue, int index)
{
	if (queue != NULL)
	{
		printf("Индекс: %d.\n", index);
		QueueItem *cur = queue->head;
		while (cur != NULL)
		{
			printf("\tКлюч: %s.\n", cur->key);
			cur = cur->left;
		}
	}
}
int hash(char *word, int m)
{
	int i = 0, sum = 0;
	while (word[i] != '\0')
	{
		sum += (int)word[i];
		i++;
	}
	return sum % m;
}

void main()
{
	setlocale(LC_ALL, "rus");
	int size;
	printf("Введите размер таблицы.\n");
	scanf("%d", &size);
	Queue **table = (Queue**)malloc(size * sizeof(Queue*));
	for (int i = 0; i < size; i++)
	{
		table[i] = NULL;
	}
	while (true)
	{
		int select; 
		printf("1)Добавить ключ.\n2)Удалить ключ.\n3)Поиск.\n4)Вывод.\n5)Выход.\n");
		scanf("%d", &select);
		if (select == 1)
		{
			char *key = (char*)malloc(256 * sizeof(char));
			printf("Введите ключ: \n");
			scanf("%s", key);
			int index = hash(key, size);
			if (search(table[index], key, index))//Если такой ключ в таблице уже существует

			{
				printf("Элемент не добавлен.\n");
				continue;
			}
			addNewKey(&table[index], key);
		}
		else if (select == 2)
		{
			char *key = (char*)malloc(256 * sizeof(char));
			printf("Введите ключ: \n");
			scanf("%s", key);
			int index = hash(key, size);
			if (table[index] != NULL)
			{
				QueueItem *cur = table[index]->head;
				if (table[index]->head == table[index]->tail)
				{
					free(table[index]);
					table[index] = NULL;
					continue;
				}
				if (!strcmp(table[index]->head->key, key))
				{
					QueueItem *deleted = table[index]->head;
					table[index]->head = deleted->left;
					deleted->left->right = NULL;
					free(deleted);
					continue;
				}
				if (!strcmp(table[index]->tail->key, key))
				{
					QueueItem *deleted = table[index]->tail;
					table[index]->tail = deleted->right;
					deleted->right->left = NULL;
					free(deleted);
					continue;
				}
				while (cur->left != NULL)
				{
					if (!strcmp(cur->key, key))
					{
						QueueItem *deleted = cur;
						cur->left->right = cur->right;
						if (cur->right != NULL)
						{
							cur->right->left = cur->left;
						}
						deleted->left = NULL;
						deleted->right = NULL;
						free(deleted);
						break;
					}
					cur = cur->left;
				}
			}
		}
		else if (select == 3)
		{
			char *key = (char*)malloc(256 * sizeof(char));
			printf("Введите ключ: \n");
			scanf("%s", key);
			int index = hash(key, size);
			search(table[index], key, index);
		}
		else if (select == 4)
		{
			for (int i = 0; i < size; i++)
			{
				show(table[i], i);
			}
		}
		else if (select == 5)
		{
			break;
		}
	}
	system("pause");
}