75664

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

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

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

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

Украинкский

2015-01-24

209.96 KB

4 чел.

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

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

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

Кафедра ПЗ

Лабораторна робота №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


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

Висновки

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


 

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

25258. Монізм-плюралізм. Суть „елейської кризи” в античній філософії 27.5 KB
  буття єдине істине нерухоме умоглядне розум та умовиводи. Існує лише буття небуття не існує тотожність мислення і буття. Оскільки небуття не можливо помислити то його не має Пізнання засобами органів відчуттів не достовірне. Апорії Зенона Ахілл і черепаха€ Стріла€: логічно неможливе мислення множинності речей припущення руху приводить до суперечностей Опоненти олеатів сперечалися з постулатами про єдність буття і його нерухомість апелювали до чуттєвоконкретної реальності що є багатоманітною і мінливою.
25259. Суть Сократовських тез 22.5 KB
  Осн заслуга в тому що діалог був осн методом знаходження істини. Даний вислів був переосмислений Сократом і означав 1 відмову від космологічної спекуляції досократиків 2 кореляцію осн постулата інтелектуальної етики Сократа добродетелб есть знание який передбач самопізнання пізнання своєї моральної сутності та її наступна реалізація пізнай хто ти єсть і стань ним шляхом досягнення щастя.
25260. Проблема співвідношення філософії та релігії 67.5 KB
  Спільне філософії і науки: конкретний предмет дослідження; обґрунтовуються особливими способами доказів філософія – верифікація само наукове знання інколи служить доказом філософського принципу; обидва знання – узагальнення ідей але ступінь узагальнення різний філософію часто називають метатеорією теорія теорії; ціль – збагачення досвіду людини; метод абстракції. Відмінності: наука вивчає лише відносне а філософія ще й абсолютне; наукове мислення інтелектуальне а філософське – розумове оскільки про відносне можна знати лише...
25261. Філософія релігії в системі філософських знань і як структурний компонент релігієзнавства. Філософія релігії і реліг. філософія: необхідність їх розрізнення 28.5 KB
  Філософія релігії в системі філософських знань і як структурний компонент релігієзнавства. Філософія релігії і реліг. філософія: необхідність їх розрізнення Філя релігії – подає понятійне тлумачення релігійних феноменів – інтелектуальний вимір релігії. осмисленість феномену релігії.
25262. Спільне філософії і науки 64.5 KB
  Природні релігії. Надприродні релігії. Природні релігії – це релігії які створив людський розум.
25263. Проблема класифікації релігій. Огляд різноманітних типологій релігії 28.5 KB
  Огляд різноманітних типологій релігії Більшість дослідників прагне розподілити релігії за певними критеріями але потрібно відкинути нормативні класифікації розподіл на релігію істинну свою і релігію хибну інших. 3 групи: 1 релігії арійських народів індоєвропейські народи; 2 релігії семітських народів семітськохамітська мовна група; 3 релігії туранських народів народи Уралу і Алтаю. Три релігії природи: чаклунство; брахманізм і буддизм; стадія переходу до релігії свободи – зороастризм єгипетська і фінікійська релігії; 2...
25264. Проблема сутності християнства: огляд різноманітних точок зору. Ідейні передумови появи християнства 30 KB
  Проблема сутності християнства: огляд різноманітних точок зору. Ідейні передумови появи християнства Афанасій Великий: Слово про втілене слово€ і сповідання віри про втіленого Бога дало стійкість християнству€ – це ортодоксальна точка зору. Іша точка зору: Євангеліє формується під грецьким впливом і долає іудаїзм; ІІга точка зору: Євангеліє – це є продовження іудаїзму іудаїзм – єдина основа християнства. Це однією точкою зору є бачення смислу християнства у етичному вченні Ісуса Христа.
25265. Утвердження християнства в Київській Русі. Володимирова версія хрещення Русі: аргументи „за” і „проти” 30 KB
  Утвердження християнства в Київській Русі. Володимирова версія хрещення Русі: аргументи за€ і проти€ Ідеї християнства на територію Східної Європи почали проникати ще за римських часів про що свідчать матеріали археологічних пам’яток Кримського півострова. На Русі знайомство з новою вірою відбулося у ІХ ст. Процес впровадження православ’я на Русі був дуже довгим і не однозначним.
25266. Українське православя: його витоки та особливості історичного розвитку. Православний рух в Україні 90-х рр. XX ст.-початку XXI ст 30 KB
  УАПЦ 1990 незалежна УПЦ Друга половина XVI ст. Філарет веде політику щоб УПЦ отримала автокефалію травень 1992 р. в Харкові Собор єпископів Російської православної церкви на якому Філарет був усунений з кафедри предстоятеля УПЦ. – утворення Української православної церкви Київського патріархату злиття УПАЦ і тих хто підтримував Філарета від УПЦ.