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;

}


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

Висновки

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


 

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

56009. SHOPS AND SHOPPING 46 KB
  Text, exercises are aimed at learning new vocabulary. Pupils are offered to complete the chart, find true or false sentences, give short answers, put questions to the statements, find the odd word, make up sentences with words, find and correct the mistakes.
56011. Шкідливі та корисні звички 664.49 KB
  Кожен із нас мріє прожити щасливе життя, мати міцне здоров’я, багато друзів, знаходити взаєморозуміння між членами родини і нашого суспільства, досягти успіху в роботі, навчанні. Але, на жаль, наші сподівання не завжди справджуються.
56012. Кохання та одруження 62.5 KB
  The topic of our lesson today is Love and Marriage. Let’s start our lesson from the small episode about a person who had all kinds of love in her life: people love, mother’s love, the love of the nation and who was a beloved woman.
56013. Запорізька Січ 70.5 KB
  Мета: зясувати становище Запорізької Січі у складі Гетьманщини ознайомити із життям та діяльністю І.Сірка та економічним розвитком Запорізької Січі ІІ половини XVII ст. Мета нашого уроку:зясувати становище Запорізької Січі у складі Гетьманщини ознайомитись з життям та діяльністю Івана Сірка та економічним розвитком Запорізької Січі цього періоду. Ми наближаємося до Запорізької Січі.
56015. Запорізька Січ у другій половині ХVІІ ст 42.5 KB
  Мета: Показати статус Запорізької Січі в нових історичних умовах ; підкреслити що на к. Опис Січі з висоти пташиного польоту карта схема.Якою була доля Січі після Андрусівського перемиряробота з картою. Чи брали ви участь у національно-визвольній війні?
56016. Сім кольорів щастя. Виховна година в 4 класі 124.5 KB
  Бо у світі багато чого позначено числом сім: сім днів у тижні сім раз відміряй а раз відріж каже народна мудрість; є сім смертних гріхів які посилаються людині щоб вона їх переборола; а ще є сім чудес світу; а ще від щастя людина буває на сьомому небі; і книга за сімома печатями є і мабуть ще багато чогось іншого позначається числом сім. А ще мені здається є сім кольорів щастя. Ви можете заперечити мені що мовляв щастя не має кольору.
56017. Симфонія перемоги 88.5 KB
  Перше завдання: обрати вірне твердження. музична форма що складається з теми та її модифікованих повторень Перевірка виконаного завдання. правильна відповідь оцінюється учнями Друге завдання: з поданих слів скласти схему за якою пишеться увертюра...