Пример 1: Класс, описывающий двунаправленный список
#include <iostream>
#include <conio.h>
#include <windows.h>
#include <stdlib.h>
using namespace std;
// структура, описывающая один узел:
struct Node
{
int data; // элемент данных
Node *next, *prev; // указатели на следующий и предыдущий узел
};
// класс для работы со списком:
class ListInt
{
/* указатели на начало, конец списка и на текущий узел (указатель на текущий узел используется многими функциями, поэтому объявим его как элемент данных класса): */
// открытые функции, которые будет использовать главная программа:
void Add( int);
void preOrder();
void inOrder();
void postOrder();
};
// Определение функций:
//Функция, которая добавляет узел к дереву:
void Tree :: Add(int m)
{
Add(rootPtr, m);
/* Здесь и далее перегрузка функций требуется, поскольку главная программа не имеет доступа к корневому узлу дерева, поэтому единственное назначение этого вызова функции Add() – передать адрес корневого узла. */
}
/* Основная функция, которая обходит дерево и привязывает новый узел к дереву: */
void Tree :: Add(TreeNode*& ptr, int m)
{
if (!ptr)
/* Если текущий указатель равен 0, к нему подвязываем новый узел
или создаем корневой */
ptr = new TreeNode(m);
/* благодаря тому, что параметр ptr объявлен как ссылка на указатель, устанавливается значение указателя на корневой узел или изменяется значение указателя в том узле, к которому привязывается новый */
else
{
if (m < ptr->data) Add(ptr->lPtr, m);
// если новый элемент меньше значения в текущем узле, идем налево
else if (m > ptr->data) Add(ptr->rPtr, m);
// в противном случае - направо
// если встречается повторяющееся значение, то оно игнорируется, благодаря этому все элементы дерева будут различны
}
}
/* три нижеследующие функции отличаются только последовательностью выполнения операторов и благодаря этому позволяют выводить элементы дерева на экран в различном порядке */
void Tree :: preOrder()
{
preOrder(rootPtr);
}
// обход дерева “по ширине”:
void Tree :: preOrder(TreeNode* ptr)
{
if (ptr)
{
cout << ptr->data << " "; // выводим элемент
preOrder(ptr->lPtr); // спускаемся влево
preOrder(ptr->rPtr); // спускаемся вправо
}
}
// Последовательный обход
void Tree :: inOrder()
{
inOrder(rootPtr);
}
// обход в порядке возрастания:
void Tree :: inOrder(TreeNode* ptr)
{
if (ptr)
{
inOrder(ptr->lPtr);
cout << ptr->data << " ";
inOrder(ptr->rPtr);
}
}
// Обход в обратном направлении:
void Tree :: postOrder()
{
postOrder(rootPtr);
}
void Tree :: postOrder(TreeNode* ptr)
{
if (ptr)
{
postOrder(ptr->lPtr);
postOrder(ptr->rPtr);
cout << ptr->data << " ";
}
}
// Пример использования класса:
int main()
{
//Настройки шрифтов и региональных стандартов:
if(SetConsoleCP(1251)==0)
//проверка правильности установки кодировки символов для ввода
{
cerr<<"Fialed to set codepage!"<<endl;
}
if(SetConsoleOutputCP(1251)==0)//тоже самое для вывода
