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;

}


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

Висновки

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


 

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

24993. Взаимодействие тел. Сила. Второй закон Ньютона 39 KB
  Сила. Сила. В простейших случаях взаимодействия количественной характеристикой является сила. Сила причина ускорения тел по отношению к инерциальной системе отсчета или их деформации.
24994. Импульс тела. Закон сохранения импульса в природе и технике 137.5 KB
  Импульс тела. Простые наблюдения и опыты доказывают что покой и движение относительны скорость тела зависит от выбора системы отсчета; по второму закону Ньютона независимо от того находилось ли тело в покое или двигалось изменение скорости его движения может происходить только при действии силы т. в результате взаимодействия с другими телами.
24995. Закон всемирного тяготения. Сила тяжести. Вес тела. Невесомость 52.5 KB
  Вес тела. Вес тела перегрузки. Исаак Ньютон выдвинул предположение что между любыми телами в природе существуют силы взаимного притяжения. гравитационная постоянная равна силе с которой притягиваются два тела по 1 кг на расстоянии 1 м.
24996. Превращение энергии при механических колебаниях. Свободные и вынужденные колебания. Резонанс 38.5 KB
  Свободные и вынужденные колебания. Свободные колебания. Вынужденные колебания.
24997. Основные этапы становления информационного общества. Информационные ресурсы государства, их структура. Образовательные информационные ресурсы 75.5 KB
  Информационные ресурсы государства их структура. Образовательные информационные ресурсы. Развитие новых информационных технологий и их быстрое проникновение во все сферы жизни породило новое направление в современной информатике социальная информатика включающее в себя следующую проблематику: информационные ресурсы как фактор социальноэкономического и культурного развития общества; закономерности и проблемы становления информационного общества; развитие личности в информационном обществе; информационная культура; информационная...
24998. Клавиатура (Keyboard) 31.69 KB
  Принцип действия клавиатуры Основным элементом клавиатуры являются клавиши. Сигнал при нажатии клавиши регистрируется контроллером клавиатуры и передается в виде так называемого скэнкода на материнскую плату. На материнской плате ПК для подключения клавиатуры также используется специальный контроллер. Когда скэнкод поступает в контроллер клавиатуры инициализируется аппаратное прерывание процессор прекращает свою работу и выполняет процедуру анализирующую скэнкод.
24999. Принцип работы модемов 62.47 KB
  Современные модемы обеспечивают гораздо большую скорость передачи данных. Применяемые в них протоколы передачи данных и коррекции ошибок обеспечивают надежную связь даже на не очень хороших телефонных линиях. В процессе передачи компьютерных данных по большинству линий связи выполняется двойное их ' преобразование: поток данных из компьютера побайтно преобразуется в последовательность отдельных бит которая далее превращается в сигнал при годный для передачи по телефонным линиям. Принимаемые данные претерпевают обратное преобразование: из...
25000. О мониторах - подробнее 131 KB
  Количество точек по горизонтали и по вертикали которые могут изображаться на экране монитора называется его разрешением. Принцип работы электроннолучевого монитора стеклянная колба сигналы управления лучом электронная пушка покрытие из люминофора электронный луч же монитора может меняться за счет объединения соседних триад. Количество раз которое сменится изображение на экране электроннолучевого монитора за 1 секунду называется частотой кадровой развертки.
25001. Манипуляторы 37.71 KB
  Наиболее распространенным из них является так называемая Мышь Она служит для ввода данных или одиночных команд выбираемых из меню ли текстограмм графических оболочек выведенных на экран монитора. Мышь представляет собой небольшую коробочку с двумя или тремя клавишами и утопленным свободно вращающимся в любом направлении шариком на нижней поверхности. Для работы с мышью необходима плоская поверхность с этой целью используют резиновые коврики Mouse Pad. Так как с помощью мыши нельзя вводить в компьютер серии команд поэтому мышь и...