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;

}


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

Висновки

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


 

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

39270. Рабочее место электромонтажника 134 KB
  В современных производственных условиях рабочие монтажники радиоэлектронной аппаратуры должны уметь пользоваться сборочномонтажными чертежами читать электрические схемы знать слесарносборочные монтажные и регулировочные операции маркировку современных электрорадиоэлементов обнаруживать и устранять неисправности в собираемых изделиях знать правила безопасности труда. 4 Перечень НТД по охране труда безопасности работы руководящим должностным и производственным инструкциям № № инструкций Наименование инструкций 1 489 По охране...
39271. Устройство защиты аппаратуры от аномальных напряжений сети 284.32 KB
  Котова Устройство защиты аппаратуры от аварийного напряжения сети Радио 2008 № 8 с. Из сетевого напряжения ограничительным диодом VD2 формируется переменное близкое к прямоугольному напряжение амплитудой около 18 В. Варистор RU1 защищает симистор VS1 от бросков напряжения при коммутации нагрузки индуктивного характера. Контроль величины сетевого напряжения осуществляет встроенный АЦП микроконтроллера DD1.
39272. Машиностроительный комплекс 425.17 KB
  Изменение структуры занятости по отраслям хозяйственного комплекса и сферам приложения труда свидетельствует о развитии рыночных структур в экономике. Повышение специализации производства требует использования высокопроизводительного оборудования; внедрения новых методов технологии механизации и автоматизации производственных процессов; повышения уровня квалификации персонала и увеличения производительности труда это снижает себестоимость при одновременном улучшении качества что приводит к увеличению реализации росту прибыли и...
39273. Социология труда и менеджмента. (Ф. Тейлор, Э. Мейо) 17.07 KB
  Социология труда (в развитых государствах Запада чаще она именуется индустриальной социологией) начала развиваться в 20-30-х гг. XX века. Исследуя проблемы, связанные с социальной сущностью труда, индустриальная социология важным объектом анализа ставит социально-трудовые отношения.
39274. АНАЛІЗ АСОРТИМЕНТУ, СПОЖИВНИХ ВЛАСТИВОСТЕЙ І КОКУРЕНТОСПРОМОЖНОСТІ КОМП’ЮТЕРІВ, ЯКІ РЕАЛІЗУЮТЬСЯ В ТОВ «САВ-ДІСТРИБ’ЮШН» В М. ДОНЕЦЬК 727 KB
  Основні тенденції розвитку світового і вітчизняного ринку компютерів Фактори які формують асортимент і якість комп'ютерів Аналіз ринку компютерів в Україні та світі Нові технології в розвитку асортименту компютерів Обґрунтування та удосконалення класифікації компютерів РОЗДІЛ 2. Практичні аспекти реалізації оцінки якості компютерів 2. Споживні параметри компютерів та методи їх оцінки 2.
39275. Изыскание путей повышения эффективности производства на НПК «Динкома» на основе оценки товарной политики предприятия 698.5 KB
  Инновационная политика разработка новой продукции ее торговой марки и упаковки основа эффективности предпринимательской деятельности в рыночных условиях гарантия высоких конкурентных позиций фирмы. Планы поступательного развития компании в средне и долгосрочной перспективе должны основываться на реалистичной и хорошо продуманной стратегической программе обновления ассортимента продукции. В интересах сохранения объемов сбыта или достигаемого уровня рентабельности предприятию необходимо быть готовым к немедленной замене вырабатываемой...
39276. Разработка автоматизированной системы измерений параметров взаимодействия жидких кристаллов с поверхностью подложки 7.52 MB
  Для них характерна относительная свобода пространственного порядка молекул в одном или более измерениях. Наиболее распространены нематические ЖК у которых длинные оси молекулы вытянуты приблизительно параллельно друг другу. Схема выключенной монохромной ячейки Если к ячейке приложено электрическое поле оси молекул поворачиваются перпендикулярно электродам и структура перестаёт вращать плоскость поляризации падающего света который при этом поглощается вторым поляризатором и устройство выглядит темным. Схема установки с вращением ячейки по...
39277. АРХИТЕКТУРА СПЕЦИАЛИЗИРОВАННЫХ СИСТЕМ ОБРАБОТКИ, АНАЛИЗА И ИНТЕРПРЕТАЦИИ ДАННЫХ 1.33 MB
  Команды. Опережающий просмотр команд. Структура ЭВМ с множественным потоком команд Глава 12. Компьютеры становятся весьма сложными кудато пропадает дружественность интерфейса программная среда переходит на жесткий командный язык и начинает требовать от пользователей предоставления такой информации которая не всегда известна и т.
39278. Концептуальная модель безопасности сети 22.04 KB
  Направлены на минимизацию или устранение Предполагают реализацию Невыполнение ведет к предпосылкам Потенциально ведут к нанесению ущерба Обуславливают наличие Из паспорта Из типа Кумулятивно и взвешенно ведут к нарушениям целостности устойчивости функционирования и безопасности ЕСЭ {C} Проверяют выполнение {R} = Учитывает ценность Учитывает стоимость Учитывает актуальность Содержат Рисунок 1 Концептуальная модель безопасности сети Условные обозначения:...