Skip to content
TheChatArchiveThe Chat Archive
o1-mini-2024-09-12· OpenAIAi2 WildChat-4.8M (AI2)

Задача: разработать программу с оптимальным хранением в памяти с использованием…

  1. 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).

  2. 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:

    1. 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 Book and pointers to its left and right children, along with a height attribute for balancing.
    2. 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).
    3. Error Handling:

      • Ensure proper parsing of commands and handle invalid inputs gracefully by outputting Error parse.
    4. 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 -pedantic flags.

    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.c
    

    Usage:

    Run the compiled program and enter commands as specified. For example:

    ./book_db
    

    Then, 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"
    NO
    

    Notes:

    • The program assumes that the EDIT command replaces the entire book record based on the title. If the book does not exist, it outputs EDIT_CANNOT.
    • The SEARCH command 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 parse accordingly.
    • 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.