пятница, 25 октября 2019 г.

Сортировка по возрастанию с помощью бинарного дерева

В С++ в STL нет контейнера для формирования динамической структуры бинарное дерево. Поэтому используют структуру с полями указателями на левое и правое поддерево:

typedef struct TNode *PNode;
typedef struct TNode
{
    int data;
    PNode left;
    PNode right;
} TNode;
Будем вводить элементы массива и сразу формировать дерево:
Функция добавления звена в дерево:
void MakeTree(int k, PNode &p)

 {
if (p==NULL) //если нет корня
    {
        p=new TNode;
        p->data=k;
        p->left=NULL;
        p->right=NULL;
    }
else {  if (k<=p->data)
// если меньше корня, то добавляем влево
        if (p->left!=NULL)
            MakeTree(k, p->left);
        else{
            p->left=new TNode;
            p->left->left=NULL;
            p->left->right=NULL;
            p->left->data=k;
        }
    }
if (k>p->data)
//если больше корня, то добавляем вправо
    {if (p->right!=NULL)
            MakeTree(k, p->right);
        else        {
            p->right=new TNode;
            p->right->left=NULL;
            p->right->right=NULL;
            p->right->data=k;        }
    }
}
}
Функции обхода дерева:

void Search_LKP(PNode p)
{//левое-корень-правое
    if(p!=NULL)
    {
        Search_LKP(p->left);
        cout << p->data << '  ';
        Search_LKP(p->right);
     }
}
Вывод данных: 1 2 3 4 5 6 9
void Search_KLP(PNode p)
{//корень-левое-правое
    if(p!=NULL)
    {
        cout << p->data << ' ';
        Search_KLP(p->left);
        Search_KLP(p->right);
    }
}
Вывод данных: 4 2 1 3 6 5 9
void Search_LPK(PNode p)
{//левое-правое-корень
    if(p!=NULL)
    {
        Search_LPK(p->left);
        Search_LPK(p->right);
        cout << p->data << ' ';
    }
}
Вывод данных: 1 3 2 5 9 6 4
Функция удаления:
void DeleteTree(PNode &p)
{
    if(p->left!=NULL)
    {
        DeleteTree(p->left);
    }
    if(p->right!=NULL)
    {
        DeleteTree(p->right);
    }
    delete p;
}

Основная программа:

int main()

{
    PNode t;
    t=NULL;
    int x;
//ввод  до нуля  
    cin>>x;
    while(x!=0)
    {
        MakeTree(x, t);   cin>>x;
    }
//обход дерева
    Search_LKP(t);
//удаление дерева
    DeleteTree(t);
    return 0;
}

вторник, 23 апреля 2019 г.

Перевод числа в строку и наоборот в С++

#include <iostream>
#include <sstream>
using namespace std;
int main()
{
    string s="12";
    istringstream in_str;
    in_str.str(s);
    int k;
    in_str >> k;
    cout<<k*2<< endl;

    ostringstream out_str;
    int N = 123;
    out_str << N;
    s = out_str.str()+" year";
    cout<<s;
    out_str.str(""); // clear stringstream
}



среда, 10 января 2018 г.

Ввод массива неизвестной длины

В некоторых задачах необходимо ввести элементы массива, но при этом сколько элементов не задано точно, кроме этого нужно считывать только данные с одной строки (например, список вершин графа). Как считать до конца строки, т.е. когда нажата клавиша Enter?

int n,a;
cin>>n; //кол-во вершин
vector <int> A[n]; //список смежных вершин
for(int i=0;i<n;i++)
{
  do{    
    cin>>a;
    A[i].push_back(a);
  }while(cin.get()!=10);//если после числа не Enter, но может быть пробел
}

Получается разреженная матрица:

for (int i=0; i<n; i++)
{
    for(int j=0; j<A[i].size(); j++)
        cout<<A[i][j]<<" ";
    cout<< endl;
}