Дослідження алгоритмів з використанням різних структур даних: черг та графів - Программирование, компьютеры и кибернетика курсовая работа
Главная
Программирование, компьютеры и кибернетика
Дослідження алгоритмів з використанням різних структур даних: черг та графів
Поняття черги в програмуванні, основні операції з чергою і їх реалізація. Опис алгоритму й специфікація програми. Розробка додатку з використанням задачі Ларсона по опису зв'язного неорієнтованого графа. Алгоритм розв’язку і результати виконання програми.
посмотреть текст работы
скачать работу можно здесь
полная информация о работе
весь список подобных работ
Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Структура даних - програмна одиниця, що дозволяє зберігати і обробляти безліч однотипних і / або логічно пов'язаних даних в обчислювальній техніці. Для додавання, пошуку, зміни та видалення даних структура даних надає деякий набір функцій, складових її інтерфейс. Структура даних часто є реалізацією будь-якого абстрактного типу даних.
При розробці програмного забезпечення велику роль грає проектування сховища даних і представлення всіх даних у вигляді безлічі пов'язаних структур даних.
Добре спроектоване сховище даних оптимізує використання ресурсів (таких як час виконання операцій, на обсяг оперативної пам'яті, число звернень до дискових накопичувачів), необхідних для виконання найбільш критичних операцій.
Структури даних формуються за допомогою типів даних, посилань і операцій над ними в обраному мовою програмування.
Різні види структур даних підходять для різних додатків; деякі з них мають вузьку спеціалізацію для певних завдань. Наприклад, B-дерева зазвичай підходять для створення баз даних, в той час як хеш-таблиці використовуються повсюдно для створення різного роду словників, наприклад, для відображення доменних імен в інтернет-адреси комп'ютерів.
При розробці програмного забезпечення складність реалізації і якість роботи програм істотно залежить від правильного вибору структур даних. Це розуміння дало початок формальним методам розробки та мов програмування, в яких саме структури даних, а не алгоритми, є наріжним архітектури програмного засобу. Велика частина таких мов володіє певним типом модульності, що дозволяє структурам даних безпечно використовуватися в різних додатках. Об'єктно-орієнтовані мови, такі як Java, C # і C + +, є прикладами такого підходу.
Багато класичних структур даних представлені в стандартних бібліотеках мов програмування або безпосередньо вбудовані в мови програмування. Наприклад, структура даних хеш-таблиця вбудована в мови програмування Lua, Perl, Python, Ruby, Tcl і ін. Широко використовується стандартна бібліотека шаблонів STL мови C + +.
Черга в програмуванні -- динамічна структура даних , що працює за принципом "перший прийшов - перший пішов" ( англ. FIFO -- first in, first out). У черги є голова ( англ . head) та хвіст ( англ . tail). Елемент, що додається до черги, опиняється в її хвості. Елемент, що видаляється з черги, знаходиться в її голові.
Така черга повністю аналогічна звичній "базарній" черзі, в якій хто перший встав в неї, той першим буде обслуженим (але, на відміну від реальної черги, імовірність пройти поза чергою виключена)
англ. enqueue -- "поставити в чергу". Операція додавання елемента в "хвіст" черги. При цьому довжина черги збільшується на одиницю. Якщо відбувається намагання додати елемент у вже заповнену чергу, відбувається її переповнення ( англ. queue overflow).
англ. dequeue -- "отримання з черги". Операція, яка повертає елемент з голови та видаляє його з черги, таким чином встановлюючи голову на наступний за видаленим елемент та зменшуючи довжину на одиницю. При намаганні видалити елемент з пустої черги, виникає ситуація "незаповнення" ( англ. queue underflow).
Черга може бути реалізована за допомогою масива Q[1...n], в якому зберігаються дані та двох додаткових змінних head[Q] та tail[Q], в яких зберігаються індекси відповідно "голови" та "хвоста" черги, lenght[Q] -- довжина черги.
Рис.1.2.1. Блок-схема алгоритму роботи програми 1
У випадку коли T < t1 або T < t2 або будь-яка змінна з вхідних даних = 0 вхідні дані задані невірно. У інших випадках йде обрахунок і виводиться на екран результат у вигляді списку, в якому вказаний час та подія яка в цей час відбулася.
Результати виконання показано в відповідному розділі.
У випадку введення невірних даних програма видає відповідне повідомлення про помилку.
В клас стандартного діалогового вікна було додано такі елементи:
Edit1- поле для вводу кількості покупців m
Edit7- поле для вводу періоду часу на якому проводиться дослідження T
StaticText1- текстове поле, в якому виводиться стан черги після виконання програми
Button1 - кнопка за допомогою якої відкривається вікно з детальною умовою поставленої задачі
Button2 - кнопка за допомогою якої формується черга та виводиться результат роботи програми на екран
StaticText - текстові поля які виводять допоміжні повідомлення
В клас стандартного діалогового вікна було додано такі функції:
afx_msg void OnBnClickedButton1() - функція для керування кнопкою 1
afx_msg void OnBnClickedButton2() - функція для керування кнопкою 2
void dodavsja() - функція, що додає до черги покупця
void obslygily() - функція, що вилучає з черги покупця
void pilgoviy() - функція, що додає до черги пільгового покупця
void zvaluv() - функція, що вилучає з черги покупця, який не витримав очікування в черзі
В клас стандартного діалогового вікна було додано такі змінні:
int now_get1 - Змінна для запам'ятовування покупця, який зараз додається до черги
int now_get2 - Змінна для запам'ятовування покупця, який зараз вилучається з черги
int now_time - Змінна, в якій задається текучий час
int real1 - Змінна, в яку записується випадкове значення, з діапазону 1..t1
int real2 - Змінна, в яку записується випадкове значення, з діапазону 1..t2
int real3 - Змінна, в яку записується випадкове значення, з діапазону 1..t3
int real4 - Змінна, в яку записується випадкове значення, з діапазону 1..t4
CString zalushok - рядок для виводу залишку черги
CString str1 - рядок для виводу процесу додавання та обслуговування покупців.
Рис 1.5.1. Результат виконання програми з вхідними даними 1
Рис 1.5.2. Результат виконання програми з вхідними даними 2
Граф -- це сукупність об'єктів із зв'язками між ними.
Об'єкти розглядаються як вершини, або вузли графу, а зв'язки -- як дуги, або ребра. Для різних областей використання види графів можуть відрізнятися орієнтовністю, обмеженнями на кількість зв'язків і додатковими даними про вершини або ребра.
Велика кількість структур, які мають практичну цінність в математиці та інформатиці, можуть бути представлені графами. Наприклад, будову Вікіпедії можна змоделювати за допомогою орієнтованого графу, в якому вершини -- це статті, а дуги (орієнтовані ребра) -- посилання на інші статті.
Першою працею з теорії графів як математичної дисципліни вважають статтю Леонарда Ейлера ( 1736 ), у якій розглядалася задача про Кенігсбергські мости. Наступний імпульс теорія графів отримала близько 100 років потому з розвитком досліджень по електричним мережам, кристалографії , органічній хімії та іншим наукам.
Теорія графів не має стійкої термінології. В різних статтях під одними й тими ж термінами розуміють різні поняття. Наведені нижче визначення є одними з найбільш розповсюджених.
Граф або неорієнтований граф G -- це впорядкована пара G: = (V,E), для якої виконуються наступні умови:
E -- множина пар (у випадку неорієнтованого графу -- невпорядкованих) вершин, які називають ребрами.
V (і так само E) зазвичай вважаються скінченними множинами. Велика кількість результатів, отриманих для скінченних графів, невірна (або інша) для нескінченних графів. Це пов'язано з тим, що певний набір ідей стає хибним у випадку нескінченних множин.
Граф (геометричний граф) -- це фігура на площині , яка складається з непорожньої скінченної множини V точок (вершин) і скінченної множини E орієнтованих чи не орієнтованих ліній (ребер), що з'єднують деякі пари вершин.
Рис 2.2.1. Блок-схема алгоритму роботи програми 2
Залежно від вхідного файлу з даними створюється певна структура даних (граф) з вершинами, що задані у вхідному файлі та з ребрами (зв'язками) між вершинами, які задаються парою вершин у вхідному файлі.
Вигляд вхідного файлу (файл input.txt):
<Вершина1><пробіл><Вершина2> <ентер>
<Вершина1><пробіл><Вершина2> <ентер>
<Вершина1><пробіл><Вершина2> <ентер>
У випадку введення невірних даних (наприклад тексту) програма їх ігнорує.
Всі дані з файлу зберігаються у графі під час роботи програми. При перезагрузці програми необхідно знову сформувани структуру даних з файлу.
Результати виконання показано у відповідному розділі.
В клас стандартного діалогового вікна було додано такі елементи:
Button1 - кнопка за допомогою якої відкривається вікно з детальною умовою поставленої задачі
Button2 - кнопка за допомогою якої формується граф з вхідного файлу та виводиться результат обрахунку на екран
StaticText1- текстове поле яке виводить допоміжне повідомлення (Необхідно )
StaticText2- текстове поле яке виводить кількість необхідних поліцейських
StaticText3- текстове поле яке виводить допоміжне повідомлення (поліцейських.)
StaticText - текстове поле яке виводить допоміжне повідомлення
В клас стандартного діалогового вікна було додано такі функціїї:
afx_msg void OnBnClickedButton1() - функція для керування кнопкою 1
afx_msg void OnBnClickedButton2() - функція для керування кнопкою 2
В клас стандартного діалогового вікна було додано такі змінні:
CString text1 - змінна, що зберігає допоміжне повідомлення (Необхідно )
int int1 - змінна, в яку записується кількість необхідних поліцейських
CString text2 - звінна, що зберігає допоміжне повідомлення (поліцейських.)
int from[500] - змінна, в яку записуються вершини графа
int to[500] - змінна, в яку записуються зв'язки(ребра) графа
Рис. 2.5.1. Текстовий файл з вхідними даними та граф, який під цим розуміється
Рис. 2.3. Результат роботи програми
Виконуючи дану курсову роботу, я закріпив основи роботи з такими структурами даних як черга та граф. Вивчив методи і принципи роботи з ними і алгоритми роботи черги та графа. Закріпив знання про створення проектів MFC.
ГОСТ 19.701-90 (ИСО 5807-85) ЕСПД. Схемы алгоритмов и прог-рамм, данных и систем. Условные обозначения и правила выполнения.
Берзтисс А.Т. Структуры данных . - М.:Статистика, 1974 - 408 с.
А.Ахо, Дж.Хопкрофт, Дж.Ульман, Д.Джеффри. Структуры данных и алгоритмы.; Пер. с англ.- М.:Изд.дом ”Вильямс”, 2001. - 384 с.
Уильям Топп, Уильям Форд. Структуры данных в С++. - М.:Бином, 2000 - 700 с.
Eppstein, David (1999), "Spanning trees and spanners", in Sack, J.-R. & Urrutia, J., Handbook of Computational Geometry, Elsevier, pp. 425-461; Mareљ, Martin (2004), "Two linear time algorithms for MST on minor closed graph classes", Archivum mathematicum Т. 40 (3): 315-320.
http://ru.wikipedia.org/wiki/ Структура _ данных
http://uk.wikipedia.org/wiki/ Черга
http://uk.wikipedia.org/wiki/ Граф _( Структура _ даних )
/**************************************************************\
\**************************************************************/
// диалоговое окно CIPZ_TEODOROVYCH1Dlg
class CIPZ_TEODOROVYCH_course1Dlg : public CDialog
CIPZ_TEODOROVYCH_course1Dlg(CWnd* pParent = NULL);// стандартный конструктор
enum { IDD = IDD_IPZ_TEODOROVYCH1_DIALOG };
virtual void DoDataExchange(CDataExchange* pDX);// поддержка DDX/DDV
// Созданные функции схемы сообщений
afx_msg void OnSysCommand(UINT nID, LPARAM lParam);
/**************************************************************\
\**************************************************************/
// Диалоговое окно CAboutDlg используется для описания сведений о приложении
virtual void DoDataExchange(CDataExchange* pDX); // поддержка DDX/DDV
CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)
void CAboutDlg::DoDataExchange(CDataExchange* pDX)
BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
// диалоговое окно CIPZ_Tostogan_course1Dlg
CIPZ_TEODOROVYCH1Dlg::CIPZ_TEODOROVYCHDlg(CWnd* pParent /*=NULL*/)
: CDialog(CIPZ_TEODOROVYCHDlg::IDD, pParent)
m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
void CIPZ_TEODOROVYCHDlg::DoDataExchange(CDataExchange* pDX)
BEGIN_MESSAGE_MAP(CIPZ_TEODOROVYCH1Dlg, CDialog)
ON_BN_CLICKED(IDC_BUTTON1, &CIPZ_Tostogan_course1Dlg::OnBnClickedButton1)
ON_BN_CLICKED(IDC_BUTTON2, &CIPZ_Tostogan_course1Dlg::OnBnClickedButton2)
// обработчики сообщений CIPZ_TEODOROVYCH1Dlg
BOOL CIPZ_TEODOROVYCHDlg::OnInitDialog()
// Добавление пункта ''О программе...'' в системное меню.
// IDM_ABOUTBOX должен быть в пределах системной команды.
ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
CMenu* pSysMenu = GetSystemMenu(FALSE);
strAboutMenu.LoadString(IDS_ABOUTBOX);
pSysMenu->AppendMenu(MF_SEPARATOR);
pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
// Задает значок для этого диалогового окна. Среда делает это автоматически,
// если главное окно приложения не является диалоговым
SetIcon(m_hIcon, TRUE);// Крупный значок
SetIcon(m_hIcon, FALSE);// Мелкий значок
// TODO: добавьте дополнительную инициализацию
return TRUE; // возврат значения TRUE, если фокус не передан элементу управления
void CIPZ_TEODOROVYCHDlg::OnSysCommand(UINT nID, LPARAM lParam)
if ((nID & 0xFFF0) == IDM_ABOUTBOX)
CDialog::OnSysCommand(nID, lParam);
// При добавлении кнопки свертывания в диалоговое окно нужно воспользоваться приведенным ниже кодом,
// чтобы нарисовать значок. Для приложений MFC, использующих модель документов или представлений,
// это автоматически выполняется рабочей средой.
void CIPZ_TEODOROVYCHDlg::OnPaint()
CPaintDC dc(this); // контекст устройства для рисования
SendMessage(WM_ICONERASEBKGND, reinterpret_cast(dc.GetSafeHdc()), 0);
// Выравнивание значка по центру клиентского прямоугольника
int cxIcon = GetSystemMetrics(SM_CXICON);
int cyIcon = GetSystemMetrics(SM_CYICON);
int x = (rect.Width() - cxIcon + 1) / 2;
int y = (rect.Height() - cyIcon + 1) / 2;
// Система вызывает эту функцию для получения отображения курсора при перемещении
HCURSOR CIPZ_TEODOROVYCHDlg::OnQueryDragIcon()
return static_cast(m_hIcon);
void CIPZ_TEODOROVYCHDlg::OnBnClickedButton1()
// TODO: добавьте свой код обработчика уведомлений
void CIPZ_TEODOROVYCH1Dlg::OnBnClickedButton2()
// TODO: добавьте свой код обработчика уведомлений
/**************************************************************\
\**************************************************************/
MyDialog1(CWnd* pParent = NULL); // стандартный конструктор
virtual void DoDataExchange(CDataExchange* pDX); // поддержка DDX/DDV
/**************************************************************\
\**************************************************************/
IMPLEMENT_DYNAMIC(MyDialog1, CDialog)
MyDialog1::MyDialog1(CWnd* pParent /*=NULL*/)
void MyDialog1::DoDataExchange(CDataExchange* pDX)
DDX_Text(pDX, IDC_STATIC2, zalushok);
BEGIN_MESSAGE_MAP(MyDialog1, CDialog)
ON_BN_CLICKED(IDC_BUTTON1, &MyDialog1::OnBnClickedButton1)
ON_BN_CLICKED(IDC_BUTTON3, &MyDialog1::OnBnClickedButton3)
void MyDialog1::OnBnClickedButton1()
MessageBox("У магазині стоїть черга з m покупців. Час обслуговування покупця з черги - це випадкове ціле число в діапазоні від 1 до t1. Час додавання нового покупця до черги - це випадкове ціле число в діапазоні від 1 до t2.\r\nПромоделювати стан черги:\r\nа) вивести повідомлення про час виникнення подій ( обслуговування та додавання покупця ) за період часу T (T >> t1, T >> t2); \r\nб) показати залишок черги;\r\nв) розв'язати задачу, передбачивши, що через випадковий час від 1 до t3 до початку черги додається „пільговий” покупець, який обслуговується першим, а через випадковий час від 1 до t4 не витримує та йде з черги останній покупець.", "Умова задачі 3.1", MB_OK);
// TODO: добавьте свой код обработчика уведомлений
void MyDialog1::OnBnClickedButton3()
MessageBox("Введіть Т більшим за t1 та t2..", "", MB_OK);
while((now_get2 <= m) && (now_time <= t) && (real1 > 0) && (real2 > 0))
if((now_time < real3) && (now_time < real4))
while(((real2 <= real1) && (now_get1 <= m) && (now_time <= t) ) || (sudden_escape))
if((real1 < real2) && (now_get1 <= now_get2))
if((real1 < real2) && (now_get1 > now_get2) && (now_time <= t) )
////////////////////////////////////////////
zalushok += "В даний момент в черзі стоять покупці ";
zalushok += "В черзі зараз немає покупців.\r\n";
zalushok += "До черги ще не підійшли покупці ";
// TODO: добавьте свой код обработчика уведомлений
str1 += " (1..t2) До черги додався покупець ";
str1 += " (1..t1) Обслужили покупця ";
str1 += " (1..t3) До черги додався покупець ";
str1 += " (1..t4) Не витримав та пішов з черги покупець ";
/**************************************************************\
\**************************************************************/
MyDialog2(CWnd* pParent = NULL); // стандартный конструктор
virtual void DoDataExchange(CDataExchange* pDX); // поддержка DDX/DDV
/**************************************************************\
\**************************************************************/
IMPLEMENT_DYNAMIC(MyDialog2, CDialog)
MyDialog2::MyDialog2(CWnd* pParent /*=NULL*/)
void MyDialog2::DoDataExchange(CDataExchange* pDX)
BEGIN_MESSAGE_MAP(MyDialog2, CDialog)
ON_BN_CLICKED(IDC_BUTTON1, &MyDialog2::OnBnClickedButton1)
ON_BN_CLICKED(IDC_BUTTON2, &MyDialog2::OnBnClickedButton2)
void MyDialog2::OnBnClickedButton1()
MessageBox("Задача Ларсона. Нехай G - кінцевий неорієнтований зв'язний граф. Припустимо, що він являє собою систему тунелів, у яких може ховатися втікач. Група з S поліцейських, рухаючись по тунелях, прагне схопити цього втікача, що може рухатися з будь-якою швидкістю, прагнучи, щоб його не спіймали. Знайти мінімальну кількість поліцейських S, що гарантовано спіймають втікача.", "Умова задачі 5.7", MB_OK);
// TODO: добавьте свой код обработчика уведомлений
void MyDialog2::OnBnClickedButton2()
for (i = 0; (i < 500) && (f.eof() != true); i++)
// TODO: добавьте свой код обработчика уведомлений
Опис методів і алгоритмів вирішення задачі в середовищі розробки Myeclipse. Основні функції програмного продукту, його структура. Розробка алгоритму та програми, інструкція користувачу. Результати тестування, лістинг основних блоків. Вікно головного меню. курсовая работа [1,8 M], добавлен 24.02.2014
Редагування за допомогою текстового редактора NotePad вхідного файлу даних. Програмна реалізація основного алгоритму з використанням засобів об'єктно-орієнтованого програмування. Об’ява та опис класів і об'єктів. Розробка допоміжних програмних засобів. курсовая работа [69,4 K], добавлен 14.03.2013
Основні розрахунки резисторів мікросхеми. Розробка алгоритму рішення задачі методом блок-схем. Характеристика та розробка програми на мові С++ з використанням принципів модульного і структурного програмування. План тестування і налагоджування програми. курсовая работа [2,9 M], добавлен 05.12.2012
Розв’язання нелінійних алгебраїчних рівнянь методом хорд. Опис структури програмного проекту та алгоритмів розв’язання задачі. Розробка та виконання тестового прикладу. Інші математичні способи знаходження коренів рівнянь, та опис виконаної програми. курсовая работа [4,1 M], добавлен 28.09.2010
Розробка програми для вирішення графічної задачі. При вирішенні задачі необхідно cтворювати програму у середовищі програмування Turbo Pascal. Розробка алгоритму функціонування програми і надання блок-схеми алгоритму. Демонстрація роботи програми. курсовая работа [1,3 M], добавлен 23.06.2010
Варіантний аналіз та вибір методів розв’язування, основні поняття та визначення, особливості розробки баз даних. Описовий алгоритм головної програми та її структури, опис авторської заставки. Структура модулів та опис функцій, лістинг програми. курсовая работа [2,6 M], добавлен 30.11.2009
Позначення і назва програми, забезпечення, необхідне для її функціонування. Опис логічної структури, алгоритм, структура. Типи комп'ютерів і пристроїв, що використовуються при роботі програми. Формат, описання та спосіб кодування вхідних і вихідних даних. курсовая работа [163,6 K], добавлен 01.04.2016
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .
© 2000 — 2021
Дослідження алгоритмів з використанням різних структур даних: черг та графів курсовая работа. Программирование, компьютеры и кибернетика.
Реферат: Адресна книга
Сочинение Про Добро И Зло 5 Класс
Реферат: Crucible Essay Research Paper Ever since Hollywood
Курсовая Работа Программирование И Алгоритмизация
Учебное пособие: Основы внутренней и внешней политики фашизма
Технико Экономическое Инвестиционное Обоснование
Контрольная работа по теме Особенности деятельности фондов
Английский Гдз 7 Контрольные Работы
Реферат: Сборник экзаменационных билетов по медицинским предметам и психологии
Курсовая работа: Управление внеоборотными активами на предприятии
Эссе Искусство Зеркало Где Каждый Видит Себя
Шпаргалка: Теория государства и права (шпаргалка)
Алексей Иванов Сочинения
Практическое задание по теме Культура поведения курсанта в кинотеатре
Курсовая Работа На Тему Проектирование Металлорежущего Инструмента
Дипломная работа по теме Международный лицензионный контракт
Проектная Деятельность В Дошкольном Образовании Курсовая
Реферат: Network Mediums Essay Research Paper With the
Контрольная работа: Сахарная свекла – главный источник сахара в России
Курсовая работа: Інформаційна система для аналізу фінансової стійкості
Медицина эпохи Возрождения - Медицина реферат
Разработка системы управления запасами - Маркетинг, реклама и торговля курсовая работа
Понятие культуры - Культура и искусство курсовая работа