Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // ConsoleApplication1.cpp: определяет точку входа для консольного приложения.
- //
- #include "stdafx.h"
- #include <iostream>
- #include <cstring>
- using namespace std;
- struct node
- {
- char* data = new char[1024];
- node* next;
- };
- node* make_linked_list(int n)
- {
- node *beg;//указатель на первый элемент
- node *p, *r;//вспомогательные указатели
- beg = new(node);//выделяем память под первый элемент
- cout << "Ввод " << n << " значений информационного поля:" << endl;
- cin >> beg->data;//вводим значение информационного поля
- beg->next = 0;//обнуляем адресное поле
- p = beg;//ставим на этот элемент указатель p (последний элемент)
- for (int i = 0; i < n - 1; i++)
- {
- r = new(node);//создаем новый элемент
- cin >> r->data;
- r->next = 0;
- p->next = r;//связываем p и r
- //ставим на r указатель p (последний элемент)
- p = r;
- }
- return beg;//возвращаем beg как результат функции
- }
- void print_linked_list(node* beg)
- {
- node* p = beg;//начало списка
- cout << "Однонаправленный список:" << endl;
- while (p != 0)
- {
- cout << p->data << " ";
- p = p->next;//переход к следующему элементу
- }
- cout << endl;
- }
- node* add_node(node* beg, int k)
- //добавление элемента с номером k
- {
- node *p = beg;//встали на первый элемент
- node *New = new(node);//создали новый элемент
- cout << "Ввод нового элемента: "; cin >> New->data;
- if (k == 0)//добавление в начало, если k=0
- {
- New->next = beg;
- beg = New;
- return beg;
- }
- for (int i = 0; i < k - 1 && p != 0; i++)
- p = p->next;//проходим по списку до(k-1) элемента или до конца
- if (p != 0)//если k-й элемент существует
- {
- New->next = p->next;//связываем New и k-й элемент
- p->next = New;//связываем (k-1)элемент и New
- }
- return beg;
- }
- /*find - функция для нахождения номера добавляемого элемента*/
- int find(node* beg, char *s)
- {
- node* p = beg;//начало списка
- int k = 1;
- while (p != 0, strcmp(p->data, s)){
- p = p->next;//переход к следующему элементу
- k++;
- }
- return k;
- }
- void delete_linked_list(node *beg)
- {
- node* p = beg;//начало списка
- node* r = p->next;
- while (p != 0 && r != 0)
- {
- delete (p);
- p = r;
- r = p->next;
- }
- cout << endl;
- }
- struct dobly_node{
- int key;
- dobly_node *next;
- dobly_node *prev;
- };
- dobly_node *make_point(int key)
- //создание одного элемента двунаправленного списка
- {
- dobly_node *p = new(dobly_node);
- p->next = 0; p->prev = 0;//обнуляем указатели
- p->key = key;//выделение памяти под строку
- return p;
- }
- dobly_node *make_dobly_list(int n)//создание двунаправленного списка
- {
- dobly_node *p, *beg;
- int a;
- cin >> a;
- beg = make_point(a);//создаем первый элемент
- beg->next = 0;//конца списка
- for (int i = 1; i<n; i++)
- {
- cin >> a;
- p = make_point(a);//создаем один элемент
- //добавление элемента в начало списка
- p->next = beg;//связываем р с первым элементом
- beg->prev = p;//связываем первый элемент с p
- beg = p;// p становится первым элементом списка
- }
- beg->prev = 0;//зануление начала списка
- return beg;
- }
- void print_dobly_list(dobly_node *beg)
- {
- dobly_node *p = beg;
- cout << "Двунаправленный список: ";
- while (p != 0)
- {
- cout << p->key << " ";
- p = p->next;//переход к следующему элементу
- }
- cout << endl;
- }
- dobly_node *delete_even(dobly_node *beg, int n)
- {
- dobly_node *p = beg, *r = 0, *del = 0;
- while (p->next != 0){
- if ((p->key % 2) == 0 && p->prev != 0){
- del = p;
- r = p->prev;
- p = del->next;
- p->prev = r;
- r->next = p;
- delete(del);
- }
- else if ((p->key % 2) == 0 && p->prev == 0){
- del = p;
- p = del->next;
- delete(del);
- p->prev = 0;
- beg = p;
- }
- else
- p = p->next;
- }
- if (p->key % 2 == 0)
- p = p->prev;
- p->next = 0;
- return beg;
- }
- void delete_dobly_list(dobly_node *beg)//удаление списка
- {
- dobly_node *p, *r;
- p = beg;
- r = beg->next;
- while (p != 0 && r != 0)
- {
- delete(p);
- p = r;
- r = p->next;
- }
- }
- struct leaf
- {
- char data;//информационное поле
- leaf *left;//адрес левого поддерева
- leaf *right;//адрес правого поддерева
- };
- leaf* first(char d)//формирование первого элемента дерева
- {
- leaf* p = new leaf;
- p->data = d;
- p->left = 0;
- p->right = 0;
- return p;
- }
- leaf* Tree(int n, leaf *p)//создание идеально сбалансированного дерева
- {
- leaf *r;
- char nl, nr;
- if (n == 0){ p = 0; return p; }
- nl = n / 2;
- nr = n - nl - 1;
- r = new leaf;
- cin >> r->data;
- r->left = Tree(nl, r->left);
- r->right = Tree(nr, r->right);
- p = r;
- return p;
- }
- void Print_tree(leaf*p)//печать дерева
- {
- if (p)
- {
- cout << p->data << ' ';
- Print_tree(p->left);//переход к левому поддереву
- Print_tree(p->right);//переход к правому поддереву
- }
- }
- int Find_hight(leaf*p, int h)//нахождение высоты дерева
- {
- if (p)
- {
- ++h;
- h = Find_hight(p->left, h);//переход к левому поддереву
- }
- return h;
- }
- void To_binary_tree(leaf*p)//преобразование идеально сбалансированного дерева в дерево поиска
- {
- if (p)
- {
- char tmp;
- if (p->left && p->left->data > p->data)
- {
- tmp = p->data;
- p->data = p->left->data;
- p->left->data = tmp;
- }
- if (p->right && p->right->data < p->data)
- {
- tmp = p->data;
- p->data = p->right->data;
- p->right->data = tmp;
- }
- To_binary_tree(p->left);//переход к левому поддереву
- To_binary_tree(p->right);//переход к правому поддереву
- }
- }
- int main()
- {
- setlocale(LC_ALL, "rus");
- cout << "Ввод начального кол-ва записей однонаправленного списка:";
- int n;
- cin >> n;
- node *beg = make_linked_list(n);
- print_linked_list(beg);
- cout << "Ввод элемента после которого будет добавляться новый элемент:";
- char* s = new char[1024];
- cin >> s;
- beg = add_node(beg, find(beg, s));
- print_linked_list(beg);
- delete_linked_list(beg);
- cout << "Ввод начального кол-ва записей двунаправленного списка:";
- cin >> n;
- dobly_node *start = make_dobly_list(n);
- print_dobly_list(start);
- start = delete_even(start, n);
- cout << "Удаление четных информационных полей..." << endl;
- print_dobly_list(start);
- delete_dobly_list(start);
- leaf *root = new leaf;
- cout << "Ввод кол-ва элементов идеально сбалансированного дерева: "; cin >> n;
- cout << "Ввод " << n << " элементов дерева:" << endl;
- root = Tree(n, root);
- cout << "Вывод идеально сбалансированного дерева:" << endl;
- Print_tree(root);
- cout << "\nВысота:" << Find_hight(root, 0) << endl;
- for (int i = 0; i < Find_hight(root, 0); ++i)
- To_binary_tree(root);
- cout << "Дерево поиска:" << endl;
- Print_tree(root);
- system("pause");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement