Задача: разработать программу с оптимальным хранением в памяти с использованием…
- User
Задача: разработать программу с оптимальным хранением в памяти с использованием AVL-дерева на языке СИ. Программа реализует простую базу данных, которая хранит набор книг из онлайн-библиотеки и предоставляет пользователю удобный консольный интерфейс взаимодействия.
Каждая книга описывается следующими полями: Название книги. Автор/Авторы. Год выпуска. Оценка читателей. Цена книги. Жанр. Допускается использование различных служебных полей (к примеру, внутреннего идентификатора книги).
Программа должна поддерживать ряд операций, а именно: Добавление книги. Удаление книги. Редактирование книги. Поиск по любому из полей по всей базе данных. Вывод информации о книгах. Требования: Книги могут описаны как на русском языке, так и на английском. Использование наиболее оптимального дерева для реализации программы. Программа запускается и ожидает на вход набор команд. Команды, которые поступают на вход, имеют следующий формат:
ADD «Название книги» «Автор/Авторы» (разделяются запятыми) «Год выпуска» «Оценка читателей» «Цена книги» «Жанр». Если указанной книги еще нет в дереве, вставить и вывести слово «ADD_DONE», если уже есть — оставить дерево как было и выводить слово «ADD_ALREADY». DELETE «Название книги». Если указанная книга есть в дереве, удалить и вывести слово «DELETE_DONE», если нет — оставить дерево как было и выводить слово «DELETE_CANNOT». SEARCH item, где item это одно из полей книги. Ответ «YES/NO». EDIT «Название книги»: «Название книги» «Автор/Авторы» (разделяются запятыми) «Год выпуска» «Оценка читателей» «Цена книги» «Жанр». Эта команда меняет какой-то параметр книги. Панков не написал, как именно писать это в командной строке. Решаем сами LNRPRINTTREE, вывод — обход LNR. Новая строка не указывается. Вывод осуществляется в соответствии с полями книги, описанными выше. NLRPRINTTREE, вывод — обход NLR. Новая строка не указывается. Вывод осуществляется в соответствии с полями книги, описанными выше. LRNPRINTTREE, вывод — обход LRN. Новая строка не указывается. Вывод осуществляется в соответствии с полями книги, описанными выше. В случае некорректного ввода программа выводит «Error parse». Между словами может быть неограниченное число пробелов. При компиляции программы не должно быть никаких предупреждений от компилятора (для удобства можно использовать ключи компиляции /Wall, /WX для Visual Studio; -Wall -pedantic для GCC).
- Assistant
To address the task, we'll develop a C program that implements an in-memory database for managing a collection of books using an AVL tree for optimal storage and retrieval. The AVL tree ensures that the tree remains balanced after every insertion and deletion, providing efficient O(log n) time complexity for these operations.
Key Components:
-
Data Structures:
- Book Structure: Represents each book with fields such as title, authors, year, rating, price, and genre.
- AVL Tree Node: Each node contains a
Bookand pointers to its left and right children, along with a height attribute for balancing.
-
Functions:
- AVL Tree Operations: Insertion, deletion, searching, and rotations to maintain tree balance.
- Command Parsing: Read and interpret user commands from the console.
- Operations Implementation: Handle
ADD,DELETE,EDIT,SEARCH, and tree traversal commands (LNRPRINTTREE,NLRPRINTTREE,LRNPRINTTREE).
-
Error Handling:
- Ensure proper parsing of commands and handle invalid inputs gracefully by outputting
Error parse.
- Ensure proper parsing of commands and handle invalid inputs gracefully by outputting
-
Localization:
- Since book titles and authors can be in Russian or English, the program handles UTF-8 encoded strings.
Assumptions:
- Book titles are unique identifiers for simplicity.
- Input commands are well-formed strings enclosed in double quotes, separated by spaces, with fields like authors separated by commas.
Compilation:
- The code is written in standard C and should compile without warnings using GCC with
-Wall -pedanticflags.
Complete Program:
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h> // Define maximum lengths for strings #define MAX_TITLE 256 #define MAX_AUTHORS 256 #define MAX_GENRE 100 typedef struct Book { char title[MAX_TITLE]; char authors[MAX_AUTHORS]; int year; double rating; double price; char genre[MAX_GENRE]; } Book; typedef struct AVLNode { Book book; struct AVLNode* left; struct AVLNode* right; int height; } AVLNode; // Function prototypes int max(int a, int b); int height(AVLNode* N); AVLNode* newNode(Book book); AVLNode* rightRotate(AVLNode* y); AVLNode* leftRotate(AVLNode* x); int getBalance(AVLNode* N); AVLNode* insertNode(AVLNode* node, Book book, int* added); AVLNode* minValueNode(AVLNode* node); AVLNode* deleteNode(AVLNode* root, char* title, int* deleted); AVLNode* searchNode(AVLNode* root, char* field, char* value); void inorderTraversal(AVLNode* root); void preorderTraversal(AVLNode* root); void postorderTraversal(AVLNode* root); void printBook(Book book); int compareBooks(const Book* a, const Book* b); int editBook(AVLNode* root, Book updatedBook); // Utility functions int max(int a, int b) { return (a > b) ? a : b; } int height(AVLNode* N) { if (N == NULL) return 0; return N->height; } AVLNode* newNode(Book book) { AVLNode* node = (AVLNode*)malloc(sizeof(AVLNode)); if (!node) { perror("Failed to allocate memory"); exit(EXIT_FAILURE); } node->book = book; node->left = node->right = NULL; node->height = 1; // New node is initially added at leaf return node; } AVLNode* rightRotate(AVLNode* y) { AVLNode* x = y->left; AVLNode* T2 = x->right; // Perform rotation x->right = y; y->left = T2; // Update heights y->height = max(height(y->left), height(y->right)) + 1; x->height = max(height(x->left), height(x->right)) + 1; // Return new root return x; } AVLNode* leftRotate(AVLNode* x) { AVLNode* y = x->right; AVLNode* T2 = y->left; // Perform rotation y->left = x; x->right = T2; // Update heights x->height = max(height(x->left), height(x->right)) + 1; y->height = max(height(y->left), height(y->right)) + 1; // Return new root return y; } int getBalance(AVLNode* N) { if (N == NULL) return 0; return height(N->left) - height(N->right); } // Compare books by title for AVL tree int compareBooks(const Book* a, const Book* b) { return strcmp(a->title, b->title); } AVLNode* insertNode(AVLNode* node, Book book, int* added) { if (node == NULL) { *added = 1; return newNode(book); } int cmp = compareBooks(&book, &node->book); if (cmp < 0) node->left = insertNode(node->left, book, added); else if (cmp > 0) node->right = insertNode(node->right, book, added); else { // Duplicate title *added = 0; return node; } // Update height node->height = 1 + max(height(node->left), height(node->right)); // Get balance factor int balance = getBalance(node); // Balance the tree // Left Left if (balance > 1 && compareBooks(&book, &node->left->book) < 0) return rightRotate(node); // Right Right if (balance < -1 && compareBooks(&book, &node->right->book) > 0) return leftRotate(node); // Left Right if (balance > 1 && compareBooks(&book, &node->left->book) > 0) { node->left = leftRotate(node->left); return rightRotate(node); } // Right Left if (balance < -1 && compareBooks(&book, &node->right->book) < 0) { node->right = rightRotate(node->right); return leftRotate(node); } return node; } AVLNode* minValueNode(AVLNode* node) { AVLNode* current = node; while (current->left != NULL) current = current->left; return current; } AVLNode* deleteNode(AVLNode* root, char* title, int* deleted) { if (root == NULL) { *deleted = 0; return root; } int cmp = strcmp(title, root->book.title); if (cmp < 0) root->left = deleteNode(root->left, title, deleted); else if (cmp > 0) root->right = deleteNode(root->right, title, deleted); else { // Node with only one child or no child if ((root->left == NULL) || (root->right == NULL)) { AVLNode* temp = root->left ? root->left : root->right; if (temp == NULL) { // No child temp = root; root = NULL; } else { // One child *root = *temp; } free(temp); *deleted = 1; } else { // Node with two children AVLNode* temp = minValueNode(root->right); root->book = temp->book; root->right = deleteNode(root->right, temp->book.title, deleted); } } if (root == NULL) return root; // Update height root->height = 1 + max(height(root->left), height(root->right)); // Get balance factor int balance = getBalance(root); // Balance the tree // Left Left if (balance > 1 && getBalance(root->left) >= 0) return rightRotate(root); // Left Right if (balance > 1 && getBalance(root->left) < 0) { root->left = leftRotate(root->left); return rightRotate(root); } // Right Right if (balance < -1 && getBalance(root->right) <= 0) return leftRotate(root); // Right Left if (balance < -1 && getBalance(root->right) > 0) { root->right = rightRotate(root->right); return leftRotate(root); } return root; } // Function to search by field and value int searchTree(AVLNode* root, char* field, char* value) { if (root == NULL) return 0; // Check current node int match = 0; if (strcasecmp(field, "Название книги") == 0 || strcasecmp(field, "Title") == 0) { match = (strcmp(root->book.title, value) == 0); } else if (strcasecmp(field, "Автор/Авторы") == 0 || strcasecmp(field, "Authors") == 0) { // Check if any author matches char authors_copy[MAX_AUTHORS]; strcpy(authors_copy, root->book.authors); char* token = strtok(authors_copy, ","); while (token) { while (isspace(*token)) token++; if (strcmp(token, value) == 0) { match = 1; break; } token = strtok(NULL, ","); } } else if (strcasecmp(field, "Год выпуска") == 0 || strcasecmp(field, "Year") == 0) { char year_str[10]; sprintf(year_str, "%d", root->book.year); match = (strcmp(year_str, value) == 0); } else if (strcasecmp(field, "Оценка читателей") == 0 || strcasecmp(field, "Rating") == 0) { char rating_str[10]; sprintf(rating_str, "%.2lf", root->book.rating); match = (strcmp(rating_str, value) == 0); } else if (strcasecmp(field, "Цена книги") == 0 || strcasecmp(field, "Price") == 0) { char price_str[20]; sprintf(price_str, "%.2lf", root->book.price); match = (strcmp(price_str, value) == 0); } else if (strcasecmp(field, "Жанр") == 0 || strcasecmp(field, "Genre") == 0) { match = (strcmp(root->book.genre, value) == 0); } if (match) return 1; // Recurse to left and right return searchTree(root->left, field, value) || searchTree(root->right, field, value); } void inorderTraversal(AVLNode* root) { if (root != NULL) { inorderTraversal(root->left); printBook(root->book); inorderTraversal(root->right); } } void preorderTraversal(AVLNode* root) { if (root != NULL) { printBook(root->book); preorderTraversal(root->left); preorderTraversal(root->right); } } void postorderTraversal(AVLNode* root) { if (root != NULL) { postorderTraversal(root->left); postorderTraversal(root->right); printBook(root->book); } } void printBook(Book book) { printf("\"%s\" \"%s\" \"%d\" \"%.2lf\" \"%.2lf\" \"%s\"", book.title, book.authors, book.year, book.rating, book.price, book.genre); } int editBook(AVLNode* root, Book updatedBook) { if (root == NULL) return 0; int cmp = strcmp(updatedBook.title, root->book.title); if (cmp < 0) return editBook(root->left, updatedBook); else if (cmp > 0) return editBook(root->right, updatedBook); else { // Update the book details root->book = updatedBook; return 1; } } // Function to trim leading and trailing whitespace void trim(char* str) { // Trim leading space while (isspace(*str)) str++; // Trim trailing space char* end = str + strlen(str) - 1; while (end > str && isspace(*end)) end--; // Write new null terminator *(end + 1) = '\0'; } // Function to parse quoted strings int parse_quoted_string(char** input, char* output, int max_len) { while (isspace(**input)) (*input)++; if (**input != '\"') return 0; (*input)++; int i = 0; while (**input != '\"' && **input != '\0' && i < max_len - 1) { output[i++] = **input; (*input)++; } if (**input != '\"') return 0; output[i] = '\0'; (*input)++; return 1; } // Main function int main() { AVLNode* root = NULL; char line[1024]; while (fgets(line, sizeof(line), stdin)) { // Remove trailing newline line[strcspn(line, "\n")] = '\0'; // Initialize pointers char* ptr = line; while (isspace(*ptr)) ptr++; // Handle empty lines if (*ptr == '\0') continue; // Identify command if (strncmp(ptr, "ADD", 3) == 0 && isspace(ptr[3])) { ptr += 3; // Parse fields Book new_book; if (!parse_quoted_string(&ptr, new_book.title, MAX_TITLE)) { printf("Error parse\n"); continue; } if (!parse_quoted_string(&ptr, new_book.authors, MAX_AUTHORS)) { printf("Error parse\n"); continue; } // Year while (isspace(*ptr)) ptr++; char year_str[10]; int i = 0; while (isdigit(*ptr) && i < 9) { year_str[i++] = *ptr++; } year_str[i] = '\0'; if (i == 0) { printf("Error parse\n"); continue; } new_book.year = atoi(year_str); // Rating while (isspace(*ptr)) ptr++; char rating_str[10]; i = 0; while ((isdigit(*ptr) || *ptr == '.') && i < 9) { rating_str[i++] = *ptr++; } rating_str[i] = '\0'; if (i == 0) { printf("Error parse\n"); continue; } new_book.rating = atof(rating_str); // Price while (isspace(*ptr)) ptr++; char price_str[20]; i = 0; while ((isdigit(*ptr) || *ptr == '.') && i < 19) { price_str[i++] = *ptr++; } price_str[i] = '\0'; if (i == 0) { printf("Error parse\n"); continue; } new_book.price = atof(price_str); // Genre if (!parse_quoted_string(&ptr, new_book.genre, MAX_GENRE)) { printf("Error parse\n"); continue; } // Insert into AVL tree int added = 0; root = insertNode(root, new_book, &added); if (added) printf("ADD_DONE\n"); else printf("ADD_ALREADY\n"); } else if (strncmp(ptr, "DELETE", 6) == 0 && isspace(ptr[6])) { ptr += 6; char title[MAX_TITLE]; if (!parse_quoted_string(&ptr, title, MAX_TITLE)) { printf("Error parse\n"); continue; } int deleted = 0; root = deleteNode(root, title, &deleted); if (deleted) printf("DELETE_DONE\n"); else printf("DELETE_CANNOT\n"); } else if (strncmp(ptr, "SEARCH", 6) == 0 && isspace(ptr[6])) { ptr += 6; // Expecting two fields: field and value // For simplicity, assume format: SEARCH "Field" "Value" char field[MAX_GENRE]; char value[MAX_TITLE]; if (!parse_quoted_string(&ptr, field, MAX_GENRE) || !parse_quoted_string(&ptr, value, MAX_TITLE)) { printf("Error parse\n"); continue; } int found = searchTree(root, field, value); printf("%s\n", found ? "YES" : "NO"); } else if (strncmp(ptr, "EDIT", 4) == 0 && isspace(ptr[4])) { ptr += 4; // Expecting: EDIT "Title": "New Title" "New Authors" "Year" "Rating" "Price" "Genre" // First, parse the existing title char existing_title[MAX_TITLE]; if (!parse_quoted_string(&ptr, existing_title, MAX_TITLE)) { printf("Error parse\n"); continue; } // Expect colon while (isspace(*ptr)) ptr++; if (*ptr != ':') { printf("Error parse\n"); continue; } ptr++; // Now parse the new book details Book updated_book; if (!parse_quoted_string(&ptr, updated_book.title, MAX_TITLE)) { printf("Error parse\n"); continue; } if (!parse_quoted_string(&ptr, updated_book.authors, MAX_AUTHORS)) { printf("Error parse\n"); continue; } // Year while (isspace(*ptr)) ptr++; char year_str[10]; int i = 0; while (isdigit(*ptr) && i < 9) { year_str[i++] = *ptr++; } year_str[i] = '\0'; if (i == 0) { printf("Error parse\n"); continue; } updated_book.year = atoi(year_str); // Rating while (isspace(*ptr)) ptr++; char rating_str[10]; i = 0; while ((isdigit(*ptr) || *ptr == '.') && i < 9) { rating_str[i++] = *ptr++; } rating_str[i] = '\0'; if (i == 0) { printf("Error parse\n"); continue; } updated_book.rating = atof(rating_str); // Price while (isspace(*ptr)) ptr++; char price_str[20]; i = 0; while ((isdigit(*ptr) || *ptr == '.') && i < 19) { price_str[i++] = *ptr++; } price_str[i] = '\0'; if (i == 0) { printf("Error parse\n"); continue; } updated_book.price = atof(price_str); // Genre if (!parse_quoted_string(&ptr, updated_book.genre, MAX_GENRE)) { printf("Error parse\n"); continue; } // Find and edit the book int edited = editBook(root, updated_book); if (edited) printf("EDIT_DONE\n"); else printf("EDIT_CANNOT\n"); } else if (strncmp(ptr, "LNRPRINTTREE", 11) == 0 && (ptr[11] == '\0' || isspace(ptr[11]))) { inorderTraversal(root); printf("\n"); } else if (strncmp(ptr, "NLRPRINTTREE", 11) == 0 && (ptr[11] == '\0' || isspace(ptr[11]))) { preorderTraversal(root); printf("\n"); } else if (strncmp(ptr, "LRNPRINTTREE", 11) == 0 && (ptr[11] == '\0' || isspace(ptr[11]))) { postorderTraversal(root); printf("\n"); } else { printf("Error parse\n"); } } // Cleanup: Implement a post-order traversal to free memory if needed return 0; }Compilation Instructions:
To compile the program using GCC with strict warnings enabled, use the following command:
gcc -Wall -pedantic -o book_db book_db.cUsage:
Run the compiled program and enter commands as specified. For example:
./book_dbThen, input commands like:
ADD "The Great Gatsby" "F. Scott Fitzgerald" 1925 4.5 10.99 "Novel" ADD_DONE SEARCH "Title" "The Great Gatsby" YES DELETE "The Great Gatsby" DELETE_DONE SEARCH "Title" "The Great Gatsby" NONotes:
- The program assumes that the
EDITcommand replaces the entire book record based on the title. If the book does not exist, it outputsEDIT_CANNOT. - The
SEARCHcommand currently supports searching for exact matches on specified fields. It can be extended for partial matches or case-insensitive searches as needed. - The AVL tree is balanced based on the book titles to ensure efficient operations.
- Error handling is implemented to catch parsing errors and invalid commands, outputting
Error parseaccordingly. - The traversal commands (
LNRPRINTTREE,NLRPRINTTREE,LRNPRINTTREE) print all books in the specified order without newlines between individual books, followed by a newline at the end.
This implementation meets the specified requirements and provides a foundation that can be further expanded with additional features or optimizations as needed.
-