75675

Динамічні інформаційні структури (ДІС)

Практическая работа

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

Засвоїти знання про динамічні інформаційні структури. Сформувати навички опису ДІС і використання стандартних функцій при реалізації АТД ДІС засобами мови С++. Сформувати вміння застосовувати ДІС для розв’язування практичних задач.

Украинкский

2015-01-24

467.95 KB

0 чел.

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

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

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

Кафедра ПЗ

Практична робота №3 варіант №9

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

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

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

Вінниця, 2013

Тема: Динамічні інформаційні структури (ДІС).

 

Мета:  Засвоїти знання про динамічні інформаційні структури. Сформувати навички опису ДІС і використання стандартних функцій при реалізації АТД ДІС засобами мови С++. Сформувати вміння застосовувати ДІС для розв’язування практичних задач.

Завдання:

Варіант № 9 (4.6). Побудувати структуру даних, описану на малюнку і реалізувати процедуру читання даних у зазначеному порядку.

х1х2х1x4х5х6

х1х2х3х6х5

Алгоритм, що використаний у програмі:

На початку виконання програми створюється 6 елементів структури даних, кожний з яких містить інформацію у вигляді цілого числа. Потім розставляються покажчики  на інші елементи або на NULL, згідно вищенаведеного малюку. Користувачу пропонується ввести значення у поле даних. Потім ці значення виводяться у зазначеному порядку, при чому безпосередньо звернення до елемента не відбувається, а лише змінюється встановлений  покажчик. Користувачеві надано можливість змінити значення будь-якого елемента, а також прослідкувати зв’язки між усіма елементами за допомогою вказівників.

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

Складність алгоритму дорівнює О( 29 + N) від деякого часу виконання T.  


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

 


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

#include <iostream>

#include <cstdlib>

using namespace std;

class Point

{

   public:

   int data;

   Point *firstOut;

   Point *secondOut;

   Point(void);

   Point(int _data);

   ~Point(void);

   void Output();

   void Input();

};

Point::Point(void)

{

   data = 0;

   firstOut=0;

   secondOut=0;

}

Point::Point(int _data): data(_data)

{

   firstOut=0;

   secondOut=0;

}

Point::~Point()

{

}

void Point::Output()

{

   cout<<data;

   cout<<" ";

}

void Point::Input()

{

   cin>>data;

}

void Print(Point *p)

{

   p->Output();

}

void DataOutput(Point *p, Point *begin)

{

   cout<<"\nThe first data row is from x1 -> x2 -> x1 -> x4 -> x5 -> x6: \n";

   p = begin;

   Print(p);

   p = p->firstOut;

   Print(p);

   p = p->secondOut;

   Print(p);

   p = p->secondOut;

   Print(p);

   p = p->firstOut;

   Print(p);

   p = p->firstOut;

   Print(p);

   cout<<"\n\nThe second data row is from x1 -> x2 -> x3 -> x6 -> x5: \n";

   p = begin;

   Print(p);

   p = p->firstOut;

   Print(p);

   p = p->firstOut;

   Print(p);

   p = p->firstOut;

   Print(p);

   p = p->secondOut;

   Print(p);

   cout<<endl;

}

void ShowRelations(Point *p, Point *i)

{

   int num=0;

   p = i;

   Print(p);

   cout<<"\nInput pointer to the next elemenet (1 or 2) or 123 to exit:  ";

   while (num!=123)

   {

       cin>>num;

       if (num==1)

       {

           p = p->firstOut;

           if (p!=0)

           {

               ShowRelations(p, p);

           }

           else if (p==NULL)

           {

               cout<<"\nPointer is NULL. End of output.\n";

               exit(1);

           }

       }

       else if (num==2)

       {

           p = p->secondOut;

           if (p!=0)

           {

              ShowRelations(p, p);

           }

           else if (p==NULL)

           {

               cout<<"\nPointer is NULL. End of output.\n";

               exit(1);

           }

       }

       else if (num!=1&&num!=2&&num!=123)

       {

           cout<<"\nERROR! Wrong input!\n";

           exit(1);

       }

   }

}

int main()

{

   Point *x1;

   x1 = new Point(0);

   Point *x2;

   x2 = new Point(0);

   Point *x3;

   x3 = new Point(0);

   Point *x4;

   x4 = new Point(0);

   Point *x5;

   x5 = new Point(0);

   Point *x6;

   x6 = new Point(0);

   Point *p;

   Point *begin;

   begin = x1;

   cout<<"Input 6 integer elements: ";

   x1->Input();

   x2->Input();

   x3->Input();

   x4->Input();

   x5->Input();

   x6->Input();

   x1->firstOut=x2;   // x1

   x1->secondOut=x4;

   x2->firstOut=x3;   // x2

   x2->secondOut=x1;

   x3->firstOut=x6;   // x3

   x3->secondOut=x2;

   x4->firstOut=x5;   // x4

   x4->secondOut=0;

   x5->firstOut=x6;   // x5

   x5->secondOut=x4;

   x6->firstOut=0;   // x6

   x6->secondOut=x5;

   DataOutput(p, begin);

   int command = 0;

   cout<<"\nTo change element press 1, to watch relations press 2, to exit press 0:  ";

   cin>>command;

   if (command==1)

       {

           int num = 0;

           cout<<"Input number of element:  ";

           cin>>num;

           switch(num)

           {

               case 1: cout<<"\nInput new value: "; x1->Input(); DataOutput(p, begin); break;

               case 2: cout<<"\nInput new value: "; x2->Input(); DataOutput(p, begin); break;

               case 3: cout<<"\nInput new value: "; x3->Input(); DataOutput(p, begin); break;

               case 4: cout<<"\nInput new value: "; x4->Input(); DataOutput(p, begin); break;

               case 5: cout<<"\nInput new value: "; x5->Input(); DataOutput(p, begin); break;

               case 6: cout<<"\nInput new value: "; x6->Input(); DataOutput(p, begin); break;

               default:

                   cout<<"\nERROR! Your command is wrong.";

                   break;

           }

       }

 

  else if (command==2)

       {

           int i=0;

           cout<<"\nInput number of the first element:  ";

           cin>>i;

           switch(i)

           {

               case 1:  ShowRelations(p, x1); break;

               case 2:  ShowRelations(p, x2); break;

               case 3:  ShowRelations(p, x3); break;

               case 4:  ShowRelations(p, x4); break;

               case 5:  ShowRelations(p, x5); break;

               case 6:  ShowRelations(p, x6); break;

               default:

                   cout<<"\nERROR! Your command is wrong.";

                   break;

           }

       }

   else return 0;

   cout<<endl;

   delete x1;

   delete x2;

   delete x3;

   delete x4;

   delete x5;

   delete x6;

   return 0;

}


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

Висновки

Засвоїли знання про динамічні інформаційні структури. Сформували навички опису ДІС, використання стандартних функцій при реалізації АТД ДІС засобами мови С++, вміння застосовувати ДІС для розв’язування практичних задач. В результаті виконання лабораторної роботи побудовано структуру даних, згідно малюнку, реалізовано процедуру читання даних у певному порядку, надано можливість змінити значення будь-якого елемента, а також прослідкувати зв’язки між усіма елементами за допомогою вказівників.


 

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

23117. Принцип найменшої дії. Функція Лагранжа 43.5 KB
  Функція Лагранжа Найбільш загальне формулювання закону руху механічних систем дає так званий принцип найменшої дії або принцип Гамільтона. Функція L називається функцією Лагранжа даної системи а інтеграл дією. Функція Лагранжа залежить лише від q и а не від більш високих похідних що пояснюється тим що механічний стан повністю визначається завданням координат та швидкостей. Для спрощення запису формул припустимо спочатку що система має лише одну степінь вільності так що буде визначена лише одна функція qt.
23118. Гамільтонова форма рівнянь 90.5 KB
  Гамільтонова форма рівнянь. Підставляючи отримане в початкове рня маємо: Для переходу до змінних і додаємо і віднімаємо: Звідси Оскільки права частина виражена через диференціали то її можна розглядати як повний диференціал певної функції що залежить від яку позначимо і назвемо функцією Гамільтона: де Залишилося довести що Маємо Враховуючи це запишемо: звідки Ця система рівнянь називається канонічними рівняннями Гамільтона. рівн. рівн.
23119. Закони руху системи матеріальних точок та твердого тіла. Тензор інерції 77 KB
  Закони руху системи матеріальних точок та твердого тіла. Запишемо другий закон Ньютона для матеріальної точки з даної системи: 1 де сумарна зовнішня сила що діє на іту м. Записавши 1 для кожної точки системи та просумувавши всі отриманні рівняння маємо: 2. З урахуванням третього закону Ньютона тобто співвідношення перепишемо 2 як: 3 Нехай Rрадіус вектор даної системи: задає точкуцентр мас системи.
23120. Закони збереження та фундаментальні властивості простору-часу 263 KB
  Рух механічної системи описується 2S величинами де Sкількість ступенів вільності. системи вибір початку відліку часу одна з сталих в диф. рівняннях що описують динаміку може бути обрана сталою 1 При розв’язанні системи 1 2S1 сталих де Отримані величини інтеграли руху визнач. системи явно не залеж.
23121. Рух тіл в інерціальній та неінерціальній системах відліку. Сили інерції. Коріолісівське прискорення 202 KB
  Коріолісівське прискорення. інваріантне 0 де – прискорення в ІСВ швидкість в ІСВ – маса тіла – рівнодійна сил взаємодії які діють на тіло. Характеризуватимемо рух початку координат НеІСВ відносно ІСВ радіусвектором а обертання НеІСВ відносно ІСВ – кутовою частотою х В НеІСВ вимагають аналогічного до 0 запису закону руху тіла відносно радіусвектора : Оскільки прискорення в НеІСВ внаслідок х нерівне та величина не змінюється при переході до НеІСВ необхідно щоб сумарна сила складалась не тільки з теж...
23122. Закони руху системи матеріальних точок та твердого тіла. Тензор інерції 159.5 KB
  Закони руху системи матеріальних точок та твердого тіла.Введемо вектор повної кількості руху систем частинок: Знайдемо його зміну з часом: Для першої суми: ТобтоТаким чином якщо сума всіх зовнішніх сил рівна нулю то має місце закон збереження імпульсу. Ведемо повний момент кількості руху:Знайдемо швидкість його зміни в часі: Другий доданок – повний момент зовнішніх сил .Розглянемо перший доданок врахувавши : За умов виконання має місце закон збереження моменту кількості руху.
23123. Хвилі у пружньому середовищі. Хвильове рівняння. Звукові хвилі 59.5 KB
  Хвилі у пружньому середовищі. Звукові хвилі. Розрізняють хвилі повздовжні і поперечні в залежності від того чи рухаються частинки біля своїх положень рівноваги вздовж чи поперек напрямку розповсюдження хвилі. Розглянемо хвилі типу Позн.
23124. Рух ідеальної рідини. Рівняння Бернуллі 55.5 KB
  Нагадаємо що поле швидкостей характеризує не швидкiсть окремих частинок середовища а швидкiсть у данiй точцi в даний момент часу будьякої частинки рiдини або газу що знаходиться в цiй точцi в цей момент часу. Надалi будемо розглядати такi рiдини або гази для яких тензор пружних напругє iзотропним: pij = −pδij 14.10 для в’язкої рiдини газу набуде вигляду: Це є рiвняння Нав’єСтокса де η – коефiцiєнт зсувної в’язкостi – коефiцiєнт об’ємної в’язкостi. Для повного опису руху рiдини необхiдно додати ще рiвняння неперервностi та...
23125. Число Рейнольдса. Рух в’язкої рідини 44 KB
  В’язкою рідиною називають середовище в якому нарівні з нормальними напругами відмінні від нуля і дотичні напруги, що виникають внаслідок сил тертя. Коли швидкості не дуже великі, в’язка частина тензора напруг матиме такий вигляд...