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;

}


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

Висновки

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


 

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

1466. ДИАЛОГ АРГУМЕНТАТИВНОГО ТИПА: КОГНИТИВНЫЕ АСПЕКТЫ; СТРУКТУРА, СЕМАНТИКА, ПРАГМАТИКА (на материале русских и английских текстов интервью) 322.43 KB
  Цель данной диссертационной работы заключается в выявлении макроструктуры, создаваемой журналистами-участниками интервью и исследовании их аргументативных стратегий по методике, принятой в когнитивной лингвистике и прагмалингвистике.
1467. ЛИНГВОКУЛЬТУРОЛОГИЧЕСКИЙ АСПЕКТ ГЕНДЕРНЫХ ОТНОШЕНИЙ: СОПОСТАВИТЕЛЬНЫЙ АСПЕКТ 325.77 KB
  Целью данной работы является сравнительный анализ манифестации лингвокультурологического аспекта гендерных отношений в казахском, немецком и русском языках.
1468. ОРГАНИЗАЦИЯ СТРОИТЕЛЬНОГО ПРОИЗВОДСТВА 327.99 KB
  Курсовой проект состоит из графической части в объеме 2 чертежных листов формата АI и расчетно-пояснительной записки, содержащей 25-30 страниц текста. Исходные данные приведены в прил. 1, схема здания выдается преподавателем. Вариант задания назначается преподавателем.
1469. ЖАНРОВО-КУЛЬТУРНАЯ СПЕЦИФИКА РУКОВОДСТВ ПО ЭКСПЛУАТАЦИИ БЫТОВЫХ ПРИБОРОВ. АСПЕКТЫ ПЕРЕВОДА 328.15 KB
  Цель исследования заключается в разработке технологии перевода, основанной на результатах сопоставительного изучения жанровых особенностей русскоязычных и англоязычных руководств по эксплуатации с точки зрения организации и реализации макроструктуры текстов данного жанра.
1470. Дискурсивные аспекты политических дебатов (на материале русских и английских текстов) 329.27 KB
  На основе выработанного метода определить сопоставительные характеристики дискурсивных особенностей англоязычной и русскоязычной речи. Представить сравнительное описание речевого поведения участников политических дебатов через призму теории пресуппозиций в рамках политического дискурса. Выявить степень привязанности к контексту речевого поведения политических деятелей, а также определить те аспекты, которые обусловливают нарушение контекстуальных фреймов.
1471. ОСОБЕННОСТИ РЕАЛИЗАЦИИ ЛИЧНОСТНО-ОРИЕНТИРОВАННОЙ КОММУНИКАЦИИ В НОВЫХ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЯХ 329.94 KB
  Цель диссертационного исследования состоит в выявлении и последующей классификации общих, универсальных и специфических, уникальных особенностей реализации личностно-ориентированной коммуникации при сопоставлении вариантов ее осуществления в русскоязычном и англоязычном киберпространстве.
1472. СТРУКТУРА И СЕМАНТИКА ДЕТЕКТИВНОГО НАРРАТИВА (на материале текстов английских и русских рассказов) 331.07 KB
  Целью диссертационной работы является сопоставительный анализ когнитивных механизмов структуры и семантики детективного нарратива на материале английского и русского языков.
1473. Win API 32. Программирование на C 337.13 KB
  Литература по API Windows. Краткая история Windows. Цикл обработки сообщений Windows. Стили окна, overlapped window, pop-up window. Структура сообщения MSG. Окно сгенерированного приложения.
1474. ЭМОЦИОНАЛЬНЫЙ КОНЦЕПТ ЛЮБОВЬ В ИДИОСТИЛЕ А.С. ПУШКИНА 332.86 KB
  Ррассмотрение понятий концепт, концептуальная картина мира, представление методологических основ исследования концепта, определение понятия идиостиля, а также особенностей и возможностей поэтического перевода.