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;

}


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

Висновки

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


 

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

52256. Аукціон фізичних знань 140.5 KB
  Команда яка швидше записала букви в кінці зірки і прочитала слово отримує 5 балів. Інша команда якщо вона правильно впоралась з завданням отримує 4 бали. Команда прослухавши повідомлення і розглянувши портрет відгадує ім'я вченого. За кожен правильно вгаданий портрет команда отримує по 3 бали.
52257. Організація закупівлі товарів на аукціонах 249.5 KB
  Інструкційно методична карта практичного заняття № 4 Тема: Організація підготовки і проведення аукціону. Навчальні цілі заняття: ознайомити студентів з планом проведення заняття ; І виявлення знань студентів по темі використовуючи різні форми і методи контролю; ІІ привити практичні навички оформлення акційних документів; ІІ навчити самостійно робити висновки вносити пропозиції щодо організації підготовки та проведення аукціону; ІІІ формувати особу спеціаліста з сучасним економічним мисленням здатну...
52259. Рельєф. Тектоніка. Геологічнабудова. Корисні копалини України 50.5 KB
  Корисні копалини України. Корисні копалини України. прищеплювати любов до України географії. Обладнання: Фізична карта України Тектонічна карта України магнітофон жетони гонг штатив молоточок таблиці атлас України 89 класи призи.
52260. Aus der Geschichte der Ukraine 50.5 KB
  Wie geht es euch Kinder Heute beginnen wir ein neues Them zu studieren. Es heißt Die Ukrine gestern und heuteâ. Dieses Them ht 10 Stunden. ber wie ds Them heutiger Stunde ist versteht ihr nch dieser ufgbe.
52261. Австралія – найменший материк Землі. Загальні відомості. Своєрідність географічного положення материка. Історія відкриття і дослідження. Рельєф і корисні копалини 7.75 MB
  Мета: сформувати в учнів загальне уявлення про своєрідність та особливості природи Австралії; продовжити формувати навички складати характеристику географічного положення материка; знайти закономірності розташування форм рельєфу та корисних копалин; розвивати вміння учнів працювати зі схемами атласу і підручника аргументувати свою відповідь у тому числі за допомогою додаткових джерел літератури. Для подальшого вивчення Австралії клас поділяється на групи: 1група. Знаходить на карті крайні точки Австралії і визначає їхні географічні...
52262. Australia. Terra Incognita 178 KB
  Terr Incognit Suggested level B 1 B1 intermedite Inn brmovsk senior techer of English school 5 L' viv Objectives: to get cquinted with ustrlin history geogrphy stte Symbols; to prctice vocbulry; to develop pupils' listening reding nd speking skills; to rouse pupils' interests in the life of ustrlin people. The Ntionl nthem...
52263. Австралійський Союз. Океанія 171 KB
  Мета: продовжити формувати систему знань про Австралію сформувати систему знань про природноресурсний потенціал Австралії і Океанії; систематизувати уявлення учнів про міжнародну спеціалізацію регіонів вдосконалити вміння і навички учнів самостійно працювати з джерелами географічної інформації. Обладнання: політична карта світу фізична карта Австралії фізична карта Океанії атласи учнівські...
52264. АВСТРАЛІЯ – найменший материк Землі. Історія відкриття і дослідження 112 KB
  Визначити географічне положення Австралії, ознайомити учнів з історією відкриття, заселення Австралії європейцями, особливостями рельєфу, корисними копалинами...