Единое окно доступа к образовательным ресурсам

Алгоритмы и структуры данных на С++: Учебное пособие

Голосов: 9

В основу данного учебного пособия легли лекции, практические и лабораторные занятия, проводившиеся авторами в Петрозаводском государственном университете по дисциплине "Информатика" для студентов I курса математического факультета специальностей "Прикладная математика и информатика" и "Информационные системы и технологии". Цель данного курса - обучить студентов основным конструкциям широко распространенного объектно-ориентированного языка программирования С++, некоторым базовым структурам данных и алгоритмам их обработки.

Приведенный ниже текст получен путем автоматического извлечения из оригинального PDF-документа и предназначен для предварительного просмотра.
Изображения (картинки, формулы, графики) отсутствуют.
    3.6.   Шаблоны                                                   41


   Второй способ
   Реализуем перегрузку операции сложения с помощью функции с
двумя параметрами, которая не является членом класса.

class complex
 {
   public:
         int real, image;

   complex(int r=0, int i=0) { real=r; image=i; }
 };

complex operator+(complex c1, complex c2)
 {
    return complex(c1.real+c2.real, c1.image + c2.image);
 }

int main()
 {
   complex c1(1,0), c2(1), c3;
   c3=c2+c1;           //эквивалентно c3=operator+(c1,c2);
   printf("re=%d im=%d", c3.real, c3.image);
 }

                        3.6. Шаблоны

   Шаблон класса (template) определяет данные и операции потен-
циально неограниченного множества типов. Например, единый шаб-
лон класса list может обеспечить общее описание для списков разных
типов int, float, char и т. д. В качестве примера использования шаб-
лонов рассмотрим реализацию последовательного стека с помощью
параметризованного класса. Далее в ряде программ эта реализация
будет использоваться.

template<class   telem> class stack
{
    telem *x;    // массив для хранения элементов стека
    int top;     // указатель на вершину стека
    int n;       // размер выделенного для стека массива


42                                             Глава 3. Классы



     public:
       stack(int size);       // конструктор
      ~stack() {delete x;} // деструктор
       void push(telem y);
       telem pop();
       int empty()
           {
              if(top==0) return 1;
              else return 0;
           }
};

// Конструктор
template<class telem> stack<telem>::stack(int size)
{
   x = new telem [size];
   if(!x)
     {
       cout << "Невозможно создать стек \n"; exit (1);
     }
   n = size;           // количество элементов в стеке
   top = 0;            // пустой стек
}

// Функция включения элемента в стек
template<class telem>void stack<telem>::push(telem y)
{
   if(top==n)
     {
       cout << "Стек заполнен \n "; return;
     }
   x[top]=y; // включение элемента
   top++;
}

// Функция исключения элемента из стека
template<class telem>telem stack<telem>::pop()
 {


3.6.   Шаблоны                                             43


   if(top==0)
     {
         cout << "Стек пуст\n";
         return 0;
     }
  top--;
  return x[top];
 }

// главная программа
void main ()
{
  stack <int> x(10);   //создаем стек с элементами типа int
  stack <double> y(10);//создаем стек с элементами типа double
  stack <char> z(10); //создаем стек с элементами типа char

 x.push(1);
 y.push(1.1);
 z.push(’z’);

 count << x.pop()<< endl;
 count << y.pop()<< endl;
 count << z.pop()<< endl;
 }


     Глава 4.     Нелинейные структуры
                     данных

                  4.1. Бинарные деревья

   Бинарным деревом называется конечное множество узлов, которое
или пусто, или состоит из корня и из двух непересекающихся бинар-
ных деревьев, называющихся левым и правым поддеревьями данного
дерева.
   На рисунке 4.1 представлено бинарное дерево, которое будет ис-
пользоваться в ряде примеров.




                            Рис. 4.1

   Структура узла дерева представлена в следующем виде:

   struct node{char info; node *llink; node *rlink;}.

   Во многих приложениях требуется обработать узлы дерева в опре-
деленном порядке. Опишем некоторые возможные алгоритмы обхода
деревьев.


4.2.   Реализация алгоритмов работы с бинарными деревьями       45



   Обход в прямом порядке

   • Попасть в корень.
   • Пройти левое поддерево в прямом порядке.
   • Пройти правое поддерево в прямом порядке.

   Обход в обратном порядке

   • Пройти левое поддерево в обратном порядке.
   • Попасть в корень.
   • Пройти правое поддерево в обратном порядке.

   Обход в концевом порядке

   • Пройти левое поддерево в концевом порядке.
   • Пройти правое поддерево в концевом порядке.
   • Попасть в корень.

   Обходы бинарного дерева, приведенного на рисунке 4.1, будут сле-
дующими:

  1) обход в прямом порядке: ABDCEGFHJ;
  2) обход в обратном порядке: DBAGECHFJ;
  3) обход в концевом порядке: DBGEHJFCA.


 4.2. Реализация алгоритмов работы с бинарными
                    деревьями
       Рекурсивная реализация обхода бинарного дерева
                     в обратном порядке

void btree1(node *t) // t - указатель на корень дерева
{
  if(t! = NULL)
   {
      btree1 (t->llink); // обход левого поддерева
      cout << t->info;   // вывод информации


46                             Глава 4. Нелинейные структуры данных


           btree1 (t->rlink); // обход правого поддерева
      }
}

          Рекурсивная реализация ввода бинарного дерева
                        в прямом порядке
      Дерево вводится в виде ab..c.., где вместо NULL-связей вводим точ-
ки.

void input(node *&t)
{
   char c;
   cin>>c;
   if(c!=’.’)
     {
       t = new node;
       t->info = c;
       input(t->llink);
       input(t->rlink);
     }
   else t=NULL;
}

          Нерекурсивный алгоритм обхода бинарного дерева
                       в обратном порядке
   Пусть есть рабочий указатель node *p и стек указателей на узлы
дерева, t – указатель на корень дерева.

      Алгоритм:
     1) p = t;
     2) пройти до конца самой левой ветки дерева, начинающейся в p,
        запоминая ссылки на узлы в стеке;
     3) если стек непуст, то вытолкнуть из него верхний указатель в p,
        вывести информацию, которая хранится в p, p = p -> rlink,
        и перейти на шаг 2.
   Далее приведена реализация некоторых алгоритмов работы с би-
нарными деревьями с использованием шаблонов.


4.2.   Реализация алгоритмов работы с бинарными деревьями    47


template<class DataT> class tree
 {
      DataT info;
      tree *llink;
      tree *rlink;
   public:
      tree *root;                 // корень дерева
      tree(){root=NULL;};         // конструктор
      void in(tree<DataT> *&t);   // ввод дерева
      void btree1(tree<DataT> *t);
      void btree2(tree<DataT> *t);
      void btree3(tree<DataT>*t);
 };

// Ввод дерева в прямом порядке
template<class DataT>void tree<DataT>::in(tree<DataT> *&t)
 {
   DataT c;
   cin>>c;
   if(c!=’.’)
     {
       t=new tree<DataT>;
       t->info=c;
       in(t->llink);
       in(t->rlink);
     )
   else t=NULL;
 }

// Рекурсивная реализация обхода в обратном порядке
template<class DataT>void tree<DataT>::btree1(tree<DataT> *t)
 {
   if(t!=NULL)
      {
        btree1(t->llink);
        cout<<t->info;
        btree1(t->rlink);
      }
 }


48                       Глава 4. Нелинейные структуры данных



// Нерекурсивная реализация обхода в обратном порядке
template <class DataT>void tree<DataT>::btree2(tree<DataT> *t)
 {
   stack <tree<DataT>*> x(100);
   tree<DataT> *p;
   p=t;
   m: while(p!=NULL)
        {
           x.push(p);
           p=p->llink;
        }

      if(!x.empty())      // если стек непуст
        {
           p=x.pop();     // выталкиваем p
           cout<<p->info;
           p=p->rlink;
           goto m;
        }
 }

// Нерекурсивная реализация обхода в прямом порядке
template<class DataT>void tree<DataT>::btree3(tree<DataT> *t)
 {
    stack<tree<DataT>*> s(100);
    tree<DataT> *p;
    p=t;
    s.push(p);
    while(!s.empty())
       {
         p=s.pop();
         cout<<p->info;
         cout<<"\n";
         if (p->rlink!=NULL)
                      s.push(p->rlink);
         if (p->llink!=NULL)
                      s.push(p->llink);
       }


4.2.    Реализация алгоритмов работы с бинарными деревьями       49


 }

//главная программа
int main()
 {
   tree<char> t; // задаем дерево с элементами типа char
   cout<<endl;
   t.in(t.root);
   t.btree1(t.root);
   t.btree2(t.root);
   t.btree3(t.root);
 }

       Нерекурсивная реализация обхода бинарного дерева
             по уровням с помощью FIFO-очереди
   Теперь рассмотрим новый обход бинарного дерева, который назы-
вают обходом в ширину. Этот метод использует FIFO-очередь и осу-
ществляет обход дерева по уровням слева направо, в отличие от сте-
кового обхода в глубину, когда алгоритм пытается пройти как можно
дальше вглубь, пока не дойдет до конца какой-либо ветки. В этой про-
грамме приведена параметризованная реализация последовательной
циклической FIFO-очереди и снова описан параметризованный класс
”бинарное дерево”. Другой вариант программы мог бы включать в
одну программу реализацию и стека, и очереди, и описание одного
класса ”бинарное дерево”.
   Этот принцип применения стека для обхода в глубину и очере-
ди для обхода в ширину сохраняется и при обходе других структур
данных, например графов. Отметим, что в функции ввода бинарного
дерева для обозначения нулевых связей используется символ точка ”.”.
Это накладывает ограничение на тип информационного узла дерева.
Если необходимо работать не только с типом char, то надо вводить
нулевые связи каким-то другим способом. Такая модификация про-
граммы оставлена читателю в качестве упражнения.

#include <iostream.h>

template<class telem> class queue{
    telem *x;
    int head;


50                        Глава 4. Нелинейные структуры данных


    int tail;
    int n;
    int elements;
public:
    queue(int size);
   ~queue(){delete x;}
    void push(telem y);
    telem pop();
    int empty()
        {
           if(elements==0) return 1;
           else            return 0;
        }
};

template<class telem>queue<telem>::queue(int size)
{
    x=new telem[size];
    if(!x)
       {
         cout<<"Невозможно создать очередь\n";
         exit(1);
       }
    n=size;
    head=0;
    elements=0;
    tail=head;
}

template<class telem>void queue<telem>::push(telem y)
{
    if(elements==n)
        {
           cout<<"Очередь заполнена\n";
           return;
        }
    x[tail]=y;
    if((tail++)>(n-1))
                      tail=0;



    
Яндекс цитирования Яндекс.Метрика