75665

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

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

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

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

Украинкский

2015-01-24

543.75 KB

1 чел.

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

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

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

Кафедра ПЗ

Лабораторна робота №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)

Висновки

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


 

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

5705. Поняття професійної етики та її категорії 56.5 KB
  Поняття професійної етики та її категорії План Поняття про етику як науку. Основні категорії етики. Мораль як суспільне явище. Поняття про етикет та професійну етику. Етичний бізнес - це чесність, порядність, повага до п...
5706. Редагування текстів в MS Word 40.5 KB
  Редагування текстів Автозаміна Автозаміна - це автоматичне виправлення помилок і неправильних слів. Крім того, автозаміна дає змогу за допомогою кількох символів вставити великий текстовий фрагмент. Для настроювання механізму автозаміни потрібн...
5707. Інтернет як джерело банківської, фінансової і підприємницької інформації 131 KB
  Інтернет як джерело банківської, фінансової і підприємницької інформації Банківська і підприємницька інформація як підсистеми економічної інформації 1. Загальна характеристика дисципліни, її місце в системі підготовки бакалаврів зі спеціал...
5708. Педагогіка вищої школи як наука 74 KB
  Педагогіка вищої школи як наука План Предмет, категорії та основні завдання педагогіки вищої школи. Місце педагогіки вищої школи в системі педагогічних наук та її зв’язок з іншими науками. Сучасні методологічні аспекти педагог...
5709. Программирование на языках среднего уровня С/С++ 689 KB
  Предисловие Настоящий конспект лекций посвящен программированию на языках среднего уровня С/С++, в нем рассмотрен объектно-ориентированный подход программирования. Условно конспект лекций можно разделить на две части: первая часть посвящена основным...
5710. Теория государства и права. Теории происхождения и становления государства 209 KB
  Тема 1. Учение о государстве 1.1. Теории происхождения и становления государства. 2. Классовая теория, связывает происхождение государства с возникновением производительной экономики, получения избыточного продукта. Согласно её формуле, ...
5711. Основи охорони праці. Основні принципи державної політики в галузі охорони праці в навчальних закладах 42.5 KB
  Предмет, структура, мета курсу Основи охорони праці Основні принципи державної політики в галузі охорони праці. Організація охорони праці у навчальних закладах. Охорона праці, згідно закону України Про охорону п...
5712. Основні поняття і категорії статистики 60.5 KB
  Основні поняття і категорії статистики Зміст поняття статистика. Слово статистика (від lat. status – стан речей) означає кількісний облік масових явищ і процесів (наприклад, соціально-економічних, соціально-демографічних тощо). В сучасних соціа...
5713. Місце, роль та завдання органів кримінальної юрисдикції 118 KB
  ПЛАН 1. Загальна характеристика органів кримінальної юрисдикції. 2. Функції органів кримінальної юрисдикції РЕКОМЕНДОВАНА ЛІТЕРАТУРА: Конституція України від 28 червня 1996 р. Кримінально-процесуальний кодекс України від....