МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
ІНСТИТУТ ПІДПРИЄМНИЦТВА ТА ПЕРСПЕКТИВНИХ ТЕХНОЛОГІЙ
при Національному університеті "Львівська політехніка"
Кафедра ЕОМ
Методичні вказівки і завдання
до курсової роботи
”Структури даних та алгоритми”
з курсу ”Основи інформатики, алгоритмізації та мов програмування ”
для студентів спеціальності
7.091502 "Технологія проблемного та системного програмування"
Затверджено на засіданні кафедри "Електронні обчислювальні машини" Протокол № __ від ________ 2002р.
Львів – 2002
Методичні вказівки і завдання до курсової роботи ”Структури даних та алгоритми” з курсу ”Основи інформатики, алгоритмізації та мов програмування” для студентів спеціальності 7.091502 "Технологія проблемного та системного програмування" / Укл. Лисак Т.А. – Львів: ІППТ, 2002. – 50 с.
Укладач Лисак Т.А., ст. викладач
Рецензенти Березко Л.О., канд.техн.наук, доц.
Мархівка В.С., ст. викладач
Відповідальний за випуск Мельник А.О., д-р техн.наук, проф.
ЗМІСТ
ВСТУП 4
1. ВИМОГИ ДО ПОРЯДКУ ВИКОНАННЯ ТА ОФОРМЛЕННЯ
КУРСОВОЇ РОБОТИ 4
1.1. Вимоги до розробки програмних продуктів 5
1.2. Вимоги до оформлення пояснювальної записки 5
2. ВАРІАНТИ ЗАВДАНЬ 6
2.1. Завдання 1 6
2.2. Завдання 2 8
2.3. Завдання 3 9
СПИСОК ЛІТЕРАТУРИ 9
ВСТУП
Комп’ютер – це машина, що обробляє інформацію. Вивчення засобів програмування передбачає вивчення того, яким чином ця інформація організована всередині ЕОМ, як вона обробляється і як може бути використана. Тому, для вивчення дисципліни студенту особливо важливо зрозуміти концепцію організації даних і роботи з ними.
Програма представляє собою в кінцевому рахунку конкретні формулювання абстрактних алгоритмів, що базуються на конкретних представленнях і структурах даних. Зрозуміло, що рішення про структури даних які необхідно застосувати неможливо прийняти без знання алгоритмів, що застусовуються до цих даних, і навпаки, вибір алгоритмів суттєво залежить від вибраних структур даних. Отже, структури програм і структури даних нерозривно пов’язані.
В курсовій роботі спочатку розглядаються фундаментальні структури які складаються з простих даних. Вони представляють собою компоненти, з яких складаються більш складні структури. Змінні фундаментальної структури можуть змінювати тільки своє значення, зберігаючи незмінною свою форму. Таким чином, розмір пам’яті яку вони займають залишається постійним. Навпаки, ускладнені структури характеризуються зміною не тільки значення, але й форми під час виконання програми. Тому для йх реалізації необхідно застусовувати більш складні прийоми. Послідовний файл займає проміжне значення, поскільки хоча його довжина й змінюється, але ця зміна форми є тривіальною. Поскільки послідовний файл грає важливу роль практично у всіх обчислювальних системах, він буде розглядатись разом з фундаментальними структурами.
В першому завданні курсової роботи досліджується представлення в пам’яті комп’ютера даних статичної структури. Розглядаються прості (цілі, дійсні, символьні, логічні, перелічувані, обмежені) і складові або фундаментальні (масиви, множини, записи, рядки символів, файли) структури даних.
В другому завданні будується одна з більш складних динамічних структур даних (стеки, черги, списки, дерева, графи), розробляються алгоритми і програмні реалізації роботи з нею і за їх допомогою розв’язується прикладна задача.
В другому завданні будується один з методів сортування або пошуку. Досліджуються основні характеристики цього метода і проводиться порівняння ефективностей даного метода і класичних методів. Алгоритмам сортування і пошуку приділяється стільки уваги у зв’язку з тим, щоза їх допомогою можна проилюструвати багато принципів програмування і ситуацій, що виникають і в інших задачах.
Велике значення в курсовій роботі приділяється методиці розробки програмних продуктів і стилю програмування.
Метою курсової роботи є:
- систематизувати, закріпити і розширити теоретичні і практичні знання з програмування, навчитися застосовувати різноманітні структури даних та алгоритми при розв'язанні конкретних прикладних задач;
отримати навики розробки більш складних програмних продуктів і оформлення програмної документації.
1. ВИМОГИ ДО ПОРЯДКУ ВИКОНАННЯ ТА ОФОРМЛЕННЯ
КУРСОВОЇ РОБОТИ
Завдання на курсову роботу видаються студенту керівником курсової роботи індивідуально. Можливе їх корегування керівником під час виконання роботи.
Виконуючи курсову роботу студент повинен розробити, відлагодити та протестувати програму на мові Turbo Pascal (або іншій - узгодивши із керівником курсової роботи) і оформити пояснювальну записку.
1.1. Вимоги до розробки програмних продуктів.
Програма має складатися із двох частин:
- модулів, що містить підпрограми, які реалізують суть кожного завдання;
- тестуючої програми, яка демонструє працездатність основних підпрограм.
Результати тестування мають видаватися у зручному для сприйтяття вигляді (текстовому, табличному, графічному). Текстові значення мають виводитися як на екран відеомонітора, так і в файл (при потребі). Вивід таблиць і графіків теж можна оформити як окремі підпрограми. Таблиці і графіки повинні мати заголовки та зручний для читання вигляд. Як підпрограму доцільно оформити і дії пов'язані із вводом даних необхідних для тестування.
Тестуюча програма повинна мати зручний користувацький інтерфейс, наприклад, вона повинна мати меню. Меню може бути декількаступеневим - після вибору пункту меню вишого рівня, з'являється меню наступного (підпорядкованого) рівня. Для кожного завдання треба передбачити як ввід довільних вхідних даних, так і можливість використання деяких тестуючих значень по замовчуванню. Всі результати, що вводяться або виводяться мають обов’язково супроводжуватись повідомленнями.
Розроблена в курсовій роботі програма повинна легко читатися, відповідати вимогам структурного програмування, всі імена повинні нести змістовне навантаження, коментарів у програмі повинно бути стільки, щоб програма була самодокументованою.
1.2. Вимоги до оформлення пояснювальної записки
Пояснювальна записка повинна бути переплетена у тверду обкладинку.
Пояснювальна записка українською мовою може бути надрукована або написана від руки. В обох випадках текст розміщується на одному боці аркуша паперу формату А4. Рекомендується розміщувати до 30 рядків на сторінці.
Обсяг пояснювальної записки повинен становити 20 - 25 сторінок друкованого тексту або 25 – 30 сторінок рукописного тексту.
На аркушах необхідно залишити поля з усіх чотирьох боків. Розмір лівого поля - 25 мм, правого - не менше 10 мм, верхнього і нижнього - не менше 20 мм.
На аркушах, де починаються розділи, зміст, анотація, вступ, висновки, список літератури рекомендується збільшувати розмір верхнього поля до 40 мм.
Чорнило, яким виконується робота, має бути чорним, фіолетовим чи синім .
Пояснювальна записка має бути стислою, чіткою, лаконічною і містити лише інформацію, яка має пряме відношення до теми курсової роботи.
Рекомендується наступний склад розділів пояснювальної записки:
Титульна сторінка
Завдання на курсову роботу
Анотація
Зміст
Вступ
1. Теоретична частина
2. Опис алгоритму
3. Текст програми
4. Тестування
Висновки
Список літератури
Додатки
В анотації викладаються короткі відомості про курсову роботу. У вступі має приводитися коротка характеристика задач, їх місце і значення в тих галузях, до яких вони мають відношення. В теоретичній частині мають приводитися всі теоретичні дані, які необхідні для розробки алгоритму. Опис алгоритму містить текстові пояснення і блок-схеми алгоритму, які мають виконуватися згідно із стандартами [1]. В тексті програми описується зміст всіх програм і підпрограм, а самі тексти програм поміщаються в додатках.
Текст розділів може розділятися на підрозділи, пункти і підпункти. Розділи повинні нумеруватися арабськими цифрами в межах всієї записки. Вступ, висновки, список літератури і додатки не нумеруються.
Підрозділи необхідно нумерувати арабськими цифрами в межах кожного розділу. Номер підрозділу складається з номера розділу і номера підрозділу, розділених крапкою. Наприклад: "3.1." (перший параграф третього розділу). Пункти (якщо вони використовуються) нуме-руються аналогічно. Наприклад: "3.1.2." (другий пункт першого параграфу третього розділу).
Нумерація сторінок має бути наскрізною: першою сторінкою є титульна сторінка, другою - завдання, третьою - анотація і т.д. Номер сторінки проставляється у верхньому правому куті. На сторінках 1 (титульна сторінка), 2 (завдання), 3 (анотація) і 4 (перша сторінка змісту) номер сторінки не пишеться.
2. ВАРІАНТИ ЗАВДАНЬ
2.1. Завдання 1
Дослідити представлення в пам’яті комп’ютера даних статичної структури. Розглянути основні прості (цілі, дійсні, символьні, логічні) і складові або фундаментальні (масиви, записи, рядки символів) структури даних:
const zz1= місяць народження (дві цифри);
zz2= дві останні цифри року народження; *
zz3= zz2-30;
var b1 : Boolean;
b2 : Wordbool;
b3 : Longbool;
ch : Char;
i1 : Byte;
i2 : Shortint;
i3 : Word;
i4 : Integer;
i5 : Longint;
r1 : Real;
r2 : Single;
r3 : Double;
r4 : Extended;
r5 : Comp;
str : String [15];
p : (Прізвище, Ім’я, По-батькові); **
d : zz1 .. zz2;
m : array [1..2, 1..5] of char;
rec : record
a1, a2 : string[15];
b1, b2, b3 : char;
c1, c2 : integer
end;
s : set of zz1 .. zz3 ;
f : text;
- - - - - - - - - -
* - Замість місяця і року народження підставляти свої конкретні дати (по дві цифри кожна).
** - Замість Прізвище, Ім’я, По-батькові підставляти свої конкретні значення, записані латинськими літерами ( перша літера - велика, решта – малі) .
Тестування провести для наступних значень змінних:
true, якщо день народження парне число;
b1 =
false, якщо день народження непарне число;
b2 := succ(b1);
b3 := pred(pred(b1));
ch – перша літера Прізвища (велика українська літера);
i1 – день народження;
i2 := -i1;
i3 := i1*125;
i4 := -i3;
i5 := -i3;
r1– дробове число: ціла частина – місяць народження, дробова частина - рік народження;
r2 := r1*125;
r3 := -r2;
r4 := r2;
r5 := i5;
{ Наприклад, якщо дата народження 21.10.1982, то:
i1 := 21; i2 := -21; i3 := 2625; i4 := 2625; i5 := -2625;
r1 := 10.1982; r2 := 1274.775; r3 := -1274.775; r4:= 1274.775; r5 := -2625; }
str – Прізвище ( українські літери, перша - велика, решта - малі);
p – Ім’я ( латинські літери, перша - велика, решта - малі);
d – число, яке відповідає дню народження + 15;
m[1,1] – символ, який відповідає першій цифрі номера домашнього телефону;
m[1,2] – символ, який відповідає другій цифрі;
m[1,3] := ’0’;
m[1,4] – символ, який відповідає третій цифрі;
m[1,5] := ’0’;
m[2,1] := ’0’;
m[2,2] - символ, який відповідає четвертій цифрі;
m[2,3] := ’0’;
m[2,4] - символ, який відповідає п’ятій цифрі;
m[2,5] - символ, який відповідає шостій цифрі;
{Якщо домашнього телефону немає, обрахунки проводити для кафедрального телефону,
його номер 398196: m[1,1]:=’3’; m[1,2]:=’9’; m[1,4]:=’8’; m[2,2]:=’1’; m[2,4]:=’9’; m[2,5]:=’6’;}
rec.a1 – назва міста в адресі прописки ( українські літери, перша - велика, решта - малі);
rec.a2 – назва вулиці в адресі прописки ( українські літери, перша - велика, решта - малі);
rec.с1 – номер будинку в адресі прописки;
rec.с2 – номер квартири в адресі прописки;
rec.b1 := ’,’ ;
rec.b2 := ’,’ ;
rec.b3 := ’/’ ;
S – множина всіх чисел кратних k з діапазону zz1 .. zz3,
( k = № mod 5 + 2 , де № - порядковий номер студента в журналі викладача );
2.2. Завдання 2
Реалізувати один із вказаних нижче методів сортування або пошуку в послідовності, представленій у вигляді масиву чисел або у вигляді лінійного однозв’язаного списку, елементи якого містять по декілька інформаційних полів (в загальному випадку – велики об’єми інформації), одне з яких є ключовим, і всі зміни положення елементів в послідовності виконуються не перестановкою самих елементів, а перестановкою їх зв’язків..
Намалювати схему алгоритму для конкретного прикладу послідовності з десяти цілих чисел зі знаком.
Дослідити метод на стійкіть.
Дослідити ефективність метода. Для цього визначити середні значення кількості порівнянь, кількості перестановок і часу виконання. Порівняти отримані характеристики з аналогічними даними для основних простих методів сортування (вставки, вибору, обміну), зробити висновки про ефективність метода, що досліджується.
Дослідити метод на економність використання пам’яті.
Дослідити метод на можливу специфіку вхідної послідовності (чи може послідовність містити елементи з одинаковими ключами, чи має бути вхідна послідовність частково відсортована, чи мають елементи послідовності знаходитись у певному діапазоні і т.п.).
Методи cортування:
Сортування методом підрахунку порівнянь [6, 94-97 c.].
Сортування методом підрахунку розпреділення [6, 97-98 c.].
Сортування методом вставки у список [6, 116-117 c.].
Сортування з обчисленням адреси [6, 118-121 c.], [8, 469-472 c.].
Обмінне сортування зі злиттям [6, 131-133 c.].
Обмінне порозрядне сортування [6, 144-150 c.].
Сортування методом двохшляхового злиття [6, 181-182 c.].
Сортування методом природнього двохшляхового злиття [6, 183-185 c.].
Сортування методом простого двохшляхового злиття [6, 186-187 c.].
Сортування методом злиття списків [6, 187-189 c.].
Порозрядне сортування списку [6, 195-200 с.]
Сортування за допомогою вставок і злиття [6, 208-210 c.].
Сортування методом квадратичного вибору [11, 71-72 c.].
Швидке сортування [11, 72-73 c.].
Розподільне сортування [11, 73-75 c.].
Бітове сортування [11, 75 c.].
Бінарне сортування [11, 75-76 c.].
Сортування злиттям списків [11, 76 c.].
Сортування злиттям [11, 76-78 c.].
Сортування вставками, що використовує бінарний пошук [8, 473 c., 495-497 с.].
Сортування Шелла, що використовує кроки 3, 2 і 1 [8, 466-469 c.].
Сортування Шелла, що використовує кроки 8, 4, 2 і 1 [8, 466-469 c.].
Сортування Шелла, що використовує кроки 7, 5, 3 і 1 [8, 466-469 c.].
Сортування Шелла, що використовує кроки 13, 4 і 1 [8, 466-469 c.].
Сортування двохшляховими вставками [8, 472-473 c.].
Сортування злиттям вставок [8, 473 c.].
Сортування простим злиттям [8, 474-477 c.].
Порозрядне обмінне сортування [8, 477-478 c.].
Порозрядне сортування [8, 478-481 c.].
Сортування бінарним злиттям [8, 482 c.].
Сортування бінарним злиттям [8, 482 c.].
Зовнішні методи cортування :
Швидке сортування рядків [11, 167-170 c.].
Сортування методом збалансованого багатошляхового злиття [3, 122-128 c.].
Багатофазне сортування [3, 128-141 c.], [6, 294-300 c.].
Осцилююче сортування [6, 340-3345 c.].
Сортування методом розпреділення початкових серій [3, 141-147 c.].
Сортування методом каскадного злиття [3, 148-149 c.] , [6, 315-325 c.].
Сортування методом вибору з заміщенням [6, 284-285 c.].
Методи пошуку :
m-Блочний пошук [11, 113 c.].
Пошук медіани [3, 103-105 c.].
Індексно-послідовний пошук [8, 493-495 c.].
Пошук методом обчислення адрес (розв’язок колізій при хешуванні методом відкритої адресації ) [8, 530-534 c.], [6, 562-568 c.].
Пошук методом обчислення адрес (розв’язок колізій при хешуванні методом ланцюжків) [8, 534-536 c.], [6, 557-562 c.].
Пошук найменьшого елемента за допомогою метода швидкого сортування [6, 131 c.(31.)].
Швидкий послідовний пошук [6, 430-431 c.].
Зчеплений пошук [6, 440-441 c.].
Однорідний бінарний пошук [6, 447-449 c.].
Пошук Фібоначчі [6, 450-452 c.].
Променевий пошук [6, 527-531 c.].
Цифровий пошук зі вставкою по дереву [6, 532-534 c.].
2. 3. Завдання 3
Побудувати базову структуру даних і алгоритми роботи з нею. Застусувати їх для розв’язку однієї з наступних задач згідно варіанту.
Многочлен виду EMBED Equation.3 , де EMBED Equation.3 представити у вигляді зв’язаного списка в якому кожний елемент має три поля: одне – для коефіцієнта Сi , друге – для показника степеня ni , третє – для вказівника на наступний елемент списку. Для описаного представлення многочленів написати програму їх диференціювання.
Многочлен виду EMBED Equation.3 , де EMBED Equation.3 представити у вигляді зв’язаного списка в якому кожний елемент має три поля: одне – для коефіцієнта Сi , друге – для показника степеня ni , третє – для вказівника на наступний елемент списку. Для описаного представлення многочленів написати програму додавання і множення многочленів.
Група людей стоїть в колі, і кожний вибирає ціле додатнє число. Вибирається одне з їх іменів і додатнє число n. Відрахунок починається за годинниковою стрілкою, починаючи з людини з вибраним ім’ям. При цьому n-а людина виключається із кола. Вибране цією людиною додатнє число використовується для продовження рахунку. Кожен раз при вилученні наступної людини вибране нею число використовується для визначення наступного вилучаємої людини. Наприклад, будем вважати, що маємо 5 людей– А,В,С,D і Е і вони вибирали числа 3,4,6,2 і 7 відповідно. Також спочатку було вибрано число 2 і людина А. Тоді, якщо рахунок був початий з А, порядок виключення людей із кола буде В,А,Е,С. Останнім в колі залишиться D.Напишіть програму, яка зчитує групу рядків з операторами DATA. Кожен оператор DATA, за виключенням першого, містить ім’я учасника і вибране ім додаткове ціле число.
Напишiть програму, що моделює обчислювальну систему з кiлькома користувачами настпним чином. Кожен користувач має свiй унiкальний iдетифiкацiйний номер ID i бажає виконати на ЕОМ ряд операцiй. У будь-який момент часу ЕОМ може виконуватитiльки одну операцiю. Кожна вхiдна стрiчка вiдповiдає одному користувачу i мiстить його ID, за яким йде прчаток роботи а за ним - набiр цiлих чисел, кожне з яких є часом виконання операцiї. Вхiднi даннi впорядкованi по зростанню часу початку роботи. Всi часи заданi в секундах. Будемо вважати, що користувач не видає запросу на проведення наступної операцiї до тих пiр, поки не закiнчилось виконання минулої, а еом виконує операцiї за принципом "перший, що поступив, обслуговується першим". Програма повинна iмiтувати роботу системи i виконувати повiдомлення, що мiстять ID користувача i час початку i закiнчення проведення операцiї. В кiнцi процесу моделювання програма повинна вивести середнмй час очiкування для кожної операцiї. (Часом очiкування називається рiзниця мiж тим часом, коли був виданий запрос на виконання операцiї, i початком її виконання.
Фірма АВС по зберіганню і збуту побутових інструментів і пристосувань дістає вантажі з товарами по різних цінах. Фірма продає їх потім з 20% надбавкою, причому товари, які вона дістала швидше, продаються в першу чергу(стратегія "який першим прийшов-першим продається"). Товари з першої партії вантажу продаються по ціні, що на 20% перевищує купівельну. Після того, як вся партія цілковито продана, беруть другу, також по збільшеній на 20% ціні і т.д. Напишіть програму, яка зчитує записи про торгові операції двох типів: операції по закупівлі і операції по продажу. Запис про продаж має префікс "S" і кількість товару, а також ціну даної партії. Запис про купівлю має префікс "R", кількість товару, ціну одного виробу і загальну ціну всієї партії. Після зчитування запису про закупівлю надрукуйте її. Після зчитування запису про операції продажу, надрукуйте її і повідомте про ціну, по якій були продані вироби. Якщо кількість товару на складі не достатньо для виконання заказу, то продаються всі товари що є і друкується повідомлення: (ххх одиниць товару відсутні на складі).
Написати алгоритм, що визначає, чи має сиимвольна стрiчка, що вводиться, вигляд x C y де x - стрiчка, що складається з букв A i B, а y - стрiчка, обернена до стрiчки x (наприклад, якщо x = ABABBA, то y опвинна дорiвнювати ABBABA). При читаннi можна зчитувати тiльки кожен наступний елемент стрiчки.
Написати алгоритм, що визначає, чи має сиимвольна стрiчка, що вводиться, наступну форму: a D b D c D ... D z де кожна стрiчка a, b, c, ..., z має форму срiчки, визначену в задачi 1.4 (Отже, стрiчка має правильну форму, якщо вона складається з будь-якої кiлькостi подiбних стрiчок, що роздiленi символом "D".) При читаннi можна зчитувати тiльки кожен наступний елемент стрiчки. (Задача 1.4. Написати алгоритм, що визначає, чи має сиимвольна стрiчка, що вводиться, вигляд x C y де x - стрiчка, що складається з букв A i B, а y - стрiчка, обернена до стрiчки x (наприклад, якщо x = ABABBA, то y опвинна дорiвнювати ABBABA). При читаннi можна зчитувати тiльки кожен наступний елемент стрiчки.
СПИСОК ЛІТЕРАТУРИ
ГОСТ 19.701-90 (ИСО 5807-85) ЕСПД. Схемы алгоритмов и программ, данных и систем. Условные обозначения и правила выполнения.
Берзтисс А.Т. Структуры данных . –М.:Статистика, 1974 - 408 с.
Вирт Н. Алгоритмы + структуры данных = програмы. –М.:Мир,1985 - 406 с.
Гудзь Р.В., Ярошко С.А. Використання динамічних даних у програмах на Borland Pascal. Тексти лекцій. –Львів.: ЛНУ ім.Ів.Франка, 2000 - 54 с.
Кнут Д. Искусство програмирования, том 1. Основные алгоритмы. –М.:Изд.дом ”Вильямс”, 2001. – 720 с.
Кнут Д. Искусство програмирования, том 3. Сортировка и поиск. –М.: Изд.дом ”Вильямс”, 2001. – 832 с.
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы , построение и анализ. Классические учебники: computer science – 2001. - 860 с.
Ленгсам Й., Огенстайн М., Тененбаум А. Структура данных для персональных ЭВМ. –М.:Мир, 1989 - 560 с.
Матьяш В.А., Путилов В.А., Фильчакрв В.В., Щекин С.В. Структуры и алгоритмы обработки данных. Учебное пособие. – Апатиты, КФ ПетрГУ, 2000 - 80 с.
Марченко А.И., Марченко Л.А. Програмирование в среде Turbo Pascal 7.0. –К.:Век+, 1999 - 460 с.
Проценко В.С., Чаленко П.Й., Ставровський А.Б. Техніка програмування мовою Сі. –К:Либідь, 1993 - 224 с.
Семотюк В. Програмування в середовищі Турбо Паскаль. –Львів:БаК, 2000 - 248 с.
Семашко Г.Л., Салтыков А.И. Програмирование на языке Паскаль. –М.:Наука, 1988 - 125 с.
Трамбле Ж., Соренсон П. Введение в структуры данных. –М.:Машиностроение, 1982 - 784 с.
Уильям Топп, Уильям Форд. Структуры данных в С++. –М.:Бином, 2000 - 700 с.