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;

}


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

Висновки

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


 

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

27974. Активное и пассивное, продуктивное и репродуктивное воображение 35.57 KB
  Феномен аттракции в межличностных отношениях различные уровни аттракции. Феномен аттракции в межличностных отношениях различные уровни аттракции. Область исследований связанных с выявлением механизмов образования различных эмоциональных отношений к воспринимаемому человеку получила название исследования аттракции. Феномен аттракции связан с перцептивной стороной межличностного общения возникает при включении в процесс восприятия эмоциональных регуляторов.
27975. Основные свойства внимания и методы их оценки 43.91 KB
  Основные свойства внимания и методы их оценки. В зависимости от объекта выделяют формы внимания: сенсорное перцептивное: зрительное и слуховое интеллектуальное моторное двигательное исполнительское. Внешнее внимание сенсорноперцептивное обращено на объекты внешнего мира необходимое условие познания и преобразования окружающего мира Внимание внутреннее интеллектуальное обращено на объекты субъективного мира человека необходимое условие самопознания и самовоспитания Виды внимания Джеймс По объекту: а чувственное...
27976. Когнитивные теории внимания и их критика. Этноцентризм и этнические стереотипы 28.85 KB
  Допускается существование группы механизмов селекции в канале ограниченной емкости в результате возникают отсеивание информации еще до момента ее полной идентификации в блоке Р. это процесс в котором два или более индивида или группы активно ищут возможность помешать друг другу достичь определенной цели предотвратить удовлетворение интересов соперника или изменить его взгляды и социальные позиции. когда группы с противоречивыми интересами поляризуются по этническому признаку. Всем известный пример внутригрушювого фаворитизма ...
27977. Мышление как регулятор деятельности и как самостоятельная деятельность Психология управления: объект, предмет, задачи. Основные теоретические школы менеджмента 65.33 KB
  Роль посредника в разрешении конфликтов Психология управления: объект предмет задачи. Поэтому в современном менеджменте навык управления конфликтами рассматривается как один из критически важных для менеджера. Цикл конфликта Первое чему необходимо научиться для успешного управления конфликтом это вовремя распознавать сигналы его эскалации. Схема выбора способа управления конфликтом Уровни конфликта в организации и их источники В любой организации существует несколько уровней конфликтов: внутриличностные межличностные межгрупповые...
27978. Мышление и интеллект, структура интеллекта, тестирование интеллекта и креативности 74.06 KB
  Проблема группы в социальной психологии. Оценка интеллекта Наибольшей популярностью пользуется так называемый коэффициент интеллектуальности сокращенно обозначаемый IQ который позволяет соотнести уровень интеллектуальных возможностей индивида со средними показателями своей возрастной и профессиональной группы. Две другие группы по 16 в каждой результаты которых соответствуют крайним показателям шкалы рассматриваются или как умственно отсталые люди со сниженным интеллектом IQ от 10 до 84 или как обладающие высокими выше среднего...
27979. Диалектическое мышление как высшая форма теоретического мышления 30.93 KB
  Понятие группы основные характеристики групп и их классификация. Детальный анализ социальнопсихологических представлений о природе социальной группы сложившихся в русле различных теоретических ориентации к числу главных отличительных признаков социальной группы позволяет отнести следующие: 1 включенность человеческой общности в более широкий социальный контекст систему общественных отношений определяющих возможность возникновения смысл и пределы существования группы и задающих прямо или от противного модели нормы или правила...
27980. Культурно-историческая детерминация процессов формирования и развития мышления 37.95 KB
  Понятие малой группы ее границы и классификация малых групп. Переход от субъективной группы к объективной Стадия конкретных операций81 2 лет Характеризуется группировкой наглядных представлений появлением обратимости интеллектуальных операций. Понятие форма мышления в которой отражаются общие и притом существенные свойства однородной группы предметов и явлений. Понятие малой группы ее границы и классификация малых групп.
27981. Язык и речь. Виды речи и их психологические характеристика 23.6 KB
  Язык и речь. Например понятия язык и речь часто используются как синонимы. Упрощая можно сказать что язык это иерархически упорядоченная система особых знаков а речь это использование языка людьми то есть деятельность которая выражается либо в устной либо в письменной форме конкретным продуктом речевой деятельности является текст.
27982. Роль внимания в становлении мотивационной сферы личности 51.88 KB
  Маслоу дал стройную классификацию и систему потребностей выделяя их группы: физиологические потребности потребности в безопасности в социальных связях самоуважении самоактуализации. При этом он считает что эти группы потребностей находятся в иерархической зависимости от первой к последней т. о межгрупповом восприятии: это не простая сумма восприятия чужой группы индивидами но именно совершенно новое качество групповое образование .: Для группысубъекта тот кто воспринимает: целостность которая определяется как степень...