work2/task3.cpp - develop - novd7/algirithms_sem2

work2/task3.cpp
158 строк5 KB
Новиков Владимир
work 2
03 апр 2026, 22:39
03 апр 2026, 22:3904518aa
#include <iostream>
#include <string>

using namespace std;

// Структура узла для хранения записи (имя и список телефонов)
struct PhoneRecord {
    string name;
    string phone;
    PhoneRecord* left;
    PhoneRecord* right;

    PhoneRecord(string n, string p) : name(n), phone(p), left(nullptr), right(nullptr) {}
};

// Функция для создания нового узла
PhoneRecord* createRecord(string name, string phone) {
    return new PhoneRecord(name, phone);
}

// Функция для добавления записи или телефона
PhoneRecord* insert(PhoneRecord* root, string name, string phone) {
    if (!root) {
        root = createRecord(name, phone);
    } else if (name < root->name) {
        root->left = insert(root->left, name, phone);
    } else if (name > root->name) {
        root->right = insert(root->right, name, phone);
    } else {
        // Человек уже существует, обновляем телефон
        root->phone = phone;
    }
    return root;
}

// Поиск записи по имени
PhoneRecord* search(PhoneRecord* root, string name) {
    if (!root || root->name == name) return root;

    if (name < root->name)
        return search(root->left, name);
    else
        return search(root->right, name);
}

// Удаление записи по имени
PhoneRecord* remove(PhoneRecord* root, string name) {
    if (!root) return root;

    if (name < root->name) {
        root->left = remove(root->left, name);
    } else if (name > root->name) {
        root->right = remove(root->right, name);
    } else {
        // Найден узел для удаления
        if (!root->left && !root->right) {
            delete root;
            return nullptr;
        } else if (!root->left) {
            PhoneRecord* temp = root->right;
            delete root;
            return temp;
        } else if (!root->right) {
            PhoneRecord* temp = root->left;
            delete root;
            return temp;
        } else {
            // Два потомка: находим минимальный в правом поддереве
            PhoneRecord* temp = root->right;
            while (temp && temp->left) temp = temp->left;
            root->name = temp->name;
            root->phone = temp->phone;
            root->right = remove(root->right, temp->name);
        }
    }
    return root;
}

// Вспомогательная функция для вывода телефонов
void printPhone(string phone) {
    cout << phone;
}

// Симметричный обход — вывод всей телефонной книги
void inorder(PhoneRecord* root) {
    if (root) {
        inorder(root->left);
        cout << root->name << ": ";
        printPhone(root->phone);
        cout << endl;
        inorder(root->right);
    }
}

// Главная функция
int main() {
    PhoneRecord* root = nullptr;
    int choice;
    string name, phone;

    while (true) {
        cout << "\n--- Телефонная книга ---" << endl;
        cout << "1. Добавить запись" << endl;
        cout << "2. Найти запись" << endl;
        cout << "3. Удалить запись" << endl;
        cout << "4. Показать всю книгу" << endl;
        cout << "5. Выход" << endl;
        cout << "Выберите действие: ";
        cin >> choice;

        switch (choice) {
            case 1: {
                cout << "Введите имя: ";
                cin >> name;
                cout << "Введите телефон: ";
                cin >> phone;
                root = insert(root, name, phone);
                cout << "Запись добавлена." << endl;
                break;
            }
            case 2: {
                cout << "Введите имя для поиска: ";
                cin >> name;
                PhoneRecord* found = search(root, name);
                if (found) {
                    cout << "Найдено:\n" << found->name << ": ";
                    printPhone(found->phone);
                    cout << endl;
                } else {
                    cout << "Запись не найдена." << endl;
                }
                break;
            }
            case 3: {
                cout << "Введите имя для удаления: ";
                cin >> name;
                root = remove(root, name);
                cout << "Запись удалена." << endl;
                break;
            }
            case 4: {
                cout << "\nВся телефонная книга:" << endl;
                inorder(root);
                break;
            }
            case 5: {
                cout << "Выход из программы." << endl;
                return 0;
            }
            default: {
                cout << "Неверный выбор. Попробуйте снова." << endl;
                break;
            }
        }
    }

    return 0;
}