Проверен код към учебника на М. Тодорова

Редактирани версии за C++17, отделени от оригиналния препис. 88 целеви проверки: успешни. Проверени са 98 събрани листинга и допълнителни фрагменти; запазени са условията за допустимите входове. Пълната коректност за всички възможни входове не следва от преминаването на тестове.

Условия и стартиране · Всички промени · Резултати от проверките · Съпоставка на всички 368 блока

Основни поправки

accumulate.cpp — Оригинални стр. 108

Свали файла

#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;
}
accumulate_cyclic.cpp — Оригинални стр. 120

Свали файла

#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;
}
accumulate_tree.cpp — Оригинални стр. 175

Свали файла

#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;
}
allways.cpp — Оригинални стр. 246

Свали файла

#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;
        }
    }
}
AVL.cpp — Оригинални стр. 206–213

Свали файла

#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);
    }
}
BFS.cpp — Оригинални стр. 241–242

Свали файла

#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);
  }
}
binOrdTree.cpp — Оригинални стр. 189–196

Свали файла

#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);
              }
    }
}
binOrdTree_print.cpp — Оригинални стр. 197

Свали файла

#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);
    }
}
binSearch_array.cpp — Оригинални стр. 302

Свали файла

#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;
}
binSearch_file.cpp — Оригинални стр. 302–303

Свали файла

#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;
}
bst_balanced_constructor.cpp — Допълващ контекст или отделни фрагменти; виж съпоставката.

Свали файла

#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);
    }
}
bst_member.cpp — Допълващ контекст или отделни фрагменти; виж съпоставката.

Свали файла

#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());
}
btree_node.cpp — Допълващ контекст или отделни фрагменти; виж съпоставката.

Свали файла

#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 от тях)
};
bubbleSort_array.cpp — Оригинални стр. 272

Свали файла

#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;
    }
}
bubbleSort_file.cpp — Оригинални стр. 272–273

Свали файла

#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();
}
common.hpp — Допълващ контекст или отделни фрагменти; виж съпоставката.

Свали файла

#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;
complexity_loops.cpp — Допълващ контекст или отделни фрагменти; виж съпоставката.

Свали файла

#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);}
}
create_graph_alternative.cpp — Оригинални стр. 239

Свали файла

#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);
        }
    }
}
cyclicList.cpp — Оригинални стр. 113–118

Свали файла

#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;
}
declarations.cpp — Допълващ контекст или отделни фрагменти; виж съпоставката.

Свали файла

#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);}
depth_tree.cpp — Оригинални стр. 175

Свали файла

#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;
}
DFS.cpp — Оригинални стр. 243

Свали файла

#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);
    }
}
differenceSets.cpp — Оригинални стр. 106

Свали файла

#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;
}
DLList.cpp — Оригинални стр. 123–129

Свали файла

#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;
}
equal_tree.cpp — Оригинални стр. 174–175

Свали файла

#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());
}
expression_demo.cpp — Допълващ контекст или отделни фрагменти; виж съпоставката.

Свали файла

#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;
}
factorial_recursive.cpp — Допълващ контекст или отделни фрагменти; виж съпоставката.

Свали файла

#pragma once
#include "common.hpp"
int fact(int n)
{ if (n == 0) return 1;
  return n*fact(n-1);
}
factorial_stack.cpp — Допълващ контекст или отделни фрагменти; виж съпоставката.

Свали файла

#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"
}
file_helpers.hpp — Допълващ контекст или отделни фрагменти; виж съпоставката.

Свали файла

#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");
}
filter.cpp — Оригинални стр. 110

Свали файла

#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;
}
filter_cyclic.cpp — Оригинални стр. 121

Свали файла

#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;
}
graph.cpp — Оригинални стр. 233–237

Свали файла

#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;
}
hashTable_chaining.cpp — Оригинални стр. 306–310

Свали файла

#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;
}
hashTable_open_addressing.cpp — Оригинални стр. 314–317

Свали файла

#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;
}
heapSort_array.cpp — Оригинални стр. 292–293

Свали файла

#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--;
    }
}
heapSort_file.cpp — Оригинални стр. 293–294

Свали файла

#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();
}
insertSort_array.cpp — Оригинални стр. 278

Свали файла

#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);
}
insertSort_file.cpp — Оригинални стр. 279

Свали файла

#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();
}
intersectionSets.cpp — Оригинални стр. 106

Свали файла

#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;
}
intro_algorithms.cpp — Допълващ контекст или отделни фрагменти; виж съпоставката.

Свали файла

#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);
}
linSearch_array.cpp — Оригинални стр. 300

Свали файла

#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;
}
linSearch_file.cpp — Оригинални стр. 301

Свали файла

#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;
}
linSearch_for.cpp — Оригинални стр. 300–301

Свали файла

#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;
}
linSearch_sentinel.cpp — Оригинални стр. 300

Свали файла

#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;
}
LList1.cpp — Оригинални стр. 79–89

Свали файла

#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;
    }
}
LList_alternative.cpp — Допълващ контекст или отделни фрагменти; виж съпоставката.

Свали файла

#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;
}
map.cpp — Оригинални стр. 109–110

Свали файла

#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;
}
map_cyclic.cpp — Оригинални стр. 120

Свали файла

#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;
}
map_tree.cpp — Оригинални стр. 176

Свали файла

#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;
}
member.cpp — Оригинални стр. 104–105

Свали файла

#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;
}
member_tree.cpp — Оригинални стр. 182

Свали файла

#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());
}
merge_array.cpp — Оригинални стр. 295–296

Свали файла

#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++;
      }
}
merge_file.cpp — Оригинални стр. 296–297

Свали файла

#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();
}
mergeLists.cpp — Оригинални стр. 96–97

Свали файла

#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;
}
mergeQueues.cpp — Оригинални стр. 72–73

Свали файла

#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;
}
mergeSort.cpp — Оригинални стр. 97

Свали файла

#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);
}
mergeSort_array.cpp — Оригинални стр. 298–299

Свали файла

#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;
}
minway.cpp — Оригинални стр. 246–247

Свали файла

#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;
        }
    }
}
minway_bfs.cpp — Оригинални стр. 249–250

Свали файла

#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;
        }
    }
}
people_queue.cpp — Допълващ контекст или отделни фрагменти; виж съпоставката.

Свали файла

#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;
    }
}

polynomial.cpp — Оригинални стр. 101–104

Свали файла

#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;
        }
    }
}
qSort_array.cpp — Оригинални стр. 284–285

Свали файла

#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);
}
qSort_file.cpp — Оригинални стр. 285–286

Свали файла

#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();
}
qsort_indices.cpp — Оригинални стр. 52–53

Свали файла

#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);
        }
    }
}
qsort_pointer.cpp — Оригинални стр. 50–52

Свали файла

#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;
}
queue_demo.cpp — Допълващ контекст или отделни фрагменти; виж съпоставката.

Свали файла

#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
}
queue_from_list.cpp — Оригинални стр. 93–95

Свали файла

#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();
}
queue_s.cpp — Оригинални стр. 58–61

Свали файла

#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;
}
selectSort.cpp — Оригинални стр. 268

Свали файла

#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();
}
selectSort_array.cpp — Оригинални стр. 267

Свали файла

#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;
    }
}
shakerSort_array.cpp — Оригинални стр. 275–276

Свали файла

#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;
    }
}
shakerSort_file.cpp — Оригинални стр. 276–277

Свали файла

#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();
}
ShellSort_array.cpp — Оригинални стр. 281

Свали файла

#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;
    }
}
ShellSort_file.cpp — Оригинални стр. 282

Свали файла

#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();
}
sort_two_halves.cpp — Оригинални стр. 131

Свали файла

#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;
}
sortList.cpp — Оригинални стр. 95–96

Свали файла

#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;
    }
}
sortQueue.cpp — Оригинални стр. 71–72

Свали файла

#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;
    }
}
stack.cpp — Оригинални стр. 36–41

Свали файла

#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;
}
stack_demo.cpp — Допълващ контекст или отделни фрагменти; виж съпоставката.

Свали файла

#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;
}
stack_from_list.cpp — Оригинални стр. 90–93

Свали файла

#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();
}
stack_s.cpp — Оригинални стр. 32–35

Свали файла

#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;
}
student_nodes.cpp — Допълващ контекст или отделни фрагменти; виж съпоставката.

Свали файла

#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);}
}
textEdit.cpp — Допълващ контекст или отделни фрагменти; виж съпоставката.

Свали файла

#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;}
translate.cpp — Оригинални стр. 44–45

Свали файла

#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';
}
tree.cpp — Оригинални стр. 168–173

Свали файла

#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);
}
unionSets.cpp — Оригинални стр. 105

Свали файла

#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;
}
value.cpp — Допълващ контекст или отделни фрагменти; виж съпоставката.

Свали файла

#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;
}
way.cpp — Оригинални стр. 245

Свали файла

#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;
}
Zad13.cpp — Оригинални стр. 98–100

Свали файла

#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;
}
Zad14.cpp — Оригинални стр. 107–108

Свали файла

#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;
}
Zad15.cpp — Оригинални стр. 108–109

Свали файла

#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;
}
Zad16.cpp — Оригинални стр. 111

Свали файла

#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;
}
Zad17.cpp — Оригинални стр. 112–113

Свали файла

#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;
}
Zad18.cpp — Оригинални стр. 119–120

Свали файла

#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;
}
Zad22.cpp — Оригинални стр. 121–123

Свали файла

#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;
}
Zad23.cpp — Оригинални стр. 129–131

Свали файла

#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;
}
Zad25.cpp — Оригинални стр. 133–137

Свали файла

#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;
}
Zad26.cpp — Оригинални стр. 173–174

Свали файла

#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;
}
Zad27.cpp — Оригинални стр. 174

Свали файла

#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;
}
Zad3.cpp — Оригинални стр. 48–49

Свали файла

#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;
}
Zad31.cpp — Оригинални стр. 176

Свали файла

#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;
}
Zad33.cpp — Оригинални стр. 177

Свали файла

#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;
}
Zad34.cpp — Оригинални стр. 178–180

Свали файла

#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;
}
Zad35.cpp — Оригинални стр. 181–182

Свали файла

#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;
}
Zad37.cpp — Оригинални стр. 185

Свали файла

#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;
}
Zad38.cpp — Оригинални стр. 196

Свали файла

#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;
}
Zad4.cpp — Оригинални стр. 67–68

Свали файла

#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;
}
Zad40.cpp — Оригинални стр. 214

Свали файла

#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;
}
Zad41.cpp — Оригинални стр. 238

Свали файла

#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;
}
zad48.cpp — Оригинални стр. 269–270

Свали файла

#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;
}
Zad5.cpp — Оригинални стр. 68–69

Свали файла

#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;
}
Zad6.cpp — Оригинални стр. 69–70

Свали файла

#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;
}
Zad7.cpp — Оригинални стр. 73–75

Свали файла

#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;
}
Zad8_main.cpp — Оригинални стр. 75–76

Свали файла

#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;
}
Zad9.cpp — Оригинални стр. 89–90

Свали файла

#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;
}