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)

Висновки

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


 

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

17661. Інтерференція в тонких шарах інтерференційні дзеркала та просвітлююча оптика 28.84 KB
  Інтерференція в тонких шарах: інтерференційні дзеркала та просвітлююча оптика. При освітленні тонкої плівки відбувається накладання хвиль від джерела S які відбилися від передньої і задньої поверхонь плівки. Якщо світло біле то інтерференції смуги будуть кольоро...
17662. Інтерференція поляризованих променів 63.33 KB
  Інтерференція поляризованих променів. Як відомо для інтерференції необхідною умовою є когерентність променів. А також із відомої формули для інтерференційного члена що враховує взаємодію пучків: видно що результат інтерференції лінійно поляризованих променів зале
17663. Інформаційні властивості оптичного зображення 21.59 KB
  Інформаційні властивості оптичного зображення. Потік інформації біт/с виражається формулою Шенона де I кількість інформації у бітах; смуга частот у якій передається інформація; Pc характеристика сигналу потужність в даному разі; Pm характеристика смуги мінімаль
17664. Квантова дисперсійна формула (порівняння з класичною) 24.1 KB
  Квантова дисперсійна формула порівняння з класичною Величини Nkкількості атомів kвласні частоти kкоефіцієнти згасання у класичній теорії дисперсії розглядаються як емпіричні сталі тобто ці величини визначаються з самої кривої дисперсії та положенням спектральн
17665. Класична теорія дисперсії 56.13 KB
  Класична теорія дисперсії. Припустимо що поле представляється плоскою хвилею Амплітуда поля змінюється від точки до точки отже електрон піддається дії поля різної амплітуди. Однак ми знехтуємо цією обставиною вважаючищо амплітуда коливань електрона мала в порі
17666. Комбінаційне розсіяння світла 30.54 KB
  Комбінаційне розсіяння світла. При спектральных исследованиях рассеяния света Мандельштам и Ландсберг обнаружили что каждая спектральная линия падающего света сопровождается появлением системы линий измененной частоты называемых сателлитами .Изменение длины волн
17667. Кристалооптика: трійка векторів 26.87 KB
  Кристалооптика: трійка векторів Кристалооптика наука що вивчає проходження світла крізь кристали та інші анізотропні середовища. Більшість кристалів є анізотропними тобто їх властивості у різних напрямках не однакові. Пояснимо це явище. Фундаментальні рівняння Мак...
17668. Молекулярна і питома рефракція рівняння Клаузіуса-Мосотті 35.79 KB
  Молекулярна і питома рефракція: рівняння КлаузіусаМосотті Виведемо рівняння КлаузіусаМосотті: Помножимо на N матимемо: . Виразимо з рівності Р: а звідси скориставшись формулою можемо стверджувати що: . Підставимо цей вираз у формулу одержимо такі формули: з я
17669. Наближення дифракції Френеля і Фраунгофера в теорії дифракції 20.48 KB
  Наближення дифракції Френеля і Фраунгофера в теорії дифракції При вивченні дифракційних явищ в оптиці виникають деякі труднощі які не завжди мають точне розвязання тому доводиться користуватися деякими наближеннями. Між дифракційними явищами Френеля та Фраунгофер