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;

}


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

Висновки

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


 

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

43129. Расчет принципиальной тепловой схемы установки К-300-240 ЛМЗ2 517.5 KB
  Основные технические характеристики Номинальная мощность МВт 300 Начальные параметры: давление МПа 235 температура 0С 545 Параметры промежуточного перегрева на выходе из ЧВД: давление МПа 305 температура 0С 284 на входе в ЦСД: давление МПа 275 температура 0С 545 Конечное давление МПа 000366 Число регенеративных отборов 8 Число подогревателей: низкого давления 5 высокого давления 3 Давление в деаэраторе МПа 0685 Температура питательной воды 0С...
43130. Расчет уровеня напряжения на вторичной стороне понижающих трансформаторов с помощью РПН 969.5 KB
  Расчет активной нагрузки трансформатора. Расчет реактивной нагрузки трансформатора. Расчетная нагрузка трансформатора. Выбор трансформатора Вывод: на трансформаторной подстанции установить два трансформатора типа ТМ.
43131. Розробка програми «Кулінарна книга» в середовищі програмування Borland C++ Builder 3.17 MB
  У першій частині «Специфікація проекту» викладено призначення розробки та підстави для її виконання, дана постановка завдання з описом того, що повинна виконувати майбутня програма, описані взаємозв'язки між таблицями і подано фізичний опис моделі. Крім того, розглянуто вимоги до програми і програмної документації. Описані структура програми, тобто використовувані класи і розробляється графічний інтерфейс.
43132. Веб-приложения на Java, реализующее функциональность просто интернет-магазина 953 KB
  Основные модели архитектуры JSP. Функционирование JSP. Заключение Список литературы Введение JSP JvServer Pges технология позволяющая веб-разработчикам легко создавать содержимое которое имеет как статические так и динамические компоненты.
43133. Поиск неисправностей в СВ 1.17 MB
  Анализ неисправности на структурном уровне По структурной схеме СВ устанавливаем вероятный неисправный блок. Согласно внешним признакам проявления неисправности очевидно что неисправен может быть либо сам ПОУ СВ либо блок ВчУ структурный уровень так как только эти устройства участвуют в записи информации с ПОУ СВ на ВчУ. Анализ неисправности на функциональном уровне По функциональной схеме устанавливаем вероятные неисправные устройства блока ПОУ СВ и ВчУ. Учитывая внешний признак проявления неисправности очевидно что этими устройствами...
43134. Проектирование привода ленточного транспортера 7.63 MB
  Расчет вала на выносливость Выбор муфты для выходного вала. Выбор муфты для ведомого вала. Редуктор имеет три вала: горизонтально расположенный ведущий быстроходный вал на котором установлена коническая шестерня и два горизонтальных вала перпендикулярных ведущему валу.
43135. Проектування корпуса фільтра вертикального однокамерного 1.3 MB
  Графічна частина виконується у обсязі двох аркушів формату А1: один аркуш складального креслення апарату загальний вигляд; один аркуш формату А2 зі складальним кресленням вузлів апарату за вказівкою викладача керівника проекту після виготовлення креслення першого аркуша; один аркуш формату А2 з робочими кресленнями деталей різноманітного призначення за вказівкою викладача керівника проекту після розробки складальних креслень формат А2 ділиться за необхідністю на декілька менших форматів. Розрахунковопояснювальна записка...
43137. Какова сущность, функции и структура морали 35.5 KB
  Всем известно, что человек — это индивид, умеющий себя ограничивать. Все мы живем в мире сплошных ограничений. Можно с уверенностью сказать, что человек и человеческое общество возникли тогда, когда научились себя ограничивать. Так, например первыми законами были законы, запрещающие браки между родственниками.