75665

Робота з динамічними структурами

Лабораторная работа

Информатика, кибернетика и программирование

Програму для роботи з двонапрваленими зв’язними списками. Кожен елемент списку містить зсилки на наступний і попередній елемент в списку. Програма повинна забезпечувати ввід і побудову списку. Програму для роботи для роботи з деревами. Кожен елемент дерева містить зсилку на батьківський елемент і зсилки на елементи-нащадки (необмежена кількість). Програма повинна забезпечувати ввід і побудову дерева.

Украинкский

2015-01-24

543.75 KB

2 чел.

Міністерство  освіти  і  науки України

Вінницький національний технічний університет

Інститут інформаційних технологій та комп’ютерної інженерії

Кафедра ПЗ

Лабораторна робота №5 варіант №9

з дисципліни Алгоритми та структури даних

Виконала: ст. гр. 1 ПІ-13б                            Лілик Л. С.

Перевірив:                                                       Власюк В. Х.

Вінниця, 2013

Тема: робота з динамічними структурами.

Мета: набуття практичних навичок опрацювання таких динамічних структур як зв’язні списки і дерева.

Завдання:

Розробити програми які виконують операції вказані в індивідуальному завданні.

  1.  Програму для роботи з двонапрваленими зв’язними списками. Кожен елемент списку містить зсилки на наступний і попередній елемент в списку. Програма повинна забезпечувати ввід і побудову списку.
  2.  Програму для роботи для роботи з деревами. Кожен елемент дерева містить зсилку на батьківський елемент і зсилки на елементи-нащадки (необмежена кількість). Програма повинна забезпечувати ввід і побудову дерева.
  3.  Кожен елемент списку містить інформаційне поле(атрибут) деякого простого типу: символ, стрічка, число.
  4.  Всі операції над динамічними структурами повинні супроводжуватись відповідним виводом на екран.
  5.  В контрольних прикладах  забезпечити опрацювання структур з 10-20 елементами.

Варіант № 9.

Двонапаравлений зв‘язний список

Дерево

9

Розбиття списку на два списки за вказаним порядковим номером елемента для розбиття.

Визначення середнього арифметичного чисел в дереві кожен елемент якого містить деяке число як значення інформаційного показника.

Складність алгоритмів

  1.  Складність алгоритму дорівнює O( 2N +12 ) від Т, де Т - час виконання.
  2.  Складність алгоритму дорівнює O( N + 2N + 8 ) від Т, де Т - час виконання.


Блок-схема алгоритму (1) 


Лістинг програми (1)

gg #include <iostream>

#include <cstdio>

using namespace std;

class Unit

{

public:

int data;

Unit *next;

   Unit *prev;

Unit(int data);

   ~Unit();

   static Unit* Add(Unit* node, Unit* iNum);

void ManualInput();

Unit* AddtoList(Unit *value);

Unit* RetNo(int num);

Unit* FindBeg();

void Show();

};

Unit::Unit(int _data)

{

data=_data;

next=0;

prev=0;

}

Unit::~Unit()

{

}

Unit *Unit::FindBeg()

{

Unit* tmp = this;

while(tmp->prev != NULL)

 tmp=tmp->prev;

return tmp;

}

Unit *Unit::RetNo(int num)

{

Unit* tmp = FindBeg();

int i=0;

if(i == num)

 return tmp;

while((i < num) && (tmp->next != NULL))

{

 tmp = tmp->next;

 i++;

}

return tmp;

}

Unit *Unit::AddtoList(Unit *value)

{

value->prev=this;

value->next=next;

next=value;

return this;

}

Unit *Unit::Add(Unit* node, Unit* iNum)

{

Unit* next;

Unit* prev;

if (node != NULL)

{

 prev = node;

 next = node->next;

 if (iNum != NULL)

 {

  iNum->prev = prev;

  iNum->next = next;

  prev->next = iNum;

  if (next != NULL)

   next->prev = iNum;

 }

}

else

 node = iNum;

return node;

}

void Unit::Show()

{

cout<<endl<<"Data: "<<data;

}

void Unit::ManualInput()

{

int _data;

cout<<"Input data: ";

cin>>_data;

data=_data;

}

void ShowList(Unit *node)

{

if (node != NULL)

{

 Unit* tmp = node->FindBeg();

 while (tmp != NULL)

 {

  tmp->Show();

  tmp = tmp->next;

 }

}

}

int SizeOfList(Unit *node)

{

int count = 0;

node = node->FindBeg();

while (node!= NULL)

{

 node = node->next;

 count++;

}

return count;

}

Unit *DivOn2 (Unit *node)

{

Unit *temp = node;

temp = temp->FindBeg();

int div = 0;

int i = 0;

cout<<endl<<"Input point of division: ";

cin>>div;

if(node!=NULL&&div<SizeOfList(node))

{

 while(temp!=node)

 {

  temp = temp->next;

  ++i;

 }

 if(i<div)

 {

  temp = temp->RetNo(div);

  (temp->prev)->next = NULL;

  temp->prev = NULL;

  return temp;

 }

 if(i>div)

 {

  temp = temp->RetNo(div-1);

  (temp->next)->prev = NULL;

  temp->next = NULL;

  return temp;

 }

}

   cout<<endl<<"ERROR! Invalid input.";

   return 0;

}

int GetNumber(Unit* node)

{

Unit* temp = node;

int i=0;

temp = temp->FindBeg();

while (temp !=node)

{

 temp = temp->next;

 i++;

}

return i;

}

Unit *Division(Unit *node)

{

Unit* temp = node;

temp = DivOn2(node);

   cout<<"\n\n~~~~~~~~~~~~~~~~~ Second part ~~~~~~~~~~~~~~~~~\n";

if(GetNumber(node)>GetNumber(temp))

{

 ShowList(node);

       cout<<"\n\n~~~~~~~~~~~~~~~~~ First part ~~~~~~~~~~~~~~~~~\n";

 ShowList(temp);

}

else

{

 ShowList(temp);

       cout<<"\n\n~~~~~~~~~~~~~~~~~ First part ~~~~~~~~~~~~~~~~~\n";

 ShowList(node);

}

return temp;

}

int main()

{

int command = -1;

Unit *list = NULL;

   Unit *manual = NULL;

   bool exist = false;

   bool divi = false;

list = Unit::Add(list, new Unit(56));

list = Unit::Add(list, new Unit(34));

list = Unit::Add(list, new Unit(66));

list = Unit::Add(list, new Unit(1));

list = Unit::Add(list, new Unit(89));

cout<<"~~~~~~~~~~~~~~~~~ Our list is ~~~~~~~~~~~~~~~~~";

   ShowList(list);

while (command!=0)

{

  cout <<"\n\nTo divide the list press 1.";

  cout <<"\nTo input your own list press 2.";

           cout <<"\nTo exit program press 0.";

  cout <<"\nInput your command: ";

  cin >> command;

  if (command==1)

  {

   if (exist||divi)

   {

                   Division(manual);

                   return 0;

   }

   else if (!divi)

   {

       Division(list);

       divi = true;

   }

   else

    {

                   cout<<"\nDivision id restricted!\n";

       return 0;

    }

           }

  if (command==2)

  {

               int num=0;

               cout<<"\nInput number of elements: ";

               cin>>num;

               cout<<endl;

               for (int i = 0; i<num; ++i)

               {

                   Unit *g = new Unit(5);

                   g->ManualInput();

                   manual = Unit::Add(manual, g);

               }

               ShowList(manual);

               exist = true;

           }

           else if(command == 0)

               return 0;

   }

   cout<<endl<<endl;

return 0;   }

Результат виконання (1)


Блок-схема алгоритму (2) 


Лістинг програми (2)

# include <iostream>

# include <cstdio>

using namespace std;

class Unit // node class

{

   public:

    int data;

Unit *right;

Unit *left;

Unit *parent;

Unit(void);

Unit(int _data);

Unit(const Unit &arg);

~Unit(void);

static void Push(int a, Unit **node);

static void Print(Unit *node, int u);

static void Traversal(Unit *node, float &arm);

};

Unit::Unit(void) // default ctor

{

data=0;

right=0;

left=0;

parent=0;

}

Unit::Unit(int _data):data(_data) // ctor

{

right=0;

left=0;

parent=0;

}

Unit::Unit(const Unit &arg)  // copy ctor

{

data=arg.data;

right=0;

left=0;

parent=0;

}

Unit::~Unit(void)  // dtor

{

}

Unit *tree = NULL;

void Unit::Push(int a, Unit **node)  // push new element to the binary tree

{

   if (*node==NULL)

   {

       (*node) = new Unit;

       (*node)->data = a;

       (*node)->left = (*node)->right = NULL;

       return;

   }

     

   if (a>(*node)->data) Push(a, &(*node)->right);

   else Push(a, &(*node)->left);

}

void Unit::Print(Unit *node, int u)  // prints tree

{

   if (node==NULL)  // return if the tree is empty

       return;

   else  // if tree exists and not empty

   {

       Print(node->left,++u);

       for (int i=0;i<u;++i)

           cout<<"_";

       cout<<node->data<<endl; // prints one node

       u--;

   }

   Print(node->right,++u);

}

float sum=0;

int num=0;

void Unit::Traversal (Unit *node, float &arm)  // traverses the tree and calculate the average (arithmetic mean)

{

   if  (node!=NULL)

   {

       Traversal((*node).left, arm);

       Traversal((*node).right, arm);

       sum+=(*node).data;

       ++num;

   }

   arm = (sum/num);

}

int main ()

{

   int n=0;

   int a=0;

   float arm=0.0;

   cout<<"Input number of elements: ";

   cin>>n;

   cout<<"Input "<<n<<" numbers: ";

   for (int i=0;i<n;++i)

   {

       cin>>a;

       Unit::Push(a,&tree);

   }

   cout<<"\n~~~~~~ THE TREE ~~~~~~~\n";

   Unit::Print(tree,0);

   cout<<"\n\nThe arithmethic mean is: ";

   Unit::Traversal(tree, arm);

   printf ("%3.4f \n\n", arm);

}

Результат виконання (2)

Висновки

Набуто практичних навичок опрацювання динамічних структур "Зв’язні списки" і "Дерева". В результаті виконання лабораторної роботи було отримано дві програми для роботи з цими структурами.


 

А также другие работы, которые могут Вас заинтересовать

63410. Понятие экономической системы. Типы экономических систем. Историческая классификация экономических систем. Натуральное хозяйство, основные этапы его развития. Недостатки натурального хозяйства 74.5 KB
  Модели смешанной экономики. Модели организации экономики отличаются между собой по степени свободы принятия решений и участия рыночных отношений в процессе перераспределения имеющихся ресурсов. В рамках каждого типа экономической системы существуют свои национальные модели.
63411. Управление режимами работы добывающих и нагнетательных скважин при заводнении 614 KB
  Режимы работы скважин определяют скорость вытеснения нефти или депрессию давления в пласте градиенты давления в пласте. Оценка добывных возможностей скважин при заводнении При заводнении пласта закачиваемыми водами происходит снижение коэффициента продуктивности скважины.
63412. ВЫБОР СУБД 404 KB
  Оптимизацию этих расходов можно произвести через правильный выбор СУБД. Выбор СУБД представляет собой сложную многопараметрическую задачу и является одним из важных этапов при создании БД.
63414. Мультиплексирование по времени 162.82 KB
  Принцип временного объединения каналов удобно пояснить с помощью коммутаторов в виде синхронно вращающихся распределителей на передающей и приемной стороне рисунок...
63417. Рынок. Основные проблемы и цели рыночной организации. Функции рынка. Виды рынка 95 KB
  Первоначально рынок рассматривался как базар место рыночной торговли рыночная площадь. Это объясняется тем что появился рынок в период разложения первобытно-общинного общества когда устанавливается более или менее регулярный обмен между общинами.