Редактирани версии за C++17, отделени от оригиналния препис. 88 целеви проверки: успешни. Проверени са 98 събрани листинга и допълнителни фрагменти; запазени са условията за допустимите входове. Пълната коректност за всички възможни входове не следва от преминаването на тестове.
Условия и стартиране · Всички промени · Резултати от проверките · Съпоставка на всички 368 блока
#pragma once
#include "common.hpp"
#include "LList1.cpp"
template <typename T>
T accumulate(T (*op)(T, T), T null_val, LList<T>& L)
{ T s = null_val;
L.iterStart();
elem_link1<T> *p = L.iter();
while (p)
{ s = op(s, p->inf);
p = p->link;
}
return s;
}
#pragma once
#include "common.hpp"
#include "cyclicList.cpp"
template <typename T>
T accumulate(T (*op)(T, T), T null_val, cyclicList<T>& L)
{ T s = null_val;
L.iterStart();
elem_cyclic<T> *p = L.iter();
while (p)
{ s = (*op)(s, p->inf); // или s = op(s, p->inf);
p = L.iter(); // използването на p = p->link ще
// предизвика зацикляне
}
return s;
}
#pragma once
#include "common.hpp"
#include "tree.cpp"
template <typename T>
T accumulate(T (*op)(T, T), T null_val, const tree<T>& t)
{ if (!t.empty())
return op(op(accumulate(op, null_val, t.leftTree()),
t.rootTree()),
accumulate(op, null_val, t.rightTree()));
return null_val;
}
#pragma once
#include "common.hpp"
#include "graph.cpp"
#include "member.cpp"
#include "way.cpp"
bool flag = false;
template <typename T>
void allways(const T& a, const T& b, graph<T>& g,
LList<T>& l)
{ l.toEnd(a);
if (a == b)
{ flag = true;
l.print();
}
else
{ elem_link1<T>* q = g.point(a);
q = q->link;
while (q)
{ if (!member(q->inf, l))
{ allways(q->inf, b, g, l);
deleteLast(l); // връщане назад
}
q = q->link;
}
}
}
#pragma once
#include "common.hpp"
template <class T>
struct node
{ T inf; // връх
int balance; // коефициент на балансираност
node *left, // указател към ЛПД
*right; // указател към ДПД
};
template <class T>
class AVL
{ public:
// канонично представяне
AVL();
~AVL();
AVL(const AVL&);
AVL& operator=(const AVL&);
// проверява дали дървото е празно
bool empty() const;
// селектори
T rootAVL() const;
int balanceAVL() const;
AVL leftAVL() const;
AVL rightAVL() const;
// включва елемента x в подразбиращото се балансирано ДНД
void insNode(const T&x)
{ insertElem(root, x);
}
// изключва елемента x от подразбиращото се балансирано ДНД
void delNode(const T&x)
{ deleteElem(root, x);
}
// извежда подразбиращото се балансирано ДНД, завъртяно на
// 90 градуса в посока обратна на часовниковата стрелка
void print_tree() const
{ pr1(root, 0);
cout << endl;
}
// създава непразно балансирано двоично
// наредено дърво чрез вмъкване
void createAVL();
private:
node<T>* root; // указател към корена
// помощни член-функции
void deleteAVL(node<T>* &) const;
void copy(node<T>*&, node<T>* const&) const;
void copyAVL(AVL<T> const&);
void pr1(const node<T>*, int) const;
// реализира завъртане наляво
void leftRotate(node<T>*&);
// реализира завъртане надясно
void rightRotate(node<T>*&);
// включва даден елемент в AVL-дърво с указан корен
int insertElem(node<T>*&, const T&);
// изключва даден елемент от AVL-дърво с указан корен
int deleteElem(node<T>*&, const T&);
};
template <class T>
AVL<T>::AVL()
{ root = NULL;
}
template <class T>
AVL<T>::~AVL()
{ deleteAVL(root);
}
template <class T>
AVL<T>::AVL(const AVL<T>& r)
{ copyAVL(r);
}
template <class T>
AVL<T>& AVL<T>::operator=(const AVL<T>& r)
{ if (this != &r)
{ deleteAVL(root);
copyAVL(r);
}
return *this;
}
template <class T>
void AVL<T>::copyAVL(const AVL<T>& r)
{ copy(root, r.root);
}
template <class T>
void AVL<T>::copy(node<T>*& pos, node<T>* const& r) const
{ pos = NULL;
if (r)
{ pos = new node<T>;
assert(pos != NULL);
pos->inf = r->inf;
pos->balance = r->balance;
copy(pos->left, r->left);
copy(pos->right, r->right);
}
}
template <class T>
void AVL<T>::deleteAVL(node<T>*& p) const
{ if (p)
{ deleteAVL(p->left);
deleteAVL(p->right);
delete p;
p = NULL;
}
}
template <class T>
bool AVL<T>::empty() const
{ return root == NULL;
}
template <class T>
T AVL<T>::rootAVL() const
{ return root->inf;
}
template <class T>
int AVL<T>::balanceAVL() const
{ return root->balance;
}
template <class T>
AVL<T> AVL<T>::leftAVL() const
{ AVL<T> t;
copy(t.root, root->left);
return t;
}
template <class T>
AVL<T> AVL<T>::rightAVL() const
{ AVL<T> t;
copy(t.root, root->right);
return t;
}
template <class T>
void AVL<T>::createAVL()
{ char ch = 'y';
while(ch == 'y')
{ T x; cout << "x= "; cin >> x;
insNode(x);
cout << "ch = y/n? ";
cin >> ch;
}
}
template <class T>
void AVL<T>::leftRotate(node<T>*& r)
{ // промяна на структурата на дървото
node<T>* p = r;
r = r->right;
p->right = r->left;
r->left = p;
// намиране и промяна на коефициентите на балансиране
p->balance = p->balance - 1;
if (r->balance > 0) p->balance = p->balance -
r->balance;
r->balance = r->balance - 1;
if (p->balance < 0) r->balance = r->balance +
p->balance;
}
template <class T>
void AVL<T>::rightRotate(node<T>*& r)
{ // промяна на структурата на дървото
node<T>* p = r;
r = r->left;
p->left = r->right;
r->right = p;
// намиране и промяна на коефициентите на балансиране
p->balance = p->balance + 1;
if (r->balance < 0) p->balance = p->balance - r->balance;
r->balance = r->balance + 1;
if (p->balance > 0) r->balance = r->balance + p->balance;
}
template <class T>
int AVL<T>::insertElem(node<T>*& r, const T&x)
{ int h = 0; // ще съдържа стойността, която функцията ще върне
// равна е на 0 или 1 и означава увеличението на
// височината след вмъкването на x в дървото
// с корен, сочен от r
if (!r)
{ // AVL дървото е празно
r = new node<T>;
assert(r != NULL);
r->inf = x;
r->balance = 0;
r->left = NULL;
r->right = NULL;
h = 1;
}
else
if (x > r->inf)
{ // включване на x в ДПД на AVL дървото, сочено от r
if (insertElem(r->right, x))
{ r->balance++; // защото височината на
// ДПД се е увеличила с 1
if (r->balance == 1) h = 1; else
if (r->balance == 2)
{ if (r->right->balance == -1)
rightRotate(r->right);
leftRotate(r);
}
}
}
else // включване на x в ЛПД на AVL дървото, сочено от r
if (x < r->inf)
{ if (insertElem(r->left, x))
{ r->balance--; // защото височината на
// ЛПД се е увеличила с 1
if (r->balance == -1) h = 1; else
if (r->balance == -2)
{ if (r->left->balance == 1)
leftRotate(r->left);
rightRotate(r);
}
}
}
return h;
}
template <class T>
int AVL<T>::deleteElem(node<T>*& r, const T&x)
{ node<T>** p, *temp;
int h = 0; // ще съдържа стойността, която функцията ще върне
if (!r) return 0; // AVL дървото е празно
// AVL дървото не е празно
if (x < r->inf)
{ // изключване на x от ЛПД на AVL дървото
if (deleteElem(r->left, x))
{ r->balance++;
if (r->balance == 0) h = 1; else
if (r->balance == 2)
{ if (r->right->balance == -1)
rightRotate(r->right);
leftRotate(r);
if (r->balance == 0) h = 1;
}
}
}
else
if (x > r->inf)
{ // изключване на x от ДПД на AVL дървото
if (deleteElem(r->right, x))
{ r->balance--;
if (r->balance == 0) h = 1; else
if (r->balance == -2)
{ if (r->left->balance == 1)
leftRotate(r->left);
rightRotate(r);
if (r->balance == 0) h = 1;
}
}
}
else // x съвпада с корена на дървото
{ if (!r->right) // ДПД е празно
{ temp = r; r = r->left;
delete temp;
return 1;
}
else
if (!r->left) // ЛПД е празно
{ temp = r; r = r->right;
delete temp;
return 1;
}
else // x съвпада с корена и лявото, и дясното
// поддървета не са празни
{ // размяна на стойностите на корена и най-големия
// елемент на ЛПД на AVL дървото
p = &r->left;
while((*p)->right) p = &(*p)->right;
r->inf = (*p)->inf;
(*p)->inf = x;
// изключване на x от ЛПД
if (deleteElem(r->left, x))
{ r->balance++;
if (r->balance == 0) h = 1; else
if (r->balance == 2)
{ if (r->right->balance == -1)
rightRotate(r->right);
leftRotate(r);
if (r->balance == 0) h = 1;
}
}
}
}
return h;
}
template <class T>
void AVL<T>::pr1(const node<T>* p, int n) const
{ if (p)
{ n = n+7;
pr1(p->right, n);
cout << setw(n) << p->inf << " " << p->balance << endl;
pr1(p->left, n);
}
}
#pragma once
#include "common.hpp"
#include "graph.cpp"
#include "queue_link.cpp"
#include "differenceSets.cpp"
#include "member.cpp"
template <typename T>
void BFS(const T& a, graph<T> g, LList<T>& l)
{ queue<T> q; q.push(a);
l.toEnd(a);
while(!q.empty())
{ T x; q.pop(x);
cout << x << " ";
elem_link1<T>* p = g.point(x);
p = p->link;
while (p)
{ if (!member(p->inf, l))
{ q.push(p->inf);
l.toEnd(p->inf);
}
p = p->link;
}
}
}
template <typename T>
void full_BFS(graph<T>& g)
{ LList<T> v = g.vertexes(),// списък с върховете на графа
l, // празен списък
h = v; // или differenceSets(v, l)
while (!h.empty())
{ h.iterStart();
elem_link1<T> *p = h.iter();
BFS(p->inf, g, l);
h = differenceSets(v, l);
}
}
#pragma once
#include "common.hpp"
template <typename T = int>
struct node_bin
{ T inf;
node_bin<T> *left,
*right;
};
template <typename T = int>
class binOrdTree
{ public:
// канонично представяне
binOrdTree();
explicit binOrdTree(int);
~binOrdTree();
binOrdTree(const binOrdTree&);
binOrdTree& operator=(const binOrdTree&);
// основни операции
bool empty() const; // проверява дали дървото е празно
T rootTree() const; // намира на корена
binOrdTree leftTree() const; // намира на ЛПД
binOrdTree rightTree() const; // намира на ДПД
// създава непразно двоично наредено
// дърво по указани върхове
void create();
// създава непразно двоично наредено
// дърво по указани корен, ЛПД и ДПД
void create3(const T&, const binOrdTree&,
const binOrdTree&);
// извежда двоично наредено дърво
void print() const
{ pr(root);
cout << endl;
}
// включва връх в двоично наредено дърво
// със запазване на наредеността
void addNode(const T& x)
{ add(root, x);
}
// изтрива връх от двоично наредено дърво
// със запазване на наредеността
void deleteNode(const T&);
// помощна член-функция, която намира минималния
// елемент на дадено двоично наредено дърво и
// двоично наредено дърво, получено от даденото
// като от него се изключи минималният елемент
void minTree(T&, binOrdTree&) const;
void print_tree() const;
private:
void pr1(const node_bin<T>*, int) const;
node_bin<T>* root; // указател към корена
// създава копие на указаното двоично наредено дърво
// на друго място в паметта, сочено от указателя this
void copyTree(const binOrdTree&);
// помощна член-функция за копиране
void copy(node_bin<T>*&, node_bin<T>* const&) const;
// изтрива двоично наредено дърво
void deleteTree(node_bin<T>*&) const;
// извежда двоично наредено дърво, сочено
// от указателя, зададен чрез параметъра
void pr(const node_bin<T>*) const;
// включва указания елемент в двоично нареденото
// дърво, зададено чрез първия параметър
void add(node_bin<T>*&, const T&) const;
};
template <typename T>
binOrdTree<T>::binOrdTree()
{ root = NULL;
}
template <typename T>
binOrdTree<T>::~binOrdTree()
{ deleteTree(root);
}
template <typename T>
binOrdTree<T>::binOrdTree(const binOrdTree<T>& r)
{ copyTree(r);
}
template <typename T>
binOrdTree<T>& binOrdTree<T>::operator=(const binOrdTree<T>& r)
{ if (this != &r)
{ deleteTree(root);
copyTree(r);
}
return *this;
}
template <typename T>
void binOrdTree<T>::copyTree(const binOrdTree<T>& r)
{ copy(root, r.root);
}
template <typename T>
void binOrdTree<T>::copy(node_bin<T>*& pos,
node_bin<T>* const& r) const
{ pos = NULL;
if (r)
{ pos = new node_bin<T>;
assert(pos != NULL);
pos->inf = r->inf;
copy(pos->left, r->left);
copy(pos->right, r->right);
}
}
template <typename T>
void binOrdTree<T>::deleteTree(node_bin<T>*& p) const
{ if (p)
{ deleteTree(p->left);
deleteTree(p->right);
delete p;
p = NULL;
}
}
template <typename T>
bool binOrdTree<T>::empty() const
{ return root == NULL;
}
template <typename T>
T binOrdTree<T>::rootTree() const
{ if(!root) throw std::out_of_range("Empty tree has no root");
return root->inf;
}
template <typename T>
binOrdTree<T> binOrdTree<T>::leftTree() const
{ binOrdTree<T> t;
if(root) copy(t.root, root->left);
return t;
}
template <typename T>
binOrdTree<T> binOrdTree<T>::rightTree() const
{ binOrdTree<T> t;
if(root) copy(t.root, root->right);
return t;
}
template <typename T>
void binOrdTree<T>::pr(const node_bin<T>* p) const
{ if (p)
{ pr(p->left);
cout << p->inf << " ";
pr(p->right);
}
}
template <typename T>
void binOrdTree<T>::add(node_bin<T>*& p, const T& x) const
{ if (!p)
{ p = new node_bin<T>;
assert(p != NULL);
p->inf = x;
p->left = NULL;
p->right = NULL;
}
else
if (x < p->inf) add(p->left, x);
else add(p->right, x);
}
template <typename T>
void binOrdTree<T>::create()
{ deleteTree(root);
T x; char c;
do
{ cout << "> "; cin >> x;
addNode(x);
cout << "next elem y/n? "; cin >> c;
} while (c == 'y');
}
template <typename T>
void binOrdTree<T>::create3(const T& x, const binOrdTree<T>& l,
const binOrdTree<T>& r)
{ if (this == &l || this == &r) { binOrdTree<T> lc(l), rc(r); create3(x,lc,rc); return; }
if (root)deleteTree(root);
root = new node_bin<T>;
assert(root != NULL);
root->inf = x;
copy(root->left, l.root);
copy(root->right, r.root);
}
template <typename T>
void binOrdTree<T>::minTree(T& x, binOrdTree<T>& mint) const
{ T a = rootTree();
if (leftTree().empty())
{ x = a;
mint = rightTree();
}
else
{ binOrdTree<T> t, t1 = rightTree();
leftTree().minTree(x, t);
mint.create3(a, t, t1);
}
}
template <typename T>
void binOrdTree<T>::deleteNode(const T& x)
{ if (root)
{ // двоично нареденото дърво не е празно
T a = rootTree();
binOrdTree<T> t1, t2;
if (a == x && leftTree().empty()) *this = rightTree();
else
if (a == x && rightTree().empty()) *this = leftTree();
else
if (a == x)
{ T c; t1 = leftTree();
rightTree().minTree(c, t2);
create3(c, t1, t2);
}
else
if (x < a)
{ t2 = rightTree();
*this = leftTree();
deleteNode(x);
t1 = *this;
create3(a, t1, t2);
}
else
{ t1 = leftTree();
*this = rightTree();
deleteNode(x);
t2 = *this;
create3(a, t1, t2);
}
}
}
#pragma once
#include "common.hpp"
#include "binOrdTree.cpp"
template <typename T>
void binOrdTree<T>::print_tree() const
{ pr1(root, 0);
cout << endl;
}
template <typename T>
void binOrdTree<T>::pr1(const node_bin<T>* p, int n) const
{ if (p)
{ n = n + 5;
pr1(p->right, n);
cout << setw(n) << p->inf << endl;
pr1(p->left, n);
}
}
#pragma once
#include "common.hpp"
template <typename T>
int binSearch(T x, T *a, int n)
{ if (n <= 0) return 0;
int middle, left = 0, right = n-1;
if (x < a[left]) return -1;
if (x == a[left]) return 0;
if (x > a[right]) return n;
while (right-left > 1)
{ middle = (left + right)/2;
if (x <= a[middle]) right = middle;
else left = middle;
}
return right;
}
#pragma once
#include "common.hpp"
template <typename T>
int binSearch(fstream& f, T x)
{ f.seekg(0, ios::end);
long n = f.tellg()/sizeof(T);
if (n <= 0) return 0;
T al, ar, am;
int middle, left = 0, right = n-1;
f.seekg(left*sizeof(T));
f.read((char*)&al, sizeof(T));
f.seekg(right*sizeof(T));
f.read((char*)&ar, sizeof(T));
if (x < al) return -1;
if (x == al)return 0;
if (x > ar) return n;
while (right - left > 1)
{ middle = (left + right)/2;
f.seekg(middle*sizeof(T));
f.read((char*)&am, sizeof(T));
if (x <= am) right = middle;
else left = middle;
}
return right;
}
#pragma once
#include "binOrdTree.cpp"
template <typename T>
binOrdTree<T>::binOrdTree(int n)
{ root = NULL;
if (n > 0)
{ int nLeft = (n-1)/2,
nRight = n-nLeft-1;
binOrdTree<T> t1(nLeft);
T x; cin >> x;
binOrdTree<T> t2(nRight);
create3(x, t1, t2);
}
}#pragma once
#include "binOrdTree.cpp"
template <typename T>
bool member(const T& a, const binOrdTree<T>& t)
{ if (t.empty()) return false;
if (a == t.rootTree()) return true;
if (a < t.rootTree()) return member(a, t.leftTree());
return member(a, t.rightTree());
}#pragma once
#include "common.hpp"
template <typename T, int m>
struct elem
{ int n; // текущ брой на елементите във възела
// ((m-1)/2 <= n <= m-1)
T c[m-1]; // масив, съдържащ елементите на възела
// (използват се само първите n от тях)
elem* p[m]; // масив от указателите към поддърветата
// на възела (използват се n+1 от тях)
};#pragma once
#include "common.hpp"
template <typename T>
void swap(T& a, T& b)
{ T x = a; a = b; b = x;
}
template <typename T>
void bubbleSort(T* a, int n)
{ int i, k, right = n-1;
while (right > 0)
{ k = 0;
for (i = 0; i < right; i++)
if (a[i+1] < a[i])
{ ::swap(a[i], a[i+1]);
k = i;
}
right = k;
}
}
#pragma once
#include "common.hpp"
#include "file_helpers.hpp"
template <typename T>
void bubbleSort(fstream &f, T& dummy)
{ // намиране на броя на елементите на файла
f.seekg(0, ios::end);
int n = f.tellg()/sizeof(T);
int i, k, right = n-1;
T a, b;
while (right > 0)
{ k = 0;
for (i = 0; i < right; i++)
{ f.seekg(i*sizeof(T));
f.read((char*)&a, sizeof(T));
f.read((char*)&b, sizeof(T));
if (a > b)
{ swap(f, i, i+1, dummy);
k = i;
}
}
right = k;
}
f.close();
}
#pragma once
#include <iostream>
#include <iomanip>
#include <cassert>
#include <fstream>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <stdexcept>
#include <algorithm>
#include <vector>
#include <sstream>
#include <limits>
using namespace std;
#pragma once
#include "common.hpp"
void examples(){
{ int n=3,p=0,s=0,h=0; double a[4]{};
for (int i = 1; i <= n; i++)
a[i] = 5; // T1(n) = O(n)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
for (int k = 1; k <= n; k++)
a[j] = a[i]*a[j] + 5*a[k]; // T2(n) = O(n*n*n)
}
{ int n=3,p=0,s=0,h=0; double a[4]{};
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) p++;
assert(p==9);}
{ int n=3,p=0,h=0; double a[4]{};
int s = 0;
for (int i = 1; i <= n; i *= 2) s++;
assert(s==2);}
{ int n=3,p=0,s=0,h=0; double a[4]{};
p = 1;
for (int i = 1; i <= n; i++)
p *= i;
assert(p==6);}
{ int n=3,p=0,s=0,h=0; double a[4]{};
s = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
s++;
assert(s==9);}
{ int n=3,p=0,s=0,h=0; double a[4]{};
s = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
s++;
assert(s==6);}
{ int n=3,p=0,s=0,h=0; double a[4]{};
s = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n*n; j++)
s++;
assert(s==27);}
{ int n=3,p=0,s=0,h=0; double a[4]{};
s = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
for (int k = 1; k <= j; k++)
s++;
assert(s==10);}
{ int n=3,p=0,s=0,h=0; double a[4]{};
s = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i*i; j++)
for (int k = 1; k <= j; k++)
s++;
assert(s==56);}
{ int n=3,p=0,s=0,h=0; double a[4]{};
s = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i*i; j++)
if (j%i == 0)
for (int k = 1; k <= j; k++)
s++;
assert(s==25);}
{ int n=3,p=0,s=0,h=0; double a[4]{};
h = 0;
while (2*(3*h+1) <= n) h = 3*h + 1;
assert(h==1);}
}#pragma once
#include "common.hpp"
#include "graph.cpp"
template <typename T>
void create_graph(graph<T>& g)
{ cout << "number of tops: ";
int n; cin >> n;
for (int i = 1; i <= n; i++)
{ cout << "top_of_graph: ";
T x; cin >> x;
g.addTop(x);
cout << "number of ribs from " << x << ": ";
int k; cin >> k;
for (int j = 1; j <= k; j++)
{ cout << "top: ";
T y; cin >> y;
g.addRib(x, y);
}
}
}
#pragma once
#include "common.hpp"
template <typename T = int>
struct elem_cyclic
{ T inf; // информационно поле
elem_cyclic<T> *link; // адресно поле
};
template <typename T = int>
class cyclicList
{ public:
// канонично представяне
cyclicList();
~cyclicList();
cyclicList(const cyclicList&);
cyclicList& operator=(const cyclicList&);
// основни функции
bool empty() const;
void iterStart(elem_cyclic<T>* = NULL);
elem_cyclic<T>* iter();
void insert(const T&);
void toEnd(const T&);
void deleteElem(elem_cyclic<T>*, T&);
void print() const;
int length() const;
private:
elem_cyclic<T> *start,
*current;
void copyList(const cyclicList&);
void deleteList();
};
template <typename T>
cyclicList<T>::cyclicList()
{ start = current = NULL;
}
template <typename T>
cyclicList<T>::~cyclicList()
{ deleteList();
}
template <typename T>
cyclicList<T>::cyclicList(const cyclicList<T>& r)
{ copyList(r);
}
template <typename T>
cyclicList<T>& cyclicList<T>::operator=(const cyclicList<T>& r)
{ if (this != &r)
{ deleteList();
copyList(r);
}
return *this;
}
template <typename T>
void cyclicList<T>::copyList(const cyclicList& r)
{ start = current = NULL;
elem_cyclic<T> *p = r.start;
if (p)
do
{ p = p->link;
toEnd(p->inf);
} while (p != r.start);
}
template <typename T>
void cyclicList<T>::deleteList()
{ iterStart();
elem_cyclic<T> *p = iter();
while (p)
{ delete p;
p = iter();
}
start = current = NULL;
}
template <typename T>
bool cyclicList<T>::empty() const
{ return start == NULL;
}
template <typename T>
void cyclicList<T>::iterStart(elem_cyclic<T>* p)
{ if (p) current = p;
else
if (!start) current = NULL;
else current = start->link;
}
template <typename T>
elem_cyclic<T>* cyclicList<T>::iter()
{ if (!current) return NULL;
elem_cyclic<T> *p = current;
if (current == start) current = NULL;
else current = current->link;
return p;
}
template <typename T>
void cyclicList<T>::insert(const T& x)
{ elem_cyclic<T>* p = new elem_cyclic<T>;
assert(p != NULL);
p->inf = x;
if (start) p->link = start->link;
else start = p;
start->link = p;
}
template <typename T>
void cyclicList<T>::toEnd(const T& x)
{ insert(x);
start = start->link;
}
template <typename T>
void cyclicList<T>::deleteElem(elem_cyclic<T>* p, T& x)
{ x = p->inf;
if (start != start->link)
{ elem_cyclic<T> *q = start;
while (q->link != p) q = q->link;
q->link = p->link;
if (p == start) start = q;
}
else start = current = NULL;
delete p;
}
template <typename T>
void cyclicList<T>::print() const
{ elem_cyclic<T> *p = start;
if(p)
do
{ p = p->link;
cout << p->inf << " ";
} while (p != start);
cout << endl;
}
template <typename T>
int cyclicList<T>::length() const
{ int n = 0;
elem_cyclic<T> *p = start;
if(p)
do
{ p = p->link;
n++;
} while (p != start);
return n;
}
#pragma once
#include "common.hpp"
struct point
{ double x, y;
};
point p;struct coef4
{ double coef; // коефициент
int powX; // степенен показател на променливата x
int powY; // степенен показател на променливата y
int powZ; // степенен показател на променливата z
};
void examples(){int i, j;
double x, y;
int a[100];
using T=int;constexpr int size=3;{T a[size];a[0]=7;assert(a[0]==7);}p.x=1;p.y=2;coef4 c{3.5,1,2,3};assert(c.powY==2);}
#pragma once
#include "common.hpp"
#include "tree.cpp"
template <typename T>
int depth(const tree<T>& t)
{ if (t.empty()) return 0;
int n, m;
n = depth(t.leftTree());
m = depth(t.rightTree());
if (n > m) return n + 1;
return m + 1;
}
#pragma once
#include "common.hpp"
#include "graph.cpp"
#include "member.cpp"
#include "differenceSets.cpp"
template <typename T>
void DFS(const T& a, graph<T>& g, LList<T>& l)
{ l.toEnd(a);
cout << a << " ";
elem_link1<T>* p = g.point(a);
p = p->link;
while(p)
{ if(!member(p->inf, l)) DFS(p->inf, g, l);
p = p->link;
}
}
template <typename T>
void full_DFS(graph<T>& g)
{ LList<T> v = g.vertexes(),// списък с върховете на графа
l, // празен списък
h = v; // differenceSets(v, l)
while (!h.empty())
{ h.iterStart();
elem_link1<T> *p = h.iter();
DFS(p->inf, g, l);
h = differenceSets(v, l);
}
}
#pragma once
#include "common.hpp"
#include "LList1.cpp"
template <typename T>
LList<T> differenceSets(LList<T> p, LList<T> q)
{ LList<T> r; // ще съдържа резултата от разликата на p и q
p.iterStart();
q.iterStart();
elem_link1<T> *pp = p.iter(),
*qq = q.iter();
while (pp)
{ if (!member(pp->inf, r) && !member(pp->inf, q))
r.toEnd(pp->inf);
pp = pp->link;
}
return r;
}
#pragma once
#include "common.hpp"
template <typename T = int>
struct elem_link2
{ T inf;
elem_link2<T> *pred,
*succ;
};
template <typename T = int>
class DLList
{ public:
// канонично представяне
DLList();
~DLList();
DLList(const DLList&);
DLList& operator=(const DLList&);
// основни функции
bool empty() const;
void iterStart(elem_link2<T>* = NULL);
void iterEnd(elem_link2<T>* = NULL);
elem_link2<T>* iterSucc();
elem_link2<T>* iterPred();
void toEnd(const T&);
void toStart(const T&);
void deleteElem(elem_link2<T>*, T&);
void print() const;
void print_reverse() const;
int length() const;
private:
elem_link2<T> *start, // указател към началото
*end, // указател към края
*currentS,// итератор към началото
*currentE;// итератор към края
// помощни член-функции
void copyList(const DLList&);
void deleteList();
};
template <typename T>
DLList<T>::DLList()
{ start = end = currentS = currentE = NULL;
}
template <typename T>
DLList<T>::~DLList()
{ deleteList();
}
template <typename T>
DLList<T>::DLList(const DLList<T>& r)
{ copyList(r);
}
template <typename T>
DLList<T>& DLList<T>::operator=(const DLList<T>& r)
{ if (this != &r)
{ deleteList();
copyList(r);
}
return *this;
}
template <typename T>
void DLList<T>::copyList(const DLList<T>& r)
{ start = end = currentS = currentE = NULL;
elem_link2<T>* p = r.start;
while (p)
{ toEnd(p->inf);
p = p->succ;
}
}
template <typename T>
void DLList<T>::deleteList()
{ elem_link2<T>* p = start;
while (p)
{ start = start->succ;
delete p;
p = start;
}
end = NULL;
}
template <typename T>
bool DLList<T>::empty() const
{ return start == NULL;
}
template <typename T>
void DLList<T>::iterStart(elem_link2<T>* p)
{ if (p) currentS = p;
else currentS = start;
}
template <typename T>
void DLList<T>::iterEnd(elem_link2<T>* p)
{ if (p) currentE = p;
else currentE = end;
}
template <typename T>
elem_link2<T>* DLList<T>::iterSucc()
{ elem_link2<T>* p = currentS;
if (currentS) currentS = currentS->succ;
return p;
}
template <typename T>
elem_link2<T>* DLList<T>::iterPred()
{ elem_link2<T>* p = currentE;
if (currentE) currentE = currentE->pred;
return p;
}
template <typename T>
void DLList<T>::toEnd(const T& x)
{ elem_link2<T>* p = end;
end = new elem_link2<T>;
assert(end != NULL);
end->inf = x;
end->succ = NULL;
if (p) p->succ = end;
else start = end;
end->pred = p;
}
template <typename T>
void DLList<T>::toStart(const T& x)
{ elem_link2<T>* p = start;
start = new elem_link2<T>;
assert(start != NULL);
start->inf = x;
start->pred = NULL;
if (p) p->pred = start;
else end = start;
start->succ = p;
}
template <typename T>
void DLList<T>::deleteElem(elem_link2<T>* p, T& x)
{ x = p->inf;
if (start == end)
start = end = currentS = currentE = NULL;
else
if (p == start)
{ start = start->succ;
start->pred = NULL;
}
else
if (p == end)
{ end = p->pred;
end->succ = NULL;
}
else
{ p->pred->succ = p->succ;
p->succ->pred = p->pred;
}
delete p;
}
template <typename T>
void DLList<T>::print() const
{ elem_link2<T>* p = start;
while (p)
{ cout << p->inf << " ";
p = p->succ;
}
cout << endl;
}
template <typename T>
void DLList<T>::print_reverse() const
{ elem_link2<T>* p = end;
while (p)
{ cout << p->inf << " ";
p = p->pred;
}
cout << endl;
}
template <typename T>
int DLList<T>::length() const
{ int n = 0;
elem_link2<T>* p = start;
while (p)
{ n++;
p = p->succ;
}
return n;
}
#pragma once
#include "common.hpp"
#include "tree.cpp"
template <typename T>
bool equal(const tree<T>& t1, const tree<T>& t2)
{ if (t1.empty() && t2.empty()) return true;
if (t1.empty() && !t2.empty() ||
!t1.empty() && t2.empty()) return false;
if (t1.rootTree() != t2.rootTree()) return false;
return equal(t1.leftTree(), t2.leftTree()) &&
equal(t1.rightTree(), t2.rightTree());
}
#pragma once
#include "common.hpp"
#include "translate.cpp"
#include "value.cpp"
int main()
{ char s[200];
cout << "s: "; cin >> s; // въвеждане на
// аритметичния израз
// в инфиксен формат
char s1[200];
translate(s,s1); // преобразуване на низа s
// в обратен полски запис
cout << value(s1) << endl; // пресмятане и извеждане
// на стойността на израза
return 0;
}#pragma once
#include "common.hpp"
int fact(int n)
{ if (n == 0) return 1;
return n*fact(n-1);
}#pragma once
#include "stack.cpp"
int fact(int n)
{ stack<int> st; st.push(n);
int x, f = 1;
while(!st.empty())
{ st.pop(x);
if(x == 0) return f;
f = f*x;
st.push(x-1);
}
return 1; // за да се избегне предупреждението
// "not all control paths return a value"
}#pragma once
#include "common.hpp"
// Binary-file demonstrations require a seekable read/write file of trivial records.
template<class T> void swap(fstream& f,int i,int j,T&) {
T a{},b{}; f.clear();f.seekg(i*sizeof(T));f.read((char*)&a,sizeof(T));
f.seekg(j*sizeof(T));f.read((char*)&b,sizeof(T));
if(!f) throw runtime_error("Cannot read binary record");
f.seekp(i*sizeof(T));f.write((char*)&b,sizeof(T));
f.seekp(j*sizeof(T));f.write((char*)&a,sizeof(T));
if(!f) throw runtime_error("Cannot write binary record");
}
#pragma once
#include "common.hpp"
#include "LList1.cpp"
template <typename T>
LList<T> filter(bool (*pred)(T), LList<T>& L)
{ LList<T> L1;
L.iterStart();
elem_link1<T> *p = L.iter();
while (p)
{ if (pred(p->inf)) L1.toEnd(p->inf);
p = p->link;
}
return L1;
}
#pragma once
#include "common.hpp"
#include "cyclicList.cpp"
template <typename T>
cyclicList<T> filter(bool (*pred)(T), cyclicList<T>& L)
{ L.iterStart();
elem_cyclic<T> *p = L.iter();
cyclicList<T> L1;
while (p)
{ if ((*pred)(p->inf)) L1.toEnd(p->inf);
p = L.iter();
}
return L1;
}
#pragma once
#include "common.hpp"
#include "LList1.cpp"
template <typename T>
class graph
{ public:
void addTop(const T&);
void deleteTop(const T&);
void addRib(const T&, const T&);
void deleteRib(const T&, const T&);
bool top(const T&);
bool rib(const T&, const T&);
bool empty() const;
elem_link1<T>* point(const T&);
LList<T> vertexes();
void print();
private:
LList< LList<T> > g;
};
// включва a като връх на неявния граф
template <typename T>
void graph<T>::addTop(const T& a)
{ // създаване на линеен списък, съдържащ елемента a
LList<T> l;
l.toEnd(a);
// включване на върха a към графа
g.toEnd(l);
}
// изключва върха a на неявния граф
template <typename T>
void graph<T>::deleteTop(const T& a)
{ // обхожда графа с цел изтриване на всички
// ребра от произволен връх до върха a
g.iterStart();
elem_link1<LList<T> >* p = g.iter(), *r;
while(p)
{ p->inf.iterStart();
elem_link1<T>* q = p->inf.iter();
if (rib(q->inf, a)) deleteRib(q->inf, a);
p = p->link;
}
// изтриване на линейния списък, представящ
// върха a и неговите наследници
g.iterStart();
elem_link1<T>* q;
do
{ r = g.iter();
r->inf.iterStart();
q = r->inf.iter();
} while(q->inf != a); // a е връх на графа
LList<T> x;
g.deleteElem(r, x);
}
// включва ребро от върха a до върха b на неявния граф
template <typename T>
void graph<T>::addRib(const T& a, const T& b)
{ // намиране на указател към върха a на неявния граф
elem_link1<T>* q = point(a),// намира указател към върха a
* p;
// включване на върха b в списъка от наследниците на върха a
p = new elem_link1<T>;
assert(p != NULL);
p->inf = b;
p->link = q->link;
q->link = p;
}
// изключва реброто от върха a до върха b на неявния граф
template <typename T>
void graph<T>::deleteRib(const T& a, const T& b)
{ g.iterStart();
elem_link1<LList<T> > *p;
elem_link1<T> *q;
do
{ p = g.iter();
p->inf.iterStart();
q = p->inf.iter();
} while (q->inf != a);
q = q->link;
// намиране на указател към наследника b на върха a
while(q->inf != b) q = q->link;
T x;
p->inf.deleteElem(q, x);
}
// проверява дали a е връх на неявния граф
template <typename T>
bool graph<T>::top(const T& a)
{ if(g.empty()) return false;
g.iterStart();
elem_link1<LList<T> > *p = g.iter();
elem_link1<T> *q;
do
{ p->inf.iterStart();
q = p->inf.iter();
p = p->link;
} while(q->inf != a && p);
return q->inf == a;
}
// проверява дали има ребро от върха a до върха b
template <typename T>
bool graph<T>::rib(const T& a, const T& b)
{ elem_link1<T>* p = point(a); // намира указател към върха a
p = p->link;
while (p && p->inf != b) p = p->link;
return p != NULL;
}
// проверява дали неявният граф е празен
template <typename T>
bool graph<T>::empty() const
{ return g.empty();
}
// намира указател към върха a на графа
template <typename T>
elem_link1<T>* graph<T>::point(const T& a)
{ g.iterStart();
elem_link1<LList<T> > *p;
elem_link1<T> *q;
do
{ p = g.iter();
p->inf.iterStart();
q = p->inf.iter();
} while(q->inf != a);
return q;
}
// връща списък от върховете на неявния граф
template <typename T>
LList<T> graph<T>::vertexes()
{ LList<T> l;
g.iterStart();
elem_link1<LList<T> > *p = g.iter();
while(p)
{ p->inf.iterStart();
elem_link1<T>* q = p->inf.iter();
l.toEnd(q->inf);
p = p->link;
}
return l;
}
// извежда неявния граф
template <typename T>
void graph<T>::print()
{ g.iterStart();
elem_link1<LList<T> > *p = g.iter();
while (p)
{ p->inf.print();
p = p->link;
}
cout << endl;
}
#pragma once
#include "common.hpp"
#include <iostream>
#include <cassert>
#include <iomanip>
#include <fstream>
#include <cstring>
#include "LList1.cpp"
using namespace std;
struct rec
{ char* name; // фамилия на студент
unsigned num; // факултетен номер на студент
// канонично представяне на структурата
rec(const char* s = "", unsigned n = 0)
{ name = new char[strlen(s)+1];
assert(name != NULL);
strcpy(name, s);
num = n;
}
~rec()
{ delete [] name;
}
rec(const rec& r)
{ name = new char[strlen(r.name)+1];
assert(name != NULL);
strcpy(name, r.name);
num = r.num;
}
rec& operator=(const rec& r)
{ if (this != &r)
{ delete [] name;
name = new char[strlen(r.name)+1];
assert(name != NULL);
strcpy(name, r.name);
num = r.num;
}
return *this;
}
};
typedef LList<rec> list_Rec;// тип свързан списък от записи
template<>
void LList<rec>::print() const
{ elem_link1<rec>* p = start;
while (p)
{ cout << p->inf.name << " " << p->inf.num << " ";
p = p->link;
}
cout << endl;
}
class hashTable
{ public:
hashTable(unsigned = 1021);
hashTable(const hashTable&) = delete;
hashTable& operator=(const hashTable&) = delete;
~hashTable();
// хеш-функция
unsigned hash(const char*) const;
// включване на нов запис по зададени компоненти
void insert(const char*, unsigned);
// търсене на запис по указан ключ
elem_link1<rec>* find(const char*) const;
// изтриване на запис по указан ключ
void delRec(const char*);
// извеждане на хеш-таблицата
void print() const;
private:
unsigned k; // брой елементи на хеш-таблицата
list_Rec *arr; // носител на хеш-таблица
};
hashTable::hashTable(unsigned n)
{ if(n==0) throw invalid_argument("Nonzero table size required");
k = n;
arr = new list_Rec[n];
assert(arr != NULL);
}
hashTable::~hashTable()
{ delete [] arr;
}
unsigned hashTable::hash(const char* str) const
{ unsigned sum = 0;
for (unsigned i = 0; str[i]; i++)
sum += (i+1)*str[i];
return sum % k;
}
void hashTable::insert(const char* str, unsigned nu)
{ rec r(str, nu);
arr[hash(str)].toEnd(r);
}
elem_link1<rec>* hashTable::find(const char* str) const
{ arr[hash(str)].iterStart();
elem_link1<rec>* p = arr[hash(str)].iter();
while (p && strcmp(p->inf.name, str))
p = p->link;
return p;
}
void hashTable::delRec(const char* str)
{ arr[hash(str)].iterStart();
elem_link1<rec>* p = arr[hash(str)].iter();
while(p && strcmp(p->inf.name, str))
p = p->link;
if (p)
{ rec y;
arr[hash(str)].deleteElem(p, y);
}
}
void hashTable::print() const
{ for (unsigned i = 0; i < k; i++)
if (!arr[i].empty())
{ arr[i].print();
cout << endl;
}
}
// примерно изпълнение
int main()
{ ifstream f("Student_Number.txt", ios::in);
if (!f)
{ cerr << "Cannot open file Student_Number.txt!\n";
return 1;
}
std::string name;
unsigned num, k;
cout << "Дължина k на хеш-таблицата: "; cin >> k;
// създаване на празна хеш-таблица
hashTable hashObj(k);
// прехвърляне на записите на файла f
// в хеш-таблицата hashObj
while (f >> name >> num)
{ cout << setw(35) << left << name
<< setw(20) <<num << endl;
hashObj.insert(name.c_str(), num);
}
// извеждане на хеш-таблицата
hashObj.print(); cout << endl;
// търсене на записи в хеш-таблицата
//(до въвеждане на end)
elem_link1<rec>* p = NULL;
cout << "Въведете име или end за край на програмата!\n";
cin >> name;
while (cin && name != "end")
{ p = hashObj.find(name.c_str());
if (p) cout << "Записът е намерен в хеш-таблицата.\n";
else cout << " Записът не е намерен в хеш-таблицата.\n";
cout << "Въведете фамилия или end "
"за край на програмата!\n";
cin >> name;
}
f.close();
return 0;
}
#pragma once
#include "common.hpp"
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
using namespace std;
struct rec
{ char name[32]; // фамилно име
unsigned num; // факултетен номер
};
class hashTable
{ public:
// конструктор на хеш-таблицата
hashTable(unsigned = 1021);
hashTable(const hashTable&) = delete;
hashTable& operator=(const hashTable&) = delete;
// деструктор
~hashTable();
// включване на запис в хеш-таблицата
void insert(const char*, unsigned);
// търсене на запис в хеш-таблицата
rec* find(const char*);
// извеждане на хеш-таблицата
void print() const;
private:
unsigned n, // размер на хеш-таблицата
sum; // за низа "Len" sum = 1.'L'+2.'e' + 3.'n'
rec* arr; // носител на хеш-таблицата
unsigned hash(const char*); // хеш-функция
unsigned increment() const; // втора хеш-функция
bool search(const char*, unsigned &); // търсене на ключ
};
hashTable::hashTable(unsigned num)
{ if(num < 3) throw invalid_argument("Prime table size >= 3 required");
for(unsigned d=2;d<=num/d;d++) if(num%d==0) throw invalid_argument("Prime table size required");
n=num;
arr = new rec[n];
assert(arr != NULL);
for (unsigned i = 0; i < n; i++)
arr[i].name[0] = '\0';
}
hashTable::~hashTable()
{ delete [] arr;
}
unsigned hashTable::hash(const char* str)
{ sum = 0;
for (unsigned i = 0; str[i]; i++)
sum += (i+1)*str[i];
return sum % n;
}
unsigned hashTable::increment() const
{ return 1 + sum % (n-2);
}
bool hashTable::search(const char* str, unsigned &i)
{ unsigned count = 0, incr;
if (strcmp(arr[i].name, str))
{ incr = increment();
do
{ count++;
if (count == n) return false;
i = (i+incr) % n;
} while(strcmp(arr[i].name, str));
}
return true;
}
void hashTable::insert(const char* str, unsigned num)
{ if (!str || strlen(str)==0 || strlen(str)>=32) throw invalid_argument("Key must contain 1..31 bytes");
unsigned i = hash(str);
if (!search("", i))
{ cout << "Хеш-таблицата е запълнена.\n";
return;
}
strcpy(arr[i].name, str);
arr[i].num = num;
}
rec* hashTable::find(const char* str)
{ if (!str || strlen(str)==0 || strlen(str)>=32) throw invalid_argument("Key must contain 1..31 bytes");
unsigned i = hash(str);
if (search(str, i)) return arr+i;
return NULL;
}
void hashTable::print() const
{ for (unsigned i = 0; i < n; i++)
if (strcmp(arr[i].name, ""))
cout << setw(5) << i
<< setw(20) << arr[i].name
<< setw(10) << arr[i].num << endl;
else cout << setw(5) << i << endl;
cout << endl;
}
// примерно изпълнение
int main()
{ ifstream f("Student_Number.txt", ios::in);
if (!f)
{ cerr << "Cannot open file Student_Number.txt!\n";
return 1;
}
std::string name;
unsigned num, n;
cout << "Дължина n на хеш-таблицата: ";
cin >> n;
// създаване на празна хеш-таблица с n записа
hashTable studentNumberTable(n);
// прехвърляне на записите на файла f в хеш-таблицата
while(f >> name >> num)
{ cout << setw(20) << setiosflags(ios::left)
<< name << setw(10) << num << endl;
studentNumberTable.insert(name.c_str(), num);
}
// извеждане на хеш-таблицата
studentNumberTable.print(); cout << endl;
// търсене на запис в хеш-таблицата
rec* p = NULL;
cout << "Въведете фамилия или end за край на програмата!\n";
cin >> name;
while(cin && name != "end")
{ p = studentNumberTable.find(name.c_str());
if(p) cout << "Записът е намерен.\n";
else cout << "Записът не е намерен.\n";
cout << "Въведете фамилия или end "
"за край на програмата!\n";
cin >> name;
}
f.close();
return 0;
}
#pragma once
#include "common.hpp"
template <typename T>
void heapInsert(T* a, int k, int n)
{ int i, j = 2*k + 1;
while (j < n)
{ i = j;
if (j < n-1 && a[j] < a[j+1]) i = j+1;
if (a[k] < a[i])
{ swap(a[k], a[i]);
k = i; j = 2*k + 1;
}
else j = n;
}
}
template <typename T>
void heapSort(T* a, int n)
{ int i = n/2-1;
for (int j=i; j>=0; j--)
heapInsert(a, j, n);
n--;
while (n > 0)
{ swap(a[0], a[n]);
heapInsert(a, 0, n);
n--;
}
}
#pragma once
#include "common.hpp"
#include "file_helpers.hpp"
template <typename T>
void heapInsert(fstream& f, int k, int n, T& dummy)
{ int i, j = 2*k + 1;
T a, b;
while (j < n)
{ i = j;
f.seekg(j*sizeof(T));
f.read((char*)&a, sizeof(T));
if (j < n-1)
{ f.read((char*)&b, sizeof(T));
if (a < b) i = j+1;
}
f.seekg(i*sizeof(T));
f.read((char*)&b, sizeof(T));
f.seekg(k*sizeof(T));
f.read((char*)&a, sizeof(T));
if (a < b)
{ swap(f, k, i, dummy);
k = i;
j = 2*k+1;
}
else j = n;
}
}
template <typename T>
void heapSort(fstream& f, T dummy)
{ f.seekg(0, ios::end);
int n = f.tellg()/sizeof(T);
int i = n/2-1;
for (int j = i; j >= 0; j--)
heapInsert(f, j, n, dummy);
n--;
while (n > 0)
{ swap(f, 0, n, dummy);
heapInsert(f, 0, n, dummy);
n--;
}
f.close();
}
#pragma once
#include "common.hpp"
template <typename T>
void insert(T* a, int i)
{ int j = i-1;
T x = a[i];
while(j >= 0 && a[j] > x)
{ a[j+1] = a[j];
j--;
}
a[j+1] = x;
}
template <typename T>
void insertSort(T* a, int n)
{ for (int i = 1; i < n; i++)
insert(a, i);
}
#pragma once
#include "common.hpp"
template <typename T>
void insert(fstream& f, int i, T& dummy)
{ int j = i-1;
T x, a;
f.seekg(i*sizeof(T));
f.read((char*)&x, sizeof(T));
f.seekg(j*sizeof(T));
f.read((char*)&a, sizeof(T));
while(j >= 0 && a > x)
{ f.seekp((j+1)*sizeof(T)); // за яснота на алгоритъма
f.write((const char*)&a, sizeof(T));
j--;
if (j >= 0) { f.seekg(j*sizeof(T));
f.read((char*)&a, sizeof(T)); }
}
f.seekp((j+1)*sizeof(T));
f.write((const char*)&x, sizeof(T));
}
template <typename T>
void insertSort(fstream& f, T& dummy)
{ //намиране на броя на елементите на f
f.seekg(0, ios::end);
long n = f.tellg()/sizeof(T);
for (int i = 1; i < n; i++)
insert(f, i, dummy);
f.close();
}
#pragma once
#include "common.hpp"
#include "LList1.cpp"
template <typename T>
LList<T> intersectionSets(LList<T> p, LList<T> q)
{ LList<T> r; // ще съдържа резултата от сечението на p и q
p.iterStart();
q.iterStart();
elem_link1<T> *pp = p.iter(),
*qq = q.iter();
while (pp)
{ if (!member(pp->inf, r) && member(pp->inf, q))
r.toEnd(pp->inf);
pp = pp->link;
}
return r;
}
#pragma once
#include "common.hpp"
void bubbleSort(int* a, int n)
{ int i, j, x;
for(i = 0; i <= n-2; i++) // (1)
for(j = n-1; j >= i+1; j--) // (2)
if(a[j-1] > a[j]) // (3)
{ x = a[j]; // (4)
a[j] = a[j-1]; // (5)
a[j-1] = x; // (6)
}
}
int fact (int n)
{ if (n <= 1) // (1)
return 1; // (2)
else
return n*fact(n-1); // (3)
}
void example1(int n, int a[][30], int b[][30],
int c[][30])
{ int i, j, k;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
{ c[i][j] = 0;
for (k = 0; k < n; k++)
c[i][j] += a[i][k]*b[k][j];
}
}
int example2(int n)
{ int i, j, sum = 0;
for (i = 1; i < n; i++)
for (j = i+1; j <= i*i; j++)
sum++;
return sum;
}
void example3(int n)
{ int i, j, k;
for (i = 1; i < n; i++)
for (j = i+1; j <= n; j++)
for (k = 1; k <= j*j; k++)
{ // последователност от оператори
// с време за изпълнение O(1)
}
}
void example4(int n)
{ int i, j, x = 0, y = 0;
for (i = 1; i <= n; i++)
if (i%2 == 1)
{ for (j = 1; j <= n; j++) x++;
for (j = 1; j <= i; j++) y++;
}
}
void recA(int n)
{ for (int i = 1; i <= n; i++)
{ // последователност от оператори
// с време за изпълнение O(1)
}
if (n > 1) recA(n-1);
}
void recB(int n)
{ for (int i = 1; i <= n; i++)
{ // последователност от оператори
// с време за изпълнение O(1)
}
if (n > 1) recB(n/2);
}
void recC(int n)
{ // последователност от оператори
// с време за изпълнение O(1)
for (int i = 1; i <= n; i++)
if (n > 1) recC(n-1);
}
int example5(int n)
{ if (n <= 1) return 1;
else return example5(n-1) + example5(n-1);
}
int fib(int n)
{ if (n == 0) return 0; else
if (n == 1) return 1; else
return fib(n-1) + fib(n-2);
}#pragma once
#include "common.hpp"
template <typename T>
int linSearch(T x, T* a, int n)
{ if (n <= 0) return 0;
int i = 0;
while (i < n-1 && x != a[i]) i++;
if (x == a[i]) return i;
return n;
}
#pragma once
#include "common.hpp"
template <typename T>
int linSearch(fstream& f, T x)
{// намиране на броя на компонентите на f
f.seekg(0, ios::end);
long n = f.tellg()/sizeof(T);
if (n <= 0) return 0;
long i = -1; T a;
do
{ i++;
f.seekg(i*sizeof(T));
f.read((char*)&a, sizeof(T));
} while (i < n-1 && x != a);
if (x == a) return i;
return n;
}
#pragma once
#include "common.hpp"
template <typename T>
int linSearch(T x, T* a, int n)
{ a[n] = x;
int i;
for (i = 0; i < n; i++)
if (x == a[i]) break;
return i;
}
#pragma once
#include "common.hpp"
template <typename T>
int linSearch(T x, T* a, int n)
{ int i = 0; a[n] = x;
while (x != a[i]) i++;
return i;
}
#pragma once
#include "common.hpp"
template <typename T = int>
struct elem_link1
{ T inf; // информационна част
elem_link1<T>* link; // адресна част
};
template <typename T = int>
class LList
{ public:
// канонично представяне
LList();
~LList();
LList(const LList&);
LList& operator=(const LList&);
// основни функции
bool empty() const;
void iterStart(elem_link1<T>* = NULL);
elem_link1<T>* iter();
void toEnd(const T&);
void insertAfter(elem_link1<T>*, const T&);
void insertBefore(elem_link1<T>*, const T&);
void deleteAfter(elem_link1<T>*, T&);
void deleteBefore(elem_link1<T>*, T&);
void deleteElem(elem_link1<T>*, T&);
void print() const;
int length() const;
void concat(const LList&);
void reverse();
private:
elem_link1<T> *start, // указател към началото
*end, // указател към края
*current;// указател към текущ елемент
// помощни функции
void copyList(const LList&);
void deleteList();
};
template <typename T>
LList<T>::LList()
{ start = end = current = NULL;
}
template <typename T>
LList<T>::~LList()
{ deleteList();
}
template <typename T>
LList<T>::LList(const LList<T>& r)
{ copyList(r);
}
template <typename T>
LList<T>& LList<T>::operator=(const LList<T>& r)
{ if (this != &r)
{ deleteList();
copyList(r);
}
return *this;
}
template <typename T>
void LList<T>::copyList(const LList<T>& r)
{ start = end = current = NULL;
elem_link1<T> *p = r.start;
while (p)
{ toEnd(p->inf);
p = p->link;
}
}
template <typename T>
void LList<T>::deleteList()
{ elem_link1<T> *p;
while (start)
{ p = start;
start = start->link;
delete p;
}
end = current = NULL;
}
template <typename T>
void LList<T>::iterStart(elem_link1<T> *p)
{ if (p) current = p;
else current = start;
}
template <typename T>
elem_link1<T>* LList<T>::iter()
{ elem_link1<T> *p = current;
if (current) current = current->link;
return p;
}
template <typename T>
void LList<T>::toEnd(const T& x)
{ elem_link1<T>* p = end;
end = new elem_link1<T>;
assert(end != NULL);
end->inf = x;
end->link = NULL;
if (p) p->link = end;
else start = end;
}
template <typename T>
void LList<T>::insertAfter(elem_link1<T>* p, const T& x)
{ elem_link1<T> *q = new elem_link1<T>;
assert(q != NULL);
q->inf = x;
q->link = p->link;
if (p == end) end = q;
p->link = q;
}
template <typename T>
void LList<T>::insertBefore(elem_link1<T>* p, const T& x)
{ elem_link1<T>* q = new elem_link1<T>;
assert(q != NULL);
*q = *p;
if (p == end) end = q;
p->inf = x;
p->link = q;
}
template <typename T>
void LList<T>::deleteAfter(elem_link1<T>* p, T& x)
{ if (p->link)
{ elem_link1<T>* q = p->link;
x = q->inf;
p->link = q->link;
if (q == end) end = p;
delete q;
}
else
{ cout << "There is not an element after p.\n";
exit(1);
}
}
template <typename T>
void LList<T>::deleteElem(elem_link1<T>* p, T& x)
{ if (p == start)
{ x = p->inf;
if (start == end)
{ start = end = current = NULL;
}
else start = start->link;
delete p;
}
else
{ elem_link1<T>* q = start;
while (q->link != p) q = q->link;
deleteAfter(q, x);
}
}
template <typename T>
void LList<T>::deleteBefore(elem_link1<T>* p, T& x)
{ if (p != start)
{ elem_link1<T>* q = start;
while (q->link != p) q = q->link;
deleteElem(q, x);
}
else
{ cout << "There is not an element before p.\n";
exit(1);
}
}
template <typename T>
bool LList<T>::empty() const
{ return start == NULL;
}
template <typename T>
void LList<T>::print() const
{ elem_link1<T> *p = start;
while (p)
{ cout << p->inf << " ";
p = p->link;
}
cout << endl;
}
template <typename T>
int LList<T>::length() const
{ int n = 0;
elem_link1<T> *p = start;
while (p)
{ n++;
p = p->link;
}
return n;
}
template <typename T>
void LList<T>::concat(const LList<T>& r)
{ if (this == &r) { LList<T> copy(r); concat(copy); return; }
elem_link1<T> *p = r.start;
while (p)
{ toEnd(p->inf);
p = p->link;
}
}
template <typename T>
void LList<T>::reverse()
{ elem_link1<T> *p, *q, *temp;
p = start;
if (p)
{ q = NULL;
temp = start;
start = end;
end = temp;
while (p != start)
{ temp = p->link;
p->link = q;
q = p;
p = temp;
}
p->link = q;
}
}
#pragma once
#include "common.hpp"
#pragma once
#include "common.hpp"
template <typename T = int>
struct elem_link1
{ T inf; // информационна част
elem_link1<T>* link; // адресна част
};
template <typename T = int>
class LList
{ public:
// канонично представяне
LList();
~LList();
LList(const LList&);
LList& operator=(const LList&);
// основни функции
bool empty() const;
void iterStart(elem_link1<T>* = NULL);
elem_link1<T>* iter();
void toEnd(const T&);
void insertAfter(elem_link1<T>*, const T&);
void insertBefore(elem_link1<T>*, const T&);
void deleteAfter(elem_link1<T>*, T&);
void deleteBefore(elem_link1<T>*, T&);
void deleteElem(elem_link1<T>*, T&);
void print() const;
int length() const;
void concat(const LList&);
void reverse();
private:
elem_link1<T> *start, // указател към началото
*end, // указател към края
*current;// указател към текущ елемент
// помощни функции
void copyList(const LList&);
void deleteList();
};
template <typename T>
LList<T>::LList()
{ start = end = current = NULL;
}
template <typename T>
LList<T>::~LList()
{ deleteList();
}
template <typename T>
LList<T>::LList(const LList<T>& r)
{ copyList(r);
}
template <typename T>
LList<T>& LList<T>::operator=(const LList<T>& r)
{ if (this != &r)
{ deleteList();
copyList(r);
}
return *this;
}
template <typename T>
void LList<T>::copyList(const LList<T>& r)
{ current = NULL;
elem_link1<T> *p = r.start, *q;
if (r.start) { start = new elem_link1<T>;
assert(start != NULL);
end = start;
while (p)
{ end->inf = p->inf;
end->link = NULL;
p = p->link;
if (p)
{ q = end;
end = new elem_link1<T>;
assert(end != NULL);
q->link = end;
}
}
}
else
start = end = NULL;
}
template <typename T>
void LList<T>::deleteList()
{ elem_link1<T> *p;
while (start)
{ p = start;
start = start->link;
delete p;
}
end = current = NULL;
}
template <typename T>
void LList<T>::iterStart(elem_link1<T> *p)
{ if (p) current = p;
else current = start;
}
template <typename T>
elem_link1<T>* LList<T>::iter()
{ elem_link1<T> *p = current;
if (current) current = current->link;
return p;
}
template <typename T>
void LList<T>::toEnd(const T& x)
{ elem_link1<T>* p = end;
end = new elem_link1<T>;
assert(end != NULL);
end->inf = x;
end->link = NULL;
if (p) p->link = end;
else start = end;
}
template <typename T>
void LList<T>::insertAfter(elem_link1<T>* p, const T& x)
{ elem_link1<T> *q = new elem_link1<T>;
assert(q != NULL);
q->inf = x;
q->link = p->link;
if (p == end) end = q;
p->link = q;
}
template <typename T>
void LList<T>::insertBefore(elem_link1<T>* p, const T& x)
{ elem_link1<T>* q = new elem_link1<T>;
assert(q != NULL);
*q = *p;
if (p == end) end = q;
p->inf = x;
p->link = q;
}
template <typename T>
void LList<T>::deleteAfter(elem_link1<T>* p, T& x)
{ if (p->link)
{ elem_link1<T>* q = p->link;
x = q->inf;
p->link = q->link;
if (q == end) end = p;
delete q;
}
else
{ cout << "There is not an element after p.\n";
exit(1);
}
}
template <typename T>
void LList<T>::deleteElem(elem_link1<T>* p, T& x)
{ if (p == start)
{ x = p->inf;
if (start == end)
{ start = end = current = NULL;
}
else start = start->link;
delete p;
}
else
{ elem_link1<T>* q = start;
while (q->link != p) q = q->link;
deleteAfter(q, x);
}
}
template <typename T>
void LList<T>::deleteBefore(elem_link1<T>* p, T& x)
{ if (p != start)
{ elem_link1<T>* q = start;
while (q->link != p) q = q->link;
deleteElem(q, x);
}
else
{ cout << "There is not an element before p.\n";
exit(1);
}
}
template <typename T>
bool LList<T>::empty() const
{ return start == NULL;
}
template <typename T>
void LList<T>::print() const
{ elem_link1<T> *p = start;
while (p)
{ cout << p->inf << " ";
p = p->link;
}
cout << endl;
}
template <typename T>
int LList<T>::length() const
{ int n = 0;
elem_link1<T> *p = start;
while (p)
{ n++;
p = p->link;
}
return n;
}
template <typename T>
void LList<T>::concat(const LList<T>& r)
{ if (this == &r) { LList<T> copy(r); concat(copy); return; }
elem_link1<T> *p = r.start;
while (p)
{ toEnd(p->inf);
p = p->link;
}
}
template <typename T>
void LList<T>::reverse()
{ LList<T> r;
iterStart();
elem_link1<T>* p = iter();
if (p)
{ r.toEnd(p->inf);
p = p->link;
while (p)
{ r.insertBefore(r.start, p->inf);
p = p->link;
}
}
*this = r;
}
#pragma once
#include "common.hpp"
#include "LList1.cpp"
template <typename T>
LList<T> map(T (*f)(T), LList<T>& L)
{ L.iterStart();
elem_link1<T> *p = L.iter();
LList<T> L1;
while (p)
{ L1.toEnd(f(p->inf));
p = p->link;
}
return L1;
}
#pragma once
#include "common.hpp"
#include "cyclicList.cpp"
template <typename T>
cyclicList<T> map(T (*f)(T), cyclicList<T>& L)
{ L.iterStart();
elem_cyclic<T>* p = L.iter();
cyclicList<T> L1;
while (p)
{ L1.toEnd((*f)(p->inf)); // или L1.toEnd(f(p->inf));
p = L.iter();
}
return L1;
}
#pragma once
#include "common.hpp"
#include "tree.cpp"
template <typename T>
tree<T> map(T (*f)(T), const tree<T>& t)
{ tree<T> t1;
if (!t.empty())
t1.create3(f(t.rootTree()), map(f, t.leftTree()),
map(f, t.rightTree()));
return t1;
}
#pragma once
#include "common.hpp"
#include "LList1.cpp"
template <typename T>
bool member(const T& x, LList<T>& l)
{ l.iterStart();
elem_link1<T> *p = l.iter();
while (p && p->inf != x) p = p->link;
return p != NULL;
}
#pragma once
#include "common.hpp"
#include "tree.cpp"
template <typename T>
bool member(const T& a, const tree<T>& t)
{ if (t.empty()) return false;
if (a == t.rootTree()) return true;
return member(a, t.leftTree()) || member(a, t.rightTree());
}
#pragma once
#include "common.hpp"
template <typename T>
void merge(T* a, int n, T* b, int m, T *c)
{ int i = 0, j = 0, k = -1;
while (i < n && j < m)
if (a[i] < b[j])
{ k++;
c[k] = a[i];
i++;
}
else
{ k++;
c[k] = b[j];
j++;
}
if (i == n)
while (j < m)
{ k++;
c[k] = b[j];
j++;
}
else
while (i < n)
{ k++;
c[k] = a[i];
i++;
}
}
#pragma once
#include "common.hpp"
template <typename T>
void merge(fstream& f, fstream& g, fstream& h, T& dummy)
{ int n, m; T a, b;
f.seekg(0, ios::end);
n = f.tellg()/sizeof(T);
g.seekg(0, ios::end);
m = g.tellg()/sizeof(T);
int i = 0, j = 0;
while (i < n && j < m)
{ f.seekg(i*sizeof(T));
f.read((char*)&a, sizeof(T));
g.seekg(j*sizeof(T));
g.read((char*)&b, sizeof(T));
if (a < b)
{ h.write((const char*)&a, sizeof(T));
i++;
}
else
{ h.write((const char*)&b, sizeof(T));
j++;
}
}
while (j < m)
{ g.seekg(j*sizeof(T));
g.read((char*)&b, sizeof(T));
h.write((const char*)&b, sizeof(T));
j++;
}
while (i < n)
{ f.seekg(i*sizeof(T));
f.read((char*)&a, sizeof(T));
h.write((const char*)&a, sizeof(T));
i++;
}
f.close();
g.close();
h.close();
}
#pragma once
#include "common.hpp"
#include "LList1.cpp"
template <typename T>
LList<T> mergeLists(LList<T> L1, LList<T> L2)
{ LList<T> L; // празен списък, който ще съдържа
// резултата от сливането
// установяване на указател p към първия елемент на списъка L1
// установяване на указател q към първия елемент на списъка L2
L1.iterStart();
L2.iterStart();
elem_link1<T> *p = L1.iter(),
*q = L2.iter();
// докато и двата списъка L1 и L2 не са празни
// се обхождат елементите им, сравняват се сочените
// от указателите p и q елементи и по-малкият елемент
// се записва в списъка L
while (p && q)
if (p->inf < q->inf)
{ L.toEnd(p->inf);
p = L1.iter();
}
else
{ L.toEnd(q->inf);
q = L2.iter();
}
// след изчерпване на елементите на единия списък,
// елементите на другия се прекопирват в списъка L
if (q)
while (q)
{ L.toEnd(q->inf);
q = L2.iter();
}
else
while (p)
{ L.toEnd(p->inf);
p = L1.iter();
}
return L;
}
#pragma once
#include "common.hpp"
#include "queue_link.cpp"
template <typename T>
queue<T> merge(queue<T> p, queue<T> q, const T& dummy)
{ p.push(dummy); // включване на dummy в опашката p
q.push(dummy); // включване на dummy в опашката q
queue<T> r; // r ще съдържа резултата
T x, y;
p.pop(x);
q.pop(y);
while (!p.empty() && !q.empty())
if (x < y)
{ r.push(x);
p.pop(x);
}
else
{ r.push(y);
q.pop(y);
}
if (!p.empty()) // опашката q е празна
do
{ r.push(x);
p.pop(x);
} while (x != dummy);
else // опашката p е празна
do
{ r.push(y);
q.pop(y);
} while (y != dummy);
return r;
}
#pragma once
#include "common.hpp"
#include "LList1.cpp"
#include "mergeLists.cpp"
template <typename T>
void mergeSort(LList<T>& L)
{ LList<T> L1, L2;
L.iterStart();
elem_link1<T> *p = L.iter();
if (!p || p->link == NULL) return;
while (p)
{ L1.toEnd(p->inf);
p = p->link;
if (p)
{ L2.toEnd(p->inf);
p = p->link;
}
}
mergeSort(L1);
mergeSort(L2);
L = mergeLists(L1, L2);
}
#pragma once
#include "common.hpp"
#include "merge_array.cpp"
template <typename T>
void mergeSort(T* a, int n)
{ if (n < 2) return;
int nLeft = n/2,
nRight = n - nLeft;
mergeSort(a, nLeft);
mergeSort(a + nLeft, nRight);
T* p = new T[n];
merge(a, nLeft, a + nLeft, nRight, p);
for (int i = 0; i < n; i++)
a[i] = p[i];
delete [] p;
}
#pragma once
#include "common.hpp"
#include "graph.cpp"
#include "member.cpp"
#include "way.cpp"
bool flag = false;
int minlen = INT_MAX;
template <typename T>
void minway(const T& a, const T& b, graph<T>& g,
LList<T>& l, LList<T>& minPath)
{ l.toEnd(a);
if (a == b)
{ flag = true;
int len = l.length();
if (len < minlen)
{ minlen = len;
minPath = l;
}
}
else
{ elem_link1<T>* q = g.point(a);
q = q->link;
while (q)
{ if (!member(q->inf, l))
{ minway(q->inf, b, g, l, minPath);
deleteLast(l); // връщане назад
}
q = q->link;
}
}
}
#pragma once
#include "common.hpp"
#include "graph.cpp"
#include "queue_link.cpp"
#include "DLList.cpp"
template <typename T>
bool member(const T& x, DLList<T>& l)
{ l.iterStart();
elem_link2<T> *p = l.iterSucc();
while (p && p->inf != x) p = p->succ;;
return p != NULL;
}
template <typename T>
DLList<T> restore(DLList<T>& l, DLList<T>& p)
{ DLList<T> temp;
l.iterEnd();
elem_link2<T> *ptr1 = l.iterPred();
p.iterEnd();
elem_link2<T> *ptr2 = p.iterPred();
temp.toEnd(ptr1->inf);
while(ptr1 != NULL)
{ T x = ptr2->inf;
do
{ ptr1 = ptr1->pred;
ptr2 = ptr2->pred;
} while (ptr1 && ptr1->inf != x);
if (ptr1) temp.toStart(ptr1->inf);
}
return temp;
}
bool flag = false;
template <typename T>
void minway_bfs(const T& a, const T& b, graph<T>& g,
DLList<T>& l)
{ queue<T> q; q.push(a);
l.toEnd(a);
DLList<T> p;
p.toEnd(a);
if (a == b)
{ flag = true;
return;
}
while (!q.empty())
{ T x; q.pop(x);
elem_link1<T>* ptr = g.point(x);
ptr = ptr->link;
while (ptr)
{ if (!member(ptr->inf, l))
{ q.push(ptr->inf);
l.toEnd(ptr->inf);
p.toEnd(x);
if (ptr->inf == b)
{ flag = true;
l = restore(l, p);
return;
}
}
ptr = ptr->link;
}
}
}
#pragma once
#include "queue_link.cpp"
// Program Zad7.cpp
#include <iostream>
#include <iomanip>
#include <cassert>
using namespace std;
#include "queue_link.cpp"
#include "sortQueue.cpp"
#include "mergeQueues.cpp"
struct people
{ char name[32];
int age;
bool operator<(const people& p) const
{ return age < p.age;
}
bool operator!=(const people& p) const
{ return age != p.age;
}
};
typedef queue<people> pqueue;
template<>
void queue<people>::print()
{ people x;
while (!empty())
{ pop(x);
cout << setw(35) << x.name << setw(15) << x.age << endl;
}
}
#pragma once
#include "common.hpp"
#include "LList1.cpp"
struct monomial
{ double coefficient; // коефициент
int power; // степен
};
typedef LList<monomial> polynomial;
void create(polynomial& p)
{ char flag;
do
{ monomial mono;
cout << "coefficient: "; cin >> mono.coefficient;
cout << "power: "; cin >> mono.power;
p.toEnd(mono);
cout << "Input y/n: ";
cin >> flag;
} while (flag == 'y');
}
template<>
void LList<monomial>::print() const
{ elem_link1<monomial> *p = start;
while (p)
{ if (p->inf.coefficient > 0) cout << " +";
else cout << " ";
cout << p->inf.coefficient << "x^" << p->inf.power;
p = p->link;
}
cout << endl;
}
void addPolynomials(polynomial p, polynomial q,
polynomial& r)
{ p.iterStart();
q.iterStart();
elem_link1<monomial> *pp = p.iter(),
*qq = q.iter();
while (pp && qq)
if (pp->inf.power > qq->inf.power)
{ r.toEnd(pp->inf);
pp = pp->link;
}
else
if (qq->inf.power > pp->inf.power)
{ r.toEnd(qq->inf);
qq = qq->link;
}
else
{ monomial mono;
mono.power = pp->inf.power;
mono.coefficient = pp->inf.coefficient +
qq->inf.coefficient;
pp = pp->link;
qq = qq->link;
if (mono.coefficient != 0) r.toEnd(mono);
}
while (qq)
{ r.toEnd(qq->inf);
qq = qq->link;
}
while (pp)
{ r.toEnd(pp->inf);
pp = pp->link;
}
}
void multPolynomialMonomial(polynomial p, monomial q,
polynomial& r)
{ p.iterStart();
elem_link1<monomial> *pp = p.iter();
while (pp)
{ monomial mono;
mono.power = pp->inf.power + q.power;
mono.coefficient = pp->inf.coefficient *
q.coefficient;
pp = pp->link;
if (mono.coefficient != 0) r.toEnd(mono);
}
}
void multPolynomials(polynomial p, polynomial q,
polynomial& r)
{ r = polynomial();
if (p.empty() || q.empty()) return;
int n = p.length(),
m = q.length();
if (n <= m)
{ p.iterStart();
elem_link1<monomial> *pp = p.iter();
monomial mono = pp->inf;
pp = pp->link;
multPolynomialMonomial(q, mono, r);
while (pp)
{ mono = pp->inf;
polynomial s, r1;
multPolynomialMonomial(q, mono, s);
addPolynomials(r, s, r1);
r = r1;
pp = pp->link;
}
}
else
{ q.iterStart();
elem_link1<monomial> *pp = q.iter();
monomial mono = pp->inf;
pp = pp->link;
multPolynomialMonomial(p, mono, r);
while (pp)
{ mono = pp->inf;
polynomial s, r1;
multPolynomialMonomial(p, mono, s);
addPolynomials(r, s, r1);
r = r1;
pp = pp->link;
}
}
}
#pragma once
#include "common.hpp"
template <typename T>
void qSort(T* a, int n)
{ if (n < 2) return;
int i = 0, j = n-1;
T x = a[j/2], y;
do
{ while (a[i] < x) i++;
while (a[j] > x) j--;
if (i < j)
{ y = a[i]; a[i] = a[j]; a[j] = y;
i++; j--;
}
else
if (i==j)
{ i++;
j--;
}
} while (i <= j);
if (j > 0) qSort(a, j+1);
if (i < n-1) qSort(a+i, n-i);
}
#pragma once
#include "common.hpp"
#include "file_helpers.hpp"
template <typename T>
void qSort1(fstream& f, int m, int n, T& dummy)
{ T x, a, b;
int i = m, j = n;
// намиране на оста x
f.seekg((i+j)/2*sizeof(T));
f.read((char*)&x, sizeof(T));
do
{ f.seekg(i*sizeof(T));
f.read((char*)&a, sizeof(T));
while (a < x)
{ i++;
f.read((char*)&a, sizeof(T));
}
f.seekg(j*sizeof(T));
f.read((char*)&b, sizeof(T));
while (b > x)
{ j--;
f.seekg(j*sizeof(T));
f.read((char*)&b, sizeof(T));
}
if (i < j)
{ swap(f, i, j, dummy);
i++; j--;
}
else
if (i == j)
{ i++;
j--;
}
} while (i <= j);
if (j > m) qSort1(f, m, j, dummy);
if (i < n) qSort1(f, i, n, dummy);
}
template <typename T>
void qSort(fstream& f, T& dummy)
{ f.seekg(0, ios::end);
int n = f.tellg()/sizeof(T);
if (n > 1) qSort1(f, 0, n-1, dummy);
f.close();
}
#pragma once
#include "common.hpp"
#include "stack.cpp"
struct rec
{ int left, // индекс, задаващ началото на масива
right; // индекс, задаващ края на масива,
// който ще се сортира
};
template <typename T>
void qsort(T* a, int n)
{ if (n < 2) return;
// създаване на празен стек
stack<rec> st;
int l, r; // помощни променливи
// създаване на командата "сортирай цялата редица"
rec r1 = {0, n-1};
// включване на командата в стека st
st.push(r1);
// докато стекът с команди не е празен,
// се изпълняват командите от стека
while(!st.empty())
{ st.pop(r1);
int i = r1.left, j = r1.right;
T x = a[(i+j)/2], y;
// запазване на границите на частта от масива,
// която ще се сортира
l = i;
r = j;
do
{ while (a[i] < x) i++;
while (a[j] > x) j--;
if (i < j)
{ y = a[i]; a[i] = a[j]; a[j] = y;
i++; j--;
}
else
if (i==j)
{ i++;
j--;
}
} while (i <= j);
// конструиране и добавяне на команда за сортиране в стека
if (j > l)
{ rec r1 = {l, j}; st.push(r1);
}
if (i < r)
{ rec r1 = {i, r}; st.push(r1);
}
}
}
#pragma once
#include "common.hpp"
#include <iostream>
#include <cassert>
#include "stack.cpp"
using namespace std;
// шаблон на структура, задаваща фрагмент за сортиране
template <typename T>
struct rec
{ T* arr; // адрес на началото на масива
int len; // дължина на масива, който ще се сортира
};
template <typename T>
void qsort(T* a, int n)
{ if(n < 2) return;
// създаване на празен стек
stack< rec<T> > st;
// създаване на командата "сортирай цялата редица"
rec<T> r1 = {a, n};
// включване на командата в стека st
st.push(r1);
// докато стекът с команди не е празен,
// се изпълняват командите, записани в него
while(!st.empty())
{ // изключване на команда от стека st
st.pop(r1);
// намиране на началото и дължината на масива, който
// ще се сортира по метода на бързото сортиране
a = r1.arr, n = r1.len;
// намиране на оста x
int i = 0, j = n-1;
T x = a[(i+j)/2], y;
// разделяне на редицата на две подредици спрямо x
do
{ while (a[i] < x) i++;
while (a[j] > x) j--;
if (i < j)
{ y = a[i]; a[i] = a[j]; a[j] = y;
i++; j--;
}
else
if (i==j)
{ i++;
j--;
}
} while (i <= j);
// конструиране и включване на команда
// за сортиране в стека
if (j > 0)
{ rec<T> r1 = {a, j+1};
st.push(r1);
}
// конструиране и включване на команда за сортиране в стека
if (i < n-1)
{ rec<T> r1 = {a+i, n-i};
st.push(r1);
}
} // край на while
}
int main()
{ int a[100];
int n; cout << "n= "; cin >> n;
if(!cin || n<0 || n>100) throw std::invalid_argument("n must be 0..100");
for (int i = 0; i < n; i++)
cin >> a[i];
qsort(a, n);
for (int i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;
return 0;
}
#pragma once
#include "common.hpp"
#include <iostream>
#include <cassert>
using namespace std;
#include "queue_s.cpp"
int main()
{ queue<> q; // създава празна опашка q
// от тип int с максимален
// размер MAXSIZE
for (int i = 1; i <= 10; i++) // включва в q целите числа
q.push(i); // от 1 до 10
q.print(); // извежда опашката q
queue<char> p(26); // създава празна опашка от
// символи p с максимален
// размер 26
for (char c = 'a'; c <= 'z'; c++) // запълва p с малките
p.push(c); // латински букви
p.print(); // извежда опашката p
return 0; // извиква деструктора на
// класа за разрушаване на
// опашките p и q
}#pragma once
#include "common.hpp"
#include "LList1.cpp"
template <typename T = int>
class queue : public LList<T>
{ public:
// канонично представяне
queue();
~queue();
queue(const queue&);
queue& operator=(const queue&);
// основни функции
bool empty() const;
void push(T const&);
void pop(T&);
void head(T&);
void print();
};
template <typename T>
queue<T>::queue() : LList<T>()
{}
template <typename T>
queue<T>::~queue()
{}
template <typename T>
queue<T>::queue(const queue<T>& r) : LList<T>(r)
{}
template <typename T>
queue<T>& queue<T>::operator=(const queue<T>& r)
{ if (this != &r)
{ LList<T>::operator=(r);
}
return *this;
}
template <typename T>
bool queue<T>::empty() const
{ return LList<T>::empty();
}
template <typename T>
void queue<T>::push(T const& x)
{ LList<T>::toEnd(x);
}
template <typename T>
void queue<T>::pop(T& x)
{ if (!empty())
{ this->iterStart();
elem_link1<T>* p = this->iter();
this->deleteElem(p, x);
}
else
{ cout << "The queue is empty.\n";
exit(1);
}
}
template <typename T>
void queue<T>::head(T& x)
{ if (!empty())
{ this->iterStart();
elem_link1<T>* p = this->iter();
x = p->inf;
}
else
{ cout << "The queue is empty.\n";
exit(1);
}
}
template <typename T>
void queue<T>::print()
{ LList<T>::print();
}
#pragma once
#include "common.hpp"
template <typename T = int>
struct elem_q
{ T inf; // информационна част
elem_q<T>* link; // адресна част
};
template <typename T = int>
class queue
{ public:
// канонично представяне
queue();
~queue();
queue(const queue&);
queue& operator=(const queue&);
// основни функции
bool empty() const;
void push(const T&);
void pop(T&);
void head(T&) const;
void print();
int length();
private:
elem_q<T> *front, // указател към началото
*rear; // указател към края
// помощни функции
void copyQueue(const queue&);
void deleteQueue();
};
// канонично представяне
template <typename T>
queue<T>::queue()
{ front = rear = NULL;
}
template <typename T>
queue<T>::~queue()
{ deleteQueue();
}
template <typename T>
queue<T>::queue(const queue<T>& r)
{ copyQueue(r);
}
template <typename T>
queue<T>& queue<T>::operator=(const queue<T>& r)
{ if (this != &r)
{ deleteQueue();
copyQueue(r);
}
return *this;
}
// помощна член-функция, която копира r в неявната опашка
template <typename T>
void queue<T>::copyQueue(const queue<T>& r)
{ front = rear = NULL;
elem_q<T> *p = r.front;
while (p)
{ push(p->inf);
p = p->link;
}
}
// помощна член-функция, която изтрива неявната опашка
template <typename T>
void queue<T>::deleteQueue()
{ T x;
while (!empty())
pop(x);
}
// проверява дали неявната опашка е празна
template <typename T>
bool queue<T>::empty() const
{ return rear == NULL;
}
// включва x в неявната опашка
template <typename T>
void queue<T>::push(const T& x)
{ elem_q<T> *p = new elem_q<T>;
assert(p != NULL);
p->inf = x;
p->link = NULL;
if (rear) rear->link = p;
else front = p;
rear = p;
}
// изключва елемент от неявната опашка, ако
// последната не е празна и го записва в x
template <typename T>
void queue<T>::pop(T& x)
{ if (empty())
{ cout << "The queue is empty.\n";
exit(1);
}
else
{ elem_q<T> *p = front;
x = p->inf;
if (p == rear)
{ rear = NULL;
front = NULL;
}
else front = p->link;
delete p;
}
}
// намира главата на неявната опашка, ако последната не
// е празна, и я записва във формалния параметър x
template <typename T>
void queue<T>::head(T& x) const
{ if (empty())
{ cout << "The queue is empty.\n";
exit(1);
}
else
x = front->inf;
}
// извежда на екрана елементите на
// неявната опашка като я разрушава
template <typename T>
void queue<T>::print()
{ T x;
while (!empty())
{ pop(x);
cout << x << " ";
}
cout << endl;
}
// намира броя на елементите на
// неявната опашка като я разрушава
template <typename T>
int queue<T>::length()
{ T x; int n = 0;
while (!empty())
{ pop(x);
n++;
}
return n;
}
#pragma once
#include "common.hpp"
const int MAXSIZE = 20;
template <typename T = int>
class queue
{ public:
// канонично представяне
queue(int = MAXSIZE);
~queue();
queue(const queue&);
queue& operator=(const queue&);
// основни функции
bool empty() const;
bool full() const;
void push(const T&);
void pop(T&);
void head(T&) const;
void print();
private:
int front, // указател към началото на опашка
rear, // указател след края на опашка
queue_size, // максимален размер на опашка
queue_len; // текущ размер на опашка
T *arr; // носител на опашката
// помощни функции
void copyQueue(const queue&);
void deleteQueue();
};
// канонично представяне
template <typename T>
queue<T>::queue(int size)
{ if (size <= 0) queue_size = MAXSIZE;
else queue_size = size;
arr = new T[queue_size]{};
assert(arr != NULL);
front = 0;
rear = 0;
queue_len = 0;
}
template <typename T>
queue<T>::~queue()
{ deleteQueue();
}
template <typename T>
queue<T>::queue(const queue<T>& r)
{ copyQueue(r);
}
template <typename T>
queue<T>& queue<T>::operator=(const queue<T>& r)
{ if (this != &r)
{ deleteQueue();
copyQueue(r);
}
return *this;
}
// помощна член-функция, която копира r в неявната опашка
template <typename T>
void queue<T>::copyQueue(const queue<T>& r)
{ queue_size = r.queue_size;
arr = new T[queue_size]{};
assert(arr != NULL);
for (int i = 0; i < queue_size; i++)
arr[i] = r.arr[i];
queue_len = r.queue_len;
front = r.front;
rear = r.rear;
}
// помощна член-функция, която изтрива неявната опашка
template <typename T>
void queue<T>::deleteQueue()
{ delete [] arr;
}
// проверява дали неявната опашка е празна
template <typename T>
bool queue<T>::empty() const
{ return queue_len == 0;
}
// проверява дали неявната опашка е пълна
template <typename T>
bool queue<T>::full() const
{ return queue_len == queue_size;
}
// включва x в неявната опашка, ако последната не е пълна
template <typename T>
void queue<T>::push(const T& x)
{ if (!full())
{ arr[rear] = x;
queue_len++;
rear++;
rear = rear % queue_size;
}
else
{ cout << "The queue is full.\n";
exit(1);
}
}
// изключва елемент от неявната опашка, ако
// последната не е празна и го записва в x
template <typename T>
void queue<T>::pop(T& x)
{ if (!empty())
{ x = arr[front];
queue_len--;
front++;
front = front % queue_size;
}
else
{ cout << "The queue is empty.\n";
exit(1);
}
}
// намира главата на неявната опашка, ако последната не
// е празна, и я записва във формалния параметър x
template <typename T>
void queue<T>::head(T& x) const
{ if (!empty())
x = arr[front];
else
{ cout << "The queue is empty.\n";
exit(1);
}
}
// извежда на екрана елементите на
// неявната опашка като я разрушава
template <typename T>
void queue<T>::print()
{ T x;
while (!empty())
{ pop(x);
cout << x << " ";
}
cout << endl;
}
#pragma once
#include "common.hpp"
#include "file_helpers.hpp"
template <typename T>
void selectSort(fstream& f, T& dummy)
{ int i, j, k;
T min, a, b;
// намиране на броя на елементите на f
f.seekg(0, ios::end);
long n = f.tellg()/sizeof(T);
for (i = 0; i < n-1; i++)
{ k = i; f.seekg(k*sizeof(T));
f.read((char*)&min,sizeof(T));
for (j = i+1; j < n; j++)
{ f.seekg(j*sizeof(T));
f.read((char*)&a, sizeof(T));
if (a < min)
{ k = j;
min = a;
}
}
f.seekg(i*sizeof(T)); f.read((char*)&a, sizeof(T));
f.seekg(k*sizeof(T)); f.read((char*)&b, sizeof(T));
f.seekp(k*sizeof(T)); f.write((const char*)&a, sizeof(T));
f.seekp(i*sizeof(T)); f.write((const char*)&b, sizeof(T));
}
f.close();
}
#pragma once
#include "common.hpp"
template <typename T>
void selectSort(T* a, int n)
{ int i, j, k;
T min;
for (i = 0; i < n-1; i++)
{ k = i; min = a[k];
for (j = i+1; j < n; j++)
if (a[j] < min)
{ k = j;
min = a[k];
}
a[k] = a[i]; a[i] = min;
}
}
#pragma once
#include "common.hpp"
template <typename T>
void shakerSort(T* a, int n)
{ int i, k;
int left = 0, right = n-1;
while (right-left > 0)
{ k = 0;
for (i = left; i < right; i++)
if (a[i] > a[i+1])
{ swap(a[i], a[i+1]);
k = i;
}
right = k;
k = n-1;
for (i = right; i > left; i--)
if (a[i-1] > a[i])
{ swap(a[i-1], a[i]);
k = i;
}
left = k;
}
}
#pragma once
#include "common.hpp"
#include "file_helpers.hpp"
template <typename T>
void shakerSort(fstream& f, T& dummy)
{ int i, k;
// намиране на броя на елементите на файла f
f.seekg(0, ios::end);
int n = f.tellg()/sizeof(T);
int left = 0, right = n-1;
T a, b;
while (right-left > 0)
{ k = 0;
for (i = left; i < right; i++)
{ f.seekg(i*sizeof(T));
f.read((char*)&a, sizeof(T));
f.read((char*)&b, sizeof(T));
if (b < a)
{ swap(f, i, i+1, dummy);
k = i;
}
}
right = k;
k = n-1;
for (i = right; i > left; i--)
{ f.seekg((i-1)*sizeof(T));
f.read((char*)&a, sizeof(T));
f.read((char*)&b, sizeof(T));
if (b < a)
{ swap(f, i-1, i, dummy);
k = i;
}
}
left = k;
}
f.close();
}
#pragma once
#include "common.hpp"
template <typename T>
void ShellSort(T* a, int n)
{ int h = 0, i, j;
T x;
while (2*(3*h +1) <= n)
h = 3*h+1;
while (h > 0)
{ for (i = h; i < n; i++)
{ x = a[i];
for (j = i-h; j >= 0; j = j-h)
if (x < a[j]) a[j+h] = a[j];
else break;
a[j+h] = x;
}
h = h/3;
}
}
#pragma once
#include "common.hpp"
template <typename T>
void ShellSort(fstream& f, T& dummy)
{ int h = 0, i, j;
T x, a;
// намиране на броя на елементите на файла f
f.seekg(0, ios::end);
long n = f.tellg()/sizeof(T);
// намиране на стъпката h
while (2*(3*h +1) <= n)
h = 3*h+1;
while (h > 0)
{ for (i = h; i < n; i++)
{ f.seekg(i*sizeof(T));
f.read((char*)&x, sizeof(T));
for (j = i-h; j >= 0; j = j-h)
{ f.seekg(j*sizeof(T));
f.read((char*)&a, sizeof(T));
if (x < a)
{ f.seekp((j+h)*sizeof(T));
f.write((const char*)&a, sizeof(T));
}
else break;
}
f.seekp((j+h)*sizeof(T));
f.write((const char*)&x, sizeof(T));
}
h = h/3;
}
f.close();
}
#pragma once
#include "common.hpp"
#include "DLList.cpp"
typedef DLList<int> intList;
intList sort(intList& L)
{ if (L.empty()) return intList();
L.iterStart();
elem_link2<int>* p = L.iterSucc();
L.iterEnd();
elem_link2<int>* q = L.iterPred();
intList L1;
while (p != q)
if (p->inf <= q->inf)
{ L1.toEnd(p->inf);
p = L.iterSucc();
}
else
{ L1.toEnd(q->inf);
q = L.iterPred();
}
L1.toEnd(p->inf);
return L1;
}
#pragma once
#include "common.hpp"
#include "LList1.cpp"
template <typename T>
void sortList(LList<T>& L)
{ if (L.empty()) return;
// линейният списък не е празен
elem_link1<T> *mp, // указател към минимален елемент
*p; // указател към текущ елемент
L.iterStart(); p = L.iter();
while (p->link)
{ T min = p->inf;
mp = p;
elem_link1<T> *q = p->link;
while (q)
{ if (q->inf < min)
{ mp = q;
min = q->inf;
}
q = q->link;
}
min = mp->inf;
mp->inf = p->inf;
p->inf = min;
p = p->link;
}
}
#pragma once
#include "common.hpp"
#include "queue_link.cpp"
template <typename T>
void minqueue(queue<T> q, T& min, queue<T>& newq)
{ T x;
q.pop(min);
while (!q.empty())
{ q.pop(x);
if (x < min)
{ newq.push(min);
min = x;
}
else newq.push(x);
}
}
template <typename T>
void sortQueue(queue<T> q, queue<T>& newq)
{ while (!q.empty())
{ T min;
queue<T> q1;
minqueue(q, min, q1); // опашката q не е празна,
// а опашката q1 е празна
newq.push(min);
q = q1;
}
}
#pragma once
#include "common.hpp"
template <typename T>
struct elem
{ T inf; // информационна част
elem* link; // адресна част
};
template <typename T = int>
class stack
{ public:
// канонично представяне
stack();
~stack();
stack(const stack&);
stack& operator=(const stack&);
// основни операции
bool empty() const;
void push(const T&);
void pop(T&);
void top(T&) const;
void print();
int length();
private:
elem<T> *start; // указател към върха на стека
void copyStack(const stack&);
void delStack();
};
// канонично представяне на шаблона на класа
template <typename T>
stack<T>::stack()
{ start = NULL;
}
template <typename T>
stack<T>::~stack()
{ delStack();
}
template <typename T>
stack<T>::stack(const stack<T>& r)
{ copyStack(r);
}
template <typename T>
stack<T>& stack<T>::operator=(const stack<T>& r)
{ if (this != &r)
{ delStack();
copyStack(r);
}
return *this;
}
// помощна член-функция, която копира r в неявния стек
template <typename T>
void stack<T>::copyStack(const stack<T>& r)
{ if (r.start)
{ elem<T> *p = r.start, *q = NULL, *s = NULL;
start = new elem<T>;
assert(start != NULL);
start->inf = p->inf;
start->link = q;
q = start;
p = p->link;
while (p)
{ s = new elem<T>;
assert(s != NULL);
s->inf = p->inf;
q->link = s;
q = s;
p = p->link;
}
q->link = NULL;
}
else start = NULL;
}
// помощна член-функция, която изтрива неявния стек
template <typename T>
void stack<T>::delStack()
{ elem<T> *p;
while (start)
{ p = start;
start = start->link;
delete p;
}
}
// проверява дали неявният стек е празен
template <typename T>
bool stack<T>::empty() const
{ return start == NULL;
}
// включва s в неявния стек
template <typename T>
void stack<T>::push(const T& s)
{ elem<T>* p = start;
start = new elem<T>;
assert(start != NULL);
start->inf = s;
start->link = p;
}
// изключва елемент от неявния стек и го записва
// в параметъра s
// операцията е възможна, ако неявният стек не е празен
template <typename T>
void stack<T>::pop(T& s)
{ if (start)
{ s = start->inf;
elem<T>* p = start;
start = start->link;
delete p;
}
else
{ cout << "The stack is empty.\n";
exit(1);
}
}
// намира върха на неявния стек и го записва в параметъра s
// операцията е възможна, ако неявният стек не е празен
template <typename T>
void stack<T>::top(T& s)const
{ if (start)
s = start->inf;
else
{ cout << "The stack is empty.\n";
exit(1);
}
}
// извежда на екрана елементите на неявния стек
// предполага, че за елементите от тип T е
// дефиниран операторът <<
// след завършване на изпълнението на функцията,
// неявният стек става празен
template <typename T>
void stack<T>::print()
{ T x;
while (!empty())
{ pop(x);
cout << x << " ";
}
cout << endl;
}
// намира броя на елементите на неявния стек
// след завършване на изпълнението на функцията,
// неявният стек става празен
template <typename T>
int stack<T>::length()
{ int n = 0;
T x;
while (!empty())
{ pop(x);
n++;
}
return n;
}
#pragma once
#include "common.hpp"
#include <iostream>
#include <cassert>
#include "stack_s.cpp"
using namespace std;
int main()
{ stack<> st(3);
st.push(10); st.push(20); st.push(30);
stack<int> st1 = st, st2;
st2 = st1;
st2.print();
return 0;
}#pragma once
#include "common.hpp"
#include "LList1.cpp"
template <typename T = int>
class stack : public LList<T>
{ public:
// канонично представяне
stack();
~stack();
stack(const stack&);
stack& operator=(const stack&);
// основни операции
bool empty() const;
void push(const T&);
void pop(T&);
void top(T&);
void print();
int length();
};
template <typename T>
stack<T>::stack() : LList<T>()
{}
template <typename T>
stack<T>::~stack()
{}
template <typename T>
stack<T>::stack(const stack<T>& r) : LList<T>(r)
{}
template <typename T>
stack<T>& stack<T>::operator=(const stack<T>& r)
{ if (this != &r)
{ LList<T>::operator=(r);
}
return *this;
}
template <typename T>
bool stack<T>::empty() const
{ return LList<T>::empty();
}
template <typename T>
void stack<T>::push(const T& x)
{ if (!empty())
{ this->iterStart();
elem_link1<T>* p = this->iter();
this->insertBefore(p, x);
}
else
this->toEnd(x);
}
template <typename T>
void stack<T>::pop(T& x)
{ if (!empty())
{ this->iterStart();
elem_link1<T>* p = this->iter();
this->deleteElem(p, x);
}
else
{ cout << "The stack is empty.\n";
exit(1);
}
}
template <typename T>
void stack<T>::top(T& x)
{ if (!empty())
{ this->iterStart();
elem_link1<T>* p = this->iter();
x = p->inf;
}
else
{ cout << "The stack is empty.\n";
exit(1);
}
}
template <typename T>
void stack<T>::print()
{ LList<T>::print();
}
template <typename T>
int stack<T>::length()
{ return LList<T>::length();
}
#pragma once
#include "common.hpp"
const int MAXSIZE = 20;
template <typename T = int>
class stack
{ public:
// канонично представяне
stack(int = MAXSIZE);
~stack();
stack(const stack<T>&);
stack<T>& operator=(const stack<T>&);
// основни операции
bool empty() const;
bool full() const;
void push(const T&);
void pop(T&);
void top(T&) const;
void print();
private:
int stack_size; // максимален размер на стека
int stack_top; // връх на стека
T* arr; // носител на стека
void copyStack(const stack<T>&);
void deleteStack();
};
// параметричен конструктор
template <typename T>
stack<T>::stack(int size)
{ if (size <= 0) stack_size = MAXSIZE;
else stack_size = size;
arr = new T[stack_size];
assert(arr != NULL);
stack_top = -1;
}
// деструктор
template <typename T>
stack<T>::~stack()
{ deleteStack();
}
// конструктор за присвояване
template <typename T>
stack<T>::stack(const stack<T>& s)
{ copyStack(s);
}
// операторна функция за присвояване
template <typename T>
stack<T>& stack<T>::operator=(const stack<T>& st)
{ if (this != &st)
{ deleteStack();
copyStack(st);
}
return *this;
}
// помощна член-функция, която копира st в неявния стек
template <typename T>
void stack<T>::copyStack(const stack<T>& st)
{ stack_size = st.stack_size;
stack_top = st.stack_top;
arr = new T[stack_size];
assert(arr != NULL);
for(int i = 0; i <= stack_top; i++)
arr[i] = st.arr[i];
}
// помощна член-функция, която изтрива неявния стек
template <typename T>
void stack<T>::deleteStack()
{ delete [] arr;
}
// проверява дали неявният стек е празен
template <typename T>
bool stack<T>::empty() const
{ return stack_top == -1;
}
// проверява дали неявният стек е пълен
template <typename T>
bool stack<T>::full() const
{ return stack_top == stack_size-1;
}
// намира върха на неявния стек, ако последният не е
// празен, и го записва във формалния параметър x
template <typename T>
void stack<T>::top(T& x) const
{ if (!empty())
x = arr[stack_top];
else
{ cout << "The stach is empty.\n";
exit(1);
}
}
// включва x в неявния стек, ако последният не е пълен
template <typename T>
void stack<T>::push(const T& x)
{ if (!full())
{ stack_top++;
arr[stack_top] = x;
}
else
{ cout << "The stack is full.\n";
exit(1);
}
}
// изключва елемент от неявния стек, ако
// последният не е празен и го записва в x
template <typename T>
void stack<T>::pop(T& x)
{ if(!empty())
{ x = arr[stack_top];
stack_top--;
}
else
{ cout << "The stack is empty.\n";
exit(1);
}
}
// извежда на екрана елементите на
// неявния стек като го разрушава
template <typename T>
void stack<T>::print()
{ T x;
while (!empty())
{ pop(x);
cout << x << " ";
}
cout << endl;
}
#pragma once
#include "common.hpp"
typedef char string20[21];
struct studentType
{ string20 couseName;
char courseGrade;
studentType* next;
};
void deleteChain(studentType* p){while(p){auto q=p->next;delete p;p=q;}}
void examples(){
{studentType* temp = new studentType;
assert(temp != NULL);
temp->next = new studentType;
assert(temp->next != NULL);
strcpy(temp->couseName, "101 Math-1");
temp->courseGrade = 'B';
strcpy(temp->next->couseName, "103 CS-1");
temp->next->courseGrade = 'A';
temp->next->next = NULL;assert(temp->next->courseGrade=='A');deleteChain(temp);}
{studentType* temp = new studentType{};
assert(temp != NULL);
temp->next = new studentType{};
assert(temp->next != NULL);
temp->next->next = new studentType{};
assert(temp->next->next != NULL);
auto removed=temp->next;temp->next=removed->next;delete removed;assert(temp->next);deleteChain(temp);}
{studentType* temp1 = new studentType;
assert(temp1 != NULL);
strcpy(temp1->couseName, "305 Eng");
temp1->courseGrade = 'F';
studentType* temp2 = new studentType;
assert(temp2 != NULL);
strcpy(temp2->couseName, "105 Math-2");
temp2->courseGrade = 'C';
temp2->next = NULL;
studentType* temp = new studentType;
assert(temp != NULL);temp1->next = temp;
strcpy(temp1->next->couseName, "107 Math-3");
temp1->next->courseGrade = 'F';
temp = temp2;
temp2 = temp1->next;
temp2->next = NULL;assert(temp->courseGrade=='C'&&temp2->courseGrade=='F');deleteChain(temp1);deleteChain(temp);}
}#pragma once
#include "stack.cpp"
void textEdit(){stack<char>s,t;char c,x;while(cin.get(c)&&c!='\n'){if(c=='!'){if(!s.empty())s.pop(x);}else if(c=='#'){while(!s.empty())s.pop(x);}else s.push(c);}while(!s.empty()){s.pop(x);t.push(x);}while(!t.empty()){t.pop(x);cout<<x;}cout<<endl;}#pragma once
#include "common.hpp"
#include "stack.cpp"
// Smaller number means higher priority, matching the book's comparison.
int t(char c){switch(c){case '^':return 1;case '*':case '/':return 2;case '+':case '-':return 3;default:return 4;}}
void translate(char* s, char* ns)
{ stack<char> st; //помощен стек
st.push('(');
char x;
int i = 0, j = -1, n = strlen(s);
while (i < n)
{ if (s[i] >= '0' && s[i] <= '9' ||
s[i] >= 'a' && s[i] <= 'z')
{ j++;
ns[j] = s[i];
}
else
if (s[i] == '(') st.push(s[i]); else
if (s[i] == ')')
{ st.pop(x);
while (x != '(')
{ j++;
ns[j] = x;
st.pop(x);
}
}
else
if (s[i] == '+' || s[i] == '-' ||
s[i] == '*' || s[i] == '/' ||
s[i] == '^')
{ st.pop(x);
while (x != '(' && t(x) <= t(s[i]))
{ j++;
ns[j] = x;
st.pop(x);
}
st.push(x);
st.push(s[i]);
}
i++;
}
st.pop(x);
while (x != '(')
{ j++; ns[j] = x;
st.pop(x);
}
j++;
ns[j] = '\0';
}
#pragma once
#include "common.hpp"
template <typename T = int>
struct node
{ T inf;
node *left,
*right;
};
template <typename T = int>
class tree
{ public:
// канонично представяне
tree();
~tree();
tree(const tree&);
tree& operator=(const tree&);
// основни операции
bool empty() const; // проверява дали двоично
// дърво е празно
node<T>* getRoot() const; // достъп до корена
T rootTree() const; // намира корена
// на двоично дърво
tree leftTree() const; // намира лявото поддърво
tree rightTree() const; // намира дясното поддърво
// създава непразно двоично дърво по дадени
// корен, ляво и дясно поддърво
void create3(const T&, const tree<T>&, const tree<T>&);
// извежда двоично дърво
void print() const
{ pr(root);
cout << endl;
}
// създава непразно двоично дърво
// чрез въвеждане на върховете му
void create()
{ deleteTree(root); createTree(root);
}
private:
node<T>* root; // указател към корена
// помощни член-функции
// създава копие на дадено двоично дърво на друго
// място в паметта, сочено от указателя this
void copyTree(const tree<T>&);
// помощна за copyTree член-функция
void copy(node<T>*&, node<T>* const &) const;
// изтрива даденото чрез указател
// към корена двоично дърво
void deleteTree(node<T>*&) const;
// помощна за print член-функция
void pr(const node<T>*) const;
// помощна за create член-функция
void createTree(node<T>*&) const;
};
template <typename T>
tree<T>::tree()
{ root = NULL;
}
template <typename T>
tree<T>::~tree()
{ deleteTree(root);
}
template <typename T>
tree<T>::tree(const tree<T>& r)
{ copyTree(r);
}
template <typename T>
tree<T>& tree<T>::operator=(const tree<T>& r)
{ if (this != &r)
{ deleteTree(root);
copyTree(r);
}
return *this;
}
template <typename T>
void tree<T>::copyTree(const tree<T>& r)
{ copy(root, r.root);
}
template <typename T>
void tree<T>::copy(node<T>*& pos, node<T>* const& r) const
{ pos = NULL;
if (r)
{ pos = new node<T>;
assert(pos != NULL);
pos->inf = r->inf;
copy(pos->left, r->left);
copy(pos->right, r->right);
}
}
template <typename T>
void tree<T>::deleteTree(node<T>*& p) const
{ if (p)
{ deleteTree(p->left);
deleteTree(p->right);
delete p;
p = NULL;
}
}
template <typename T>
bool tree<T>::empty() const
{ return root == NULL;
}
template <typename T>
node<T>* tree<T>::getRoot() const
{ return root;
}
template <typename T>
T tree<T>::rootTree() const
{ if(!root) throw std::out_of_range("Empty tree has no root");
return root->inf;
}
template <typename T>
tree<T> tree<T>::leftTree() const
{ tree<T> t;
if(root) copy(t.root, root->left);
return t;
}
template <typename T>
tree<T> tree<T>::rightTree() const
{ tree<T> t;
if(root) copy(t.root, root->right);
return t;
}
template <typename T>
void tree<T>::pr(const node<T>* p) const
{ if (p)
{ pr(p->left);
cout << p->inf << " ";
pr(p->right);
}
}
template <typename T>
void tree<T>::create3(const T& x, const tree<T>& l,
const tree<T>& r)
{ if (this == &l || this == &r) { tree<T> lc(l), rc(r); create3(x,lc,rc); return; }
if (root) deleteTree(root);
root = new node<T>;
assert(root != NULL);
root->inf = x;
copy(root->left, l.root);
copy(root->right, r.root);
}
template <typename T>
void tree<T>::createTree(node<T>*& pos) const
{ T x; char c;
cout << "root: "; cin >> x;
pos = new node<T>;
assert(pos != NULL);
pos->inf = x;
pos->left = NULL;
pos->right = NULL;
cout << "Left Tree of: " << x << " y/n? ";
cin >> c;
if (c == 'y') createTree(pos->left);
cout << "Right Tree of: " << x << " y/n? ";
cin >> c;
if (c == 'y') createTree(pos->right);
}
#pragma once
#include "common.hpp"
#include "LList1.cpp"
template <typename T>
LList<T> unionSets(LList<T> p, LList<T> q)
{ LList<T> r; // ще съдържа резултата от обединението на p и q
p.iterStart();
q.iterStart();
elem_link1<T> *pp = p.iter(),
*qq = q.iter();
while (pp)
{ if (!member(pp->inf, r)) r.toEnd(pp->inf);
pp = pp->link;
}
while (qq)
{ if (!member(qq->inf, r)) r.toEnd(qq->inf);
qq = qq->link;
}
return r;
}
#pragma once
#include "stack.cpp"
int value(char* s)
{ stack<int> st; // създава празен стек st от цели числа
int x, y, z;
unsigned int i = 0, n = strlen(s);
while (i < n)
{ if (s[i] >= '0' && s[i] <= '9')
st.push((int)s[i]-(int)'0');
else
if (s[i] == '+' || s[i] == '-' ||
s[i] == '*' || s[i] == '/' ||
s[i] == '^')
{ st.pop(y);
st.pop(x);
switch (s[i])
{ case '+': z = x+y; break;
case '-': z = x-y; break;
case '*': z = x*y; break;
case '/': if(y==0) throw domain_error("Division by zero"); z = x/y; break;
case '^': z = (int)pow(x,y);
}
st.push(z);
}
i++;
}
st.pop(z);
return z;
}#pragma once
#include "common.hpp"
#include "graph.cpp"
#include "member.cpp"
template <typename T>
void deleteLast(LList<T>& l)
{ // списъкът l не е празен
l.iterStart(); T x;
elem_link1<T>* p = l.iter();
while (p->link) p = l.iter();
l.deleteElem(p, x);
}
template <typename T>
bool way(const T & a, const T & b, graph<T>& g, LList<T>& l)
{ l.toEnd(a);
if (a == b) return true;
elem_link1<T>* q = g.point(a);
q = q->link;
while (q)
{ if (!member(q->inf, l))
{ if (way(q->inf, b, g, l)) return true;
deleteLast(l); // връщане назад
}
q = q->link;
}
return false;
}
#pragma once
#include "common.hpp"
// Program Zad13.cpp
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cstring>
using namespace std;
#include "LList1.cpp"
#include "sortList.cpp"
#include "mergeLists.cpp"
struct people
{ char name[32]; // име на човек
bool operator<(const people& p) const
{ return strcmp(name, p.name) < 0;
}
};
typedef LList<people> peopleList;
typedef LList<peopleList> list_of_lists;
template<>
void LList<people>::print() const
{ elem_link1<people> *p = start;
while (p)
{ cout << p->inf.name << endl;
p = p->link;
}
cout << endl;
}
template<>
void LList<peopleList>::print() const
{ elem_link1<peopleList> *p = start;
while (p)
{ p->inf.print();
p = p->link;
}
}
int main()
{ // създаване на празен списък от
// списъци от имена на хора
list_of_lists LL;
cout << "Number of the sublists: ";
int n; cin >> n;
for (int k = 1; k <= n; k++)
{ // създаване на празен списък от имена на хора
peopleList L;
people s;
// въвеждане на броя на елементите на списъка
cout << "Number of the elements of the list: ";
int p; cin >> p;
// игнориране на символа за край на ред
cin.ignore();
// включване на имена в списъка L
for (int i = 1; i <= p; i++)
{ cout << "s= "; cin.getline(s.name, 32);
L.toEnd(s);
}
// включване на списъка L в списъка от списъци LL
LL.toEnd(L);
}
// извеждане на списъка от списъци от имена на хора
LL.print();
// установяване на указател p към началото на
// списъка от списъци от имена на хора LL
LL.iterStart();
elem_link1<peopleList> *p = LL.iter();
// обхождане на LL и сортиране на всеки списък от имена
while (p)
{ sortList(p->inf);
p = LL.iter();
}
// извеждане на LL след сортирането на
// всеки от подсписъците му
LL.print();
// сливане на подсписъците на LL в списъка L
LL.iterStart();
p = LL.iter();
if (!p) return 0;
peopleList L = p->inf;
p = LL.iter();
while (p)
{ L = mergeLists(L, p->inf);
p = LL.iter();
}
// извеждане на списъка L
L.print();
return 0;
}
#pragma once
#include "common.hpp"
// Program Zad14.cpp
#include <iostream>
#include <cassert>
using namespace std;
#include "LList1.cpp"
#include "member.cpp"
#include "unionSets.cpp"
#include "intersectionSets.cpp"
#include "differenceSets.cpp"
typedef LList<int> intSet;
// създаване на множество от цели числа
void createSet(intSet& L)
{ int s;
cout << "number= ";
int p; cin >> p;
for (int i = 1; i <= p; i++)
{ cout << "elem= "; cin >> s;
L.toEnd(s);
}
}
int main()
{ intSet A, B, C, D, E, F, R;
cout << "Set A\n";
createSet(A);
cout << "Set B\n";
createSet(B);
cout << "Set C\n";
createSet(C);
cout << "Set D\n";
createSet(D);
cout << "A: "; A.print();
cout << "B: "; B.print();
cout << "C: "; C.print();
cout << "D: "; D.print();
E = differenceSets(A, B);
F = intersectionSets(C, D);
R = unionSets(E, F);
R.print();
return 0;
}
#pragma once
#include "common.hpp"
// Program Zad15.cpp
#include <iostream>
#include <cassert>
using namespace std;
#include "LList1.cpp"
#include "accumulate.cpp"
typedef LList<int> intList;
void createList(intList& L)
{ int s;
cout << "number= ";
int p; cin >> p;
for (int i = 1; i <= p; i++)
{ cout << "elem= "; cin >> s;
L.toEnd(s);
}
}
int sum(int x, int y)
{ return x+y;
}
int main()
{ intList L;
cout << "List\n";
createList(L);
cout << "L: "; L.print();
cout << accumulate(sum, 0, L) << endl;
return 0;
}
#pragma once
#include "common.hpp"
// Program Zad16.cpp
#include <iostream>
#include <cassert>
using namespace std;
#include "LList1.cpp"
#include "accumulate.cpp"
#include "map.cpp"
#include "filter.cpp"
int plus(int a, int b)
{ return a + b;
}
bool even(int x)
{ return x%2 == 0;
}
int cube(int x)
{ return x*x*x;
}
int main()
{ LList<int> L, L1;
// създаване на линеен списък L от цели числа
int k;
cout << "Length of the list: "; cin >> k;
for (int j = 1; j <= k; j++)
{ cout << "Element: ";
int a; cin >> a;
L.toEnd(a);
}
L.print(); // извеждане на списъка L
// намиране на списъка L1 от кубовете
// на четните числа на списъка L
auto evens = filter(even, L);
L1 = map(cube, evens);
L1.print();
// намиране и извеждане на сумата от елементите на L1
cout << accumulate(::plus, 0, L1) << endl;
return 0;
}
#pragma once
#include "common.hpp"
// Program Zad17.cpp
#include <iostream>
#include <cassert>
using namespace std;
#include "LList1.cpp"
#include "accumulate.cpp"
typedef LList<double> doubleList;
doubleList concat(doubleList L1, doubleList L2)
{ doubleList L;
L.concat(L1);
L.concat(L2);
return L;
}
int main()
{ // създаване на линеен списък от
// линейни списъци от реални числа
LList<doubleList> L;
int n;
cout << "n= "; cin >> n; // брой на елементите на L
for (int i = 1; i <= n; i++)
{ doubleList m;
cout << "k= "; int k; // брой на елементите на i-тия
// линеен списък от реални числа
cin >> k;
// създаване на i-тия линеен списък от реални числа
for (int j = 1; j <= k; j++)
{ cout << "elem: ";
double elem; cin >> elem;
m.toEnd(elem);
}
// включване на i-тия линеен списък от реални числа
// в списъка от списъци от реални числа L
L.toEnd(m);
}
// конкатенация на списъците, съставящи L
doubleList L2;
doubleList L1 = accumulate(concat, L2, L);
L1.print();
return 0;
}
#pragma once
#include "common.hpp"
// Program Zad18.cpp
#include <iostream>
#include <cassert>
using namespace std;
#include "cyclicList.cpp"
typedef cyclicList<int> intCycl;
// създаване на цикличен списък,
// съдържащ целите числа 1, 2, ..., m,
// подредени последователно
void create(int m, intCycl& L)
{ for (int i = 1; i <= m; i++)
L.toEnd(i);
}
// докато има елементи в списъка L отброява n-тия
// елемент и го изключва от цикличния списък
void josiff(int n, intCycl L)
{ if(L.empty()) return;
if(n<=0) throw invalid_argument("Positive step required");
L.iterStart();
elem_cyclic<int> *p = L.iter(), *q;
while (p != p->link)
{ q = p;
for (int i = 1; i <= n-1; i++)
q = q->link;
p = q->link;
int x; L.deleteElem(q, x);
cout << x << " ";
}
cout << p->inf << endl;
}
int main()
{ intCycl L;
int m, n;
cout << "m: "; cin >> m;
create(m, L);
L.print();
cout << "n: "; cin >> n;
josiff(n, L);
return 0;
}
#pragma once
#include "common.hpp"
// Program Zad22.cpp
#include <iostream>
#include <cassert>
using namespace std;
#include "cyclicList.cpp"
template <typename T>
T accumulate(T (*op)(T, T), T null_val, cyclicList<T>& L)
{ T s = null_val;
L.iterStart();
elem_cyclic<T> *p = L.iter();
while (p)
{ s = op(s, p->inf);
p = L.iter();
}
return s;
}
typedef cyclicList<int> intList;
typedef cyclicList<intList> intListList;
// конкатениране на циклични списъци
intList concat(intList L1, intList L2)
{ intList L;
L1.iterStart();
L2.iterStart();
elem_cyclic<int> *p = L1.iter(),
*q = L2.iter();
while (p)
{ L.toEnd(p->inf);
p = L1.iter();
}
while (q)
{ L.toEnd(q->inf);
q = L2.iter();
}
return L;
}
// създаване на цикличен списък L от n
// циклични списъка от цели числа
void create(int n, intListList& L)
{ for (int i = 1; i <= n; i++)
{ intList m;
cout << "k= "; int k; cin >> k;
for (int j = 1; j <= k; j++)
{ cout << "x: "; int x; cin >> x;
m.toEnd(x);
}
L.toEnd(m);
}
}
int main()
{ int n; cout << "n= "; cin >> n; // брой на подсписъците
intListList L;
// създаване на цикличен списък L от n циклични списъка
create(n, L);
intList L2; // нулева стойност на concat
// конкатенация на цикличните списъци от цели
// числа, съставящи цикличния списък L
intList L1 = accumulate(concat, L2, L);
L1.print();
return 0;
}
#pragma once
#include "common.hpp"
// Program Zad23.cpp
#include <iostream>
#include <cassert>
using namespace std;
#include "DLList.cpp"
typedef DLList<int> intList;
// създаване на линеен списък с две връзки
// списъкът от цели числа L трябва да е празен
// при започване изпълнението на процедурата
void createList(int n, intList& L)
{ for (int i = 1; i <= 2*n; i++)
{ cout << "> ";
int x; cin >> x;
L.toEnd(x);
}
}
// а)
int sum(intList& L)
{ L.iterStart();
elem_link2<int>* p = L.iterSucc();
L.iterEnd();
elem_link2<int>* q = L.iterPred();
int n = L.length()/2;
int s = 0;
for (int i = 1; i <= n; i++)
{ s = s + p->inf * q->inf;
p = L.iterSucc();
q = L.iterPred();
}
return s;
}
// б)
int maximin(intList& L)
{ if(L.empty() || L.length()%2) throw invalid_argument("Nonempty even-sized list required");
int max;
L.iterStart();
elem_link2<int>* p = L.iterSucc();
L.iterEnd();
elem_link2<int>* q = L.iterPred();
int n = L.length()/2;
// инициализиране на променливата max с
// минимума на първия и последния елементи
if (p->inf <= q->inf) max = p->inf;
else max = q->inf;
for (int i = 1; i <= n-1; i++)
{ p = L.iterSucc();
q = L.iterPred();
int min;
if (p->inf <= q->inf) min = p->inf;
else min = q->inf;
if (min > max) max = min;
}
return max;
}
int main()
{ intList L;
cout << "n= "; int n; cin >> n;
createList(n, L);
L.print();
cout << "sum: " << sum(L) << endl;
cout << "maximin: " << maximin(L) << endl;
return 0;
}
#pragma once
#include "common.hpp"
// Program Zad25.cpp
#include <iostream>
#include <cassert>
using namespace std;
#include "LList1.cpp"
#include "stack.cpp"
#include "queue_link.cpp"
class object
{ public:
virtual ~object() = default;
// полиморфни действия
virtual void print() = 0;
virtual int length() = 0;
};
typedef stack<object*> stackObj;
typedef LList<int> intList;
typedef stack<int> intStack;
typedef queue<int> intQueue;
class polyStack: public stackObj, public object
{ public:
void print();
int length();
};
void polyStack::print()
{ polyStack ps(*this); // копира хетерогенния стек в
// стека ps
object *x;
while (!ps.empty())
{ ps.pop(x);
x->print(); // разрешава се динамично
}
cout << endl;
}
int polyStack::length()
{ polyStack ps(*this); // копира хетерогенния стек в
// стека ps
int num = 0;
object *x;
while (!ps.empty())
{ ps.pop(x);
cout << x->length() << " "; // разрешава се динамично
num++;
}
cout << endl;
return num;
}
class newList : public intList, public object
{ public:
void print();
int length();
};
void newList::print()
{ intList::print();
}
int newList::length()
{ return intList::length();
}
class newStack : public intStack, public object
{ public:
void print();
int length();
};
void newStack::print()
{ intStack temp(*this); // копира текущия стек
// в стека temp
temp.print();
}
int newStack::length()
{ intStack temp(*this); // копира текущия стек
// в стека temp
return temp.length();
}
class newQue: public intQueue, public object
{ public:
void print();
int length();
};
void newQue::print()
{ intQueue temp(*this); // копира текущата опашка
// в опашката temp
temp.print();
}
int newQue::length()
{ intQueue temp(*this); // копира текущата опашка
// в опашката temp
return temp.length();
}
int main()
{ // създаване на празен хетерогенен стек lh1
polyStack lh1;
// създаване на контейнерите на lh1:
// първи контейнер - линеен списък от цели числа ln1
newList ln1;
int i;
for (i = 15; i <= 65; i = i+10)
ln1.toEnd(i);
// включване на първия контейнер в хетерогенния стек lh1
lh1.push(&ln1);
// втори контейнер - стек от цели числа ls1
newStack ls1;
for (i = 10; i <= 40; i = i+10)
ls1.push(i);
// включване на втория контейнер в хетерогенния стек lh1
lh1.push(&ls1);
// трети контейнер - опашка от цели числа lq1
newQue lq1;
for (i = 17; i <= 87; i = i+10)
lq1.push(i);
// включване на третия контейнер в хетерогенния стек lh1
lh1.push(&lq1);
// извеждане на контейнерите на хетерогенния стек lh1
lh1.print();
// намиране и извеждане на броя на елементите на
// хетерогенния стек lh1 и на неговите контейнери
cout << lh1.length() << "\n\n";
// създаване на нов празен хетерогенен стек lh2
polyStack lh2;
// създаване на контейнерите на lh2:
// първи контейнер - опашка от цели числа lq2
newQue lq2;
for (i = 11; i <= 51; i = i+10)
lq2.push(i);
// включване на първия контейнер в хетерогенния стек lh2
lh2.push(&lq2);
// втори контейнер - стек от цели числа ls2
newStack ls2;
for (i = 18; i <= 58; i = i+10)
ls2.push(i);
// включване на втория контейнер в хетерогенния стек lh2
lh2.push(&ls2);
// извеждане на контейнерите на хетерогенния стек lh2
lh2.print();
// намиране и извеждане на броя на елементите на
// хетерогенния стек lh2 и на неговите контейнери
cout << lh2.length() << "\n\n";
// създаване на нов празен хетерогенен стек lh
polyStack lh;
// създаване на контейнерите на lh:
// първи контейнер - хетерогенният стек lh1
lh.push(&lh1);
// втори контейнер - хетерогенният стек lh2
lh.push(&lh2);
// трети контейнер - стекът от цели числа ls1
lh.push(&ls1);
// четвърти контейнер - опашката от цели числа lq2
lh.push(&lq2);
// извеждане на контейнерите на хетерогенния стек lh
lh.print();
// намиране и извеждане на броя на елементите на
// хетерогенния стек lh и на неговите контейнери
cout << lh.length() << endl;
return 0;
}
#pragma once
#include "common.hpp"
// Program Zad26.cpp
#include <iostream>
#include <cassert>
using namespace std;
#include "tree.cpp"
typedef tree<int> intTree;
int main()
{ intTree t;
t.create(); // създаване на непразно двоично дърво
t.print(); // извеждане на двоичното дърво
int x = t.rootTree(); // намиране на корена
cout << "root: " << x << endl; // извеждане на корена
intTree t1 = t.leftTree(), // намиране на ЛПД
t2 = t.rightTree(); // намиране на ДПД
cout << "leftTree: \n";
t1.print(); // извеждане на ЛПД
cout << "rightTree: \n";
t2.print(); // извеждане на ДПД
intTree t3;
t3.create3(x, t2, t1); // генериране на новото двоично дърво
t3.print(); // извеждане на полученото дърво
return 0;
}
#pragma once
#include "common.hpp"
// Program Zad27.cpp
#include <iostream>
#include <cassert>
using namespace std;
#include "tree.cpp"
typedef tree<int> intTree;
intTree addElem(int a, const intTree& t)
{ intTree t1; // създаване на празно двоично дърво
if (!t.empty())
// създаване на търсеното двоично дърво
t1.create3(t.rootTree() + a,
addElem(a, t.leftTree()),
addElem(a, t.rightTree()));
return t1;
}
int main()
{ intTree t;
t.create();
t.print();
cout << "Number: "; int a; cin >> a;
addElem(a, t).print();
return 0;
}
#pragma once
#include "common.hpp"
// Program Zad3.cpp
#include <iostream>
#include <cstring>
#include <cassert>
#include "stack.cpp"
using namespace std;
bool boolFormula(char* s)
{ stack<char> s1, s2; //помощни стекове
char c, x, y;
int i = 0, n = strlen(s);
while (i < n)
{ if (s[i] == '~' || s[i] == '*' || s[i] == '+')
s1.push(s[i]);
else
if (s[i] == 't' || s[i] == 'f') s2.push(s[i]);
else
if (s[i] == ')')
{ s1.pop(c);
switch(c)
{ case '~': s2.pop(x);
if (x == 't') c = 'f';
else c = 't';
s2.push(c); break;
case '*': s2.pop(y); s2.pop(x);
if (x == 't' && y == 't') c = 't';
else c = 'f';
s2.push(c); break;
case '+': s2.pop(y); s2.pop(x);
if (x == 'f' && y == 'f') c = 'f';
else c = 't';
s2.push(c);
}
}
i++;
}
s2.pop(c);
return c == 't';
}
int main()
{ char s[50];
cout << "s: "; cin >> s;
cout << boolalpha << boolFormula(s) << endl;
return 0;
}
#pragma once
#include "common.hpp"
#include "tree.cpp"
#include "accumulate_tree.cpp"
typedef tree<int> intTree;
int sum(int x, int y)
{ return x + y;
}
int po(int x, int y)
{ return x * y;
}
int main()
{ intTree t;
t.create();
t.print();
cout << accumulate(sum, 0, t) << endl;
cout << accumulate(po, 1, t) << endl;
return 0;
}
#pragma once
#include "common.hpp"
#include "tree.cpp"
#include "map_tree.cpp"
typedef tree<int> intTree;
int f(int x)
{ return x + 1;
}
int g(int x)
{ int f = 1;
for (int i = 2; i <= x; i++)
f = f*i;
return f;
}
int main()
{ intTree t;
t.create();
t.print();
map(f, t).print(); // увеличаване с 1 и извеждане
map(g, t).print(); // намиране на дървото
// с факториелите и извеждане
return 0;
}
#pragma once
#include "common.hpp"
#include "member_tree.cpp"
// Program Zad34.cpp
#include <iostream>
#include <cassert>
#include "tree.cpp"
using namespace std;
typedef tree<char> charTree;
// а
charTree create_tree_form()
{ char ch; charTree t;
cin >> ch;
if (ch >= '0' && ch <= '9')
{ charTree t1;
t.create3(ch, t1, t1);
}
else
{ charTree t1, t2;
t1 = create_tree_form();
cin >> ch;
t2 = create_tree_form();
t.create3(ch, t1, t2);
cin >> ch;
}
return t;
}
// б)
bool isForm(const charTree& t)
{ if (t.empty()) return false;
char c = t.rootTree();
if (c >= '0' && c <= '9')
return t.leftTree().empty() && t.rightTree().empty();
if (c != '+' && c != '-' &&
c != '*' && c != '/') return false;
return isForm(t.leftTree()) && isForm(t.rightTree());
}
// в)
int arrExpr(const charTree& t)
{ char c = t.rootTree();
if (c >= '0' && c <= '9') return (int)c - (int)'0';
switch (c)
{ case '+': return arrExpr(t.leftTree()) +
arrExpr(t.rightTree());
case '-': return arrExpr(t.leftTree()) -
arrExpr(t.rightTree());
case '*': return arrExpr(t.leftTree()) *
arrExpr(t.rightTree());
case '/': int denom = arrExpr(t.rightTree());
if (denom != 0)
return arrExpr(t.leftTree())/denom;
else
{ cout << "Error! Division by 0!\n";
return 0;
}
}
return INT_MAX; // добавено е за коректност на кода
}
// г)
void print_tree(const charTree& t)
{ char c = t.rootTree();
if (c >= '0' && c <= '9') cout << c;
else
{ cout << '(';
print_tree(t.leftTree());
cout << c;
print_tree(t.rightTree());
cout << ')';
}
}
int main()
{ charTree t;
t.create(); // или t=create_tree_form();
if (isForm(t))
{ print_tree(t);
cout << endl << arrExpr(t) << endl;
}
else cout << "It is not a formula.\n";
return 0;
}
#pragma once
#include "common.hpp"
#include "depth_tree.cpp"
// Program Zad35.cpp
#include <iostream>
#include <cassert>
using namespace std;
#include "tree.cpp"
typedef tree<char> charTree;
void reduce(charTree& t)
{ char c = t.rootTree();
if (c == '+' || c == '-' || c == '*' || c == '/')
{ charTree t1, t2;
t1 = t.leftTree();
t2 = t.rightTree();
reduce(t1);
reduce(t2);
t.create3(c, t1, t2);
if (c == '+' && t1.rootTree() == '0' ||
c == '*' && t1.rootTree() == '1')
t = t2;
else
if ((c == '*' || c == '/') && t2.rootTree() == '1' ||
(c == '+' || c == '-') && t2.rootTree() == '0')
t = t1;
else
if (c == '*' && (t1.rootTree() == '0' ||
t2.rootTree() == '0') ||
c == '/' && t1.rootTree() == '0' &&
t2.leftTree().empty() && t2.rightTree().empty() &&
t2.rootTree() >= '1' && t2.rootTree() <= '9')
{ charTree t3;
t.create3('0', t3, t3);
}
}
}
int main()
{ charTree t;
t.create();
reduce(t);
t.print();
return 0;
}
#pragma once
#include "common.hpp"
#include "equal_tree.cpp"
// Program Zad37.cpp
#include <iostream>
#include <iomanip>
#include <cassert>
using namespace std;
#include "tree.cpp"
typedef tree<char> morseTree;
int main()
{ morseTree tr;
tr.create(); tr.print(); // създава и извежда двоичното
// дърво с Морзовата азбука
node<char>* ptr = tr.getRoot();
cout << "Enter a sentence!\n";
char ch, ch1 = '.'; cin.get(ch);
while(cin)
{ if (ch == '.') { if(!ptr || !ptr->left) throw std::invalid_argument("Invalid Morse path"); ptr = ptr->left; ch1 = '.'; } else
if (ch == '-') { if(!ptr || !ptr->right) throw std::invalid_argument("Invalid Morse path"); ptr = ptr->right; ch1 = '-'; }
else
if (ch == ' ')
{ if (ch1 != ch)
{ cout << ptr->inf;
ptr = tr.getRoot();
ch1 = ch;
}
else
{ cout << ' ';
ptr = tr.getRoot();
ch1 = '.';
}
}
cin.get(ch);
}
if(ptr != tr.getRoot() && ptr) cout << ptr->inf;
return 0;
}
#pragma once
#include "common.hpp"
#include "binOrdTree_print.cpp"
// Program Zad38.cpp
#include <iostream>
#include <cassert>
#include "binOrdTree.cpp"
using namespace std;
typedef binOrdTree<int> intTree;
int main()
{ intTree t;
t.create(); // създаване на двоично наредено дърво,
// съдържащо елементите на въведената редица
t.print(); // извежда въведените елементи във възходящ ред
int x;
char c;
// изключване на указани върхове
do
{ cout << "x: ";
cin >> x;
t.deleteNode(x);
t.print();
cout << "next: y/n: ";
cin >> c;
} while (c == 'y');
t.print();
return 0;
}
#pragma once
#include "common.hpp"
// Program Zad4.cpp
#include <iostream>
#include <cassert>
#include "queue_link.cpp"
using namespace std;
// дефиниране на клас intQueue, определящ опашка от цели числа
typedef queue<int> intQueue;
// дефиниране на клас queueQueue, определящ опашка
// от опашки от цели числа
typedef queue<intQueue> queueQueue;
// специализиране на шаблонната член-функция print
// за извеждане на опашка от опашки от цели числа
template<>
void queue<intQueue>::print()
{ intQueue x;
while (!empty())
{ pop(x);
x.print();
}
cout << endl;
}
int main()
{ // qq е обект, представящ опашка от опашки от цели числа
queueQueue qq;
for (int i = 1; i <= 5; i++)
{ // конструиране на опашка q от цели числа
intQueue q;
for (int j = i; j <= 2*i; j++)
q.push(j);
// включване на опашката q в опашката qq
qq.push(q);
}
qq.print();
return 0;
}
#pragma once
#include "common.hpp"
// Program Zad40.cpp
#include <iostream>
#include <iomanip>
#include <cassert>
using namespace std;
#include "AVL.cpp"
typedef AVL<int> intAVL;
int main()
{ // създаване на празно AVL дърво t
intAVL t;
// включване на елементи в дървото
t.createAVL();
// извеждане на създаденото AVL дърво
t.print_tree();
int x;
char c;
do
{ cout << "x: ";
cin >> x;
t.delNode(x); // изключва върха x
t.print_tree(); // извежда AVL дървото
cout << "next: y/n: ";
cin >> c;
} while (c == 'y');
t.print_tree();
return 0;
}
#pragma once
#include "common.hpp"
// Program Zad41.cpp
#include <iostream>
#include <cassert>
#include "LList1.cpp"
#include "graph.cpp"
using namespace std;
template <typename T>
void create_graph(graph<T> &g)
{ // включване на върховете
char c;
do
{ cout << "top_of_graph: ";
T x; cin >> x;
g.addTop(x);
cout << "Top y/n? "; cin >> c;
} while (c == 'y');
// включване на ребрата
cout << "ribs:\n";
do
{ cout << "start top: ";
T x; cin >> x;
cout << "end top: ";
T y; cin >> y;
g.addRib(x, y);
cout << "next: y/n? "; cin >> c;
} while (c == 'y');
}
typedef graph<int> intGraph;
int main()
{ intGraph g; // създаване на празен граф g
create_graph(g); // включване на върхове и ребра в g
g.print(); // извеждане на екрана на графа g
return 0;
}
#pragma once
#include "common.hpp"
// Program zad48.cpp
#include <iostream>
#include <fstream>
using namespace std;
#include "selectSort.cpp"
template <typename T>
void readT(T& x)
{ cin >> x;
}
template <typename T>
void createFile(fstream& f, T& dummy)
{ T x;
readT(x);
while (cin)
{ f.write((const char*)&x, sizeof(T));
readT(x);
}
f.close();
}
template <typename T>
void writeT(T x)
{ cout << x << " ";
}
template <typename T>
void writeFile(fstream& f, T& dummy)
{ T x;
cout << "Sequence\n";
while (f.read((char*)&x, sizeof(T)))
writeT(x);
cout << endl;
f.close();
}
int main()
{ fstream f("pom.dat", ios::out|ios::binary);
int dummy;
createFile(f, dummy);
f.open("pom.dat", ios::in|ios::out|ios::binary);
selectSort(f, dummy);
f.open("pom.dat", ios::in|ios::out|ios::binary);
writeFile(f, dummy);
return 0;
}
#pragma once
#include "common.hpp"
// Program Zad5.cpp
#include <iostream>
#include <cassert>
using namespace std;
#include "queue_link.cpp"
typedef queue<int> intQueue;
// въвеждане на масив
void read(int n, int* a)
{ for (int i = 0; i < n; i++)
{ cout << "a[" << i << "]= ";
cin >> a[i];
}
}
int main()
{ // създаване на масив arr от числа
int arr[100], n;
do
{ cout << "n= ";
cin >> n;
} while (n < 1 || n > 100);
read(n, arr);
// въвеждане на границите на интервала
cout << "a < b = ";
int a, b;
cin >> a >> b;
// създаване на две празни опашки от цели числа
intQueue q1, q2;
// обхождане на масива arr и извеждане на екрана на
// всички числа, които са по-малки от a; включване в
// опашката q1 на числата, които са в интервала [a, b]
// и включване на числата по-големи от b в опашката q2
for (int i = 0; i < n; i++)
if (arr[i] < a) cout << arr[i] << " ";
else if (arr[i] <= b) q1.push(arr[i]);
else q2.push(arr[i]);
// извеждане на елементите натрупани в опашките q1 и q2
cout << endl;
q1.print();
q2.print();
return 0;
}
#pragma once
#include "common.hpp"
// Program Zad6.cpp
#include <iostream>
#include <iomanip>
#include <cassert>
using namespace std;
#include "queue_link.cpp"
typedef queue<int> intQueue;
// намиране на минимума на три числа
int min(int a, int b, int c)
{ int m = a;
if (b < m) m = b;
if (c < m) m = c;
return m;
}
intQueue q2, q3, q5; // създаване на три празни опашки
void displayAndPush(int x)
{ if (x != 1) cout << setw(5) << x;
q2.push(x*2);
q3.push(x*3);
q5.push(x*5);
}
int main()
{ int x, i, n;
cout << "Брой на елементите, които да се изведат ";
cin >> n;
displayAndPush(1);
for(i = 1; i <= n; i++)
{ int a, b, c;
q2.head(a);
q3.head(b);
q5.head(c);
x = min(a, b, c);
displayAndPush(x);
if (x == a) q2.pop(a);
if (x == b) q3.pop(b);
if (x == c) q5.pop(c);
}
cout << endl;
return 0;
}
#pragma once
#include "common.hpp"
// Program Zad7.cpp
#include <iostream>
#include <iomanip>
#include <cassert>
using namespace std;
#include "queue_link.cpp"
#include "sortQueue.cpp"
#include "mergeQueues.cpp"
struct people
{ char name[32];
int age;
bool operator<(const people& p) const
{ return age < p.age;
}
bool operator!=(const people& p) const
{ return age != p.age;
}
};
typedef queue<people> pqueue;
template<>
void queue<people>::print()
{ people x;
while (!empty())
{ pop(x);
cout << setw(35) << x.name << setw(15) << x.age << endl;
}
}
int main()
{ people s, dummy = {"xxx", -1};
pqueue q1;
int i, n;
// създаване на първата опашка
cout << "First Queue:\n n= ";
cin >> n;
for (i = 0; i < n; i++)
{ cout << "Name: ";
cin.ignore();
cin.getline(s.name, 32);
cout << "Age: ";
cin >> s.age;
q1.push(s);
}
// създаване на втората опашка
pqueue q2;
cout << "Second Queue \n n= ";
cin >> n;
for (i = 0; i < n; i++)
{ cout << "Name: ";
cin.ignore();
cin.getline(s.name, 32);
cout << "Age: ";
cin >> s.age;
q2.push(s);
}
pqueue p, q, r;
sortQueue(q1, p); // сортиране на първата опашка
sortQueue(q2, q); // сортиране на втората опашка
r = merge(p, q, dummy); // сливане на сортираните опашки
r.print(); // извеждане на резултата
return 0;
}
#pragma once
#include "common.hpp"
#include "people_queue.cpp"
#include "sortQueue.cpp"
#include "mergeQueues.cpp"
int main()
{ queue<pqueue> qq; // празна опашка от опашки от хора
int m; // брой на опашките на qq
cout << "m= "; cin >> m;
// създаване на опашката от опашки от хора qq
for (int j = 1; j <= m; j++)
{ int i, n;
pqueue q;
cout << j << " Queue:\n n= ";
// брой на елементите на j-тата опашка
cin >> n;
// създаване на j-тата опашка
for (i = 0; i < n; i++)
{ people s;
cout << "Name: ";
cin.ignore();
cin.getline(s.name, 32);
cout << "Age: ";
cin >> s.age;
q.push(s);
}
// включване на j-тата опашка в опашката qq
qq.push(q);
}
// създаване на помощна опашка от опашки от хора qq1,
// която ще съдържа сортираните опашки
queue<pqueue> qq1;
while (!qq.empty())
{ pqueue r;
qq.pop(r);
pqueue t;
sortQueue(r, t);
qq1.push(t);
}
// сливане на сортираните по възраст опашки
pqueue merge_queue, help_queue; // помощни опашки от хора
if (qq1.empty()) return 0;
qq1.pop(merge_queue);
people dummy = {"xxx", -1};
while (!qq1.empty())
{ qq1.pop(help_queue);
merge_queue = merge(merge_queue, help_queue, dummy);
}
merge_queue.print(); // извежда опашката,
// съдържаща резултата
// от сливането
return 0;
}
#pragma once
#include "common.hpp"
// Program Zad9.cpp
#include <iostream>
#include <cassert>
using namespace std;
#include "LList1.cpp"
int main()
{ // създаване на празните списъци L1 и L2
LList<int> L1, L2;
// включване на елементите 1, 2, 3, 4, 5 в списъка L1
int i;
for (i = 1; i <= 5; i++)
L1.toEnd(i);
// включване на елементите 6, 7, 8 в списъка L2
for (i = 6; i <= 8; i++)
L2.toEnd(i);
// създаване на списъка L3, равен на L1
LList<int> L3 = L1;
// извеждане на елементите на L1, L2 и L3
cout << "L1= "; L1.print();
cout << "L2= "; L2.print();
cout << "L3= "; L3.print();
// обръщане на елементите на L1, L2 и L3
L1.reverse();
L2.reverse();
L3.reverse();
// извеждане на екрана на обърнатите списъци
cout << "L1-rev: "; L1.print();
cout << "L2-rev: "; L2.print();
cout << "L3-rev: "; L3.print();
// създаване на списъка L, равен на конкатенацията
// на списъците L1, L2 и L3
LList<int> L;
L.concat(L1);
L.concat(L2);
L.concat(L3);
// извеждане на списъка L
cout << "L= "; L.print();
return 0;
}