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;

}


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

Висновки

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


 

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

42401. Философия эпохи возрождения, антропоцентризм - принцип возрожденческой философии 80.5 KB
  Это представление дало название целой эпохе эпохе Возрождения или что тоже если использовать французское выражение эпохе Ренессанса приблизительно XIVXVI вв. В эпоху Возрождения было выработано новое философское мировоззрение прежде всего благодаря творчеству целой плеяды выдающихся философов таких как Николай Кузанский Марсилио Фичино Леонардо да Винчи Микеланджело Джордано Бруно и др. Этот шаг и был сделан в эпоху Возрождения с максимальной решительностью которая вообще часто характерна для новаторов.
42402. ИНФОРМАЦИОННЫЕ СИСТЕМЫ В ЭКОНОМИКЕ 14.01 MB
  Напротив каждого сектора появилось значение в рублях или значение в процентах от общей суммы товарооборота соответственно. Постройте круговую диаграмму показывающую удельный вес поступлений в рублях по каждому виду товара в общей сумме по складу.03 на сумму превышающую 2000000 руб. рублей.
42404. Работа со сканером 325.5 KB
  Планшетные сканеры пригодны как для качественного сканирования цветных изображений так и для более или менее быстрого ввода текстовых документов. Для процесса сканирования необходимо задать такие параметры: Тип изображения цветное чернобелое с оттенками серого или чернобелое Разрешение сканирования DPI Яркость и контрастность Имя тип и место расположения получаемого графического файла. Нажать на кнопку настроить и: выбрать тип изображения цветной снимок затем поменять разрешение сканирования на 300 dpi....
42405. Имитация трёхмерного текста 87 KB
  Нажмите [ltBckspce] [CtrlBckspce] [ltDelete] [CtrlDelete] чтобы залить фон черным цветом. Выберите пункт меню Edit Trnsform Perspective или нажмите [CtrlT] свободная трансформация и удерживая клавишу [Ctrl] передвигайте за углы и придайте надписи вид сходный с рисунком ниже. Затем скопируйте получившийся слой [CtrlJ] путём перетаскивания его на иконку Crete New Lyer в палитре Lyers Слои. Переключитесь на слой Bckground и нажмите [CtrlShiftE] чтобы произвести слияние видимых слоёв.
42406. Создание «металлических» надписей 99 KB
  Новому каналу будет автоматически присвоено имя lph 1. Скопируйте канал lph 1 путём перетаскивания его на пиктограмму Crete New Chnnel в палитре Chnnels. Новому каналу будет присвоено имя lph 2 и он станет активным. Примените к каналу lph 2 фильтр Gussin Blur со значением 3 pixels.
42407. Работа с режимом редактирования маски 476 KB
  Нажмите [D] чтобы установить foreground цвет в черный. Нажмите [CtrlI] чтобы инвертировать выделение после чего нажмите [Del] чтобы удалить ненужное выделение. Нажмите [CtrlD] чтобы снять выделение. Нажмите OK.
42408. Работа с простыми объектами в Corel Draw 66 KB
  Порядок выполнения работы Для того чтобы нарисовать линию необходимо воспользоваться горячей клавишей [F5] или иконкой на панели инструментов. Для того чтобы вставить прямоугольник можно воспользоваться иконкой на панели инструментов или горячей клавишей [F6]. Для того чтобы вставить окружность можно воспользоваться горячей клавишей [F7] или воспользоваться иконкой на панели задач. Как и с прямоугольником можно воспользоваться дополнительными клавишами [Ctrl и или Shift].
42409. Работа с текстом и заливкой в Corel Draw 383.5 KB
  Для того чтобы залить объект заливкой можно воспользоваться одним из инструментов: Fill Color Dilog [ShiftF11] Fountin Fill Dilog [F11] Pttern Fill Dilog Texture Fill Dilog PostScript Fill Dilog Not Fill. Fill Color Dilog Fountin Fill Dilog Pttern Fill Dilog Texture Fill Dilog PostScript Fill Dilog Not Fill убирает заливку Содержание отчета Тема и цель лабораторной работы Отчет о проделанной работе Вывод Контрольные вопросы Как с помощью горячих клавиш вставить текст Какие параметры текста можно выставить на...