75664

Стек і черга. Хеш таблиця

Лабораторная работа

Информатика, кибернетика и программирование

Розробити підпрограми, які забезпечують запити на запис або читання даних з черги, стека або дека. Для організації вказаних структур використовувати масиви або списки. Перевірити працездатність розроблених підпрограм. Послідовність виконання операцій запису або читання вибираються випадково. Порівняти результати роботи, зробити висновки.

Украинкский

2015-01-24

209.96 KB

5 чел.

Міністерство  освіти  і  науки України

Вінницький національний технічний університет

Інститут інформаційних технологій та комп’ютерної інженерії

Кафедра ПЗ

Лабораторна робота №4 варіант №9

з дисципліни Алгоритми та структури даних

Виконала: ст. гр. 1 ПІ-13б                            Лілик Л. С.

Перевірив:                                                       Власюк В. Х.

Вінниця, 2013

Тема: Стек і черга. Хеш таблиця.

Мета: набуття навичок моделювання зв’язаних динамічних структур даних та роботи з ними

Завдання:

Розробити підпрограми, які забезпечують запити на запис або читання даних з черги, стека або дека. Для організації вказаних структур використовувати масиви або списки. Перевірити працездатність розроблених підпрограм. Послідовність виконання операцій запису або читання вибираються випадково. Порівняти результати роботи, зробити висновки.

Варіант № 9.

Розробити підпрограми роботи з пріоритетною чергою. Встановлення запитів в чергу виконується по пріоритету, зняття - з молодших адрес (початок черги). Черга організована на масиві з циклічним заповненням і списку. Пріоритет: мах значення числового параметра, при збігу параметрів - FIFO.

Хід роботи

У програмі у головній функції створюються черги: одна як відображення на масив, інша – на список. Користувачеві пропонується обрати для перегляду одну з цих черг. Крім того, користувач має змогу ввести дані і створити свою чергу. Дані з усіх черг програми виводяться за пріоритетом, який також вказано у вигляді числового поля-ключа для кожного поля даних окремо.

 

Складність алгоритму

Складність алгоритму дорівнює O( 2N +10 ) від Т, де Т - час виконання.


Блок-схема алгоритму


Лістинг програми

//--------------------MAIN.CPP-------

#include "all_the_headers.h"

int main()

{

   int command = 0;

   cout<<"\nTo watch array-queue press 1\nTo watch list-queue press 2\nTo make own queue press 3\nTo exit press 0:  ";

   cin>>command;

   if (command==1)

       {

           // --------------------------------------------

           // -------------------------  queue as arr-----

           // --------------------------------------------

           cout<<"\n~~~~~~~~~~~~~~ How to Make an Omelet ~~~~~~~~~~~~~~\n";

           QueueArr arr;

           int count=0;

           arr.AddElem(*(new Data("Heat a pan.")),42);

           ++count;

           arr.AddElem(*(new Data("Pour in the eggs.")),25);

           ++count;

           arr.AddElem(*(new Data("Crack the eggs and beat them.")),50);

           ++count;

           arr.AddElem(*(new Data("Flip the egg pancake over and cook for another few seconds.")),5);

           ++count;

           arr.AddElem(*(new Data("Take some eggs.")),67);

           ++count;

           arr.AddElem(*(new Data("Transfer the finished omelet to a plate.")),5);

           ++count;

           arr.AddElem(*(new Data("Cook for a minute.")),25);

           ++count;

           arr.AddElem(*(new Data("Add the butter and let it melt.")),30);

           ++count;

           for (int i=0; i<count; ++i)

               cout<<arr.TakeDestroy().name<<endl;

       }

   else if (command==2)

       {

           // --------------------------------------------

           // -------------------------  queue as list----

           // --------------------------------------------

           cout<<"\n~~~~~~~~~~~~~~ How to Make an Omelet ~~~~~~~~~~~~~~\n";

           QueueList list;

           int count=0;

           list.AddElem(new Data("Heat a pan."),42);

           ++count;

           list.AddElem(new Data("Pour in the eggs."),25);

           ++count;

           list.AddElem(new Data("Crack the eggs and beat them."),50);

           ++count;

           list.AddElem(new Data("Flip the egg pancake over and cook for another few seconds."),5);

           ++count;

           list.AddElem(new Data("Take some eggs."),67);

           ++count;

           list.AddElem(new Data("Transfer the finished omelet to a plate."),5);

           ++count;

           list.AddElem(new Data("Cook for a minute."),25);

           ++count;

           list.AddElem(new Data("Add the butter and let it melt."),30);

           ++count;

           for (int i=0; i<count; ++i)

               cout<<list.TakeDestroy()->name<<endl;

       }

       else if (command==3)

       {

           cout<<"\n\nInput number of the units: ";

           int n=0;

           cin>>n;

           QueueArr own;

           for(int i=0; i<n; ++i)

           {

               cout<<"\nInput priority: ";

               int p=0;

               cin>>p;

               own.AddElem(*(new Data("manual")),p);

           }

           cout<<"\n~~~~~~~~~~~~~~ Your own queue ~~~~~~~~~~~~~~\n";

           for (int i=0; i<n; ++i)

               cout<<own.TakeDestroy().name<<endl;

       }

       else return 0;

return 0;

}

//--------------------CLASS_STRUCT.H-------

#ifndef CLASS_STRUCT_H_INCLUDED

#define CLASS_STRUCT_H_INCLUDED

#include "all_the_headers.h"

class Data // data field class

{

public:

string name;

Data(string _name="") // ctot

{

 if (_name.compare("manual") == 0)

          {

             cout<<"Input data: ";

             std::getline(cin, _name);

             std::getline(cin, _name);

          }

 name=_name;

}

~Data() // dtor

{

}

};

// --------------------------------------------

// -------------------------  queue as arr-----

// --------------------------------------------

struct Unit  // unit of queue

{

int key;  // key field

Data elem;  // data field

};

class QueueArr

{

private:

Unit *arr;  // arr of units

int numOfUnit;  // number of units

public:

QueueArr() // ctor

{

 numOfUnit=0;

 arr=0;

}

~QueueArr() // dtor

{

}

   void AddElem(Data &elem, int key)  // add unit to the queue

{

 Unit *temp = new Unit[numOfUnit+1];

 for(int i=0; i<numOfUnit; ++i)

 {

  temp[i]=arr[i];

 }

 temp[numOfUnit].elem=elem;

 temp[numOfUnit].key=key;

 ++numOfUnit;

 delete [] arr;

 arr=temp;

}

Data TakeDestroy()

{

 Unit *tmp = new Unit[numOfUnit-1];

 int j = 0; // counter for the new  arr

 int max = 0;

 Data temp;

 for(int i=0; i<numOfUnit; ++i)

 {

  if(arr[i].key>arr[max].key)

  {

   max = i;

  }

 }

 for(int i=0; i<numOfUnit; ++i)

 {

  if(i!=max)

  {

   tmp[j] = arr[i];

   ++j;

  }

 }

 temp = arr[max].elem;

 delete [] arr;

 arr = tmp;

 --numOfUnit;

 return temp;

}

};

// --------------------------------------------

// -------------------------  queue as list--

// --------------------------------------------

struct ListStr  // sructure for list (element of list)

{

int key;  // key field

Data *elem;   // pointer to the data field

ListStr *next; // pointer to thenext elem

};

class QueueList  // queue list class

{

public:

ListStr *begin;  // pointer to the beginning

QueueList()  // ctor

{

 begin=0;

}

~QueueList() // dtor

{

}

void AddElem(Data *elem, int key)  // add new elem to list

{

 ListStr *cur = begin;

 if(begin==0)

       {

  begin=new ListStr();

  begin->elem=elem;

  begin->key=key;

  begin->next=0;

  return;

 }

 while(cur->next!=0)

 {

  cur=cur->next;

 }

 cur->next=new ListStr();

 cur->next->elem=elem;

 cur->next->key=key;

 cur->next->next=0;

}

Data* TakeDestroy() // get and delete current element from list

{

 ListStr *cur = begin;

 ListStr *max = begin;

 while(cur!=0)

 {

  if(cur->key>max->key)

               max=cur;

  cur=cur->next;

 }

 if(max==begin)

 {

  begin=begin->next;

  return max->elem;

 }

 cur=begin;

 while(cur->next!=max)

 {

  cur=cur->next;

 }

 cur->next=max->next;

 return max->elem;

}

};

#endif // CLASS_STRUCT_H_INCLUDED


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

Висновки

Набуто навички моделювання зв’язаних динамічних структур даних та роботи з ними. В результаті виконання лабораторної роботи було розроблено підпрограму роботи з пріоритетною чергою, організованою як а масиві, так і на списку.


 

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

41156. УЧЕТ ДЕНЕЖНЫХ СРЕДСТВ И ИХ ЭКВИВАЛЕНТОВ 138 KB
  Управление денежными средствами становится все более важным изза огромной сложности финансовых рынков. Правильное раскрытие и классификация денежных средств и их эквивалентов необходимы для точной оценки ликвидности компании. В МСБУ 7 Отчеты о движении денежных средств даны следующие определения денежным средствам их эквивалентам и потокам денежных средств: Денежные средства включают наличные деньги и вклады до востребования. Эквивалент денежных средств краткосрочные высоколиквидные вложения...
41157. Пошук інформації в системі 121.5 KB
  Перегляд тексту документа.Друк тексту документа. Підведення підсумків уроку Яку роботу можна проводити з документами Що таке закладка Що таке інформаційна панель Що таке експорт документів Що таке структура документа Відповіді студентів 2 хв. Перегляд тексту документа.
41158. Влияние отдельных факторов на интенсивность теплоотдачи при пленочной конденсации пара 431.5 KB
  Влияние отдельных факторов на интенсивность теплоотдачи при пленочной конденсации пара. Влияние перегрева пара Конденсация перегретого пара будет иметь место если температура поверхности стенки меньше температуры насыщения. При этом в случае конденсации перегретого пара его температура у стенки постоянно снижается и конденсируется по существу насыщенный пар. В случае конденсации одного килограмма перегретого пара к стенке отводится теплота равная 1337...
41159. Логические функции и логические элементы 754.5 KB
  Физическими аналогами логических переменных 0 и 1 служат сигналы способные принимать два хорошо различимых состояния например потенциал низкого и высокого уровней разомкнутое и замкнутое состояние контакта реле и т. Триггеры Триггер это устройство имеющее два устойчивых состояния способное под воздействием управляющего сигнала скачком переходить из одного состояния в другое и хранить это состояние сколь угодно долго. Способность хранить состояние сколь угодно долго и определяет память триггера. состояние триггера не меняется.
41160. Морфологические и синтаксические нормы русского литературного языка 79 KB
  Морфологические ошибки связаны с нарушением грамматических форм слов незнанием склонений с неправильным употреблением окончаний с неправильным ударением если это влияет на форму слова. Морфологостилистические ошибки связаны с использованием сложных конструкций характерных для официально делового и научного стиля в разговорном стиле.Синтаксические ошибки синтаксическим ошибкам относятся следующие: Нарушения в управлении.
41161. Методы преобразования комплексного чертежа (эпюра Монжа) 286 KB
  Сущность этого метода заключается в следующем: положение точек линий плоских фигур поверхностей в пространстве не изменяется а система П1 П2 заменяется дополняется плоскостями образующими с П1 или П2 или между собой системы двух взаимно перпендикулярных плоскостей принимаемых за плоскости проекций. Если введение одной плоскости П4 или П5 не позволяет решить задачу то прибегают к последовательному дополнению основной системы плоскостей проекций новыми П6 П7 и т. показано преобразование проекций точки А из системы П2 П1 в систему П4...
41162. История лазерных принтеров 1.9 MB
  На поверхности фоторецептора создается электростатическое а затем видимое изображение копируемого оригинала с последующим переносом этого изображения на бумагу или специальный материал. Формирование изображения На этапе формирования изображения на поверхности фоторецептора создается оптическое изображение оригинала. Полученное оптическое изображение должно: а обладать требуемыми геометрическими параметрами б иметь распределение освещенностей соответствующее оптическим плотностям оригинала. Проявление На этапе проявления на участки...
41163. Метод узловых напряжений 192.5 KB
  Метод узловых напряжений. Метод узловых напряжений заключается в определении на основании первого закона Кирхгофа потенциалов в узлах электрической цепи относительного некоторого базисного узла. Положительное напряжение узловых напряжений указывается стрелкой от рассматриваемого узла к базисному. Иллюстрация к методу узловых напряжений.
41164. Власть, влияние, лидерство 198 KB
  Они делают это посредством допущения подчиненных к выработке управленческих решений развитию лидерства в рабочих командах инициативы обучения и т. Лидерство Вопросы лидерства вызывали интерес людей с древних времен. Природа лидерства может быть лучше понята если сравнить лидерство с управлением. Теория лидерских качеств Это один из наиболее ранних подходов к изучению и объяснению лидерства.