1. Односвязные списки
typedef int datatype;
using namespace std;
struct Node
{
datatype data;
Node* next;
};
void init(Node*& head)
{
head = nullptr;
}
bool isEmpty(Node* head)
{
return head == nullptr;
}
void addToHead(Node*& head, datatype data)
{
Node* p = new Node;
p->data = data;
p->next = head;
head = p;
}
void addAfterNode(Node* pNode, datatype data)
{
Node* p = new Node;
p->data = data;
p->next = pNode->next;
pNode->next = p;
}
void deleteFromHead(Node*& head)
{
Node* p = head;
head = head->next;
p->next = nullptr;
delete p;
p = nullptr;
}
void deleteAfterNode(Node*& pNode)
{
Node* p = pNode->next;
pNode->next = p->next;
p->next = nullptr;
delete p;
p = nullptr;
}
void clear(Node*& head)
{
while (!isEmpty(head))
deleteFromHead(head);
}
void print(Node* head)
{
Node* p = head;
while (!isEmpty(p))
{
cout << p->data << " ";
p = p->next;
}
}
Node* search(Node* head, datatype data)
{
Node* p = head;
Node* res = nullptr;
while (!isEmpty(p))
{
if (p->data == data)
{
res = p;
}
p = p->next;
}
return res;
}
2. Односвязные списки с заглавным звеном
void init(Node*& head)
{
head = new Node;
head->next = nullptr;
}
bool isEmpty(Node* head)
{
return head->next == nullptr;
}
3-4. Рекурсивная печать списка и сумма
void printRec(Node* head)
{
if (head)
{
cout << head->data; // чтобы в обратном порядке
printRec(head->next); // поменять эти строки
}
}
datatype sumRec(Node* head)
{
if (isEmpty(head))
return 0;
return (head->data + sumRec(head->next));
}
5. Двусвязные списки
typedef int datatype;
struct Node
{
datatype data;
Node* next;
Node* prev;
Node(int elem)
{
data = elem;
next = nullptr;
prev = nullptr;
}
};
void init(Node*& head, Node*& tail)
{
head = nullptr;
tail = nullptr;
}
bool isEmpty(Node* head)
{
return head == nullptr;
}
void addToHead(Node*& head, datatype data)
{
Node* p = new Node(data);
p->next = head;
if (!isEmpty(head))
{
head->prev = p;
}
head = p;
}
void addAfterNode(Node* pNode, Node*& tail, datatype data)
{
Node* p = new Node(data);
p->prev = pNode;
p->next = pNode->next;
if (pNode->next != nullptr)
pNode->next->prev = p;
else
tail = p;
pNode->next = p;
}
void deleteAfterNode(Node* pNode, Node* tail)
{
if (pNode->next != nullptr)
{
Node* p = pNode->next;
pNode->next = p->next;
if (p->next != nullptr)
{
p->next->prev = pNode;
}
else
{
tail = pNode;
}
p->next = nullptr;
p->prev = nullptr;
delete p;
p = 0;
}
}
void deleteNode(Node* head, Node* pNode)
{
if (head == pNode)
head = pNode->next;
if (pNode->next != nullptr)
pNode->next->prev = pNode->prev;
if (pNode->prev != nullptr)
pNode->prev->next = pNode->next;
pNode->next = nullptr;
pNode->prev = nullptr;
delete pNode;
pNode = 0;
return;
}
void print(Node* head)
{
Node* p = head;
while (!isEmpty(p))
{
cout << p->data << " ";
p = p->next;
}
}
Node* search(Node* head, datatype data)
{
Node* p = head;
Node* res = nullptr;
while (!isEmpty(p))
{
if (p->data == data)
{
res = p;
break;
}
p = p->next;
}
return res;
}
void clear(Node* head, Node* tail)
{
while (!isEmpty(head))
{
deleteAfterNode(head, tail);
}
}
7. Реализация стека на основе массива
class AStack
{
int top;
datatype* stack;
int size;
void clear();
public:
AStack(int size1):size(size1),stack(new datatype[size1]),top(-1){}
~AStack();
void push(datatype elem);
void pop();
datatype peek();
bool isEmpty();
void resize();
};
void AStack::clear()
{
top = -1;
}
AStack::~AStack()
{
delete[] stack;
stack = nullptr;
}
void AStack::push(datatype elem)
{
if (top >= size - 1)
resize();
top++;
stack[top] = elem;
}
void AStack::pop()
{
if (top > -1)
top--;
else
cout << "Stack is empty";
}
datatype AStack::peek()
{
return stack[top];
}
bool AStack::isEmpty()
{
return top==-1;
}
void AStack::resize()
{
datatype* new_stack = new datatype[2 * size];
for (int i = 0; i < size; i++)
new_stack[i] = stack[i];
size *= 2;
delete[] stack;
stack = new_stack;
}
8. Реализация стека на основе списка
class TStack {
struct Node {
datatype data;
Node* next;
Node(datatype elem) {
data = elem;
next = nullptr;
}
};
Node* top;
void clear();
public:
TStack() :top(nullptr) {}
~TStack() {
void clear();
}
void push(datatype elem);
void pop();
datatype peek();
bool isEmpty();
void print();
datatype min();
datatype max();
};
void TStack::push(datatype elem)
{
Node* p = new Node(elem);
p->next = top;
top = p;
}
void TStack::pop()
{
Node* p = top;
top = top->next;
p->next = nullptr;
delete p;
p = nullptr;
}
datatype TStack::peek()
{
return top->data;
}
bool TStack::isEmpty()
{
return top==nullptr;
}
void TStack::clear()
{
while(!isEmpty())
{
pop();
}
}
void TStack::print()
{
Node* p = top;
while (p != nullptr)
{
cout << p->data << "";
p = p->next;
}
}9. Применение стека: проверка баланса скобок.
bool balanced(string& s) {
TStack stack;
for (char c : s) {
switch (c) {
case '(': stack.push(')'); break;
case '[': stack.push(']'); break;
case '{': stack.push('}'); break;
case '<': stack.push('>'); break;
case ')':
case ']':
case '}':
case '>':
if (stack.isEmpty() || stack.peek() != c) {
return false;
}
stack.pop();
break;
default:
break;
}
}
return stack.isEmpty();
}10. Применение стека: преобразование формулы из инфиксной в постфиксную запись
int prec(char c)
{
if (c == '*' || c == '/') {
return 1;
}
if (c == '+' || c == '-') {
return 2;
}
return 3; // для открывающей скобки '('
}
bool isOperand(char c) {
return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9');
}
string infixToPostfix(string infix)
{
TStack s;
string postfix;
// обрабатываем инфиксное выражение слева направо
for (char c : infix)
{
// Случай 1. Если текущий токен '(', помещаем его в stack
if (c == '(') {
s.push(c);
}
// Случай 2. Если текущий токен является закрывающей скобкой ')'
else if (c == ')')
{
// извлекаем токены из stack до тех пор, пока не появится открывающая скобка '('
while (s.peek() != '(')
{
postfix.push_back(s.peek());
s.pop();
}
s.pop();
}
// Случай 3. Если текущий токен является операндом, добавляем его в конец
else if (isOperand(c)) {
postfix.push_back(c);
}
// Случай 4. Если текущий токен является оператором
else {
// удаляем из stack операторы с >= приоритетом
// и добавляем их в конец постфиксного выражения
while (!s.isEmpty() && prec(c) >= prec(s.peek()))
{
postfix.push_back(s.peek());
s.pop();
}
s.push(c);
}
}
while (!s.isEmpty())
{
postfix.push_back(s.peek());
s.pop();
}
return postfix;
}
11. Применение стека: вычисление значения формулы
int calculate_Postfix(string s)
{
TStack stack;
int len = s.length();
for (char c : s)
{
if (c >= '0' && c <= '9')
{
stack.push(c - '0');
}
else
{
int a = stack.peek();
stack.pop();
int b = stack.peek();
stack.pop();
switch (c)
{
case '+':
stack.push(b + a);
break;
case '-':
stack.push(b - a);
break;
case '*':
stack.push(b * a);
break;
case '/':
stack.push(b / a);
break;
}
}
}
return stack.peek();
}
13. Реализация очереди с помощью списка:
typedef char datatype;
class TQueue {
struct Node {
datatype data;
Node* next;
Node(datatype elem) : next(nullptr), data(elem) {}
};
Node* head, * tail;
public:
TQueue(): head(nullptr), tail(nullptr) {}
~TQueue() { clear(); }
bool isEmpty()
{
return head == nullptr;
}
void enque(datatype elem)
{
if (isEmpty())
{
tail = new Node(elem);
head = tail;
}
else
{
tail->next = new Node(elem);
tail = tail->next;
}
}
void deque()
{
Node* p = head;
head = head->next;
p->next = nullptr;
delete p;
p = nullptr;
}
void clear()
{
while (!isEmpty())
deque();
}
datatype peek()
{
return head->data;
}
};
14. Деревья. Основные определения. Применение деревьев.
Граф - множество вершин и их отношений
Дерево - связный граф без циклов(1)
Все вершины дерева называются узлами дерева
Вершина от которой отходят ребра - родительская, связанные с ней дочерние
Вершина без родительских - корень
Дерево хранится в памяти с помощью корня
От корня можно последовательно перейти к любой вершине дерева через ребра
Вершины без дочерних - листья
Если каждый узел дерева может содержать не более n узлов, то он n-арное
Пример(2)
Граф - множество вершин и их отношений
Дерево - связный граф без циклов(1)
Все вершины дерева называются узлами дерева
Вершина от которой отходят ребра - родительская, связанные с ней дочерние
Вершина без родительских - корень
Дерево хранится в памяти с помощью корня
От корня можно последовательно перейти к любой вершине дерева через ребра
Вершины без дочерних - листья
Если каждый узел дерева может содержать не более n узлов, то он n-арное
Пример(2)
struct TreeNode
{
datatype data;
TreeNode* left;
TreeNode* right;
};
void init(TreeNode*& root) //1
{
root = nullptr;
}
void init(TreeNode*& root, datatype elem) //2
{
root = new TreeNode;
root->data = elem;
root->left = nullptr;
root->right = nullptr;
}
bool attachLeftSubtree(TreeNode* root, TreeNode* subtree) //7
{
bool canAttach = false;
if (root->left == nullptr)
{
root->left = subtree;
canAttach = true;
}
return canAttach;
}
bool attachRightSubtree(TreeNode* root, TreeNode* subtree) //7
{
bool canAttach = false;
if (root->right == nullptr)
{
root->right = subtree;
canAttach = true;
}
return canAttach;
}
void init(TreeNode*& root, datatype elem, TreeNode* leftSubtree, TreeNode* rightSubtree) //3
{
init(root, elem);
attachLeftSubtree(root, leftSubtree);
attachRightSubtree(root, rightSubtree);
}
bool dettachLeftSubtree(TreeNode* root, TreeNode*& subtree) //9
{
subtree = root->left; //root must not be empty
root->left = nullptr;
}
bool dettachRightSubtree(TreeNode* root, TreeNode*& subtree) //9
{
subtree = root->right;
root->right = nullptr;
}
void copy(TreeNode* root, TreeNode*& newroot)
{
if (root != nullptr)
{
init(newroot, root->data);
copy(root->left, newroot->left);
copy(root->right, newroot->right);
}
else
newroot = nullptr;
}
TreeNode* copyLeftSubtree(TreeNode* root) //10
{
TreeNode* leftSubtree;
init(leftSubtree);
//if (root != nullptr)
copy(root->left, leftSubtree);
}
TreeNode* copyRightSubtree(TreeNode* root) //10
{
TreeNode* rightSubtree;
init(rightSubtree);
//if (root != nullptr)
copy(root->right, rightSubtree);
}
16. Обход дерева в ширину
void BFS(TreeNode* root) //Breadth First Search
{
TQueue queue;
queue.enque(root);
while (!queue.isEmpty())
{
cur = queue.peek();
cout << cur->data;
queue.deque();
if (!cur->left != nullptr)
{
queue.enque(cur->left);
}
if (!cur->right != nullptr)
{
queue.enque(cur->right);
}
}
}
17-18. Обход узлов бинарного дерева в прямом, симметричном или обратном порядке. Итеративный обход дерева в глубину
// префиксный в глубину(прямой)
void preorder(TreeNode* root)
{
if (root != nullptr)
{
cout << root->data;
preorder(root->left);
preorder(root->right);
}
}
// инфиксный в глубину(симметричный)
void inorder(TreeNode* root)
{
if (root != nullptr)
{
preorder(root->left);
cout << root->data;
preorder(root->right);
}
}
// постфиксный в глубину(обратный)
void postorder(TreeNode* root)
{
if (root != nullptr)
{
preorder(root->left);
preorder(root->right);
cout << root->data;
}
}
// итерационный префиксный в глубину
void inorder_iterated(TreeNode* root)
{
TStack stack;
bool done = false;
TreeNode* cur = root;
while (!done)
{
if (cur != nullptr)
{
stack.push(cur);
cur = cur->left;
}
else if(!stack.isEmpty())
{
cur = stack.peek();
cout << cur->data;
stack.pop();
cur = cur->right;
}
else
{
done = true;
}
}
}
19. Бинарное дерево поиска
Бинарным деревом поиска называется бинарное дерево, обладающее св-вами:
1. Значение ключа любого узла в левом поддереве меньше значения ключа самого узла.
2. Значение ключа любого узла в правом поддереве больше значения ключа самого узла.
3. Левое и правое поддеревья каждого узла также являются бинарными деревьями поиска.
Бинарным деревом поиска называется бинарное дерево, обладающее св-вами:
1. Значение ключа любого узла в левом поддереве меньше значения ключа самого узла.
2. Значение ключа любого узла в правом поддереве больше значения ключа самого узла.
3. Левое и правое поддеревья каждого узла также являются бинарными деревьями поиска.
typedef int datatype;
struct TSearchTree {
datatype data;
TSearchTree* left;
TSearchTree* right;
TSearchTree(int value) : data(value), left(nullptr), right(nullptr) {}
};
bool isEmpty(TSearchTree* root) {
return root == nullptr;
}
void insert(TSearchTree* root, datatype elem)
{
if (root == nullptr)
root = new TSearchTree(elem);
else
{
if (root.data > elem)
insert(root->left, elem);
if (root.data < elem)
insert(root->right, elem);
}
}
void remove(TSearchTree*& root, datatype elem)
{
if (root->data == elem)
deleteNode(root);
else
{
if (root.data > elem)
remove(root->left, elem);
if (root.data < elem)
remove(root->right, elem);
}
}
void deleteNode(TSearchTree*& root)
{
if (root->left == nullptr && root->right == nullptr)
{
delete root;
root = nullptr;
}
else if (root->left == nullptr || root->right == nullptr)
{
TSearchTree* temp = root;
if (root->left != nullptr)
root = root->left;
else
root = root->right;
delete temp;
}
else
root->data = findSuccessor(root->right)
}
datatype findSuccessor(TSearchTree*& root)
{
TSearchTree* cur = root;
while (cur->left != nullptr)
cur = cur->left;
datatype temp = cur->data;
deleteNode(cur);
return cur;
}