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)

Висновки

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


 

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

47143. The attribute. Ways of expressing attributes 66.5 KB
  The attribute is a secondary part of the sentence which characterizes person or non-person expressed by the headword either qualitatively, quantitatively, or from the point of view of situation. Attributes may refer to nouns and other words of nominal nature, such as pronouns gerunds and substitute words, as in...
47145. Определение числовой последовательности и её предела 66.64 KB
  предел функции одной переменной в точке.бесконечно большие и бесконечно малые функции. Предел функциис его помощью определяются многие др. Определение предела функции в точке по Коши число А принадлежащее R называется пределом функции fх в точке х0 если она определена в некоторой проколотой окрестности точки х0 и если для любого сколь угодно малого числа Е 0 можно указать такое число b=b х0 е 0 что для всех х удовлетворяющих условие 0 xx0 b выполняется неравенство fx e если e 0 b 0 то 0 xx0 b Определение предела функции в...
47147. Ответственность за экологический вред, принесенный источником повышенной опасности 67.18 KB
  Возмещение вреда причиненного источником повышенной опасности для окружающей среды характеризуется существенной спецификой. К объектам повышенной опасности ГК РФ относит средства механизмы электрическую энергию высокого напряжения атомную энергию взрывчатые вещества сильнодействующие яды и т. Обязанность возмещения такого вреда возлагается на юридическое лицо или гражданина которые владеют источником повышенной опасности на праве собственности праве хозяйственного ведения или праве оперативного управления либо на ином...