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;

}


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

Висновки

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


 

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

37642. Знайомство з об’єктно орієнтованим середовищем 26.48 KB
  Створив новий проект,для зручності додав допоміжну форму. Для виклику допоміжної форми достатньо клацнути по формі (подія FormClick)
37643. Дослідження типів, що визначаються, в мові Паскаль (інтервальний, перечислювальний, множинний) 19.02 KB
  Написати програму на мові Паскаль яка складається з наступних дій: Опису перечислювального типу згідно з варіантом завдання. Опису трьох інтервальних типів на основі перечислювального типу. Опису та ініціювання двох змінних різних інтервальних типів. Написати програму на мові Паскаль яка складається з наступних дій: Опису перечислювального типу згідно з варіантом завдання.
37644. ОСНОВЫ ПРОИЗВОДСТВЕННОЙ И КОММЕРЧЕСКОЙ ДЕЯТЕЛЬНОСТИ 2.54 MB
  Для выполнения своих функций муниципальный сектор располагает разнообразными природными, производственными, финансовыми, информационными и другими ресурсами, которые потребляются непосредственно населением муниципальных образований или через предприятия и учреждения
37645. Стабилизатор напряжения СТН 695.5 KB
  Лабораторная работа №01 Стабилизатор напряжения СТН Цель работы: определить неисправность в стабилизаторе напряжения СТН.1 Стабилизатор напряжения СТН 1.1 ТЕХНИЧЕСКИЕ ДАННЫЕ СТАБИЛИЗАТОРА НАПРЯЖЕНИЯ СТН: 1.
37646. Прохождение импульсов через реостатно – емкостные цепи 270.5 KB
  Цель работы: ознакомление с электрическими процессами в простейших реостатно – емкостных цепях при воздействии на них импульсных сигналов прямоугольной формы.
37647. Стабилизатор тока СТТ 655 KB
  Цель работы: определить неисправность в стабилизаторе тока СТТ. Оборудование: осциллограф С1 – 101, тренажер Т – 97, вольтметр В7 – 20.
37648. Генератор пилообразного напряжения 277.5 KB
  Цель работы: ознакомление с принципом действия генераторов пилообразных напряжений (ГПН). Оборудование: лабораторный стенд Е91А 2636, осциллограф С1 – 143, генератор сигналов – низкочастотный Г3 – 120.
37649. МІЖНАРОДНО-ПРАВОВА ОХОРОНА СЕРЕДОВИЩА СВІТОВОГО ОКЕАНУ, ТВАРИННОГО ТА РОСЛИННОГО СВІТУ 709.5 KB
  Мета курсової роботи залежить від пошуку ефективних шляхів, вкладених у гарантоване забезпечення сприятливого середовища Світового океану, тваринного та рослинного світу, екологічну безпеку із застосуванням міжнародно-правових екологічних принципів, і норм.
37650. Транзисторный ключ с нагрузкой индуктивного характера 326.5 KB
  Цель работы: ознакомление с особенностями переходных процессов в схемах транзисторных ключей с нагрузкой индуктивного характера. Оборудование: лабораторный стенд Е91А 2636, осциллограф С1 – 143, генератор сигналов – низкочастотный Г3 – 120.