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)

Висновки

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


 

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

53747. Конструирование из бумаги. Изготовление новогодней елочки 95.5 KB
  Технологии: технология сотрудничества, деятельностный подход, активное обучение, технологии объяснительно-иллюстративного обучения (в основе которых информирование, просвещение учащихся и организация из репродуктивных действий с целью выработки у них общеучебных умений и навыков).
53748. Теорема Виета 95 KB
  Предметные результаты: наблюдать и анализировать связь между корнями и коэффициентами квадратного уравнения. Формулировать и доказывать теорему Виета, а также обратную теорему, применять теоремы для решения уравнений и задач.
53749. Прогнозирование экономических показателей. Модели финансового планирования 27.5 KB
  Экономический прогноз — это научно обоснованное предвидение возможных направлений и результатов развития субъектов хозяйствования и их структурных подразделений. Методы экономического прогнозирования можно условно объединить в две группы. Наверняка все из вас пускали самолетики лодочки красовались в треуголке из бумаги различных форм фигурок – это и есть оригами. Однако независимые традиции складывания из бумаги хоть и не столь развитые как в Японии существовали среди прочего в Китае Корее Германии и Испании.
53750. День святого Валентина 43.5 KB
  Как они называются валентинки А знаете ли вы что согласно легенде в далекие времена жестокий римский император Клавдий II решил что одинокий мужчина без семьи и жены лучше сражается на поле битвы и запретил мужчинам жениться. Сегодня нам предстоит пусть с опозданием но изготовить валентинки для своих родных а может и любимых своими руками потому что мы знаем знаменитую пословицу: Лучше поздно чем ...
53751. Звери в лесу 48.5 KB
  Закрепить навык разметки по шаблонам, вырезание деталей сложной формы в виде встречного реза, выполнение алгоритма изготовления аппликации умение составлять композицию, намазывать детали клеем используя подкладной лист, приклеивать последовательно детали аппликации используя притирочный лист.
53752. Целеполагание в воспитательной работе педагога 62.5 KB
  Сущность цели и целеполагания в воспитательной работе педагога. Особенности цели и целеполагания в воспитательной работе педагога. В педагогической литературе встречаются различные определения цели Рожков М. Важность правильной постановки цели трудно переоценить.
53753. Ordering food 372 KB
  On the slide you see the picture with a lot of fruit and vegetables. You must write the name of them in your card in right column. If you know more words, you can write them too.
53754. Народные движения первой четверти XVIII века 140.5 KB
  Я уроженец станицы Зимовейской под моим командованием небольшая флотилия кораблей разгромила флот иранского шаха в 1671 году меня предала казацкая верхушка хотя именно я поднял восстание с боярами воеводами и другими притеснителями народа . Сейчас ребята мы с вами оказались на Юго – Восток России в начале18 веке здесь произошло крупное восстание. Астраханское восстание В 18 веке г Астрахань Рассказ учителя о восстании в Астрахани. Вспыхнув в Астрахани восстание быстро распространилось на...
53755. АЛГОРИТМЫ В НАШЕЙ ЖИЗНИ 108.5 KB
  Формирование умения грамотно излагать свою точку зрения Задачи урока: Развивать логическое и алгоритмическое мышление умение анализировать делать выводы; Ввести понятие алгоритм витражи; Ознакомить с видами алгоритмов; Отработать навык создания орнамента по алгоритму. Разминка Сейчас мы с вами проведем небольшую разминку нам необходимо будет расшифровать слово это и...