48047

Методичні вказівки. Програмування

Конспект

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

В ході самостійної підготовки, що передує курсовій роботі, вивчається лекційний та допоміжний матеріал, проводиться аналіз завдання, виконується розробка алгоритму його вирішення та підготовлюється вихідний текст програми на паперовому та електронному носії

Украинкский

2013-12-06

189.5 KB

1 чел.

- 22 -

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

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

Інститут комп'ютерних систем

Кафедра "Комп'ютерних інтелектуальних систем та мереж"

Методичні вказівки

до курсової роботи
з дисципліни "Програмування"

для студентів спеціальності 7.091501

Мови С та С++

2010


Методичні вказівки до курсової роботи з дисципліни "Програмування" для студентів денної форми навчання спеціальності 7.091501. Укл.: О.В. Олещук. Одеса: ОНПУ, 2010.

Укладач:  О.В. Олещук, доц.


Вступ

Метою даної курсової роботи є закріплення та доповнення лекційного матеріалу, а також виробіток у студентів навичок вирішення основних завдань програмування на мовах С та С++.

Для курсової роботи наведені теоретичні та довідкові положення, приклади рішень типових задач та завдання до курсової роботи. Номер завдання відповідає порядковому номеру за журналом.

В ході самостійної підготовки, що передує курсовій роботі, вивчається лекційний та допоміжний матеріал, проводиться аналіз завдання, виконується розробка алгоритму його вирішення та підготовлюється вихідний текст програми на паперовому та електронному носії.

Курсова робота виконується на протязі семестру. Розробка структури даних та алгоритмів для роботи з нею відноситься до першого модулю і оцінюється у 30 балів. Написання програми та контрольних прикладів для її тестування – до другого модулю і оцінюється у 30 балів. На захист роботи відводиться 40 балів. За помилки, як при виконанні роботи так і при її захисті, оцінка може зменшуватися.

1. Теоретичні відомості

1.1. Динамічні структури даних

Динамічні структури за визначенням характеризуються відсутністю фізичної суміжності елементів структури в пам'яті непостійністю і непередбачуваністю розміру (числа елементів) структури в процесі її обробки [1-2]. У цьому розділі розглянуті особливості динамічних структур, визначувані їх першою характерною властивістю. Особливості, пов'язані з другою властивістю розглядаються в останньому розділі даного розділу.

Оскільки елементи динамічної структури розташовуються по непередбачуваних адресах пам'яті, адреса елементу такої структури не може бути обчислений з адреси початкового або попереднього елементу. Для встановлення зв'язку між елементами динамічної структури використовуються покажчики, через які встановлюються явні зв'язки між елементами. Таке представлення даних в пам'яті називається зв'язним. Елемент динамічної структури складається з двох полів:

  •  інформаційного поля або поля даних, в якому містяться ті дані, ради яких і створюється структура; у загальному випадку інформаційне поле само є інтегрованою структурою - вектором, масивом, записом і т.п.;
  •  поле зв'язок, в якому містяться один або декілька покажчиків, що пов'язує даний елемент з іншими елементами структури;

Коли зв'язне представлення даних використовується для вирішення прикладного завдання, для кінцевого користувача "видимим" робиться тільки вміст інформаційного поля, а поле зв'язок використовується тільки програмістом-розробником.

Достоїнства зв'язного представлення даних - в можливості забезпечення значної мінливості структур;

  •  розмір структури обмежується тільки доступним об'ємом машинної пам'яті;
  •  при зміні логічній послідовності елементів структури потрібне не переміщення даних в пам'яті, а тільки корекція покажчиків.

Разом з тим зв'язне уявлення не позбавлене і недоліків, основні з яких:

робота з покажчиками вимагає, як правило, вищої кваліфікації від програміста;

  •  на поля зв'язок витрачається додаткова пам'ять;
  •  доступ до елементів зв'язної структури може бути менш ефективним за часом.

Останній недолік є найбільш серйозним і саме їм обмежується застосовність зв'язного представлення даних. Якщо в суміжному представленні даних для обчислення адреси будь-якого елементу нам у всіх випадках достатньо було номери елементу і інформації, що міститься в дескрипторі структури, то для зв'язного уявлення адреса елементу не може бути обчислений з початкових даних. Дескриптор зв'язної структури містить один або декілька покажчиків, що дозволяють увійти до структури, далі пошук необхідного елементу виконується проходженням по ланцюжку покажчиків від елементу до елементу. Тому зв'язне уявлення практично ніколи не застосовується в завданнях, де логічна структура даних має вид вектора або масиву - з доступом по номеру елементу, але часто застосовується в завданнях, де логічна структура вимагає іншої початкової інформації доступу (таблиці, списки, дерева і так далі).

1.2. Зв'язні лінійні списки

Списком називається впорядкована множина, що складається із змінного числа елементів, до яких застосовні операції включення, виключення. Список, що відображає відносини сусідства між елементами, називається лінійним. Якщо обмеження на довжину списку не допускаються, то список представляється в пам'яті у вигляді зв'язної структури. Лінійні зв'язні списки є простими динамічними структурами даних.

Графічно зв'язок в списках зручно зображати за допомогою стрілок [3]. Якщо елемент не пов'язаний ні з яким іншим елементом, то в полі покажчика записують значення, не вказуюче ні на який елемент. Таке посилання позначається спеціальним ім'ям - null (в деяких мовах програмування - nil).

1.2.1. Машинне представлення зв'язних лінійних списків

На рис. 1.1 приведена структура односвязного списку. На нім поле INF - інформаційне поле, дані, NEXT - покажчик на наступний елемент списку. Кожен список повинен мати особливий елемент, званий покажчиком початку списку або головою списку, який зазвичай по формату відмінний від решти елементів. У полі покажчика останнього елементу списку знаходиться спеціальна ознака null, що свідчить про кінець списку.

Рис.1.1. Структура односвязного списку

Проте, обробка односвязного списку не завжди зручна, оскільки відсутня можливість просування в протилежну сторону. Таку можливість забезпечує двозв'язний список, кожен елемент якого містить два покажчики: на наступний і попередній елементи списку. Структура лінійного двозв'язного списку приведена на рис. 1.2, де поле NEXT - покажчик на наступний елемент, поле PREV - покажчик на попередній елемент. У крайніх елементах відповідні покажчики повинні містити null, як і показано на рис. 1.2.

Ріс.1.2. Структура двозв'язного списку

Для зручності обробки списку додають ще один особливий елемент - покажчик кінця списку. Наявність двох покажчиків в кожному елементі ускладнює список і приводить до додаткових витрат пам'яті, але в той же час забезпечує ефективніше виконання деяких операцій над списком.

Різновидом розглянутих видів лінійних списків є кільцевий список, який може бути організований на основі як односвязного, так і двозв'язного списків. При цьому в односвязном списку покажчик останнього елементу повинен указувати на перший елемент; у двозв'язному списку в першому і останньому елементах відповідні покажчики перевизначаються, як показано на рис.1.3.

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

Ріс.1.3. Структура кільцевого двозв'язного списку

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

1.3. Дерева

1.3.1. Основні визначення

Дерево - це граф, який характеризується наступними властивостями:

1. Існує єдиний елемент (вузол або вершина), на який не посилається ніякий інший елемент, і який називається коренем.

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

3. На кожен елемент, окрім кореня, є єдине посилання, тобто кожен елемент адресується єдиним покажчиком.

1.3.2. Бінарні дерева

Існують m-арне дерева, тобто такі дерева у яких напівступінь результату кожної вершини менше або рівна m (де m може бути рівне 0,1,2,3 і так далі). Якщо напівступінь результату кожної вершини в точності рівний або m, або нулю, то таке дерево називається повним m-арним деревом.

При m=2 такі дерева називаються відповідно бінарними, або повними бінарними. На малюнку 1.4(a) зображено бінарне дерево, 1.4(b) - повне бінарне дерево, а на 6.12(c) показані всі чотири можливі розташування синів деякої вершини бінарного дерева.

Рис. 1.4. Зображення бінарних дерев

Бінарні дерева, зображені на ріс.1.4(a) і 1.4(d), є різними позиційними деревами, хоча вони не є різними впорядкованими деревами.

У позиційному бінарному дереві кожна вершина представлена єдиним чином за допомогою рядка символів над алфавітом {0,1}, при цьому корінь характеризується порожнім рядком. Будь-який син вершини "u" характеризується рядком, префікс (початкова частина) якого є рядком, характеризуючою "u".

Прикладом бінарного дерева є фамільне дерево з отцем і матерью людини як його нащадки. Ще один приклад - це арифметичний вираз з двомісними операціями, де кожна операція є вузлом, що гілкується, з операндами як піддерева.

Представити m-арне дерево в пам'яті ЕОМ складно, оскільки кожен елемент дерева повинен містити стільки покажчиків, скільки ребер виходить з вузла (при m-3,4.5.6... відповідає 3,4,5,6... покажчиків). Це приведе до підвищеної витрати пам'яті ЕОМ, різноманітності початкових елементів і ускладнить алгоритми обробки дерева. Тому m-арне дерева необхідно привести до бінарних для економії пам'яті і спрощенню алгоритмів [4]. Всі вузли бінарного дерева представляються в пам'яті ЕОМ однотипними елементами з двома покажчиками, крім того, операції над двійковими деревами виконуються просто і ефективно.

2. Зміст пояснювальної записки

  1.  Титульний лист.
  2.  Анотація.
  3.  Зміст.
  4.  Вступ.
  5.  Теоретичні відомості про динамічні структури даних.
  6.  Основний розділ (розробка).
    1.   Опис обраної структури даних.
    2.   Опис алгоритму і програми.
    3.   Контрольні приклади.
    4.   Керівництво користувача.
  7.  Висновки
  8.  Перелік літератури.
  9.  Тексти програм.
  10.   Схеми алгоритмів.

Тексти програм і схеми алгоритмів оформлюються як додатки до пояснювальної записки. Схеми алгоритмів оформлюються на двох листах формату А1.

3. Приклади програм

3.1. Черга

#include <iostream.h>

#include <conio.h>

// Структура елементу черги.

struct Tqueue {

 int Info;// інформаційне поле.

 Tqueue* Next;// покажчик на наступний елемент в черзі.

};

// Покажчик на голову черги. Спочатку рівний NULL, оскільки черга порожня.

Tqueue* Head = NULL;

// Покажчик на хвіст черги. Спочатку рівний NULL, оскільки черга порожня.

Tqueue* Tail = NULL;

// Фунция додавання елементу в чергу.

void Add(int Value){// Value - значення, яке потрібно помістити в чергу.

 Tqueue* Newrecord = new Tqueue;// Створюється новий елемент черги.

 Newrecord->info = Value;// Заповнюється інформаційне поле.

 Newrecord->next = NULL;// Після Newrecord елементів немає.

 if (Tail) // Якщо черга не порожня, то

 Tail->next = Newrecord;// наступним елементом після хвоста черги

// стає Newrecord

 else Head = Newrecord;// інакше Newrecord стає головою черги.

 Tail = Newrecord;// Newrecord стає хвостом черги.

}

// Функція читання елементу з черги з видаленням.

// Повертає 1, якщо черга не порожня, і 0 - якщо порожня.

char Del(int &Value){// в Value поміщається прочитане значення.

 if (Head) {// Перевірка, чи не порожня черга.

 Value = Head->info;// Читаємо інформаційне поле з голови черги.

 Tqueue* Temp = Head;// Запам'ятовуємо покажчик на голову черги.

 Head = Head->next;// Встановлюємо як голову черги елемент

// який був наступним після голови.

 delete Temp;// Видаляємо елемент, який був головою черги.

 if (!Head) Tail = NULL; // Якщо був лічений останній елемент черги

// то обнуляємо хвіст.

 return 1;// Читання успішне.

 

 else return 0;// Повертаємо значення, що повідомляє про спробу читання з порожньої черги.

}

int main() {

 Add(1);// Вносимо до черги значення 1,2,3

 Add(2);

 Add(3);

// Намагаємося прочитати з черги 4 значення.

// Набуваємо значень 3,2,1 і повідомлення про порожню чергу.

 int а = 0;

 for (int i=0; i<4; i++) {

 if (Del(a))

 cout << а << endl;

 else cout << "Queue is empty";

 

 return 0;

}

3.2. Стек

#include <iostream.h>

#include <conio.h>

// Структура елементу стека.

struct Tstack {

 int Info;// інформаційне поле.

 Tstack* Next;// покажчик на наступний елемент в списку.

};

// Покажчик на вершину стека. Спочатку рівний NULL, оскільки стек порожній.

Tstack* First = NULL;

// Фунция додавання елементу в стек

void Push(int Value){// Value - значення, яке потрібно помістити в стек.

 Tstack* Newrecord = new Tstack;// Створюється новий елемент стека.

 Newrecord->info = Value;// Заповнюється інформаційне поле.

 Newrecord->next = First;// Наступним елементом після знов створеного

// стає елемент, який раніше був у вершині стека.

 First = Newrecord;// Як вершина стека встановлюється Newrecord.

}

// Функція читання елементу із стека з видаленням.

// Повертає 1, якщо стік не порожній, і 0 - якщо порожній.

char Pop(int &Value){// в Value поміщається прочитане значення.

 if (First) {// Перевірка, чи не порожній стек.

 Value = First->info;// Читаємо інформаційне поле з елементу у вершині стека.

 Tstack* Temp = First;// Запам'ятовуємо покажчик на перший елемент в стеку.

 First = First->next;// Встановлюємо як вершину стека елемент

// який був наступним після вершини.

 delete Temp;// Видаляємо елемент, який був вершиною стека.

 return 1;// Читання успішне.

 

 else return 0;// Повертаємо значення, що повідомляє про спробу читання з порожнього стека.

}

int main() {

 Push(1);// Вносимо до стека значення 1,2,3

 Push(2);

 Push(3);

// Намагаємося прочитати із стека 4 значення.

// Набуваємо значень 3,2,1 і повідомлення про порожній стек.

 int а = 0;

 for (int i=0; i<4; i++) {

 if (Pop(a))

 cout << а << endl;

 else cout << "Stack is empty";

 

 return 0;

}

3.3. Дерево

#include <iostream.h>

#include <conio.h>

// Структура елементу дерева.

struct Ttree {

 int Info;// інформаційне поле.

 Ttree* Brother;// покажчик на наступного за старшинством брата.

 Ttree* Son;// покажчик на старшого сина.

};

// Покажчик на корінь дерева. Спочатку рівний NULL, оскільки дерево порожнє.

Ttree* Root = NULL;

// Додавання елементу в дерево.

// Parent - батьківський елемент. Якщо він рівний NULL 

// то відбувається додавання в корінь.

// Value - значення, записуване в інформаційне поле.

void Add(Ttree* Parent, int Value)

{

 Ttree* Newrecord = new Ttree;// Створюється новий елемент дерева.

 Newrecord->info = Value;// Заповнюється інформаційне поле.

 Newrecord->son = NULL;// Покажчик на сина обнуляється.

 if (Parent) {// Якщо існує батьківський елемент

// то його братом стає старший син його батька.

 Newrecord->brother = Parent->son;

// Створений елемент стає сином елементу Parent.

 Parent->son = Newrecord;

 

 else {// Якщо батьківського елементу не існує

// то братом створеного елементу стає корінь дерева.

 Newrecord->brother = Root;

// Створений елемент стає коренем.

 Root = Newrecord;

 

}

// Пошук елементу.

// Повертає покажчик на знайдений елемент або NULL 

// якщо шуканий елемент не існує.

// Вважаємо, що поле Info має унікальне значення у кожного елементу дерева.

// Currentroot - поточний корінь дерева.

// Value - значення, яке повинне міститися в полі Info шуканого елементу.

Ttree* Find(Ttree* Currentroot, int Value)

{

// Якщо поточний корінь дерева існує

 if (Currentroot) {

// то перевірятимуться, чи співпадає його поле Info із значенням Value.

// Якщо співпадає, то повертається покажчик на поточний корінь.

 if (Currentroot->info == Value) return Currentroot;

 else {// Інакше здійснюється пошук в поддереве, де

// коренем є Currentroot->son.

 Ttree* Temp = Find(Currentroot->son,value);

// Якщо значення Temp не нульове, означає шуканий елемент

// знайдений в поддереве з коренем Currentroot->son.

// Тоді Temp повертається як відповідь.

 if (Temp) return Temp;

// Інакше повертається покажчик, знайдений в поддереве

// з коренем Currentroot->brother.

 else return Find(Currentroot->brother,value);

 

 

// Якщо поточний корінь не існує, повертається NULL.

 else return NULL;

}

// Відображає дерево на екрані.

// Currentroot - покажчик на поточний корінь.

void Show(Ttree* Currentroot)

{

// Якщо поточний корінь існує, то

 if (Currentroot) {

// значення поля Info поточного кореня виводиться на екран.

 cout << Currentroot->info << " ";

// Виводиться поддерево з коренем Currentroot->son.

 Show(Currentroot->son);

// Виводиться поддерево з коренем Currentroot->brother.

 Show(Currentroot->brother);

 

}

// Видаляє всі вузли дерева.

// Currentroot - покажчик на поточний корінь.

void Clear(Ttree* Currentroot)

{

// Якщо поточний корінь існує, то

 if (Currentroot) {

// Віддаляється поддерево з коренем Currentroot->son.

 Clear(Currentroot->son);

// Віддаляється поддерево з коренем Currentroot->brother.

 Clear(Currentroot->brother);

// Віддаляється поточний корінь.

 delete Currentroot;

 

}

// Головна функція.

int main() {

// Додаємо елемент в корінь.

 Add(Null,1);

// Додаємо синів до елементу 1.

 Add(Find(Root,1),11);

 Add(Find(Root,1),12);

 Add(Find(Root,1),13);

// Додаємо синів до елементу 11.

 Add(Find(Root,11),111);

 Add(Find(Root,11),112);

// Додаємо синів до елементу 13.

 Add(Find(Root,13),131);

 Add(Find(Root,13),132);

 Add(Find(Root,13),133);

// Додаємо ще одного сина до елементу 1.

 Add(Find(Root,1),14);

// Додаємо ще один елемент в корінь.

 Add(Null,2);

// Виводимо дерево на екран.

 Show(Root);

// Очищаємо дерево.

 Clear(Root);

 return 0;

}

 

4. Варіанти завдань

Варіант №1.

Реалізувати стек для зберігання і операцій з даними виду:

Ім'я процедури

Кількість параметрів

Параметри (по 2 байти)

Забезпечити виконання операцій:

  •  додавання процедури в стек;
  •  видалення процедури зі стека;
  •  видалення стека (висвободження місця у пам'яті);
  •  роздрукування вмісту стека;
  •  підрахунок розміру пам'яті, зайнятої стеком;
  •  підрахунок кількості процедур, що знаходиться у стеку.

Варіант №2.

Реалізувати стек для зберігання і операцій з даними виду:

Ім'я функції

Значення, що повертається (6 байтів)

Кількість параметрів

Параметри (по 6 байтів)

Забезпечити виконання операцій:

  •  виділення місця в пам'яті під стек;
  •  додавання функції в стек;
  •  видалення функції із стека;
  •  попередження про можливе переповнювання;
  •  повідомлення про переповнювання;
  •  роздрук вмісту стека;
  •  звільнення пам'яті, виділеної під стек.

Варіант №3.

Реалізувати чергу для зберігання і операцій з даними виду:

Прізвище

Спеціальність

Дата подання заяви

Дата реєстрації на біржі праці

Забезпечити виконання операцій:

  •  додавання елементу в чергу;
  •  видалення елементу з черги;
  •  визначення розміру черги;
  •  роздрук черги;
  •  знаходження в черзі елементу по прізвищу з вказівкою черговості;
  •  формування списку по заданій спеціальності.

Варіант №4.

Реалізувати чергу для зберігання і операцій з даними виду:

Ім'я програми

Мова програмування

Розмір пам'яті, що потребується

Час виконання

Забезпечити виконання операцій:

  •  виділення місця в пам'яті під чергу;
  •  додавання елементу в очередеь;
  •  видалення елементу з черги;
  •  попередження про можливе переповнювання;
  •  повідомлення про переповнювання;
  •  визначення часу виконання всіх програм;
  •  звільнення пам'яті, виділеної під чергу.

Варіант №5.

Реалізувати кільцеву чергу (циклічний список) для зберігання і операцій з даними виду:

Найменування пристрою

Рік випуску

Вартість

Забезпечити виконання операцій:

  •  додавання елементу в чергу;
  •  видалення елементу з черги в порядку запису;
  •  визначення позиції елементу у черзі;
  •  видалення всіх елементів із заданим полем;
  •  роздрукування черги.

Варіант №6.

Реалізувати кільцеву чергу для зберігання і операцій з даними виду:

Ім'я програми

Час виконання

Забезпечити виконання операцій:

  •  формування черги;
  •  автоматична прокрутка черги з виділенням "кванта часу центрального процесора";
  •  додавання елементів в чергу;
  •  автоматичне виведення елементів з черги по використанню часу процесора (видати повідомлення);
  •  видача довідки про кількість елементів в черзі;
  •  роздрукування черги.

Варіант №7.

Реалізувати однозв'язний список для зберігання і операцій з даними виду:

Найменування мікросхеми

Вартість

Кількість

Забезпечити виконання операцій:

  •  додавання елементу в неврегульований список;
  •  видалення елементу із заданим полем з неврегульованого списку;
  •  додавання елементу після вказаного;
  •  видалення всіх елементів із заданим полем;
  •  роздрукування списку.

Варіант №8.

Реалізувати однозв'язний список для зберігання і операцій з даними виду:

Ім'я змінної

Тип

Кількість байтів

Забезпечити виконання операцій:

  •  сортування списку по полю "Ім'я";
  •  додавання елементу у впорядкований список;
  •  видалення елементу із списку;
  •  зміну полий "Тип" і "Число байтів" елементу, визначуваних полемо "Ім'я змінної";
  •  роздрукування списку.

Варіант №9.

Реалізувати однозв'язний список для зберігання і операцій з даними виду:

Країна

Місто

Кількість мешканців

Забезпечити виконання операцій:

  •  додавання елементу в список;
  •  видалення елементу із списку;
  •  розділення списку на два за ознакою: "Країна", що має міста з числом мешканців >=K і <K;
  •  підрахунок "Числа мешканців" у всіх містах заданої країни;
  •  роздрукування списку.

Варіант №10.

Реалізувати однозв'язний список для зберігання і операцій з даними виду:

Об'єкт

Кількість зовнішніх зв'язків

Зовнішні зв'язки

Забезпечити виконання операцій:

  •  установка максимального розміру списку;
  •  контроль переповнювання списку;
  •  додавання об'єкту в список;
  •  видалення об'єкту із списку;
  •  знаходження вказаного об'єкту в списку.

Варіант №11.

Реалізувати лінійний двозв'язний список для зберігання і операцій з даними виду:

Прізвище

Рів вступу

Середній бал

Забезпечити виконання операцій:

  •  додавання елементу в неврегульований список;
  •  сортування списку по полю "Прізвище";
  •  додавання елементу у впорядкований список;
  •  видалення елементу із списку;
  •  роздрукування списку;
  •  розділення списку на два по значенню поля "Середній бал".

Варіант №12.

Реалізувати двозв'язний список з розгалуженнями для зберігання і операцій з даними виду:

Ім'я

Послідовність чисел

Забезпечити виконання операцій:

  •  додавання елементів в список;
  •  пошук і роздрукування елементу в списку;
  •  видалення елементу із списку;
  •  підрахунок елементів в списку.

Примітка. Послідовність чисел може містити від 1 до N чисел. Для послідовностей завдовжки більш K (K<N) організувати гілки.

Варіант №13.

Реалізувати двозв'язний список з розгалуженнями для зберігання і операцій з даними виду:

Ім'я

Послідовність символів (довідник)

Забезпечити виконання операцій:

  •  додавання елементів в невпорядкований список;
  •  сортування списку за полем ім'я;
  •  додавання елементу в відсортований список;
  •  видалення елементу зі списку.
  •  роздрукування групи елементів з довжиною "Послідовність символів) >= K;
  •  редагування послідовності символів (заміна на нову).

Примітка. Послідовність чисел може містити від 1 до N чисел. Для послідовностей завдовжки більш K (K<N) організувати гілки.

Варіант №14.

Реалізувати двозв'язний список з розгалуженнями для зберігання і операцій з даними виду:

Ім'я процедури

Кількість параметрів

Значення параметрів (по 4 байти)

Забезпечити виконання операцій:

  •  додавання елементів в список;
  •  видалення елементу з заданим ім'ям зі списку;
  •  визначення кількості процедур у списку;
  •  визначення зайнятого місця у пам'яті під список;
  •  роздрукування усього списку;
  •  роздрукування списку процедур без параметрів.

Варіант №15.

Реалізувати двозв'язний список для зберігання і операцій з даними виду:

Найменування моделі

Дата виготовлення

Кількість

У перший підсписок входять усі записи. В другий - лише ті записи, де поле "Кількість" < К.

Забезпечити виконання операцій:

  •  додавання нового елементу в список;
  •  пошук елементу за полем кількість;
  •  роздрукування підсписків;
  •  корегування значення поля "Кількість" вибраного елементу.

Варіант №16.

Реалізувати двозв'язний список для зберігання і операцій з даними виду:

Прізвище

Країна

Рік вступу

Вартість навчання

У перший підсписок входять усі записи. В другий - лише ті записи, де поле "Країна" не дорівнює "Україна".

Забезпечити виконання операцій:

  •  додавання нового елементу в невпорядкований список;
  •  впорядкування списку за полем "Прізвище";
  •  додавання елемента в впорядкований список;
  •  корегування поля "Країна" обраного елементу;
  •  роздрукування підсписків;
  •  роздрукування переліку країн.

Варіант №17.

Реалізувати трьохзв'язний список для зберігання і операцій з даними виду:

Товар

Вартість

Кількість

Дата постачання

У перший підсписок входять усі записи. В другий - лише ті, у яких "Вартість" більша ніж С. В третій - лише ті, дата постачання яких більш рання, ніж D.

Забезпечити виконання операцій:

  •  додавання нового елементу в список;
  •  роздрукування списків;
  •  видалення елементу з заданим полем;
  •  знаходження сумарної вартості товару;
  •  зміна критерію С.

Варіант №18.

Реалізувати трьохзв'язний список для зберігання і операцій з даними виду:

Відділ

Тип ПЕВМ

Кількість

Наявність мережі

У перший підсписок входять усі записи. В другий - лише ті, у яких "Тип ПЕВМ" не нижче, ніж 80386. В третій - відділи, де є мережа.

Забезпечити виконання операцій:

  •  додавання нового елементу в список;
  •  дооснащення відділу технікою;
  •  списання старої техніки;
  •  встановлення у відділі мережевого обладнання;
  •  роздрукування списків;
  •  визначення відділів з найкращим технічним забезпеченням. 

Варіант №19.

Реалізувати трьохзв'язний список для зберігання і операцій з даними виду:

Прізвище

Рік народження

Освіта

Стаж

У перший підсписок входять усі записи. В другий - лише ті, у яких "Рік народження" менше, ніж G. В третій - лише ті, у яких стаж більше n років.

Забезпечити виконання операцій:

  •  додавання нового елементу в невпорядкований список;
  •  сортування списку за полем "Прізвище";
  •  додавання нового елементу в впорядкований список;
  •  роздрукування третього підсписку;
  •  видалення елементу з першого списку;
  •  визначення кількості осіб з вищою освітою.

Варіант №20.

Реалізувати бінарне дерево для зберігання і операцій з даними виду:

Ім'я

Рік народження

Місто

Забезпечити виконання операцій:

  •  додавання нового елементу в дерево у діалоговому режимі;
  •  обхід зверху;
  •  підрахунок кількості листів;
  •  знаходження найдовшої гілки;
  •  роздрукування дерева;
  •  роздрукування усіх вузлів з однаковим містом.

Варіант №21.

Реалізувати бінарне дерево для зберігання і операцій з даними виду:

Найменування блоку

Вартість

Кількість вузлів

Забезпечити виконання операцій:

  •  додавання нового елементу в дерево у діалоговому режимі;
  •  обхід зліва направо;
  •  підрахунок кількості гілок;
  •  знаходження блоку з найбільшим числом вузлів;
  •  роздрукування листя;
  •  роздрукування дерева.

Варіант №22.

Реалізувати бінарне дерево для зберігання і операцій з даними виду:

Найменування товару

Кількість

Вартість одиниці

Забезпечити виконання операцій:

  •  додавання нового елементу в дерево у діалоговому режимі;
  •  обхід знизу;
  •  виділення піддерева в самостійне дерево (задається вузел);
  •  побудова копії вказаного дерева;
  •  роздрукування дерева;
  •  підрахунок загальної вартості товару.

Варіант №23.

Реалізувати бінарне дерево для зберігання і операцій з даними виду:

Деталь

Кількість

Постачальник

Забезпечити виконання операцій:

  •  додавання нового елементу в дерево у діалоговому режимі;
  •  обхід зверху;
  •  визначення входження "Деталі" в дерево;
  •  роздрукування дерева;
  •  визначення постачальника найбільшої кількості деталей.

Варіант №24.

Реалізувати бінарне дерево для зберігання і операцій з даними виду:

Найменування служби

Кількість співробітників

Сума заробітної платні

Забезпечити виконання операцій:

  •  додавання нового елементу в дерево у діалоговому режимі;
  •  обхід зліва направо;
  •  видалення із дерева вказаного вузла;
  •  визначення найбільш дорогої служби;
  •  роздрукування дерева;
  •  визначення кількості співробітників у вказаній службі та в усіх її підлеглих.

Варіант №25.

Реалізувати бінарне дерево для зберігання і операцій з даними виду:

Найменування

Рік видання

Кількість сторінок

Автор

Забезпечити виконання операцій:

  •  додавання нового елементу в дерево у діалоговому режимі;
  •  обхід знизу;
  •  роздрукування усіх вузлів, що створюють заданий рівень;
  •  формування окремого дерева з творів заданого автора;
  •  підрахунок кількості творів кожного автора;
  •  видалення із дерева однакових вузлів.

Варіант №26.

Реалізувати бінарне дерево для зберігання і операцій з даними виду:

Найменування процесу

Кількість складових

Тривалість

Забезпечити виконання операцій:

  •  додавання нового елементу в дерево у діалоговому режимі;
  •  обхід зверху;
  •  створення окремого дерева із усіх процесів з однаковою тривалістю;
  •  перерозподіл вузлів в дереві таким чином, щоб процеси з найбільшою кількістю складових займали найбільш високий рівень;
  •  роздрукування вказаного піддерева;
  •  роздрукування дерева.

Варіант №27.

Реалізувати бінарне дерево для зберігання і операцій з даними виду:

Клас

Кількість підкласів

Місце проживання

Забезпечити виконання операцій:

  •  додавання нового елементу в дерево у діалоговому режимі;
  •  обхід зліва направо;
  •  роздрукування усіх вузлів з однаковим місцем проживання;
  •  знаходження місця проживання, де знаходиться найбільша кількість класів і підкласів;
  •  роздрукування найбільш довгої гілки дерева;
  •  роздрукування дерева.

Варіант №28.

Реалізувати бінарне дерево для зберігання і операцій з даними виду:

Найменування

Вага

Вартість

Колір

Забезпечити виконання операцій:

  •  додавання нового елементу в дерево у діалоговому режимі;
  •  обхід знизу;
  •  побудова окремих дерев для різних кольорів;
  •  роздрукування дерева;
  •  видалення із дерева усіх вузлів, що повторюються (в діалоговому режимі з підтвердженням).


Література

1. Ахо Альфред В., Хопкрофт Джон Ульман, Джеффри, Д. Структуры данных и алгоритмы : Пер. с англ. : Уч. пос. - М. : Издательский дом "Вильяме", 2000. - 384 с.

2. Матьяш В.А., Путилов В.А., Фильчаков В.В. , Щёкин С.В. Структуры и алгоритмы обработки данных - Апатиты, КФ ПетрГУ, 2000. - 80 с.

3. Дейтел Х.М., Дейтел П.Дж., Как программировать на С++, Москва-Радио и связь. 1996. - 447 с.

4. Герберт Шилд, Программирование на языке C++ - М.: Высшая школа, 2002. - 584 с.

5. Шпак З.Я. Програмування мовою С. – Львів: Оріяна-Нова, 2006. – 432 с.

6. Ковалюк Т.В. Основи програмування. – К.: Видавнича група BHV, 2005. - 384c.


 

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

82040. Основные компоненты бизнес-плана Агентства наружной рекламы 464.5 KB
  Обычно полотно перетяжки изготавливается методом трафаретной печати на хлопчатобумажной ткани. При необходимости размещения на длительный срок или при изготовлении сложного макета используется либо сублимационная печать на шелковой ткани, либо печать на баннере.
82041. Тиристорні перетворювачі 297.5 KB
  Система імпульснофазового управління в свою чергу складається із вузла що перетворює напругу управління в послідовність імпульсів визначеної тривалості форми моменти яких залежать від напруги управління; вузла підсилення імпульсів що формує імпульси з визначеними електричними параметрами.
82042. Туристическая база 13.36 MB
  Туризм можно классифицировать по различным критериям: По цели отдыха По характеру отдыха и его организации По продолжительности путешествия По сезонности Эти критерии имеют решающее значение потому что именно цель поездки больше всего влияет на формирование тура и организацию туристического обслуживания.
82043. Изготовление изделий из бисера 6.73 MB
  В настоящее время бисерная вышивка переживает свой расцвет. Это красиво, модно, современно. Вышивкой из бисера украшают не только платья, кофточки, но и обувь, сумки и многое другое. Основой для вышивки служат холст, лен, бархат, атлас, шерсть. Сукно. Нитки следует брать армированные, чтобы бусинки их не перетирали.
82044. Країни південно-східної Азії у другій половині ХХ-го століття 7.55 MB
  Економічна колонізація В’єтнаму французьким капіталом розпочата у другій половині ХІХ ст. в умовах післявоєнного економічного буму французькі колонізатори вдалися до розширеної експлуатації людських і природних багатств В’єтнаму.
82045. Beethovens Musik ist ewig 85 KB
  Liebe Kunstfreunde, liebe Gäste! Es freut mich euch alle in diesem gemütlichen Saal zu begrüßen. Unsere außerschulische Veranstaltung ist dem genialen deutschen Komponisten Ludwig van Beethoven gewidmet. Schüler 1: Ludvig van Beethoven ist einer der größten Komponisten, Schüler 2: einer der berühmtesten Komponisten der Welt,
82046. Золоті правила країни ввічливості 77 KB
  Серед слів які ми вживаємо є чарівні слова ввічливості. Бережи свій час; тримай кожну річ на своєму місці; дотримуйся свого слова. І посміхаються У відповідь люди Добрі слова ж бо Для кожного любі.Я слова чарівні знаю Вивчила охоче І в розмові їх вживаю Зранку і до ночі Доброго здоров’я Галю Добрий день...
82047. «Шануй батька і неньку, то буде тобі скрізь гладенько». Любов до батьків, турбота про них 59.5 KB
  Мета: виховувати у дітей любов та повагу до батьків турботу про них шанобливе ставлення до їхніх настанов та порад бажання щоденно піклуватися про їхнє здоров’я не завдавати їм душевного болю негідними вчинками; прищеплювати бажання бути гідними дітьми своїх батьків прагнення приносити щастя в свій дім.
82048. Подорож країною Екологія 84.5 KB
  Мета: Пробудити в школярів особистої відповідальності за охорону навколишнього середовища, виховувати любов до рідного краю. Обладнання: плакати, телевізор, заставки зупинок, малюнки рослин і тварин Червоної книги України, грамзапис мелодій, присвячених природі, модель квітки.