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


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

Висновки

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


 

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

25337. Водно-солевой обмен 26.5 KB
  Тело взрослого человека на 5065 состоит из воды у детей на 80 и более. В разных органах и тканях содержание воды на единицу массы Неодинаково. В мышцах воды содержится 70 во внутренних органах 7585 их массы. Наиболее велико и постоянно содержание воды в крови 92.
25338. Витамины 63 KB
  Витамины выполняют в организме различные каталитические функции и требуются в ничтожно малых количествах. В организме животных для которых необходимо поступление с пищей определенного витамина последний или совсем не образуется или же образуется в недостаточных для удовлетворения физиологических потребностей количествах. Источником витаминов в основном являются растения в кот.
25339. ТЕПЛОВОЙ ОБМЕН 33 KB
  Поддержание теплового баланс осуществляется благодаря строгой соразмерности в образовании тепла и в ее отдаче. Способность человека противостоять воздействию тепла и холода сохраняя стабильную температуру тела имеет известные пределы. МЕХАНИЗМЫ ТЕПЛООБРАЗОВАНИЯ Образование тепла в организме происходит главным образом в результате химических реакций обмена веществ. В виде первичного тепла рассеивается 6070 энергии.
25340. ВЫДЕЛИТЕЛЬНЫЕ ПРОЦЕССЫ 48 KB
  Органами выделения у человека являются почки потовые железы легкие кишечник. Выделительные органы почки легкие потовые железы имеют важное значение и в поддержании постоянства концентрации водородных ионов в организме. Поскольку испарение воды с поверхности кожи и альвеол легких понижает температуру тела потовые железы и легкие имеют значение и в терморегуляции. Особое место среди органов выделения занимают сальные и молочные железы.
25341. ПРОЦЕСС МОЧЕОБРАЗОВАНИЯ И ЕГО РЕГУЛЯЦИЯ 29.5 KB
  Процесс фильтрации воды и низкомолекулярных компонентов плазмы через стенки капилляров клубочка происходит только в том случае если давление крови в капиллярах около 70 мм рт. Из 150180 л первичной мочи реабсорбируется около 148178 л воды. Реабсорбции подвергаются кроме воды многие необходимые для организма органические глюкоза аминокислоты витамины и неорганические ионы К N3 Са2 фосфаты вещества. Импульсы от рецепторов почек по симпатическим нервам поступают в гипоталамус где вырабатывается антидиуретический гормон АДГ...
25342. КОЖА И ЕЕ ПРОИЗВОДНЫЕ 30.5 KB
  Различные воздействия воспринимают расположенные в коже терморецепторы механорецепторы ноцицепторы. Первые воспринимают изменение температуры вторые прикосновения к коже третьи болевые раздражения. Расположенные на разной глубине в коже нервные окончания воспринимают прикосновения температурное чувство чувство боли. Распределены рецепторы неравномерно их много в коже кончиков пальцев рук ладоней подошв губ наружных половых органов.
25343. ОБЩАЯ ХАРАКТЕРИСТИКА ЭНДОКРИННОЙ СИСТЕМЫ 31.5 KB
  действием на соседние клетки в пределах одного органа или ткани биологически активных веществ тканевых гормонов гистамина серотомина кининов простагландинов и продуктов клеточного метаболизма например появление при физических нагрузках молочной кислоты в мышцах ведет к расширению в них кровеносных сосудов и увеличению доставки кислорода. В современных условиях концентрацию гормонов в железах крови или моче изучают биологическими ихимическими методами используют ультразвуковое исследований применяют радиоиммунологический метод....
25344. Гипофиз 36 KB
  В аденогипофизе главную секреторную функцию выделяют 5 групп клеток которые вырабатывают 5 специфических гормонов. Среди них выделяют тропные гормоны лат. направление регулирующие функции периферических желез эффекторные гормоны непосредственно действующие на клеткимишени. К тропным гормонам относят следующие: кортикотропин илиадренокортикотропныйгормонАКТГрегулирующий функции коркового слоя надпочечников; тиреотропный гормон ТТГ активизирующий щитовидную железу; гонадотропныи гормон ГТГ влияющий на функции половых желез.
25345. ФУНКЦИИ ВИЛОЧКОВОЙ ЖЕЛЕЗЫ И ЭПИФИЗА 22.5 KB
  Функции эпифиза верхнего мозгового придатка или шишковидной железы связаны со степенью освещенности организма и соответственно имеют четкую суточную периодичность. Мелатонин угнетает функции гипофиза снижая с одной стороны выработку облегающих его функции гипоталамических либеринов а с другой непосредственно угнетая активность аденогипофиза в первую очередь подавляя образование гонадотропинов.