Створення та обробка динамічного списку

Інформатика, програмування

Пензенський технологічний інститут (завод-ВТУЗ)
Факультет ФСВТ
Кафедра Вміс

Пояснювальна записка до курсової роботи з дисципліни:

«Алгоритмічні мови та програмування» на тему

«Створення та обробка динамічного списку»

Виконав: студент групи 02В2

Новокшонов М.С.

Керівник: Даніліна Н.П.

Проект захищений з оцінкою ________

Пенза 2003

1. Постановка завдання

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

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

3
2. Розробка методу розв'язання задачі та його формалізація

1) У цій програмі будуть використовуватися такі глобальні змінні:n - масив 30 змінних типу char. Несе інформацію про назву газети.s - масив 30 змінних типу char. Несе інформацію про назву статтіst - змінна типу int. Несе інформацію про номер сторінки.
Усі ці змінні є елементами структури gaseta:struct games (char n [30];char s [30];int st ;};

g - мінлива типу gaseta. Несе повну інформацію про газету.n - покажчик на структуру news.
Усі ці змінні є елементами структури news:struct news (gaseta g;news * n ;};

un - покажчик на структуру news. Несе інформацію про адресу першогоелемента однонаправленої динамічного списку.p - покажчик на структуру news. Несе інформацію про адресу поточногоелемента однонаправленої динамічного списку.q - покажчик на структуру news. Несе інформацію про адресу останньогоствореного елемента однонаправленої динамічного списку.news * un, * p, * q;

i - змінна типу int. Несе інформацію про кількість елементіводнонаправленої динамічного списку.int i;

4
2) Локальні змінні процедури введення даних:j - змінна типу int. Ця змінна є параметром всіх циклівщо використовуються в даній процедурі.int j;

3) Локальні змінні процедури виведення даних:j - змінна типу int. Ця змінна є параметром всіх циклівщо використовуються в даній процедурі.int j;

4) Локальні змінні процедури видалення першого елемента списку:
У даної процедури немає локальних змінних.

5) Локальні змінні процедури зміни місць елементів, які заданіза назвою:j - змінна типу int. Ця змінна є одним параметром всіхциклів використовуються в даній процедурі.int j;

k1 - мінлива типу char. Несе інформацію про назву першої газети,місце якої будемо змінювати.k1 - мінлива типу cnar. Несе інформацію про назву другого газети,місце якої будемо змінювати.char k1 [30], k2 [30];

p2 - покажчик на структуру news. Несе інформацію про адресу другапоточного елемента однонаправленої динамічного списку.news * p2;

c - мінлива типу gaseta. Несе повну інформацію про гру.

gaseta c;

5
6) Локальні змінні основної частини програми:a - змінна типу int. Несе інформацію про поточну процедурою і єпараметром циклу та оператора множинного вибору.int a;

3. Розробка складу та структури вихідних даних і результату

Вихідні дані й результат є односпрямованийдинамічний список. Елементом списку буде структура, що складаєтьсяз внутрішньої структури та вказівника на наступний елемент списку. Внутрішняструктура складається з полів:
1) назву газети (тип char)
2) назва статті (тип char)
3) номери сторінок (тип int)

На екрані вихідні дані будуть представлені:
Введіть дані про 1 статті
Назва: Комсомольская правда
Стаття: Про шкоду куріння
Сторінка: 12
... ... ... ... ... ... ... ... ... ... ... ...

12 |

4. Розробка алгоритму

4.1 Основна частина програми.
0. Початок
1 Очищаємо екран
2 Надаємо змінної а, яка є параметром наступного циклута оператора множинного вибору значення рівне одиниці
3 Відкриваємо цикл з передумовою (умова: мінлива а не дорівнює 5); в циклібудуть виконуватися кроки з 4 по 11
4 Вводимо змінну а
5 Виконуємо оператор множинного вибору з параметром а; операторвключає кроки з 6 по 10
6 Якщо а = 1, викликаємо процедуру введення даних
7 Якщо а = 2, викликаємо процедуру виведення даних
8 Якщо а = 3, викликаємо процедуру видалення першого елемента
9 Якщо а = 4, викликаємо процедуру зміни місць елементів, які заданіназвами
10 Якщо а не одно не одним із зазначених раннє значень, то а присвоюємозначення 5
11 Закриваємо оператор множинного вибору
12 Закриваємо цикл з передумовою
13 Кінець

4.2 Процедура введення даних
0 Початок процедури
1 резервуємо область оперативної пам'яті розміром рівним розміром елемента іприсвоюємо вказівником на останній елемент q адресу цієї області.
2 Послідовно вводимо дані внутрішньої структури, на яку будитьвказувати покажчик q.
3 Надаємо вказівником на перший елемент списку un і вказівником на поточнийелемент p значення покажчика q. Надаємо змінної i, яка міститьдані про кількість записів у списку і змінної j, яка є параметромнаступних циклів значення рівне 1
4 Відкриваємо цикл з передумовою (умова: мінлива j дорівнює 1); в циклібудуть виконуватися кроки з 5 по 9

5 Збільшуємо значення змінної i на одиницю
6 резервуємо область оперативної пам'яті розміром рівним розміром елемента іприсвоюємо вказівником q адресу цієї області
7 Послідовно вводимо дані внутрішньої структури, на яку будитьвказувати покажчик q
8 Встановлюємо покажчик введеного раніше елемента n на елемент, введенийкроком 7, а вказівником p значення покажчика q
9 Вводимо нове значення змінної j
10 Закриваємо цикл з передумовою
11 Встановлюємо покажчик n поточного елементу на NULL
12 Кінець процедури

4.3 Процедура виведення даних
0 Початок процедури
1 Встановлюємо вказівник p на перший елемент списку, а змінну j,яка буде параметром наступного циклу, встановлюємо в 1
2 Відкриваємо цикл з передумовою (умова: мінлива j менше або рівне i);в циклі буде виконуватися кроки з 3 по 4
3 Послідовно виводимо дані внутрішньої структури, на яку будитьвказувати покажчик p
4 Покажчик поточного елемента p встановлюємо на наступний елемент, азначення змінної j збільшуємо на 1
5 Закриваємо цикл з передумовою
6 Кінець процедури

4.4 Процедура видалення першого в списку елемента
0 Початок процедури
1 Покажчик поточного елемента p встановлюємо на початок, а покажчик першимелемента в списку un встановлюємо на наступний елемент
2 Звільняємо область пам'яті, на яку вказує покажчик поточногоелемента p

9
3 Значення змінної i, що містить дані про число елементів усписку, зменшуємо на 1
4 Кінець процедури

4.5 Процедура зміни місць елементів, які задані номерами
0 Початок процедури
1 Вводимо змінну k1, яка вказує на назву першого елемента воперації зміни місць
2 Встановлюємо вказівник p на перший елемент списку.
3 Відкриваємо цикл з заданим числом повторень (j = 0 ... k1); в циклі будевиконуватися крок 4
4 Покажчик на поточний елемент p встановлюємо на наступний елемент списку
5 Закриваємо цикл з заданим числом повторень
6 Вводимо змінну k2, яка вказує на назву другого елемента воперації зміни місць
7 Встановлюємо покажчик p2 на перший елемент списку.
8 Відкриваємо цикл з заданим числом повторень (j = 0 ... k2); в циклі будевиконуватися крок 4
9 Покажчик на поточний елемент p2 встановлюємо на наступний елемент списку

10 Закриваємо цикл з заданим числом повторень
11 Змінній з присвоюємо дані внутрішньої структури, на яківказує вказівник поточного елемента p
12 Дані внутрішньої структури, на які вказує покажчик поточногоелемента p2, копіюємо в змінні внутрішньої структури, на яківказує вказівник поточного елемента p.
13 Значення змінної з присвоюємо змінним внутрішньої структури, наякі вказує вказівник поточного елемента p2.
14 Кінець процедури

10
5. Вибір мови

Мова програмування СІ + + є мовою високого рівня. Мова СІ + +був розроблений на основі мови СІ Б'ярне Страуструп. Вибір мови СІ + +для вирішення даного завдання обумовлений наявністю в мові СІ + + засобів длядинамічного розподілу пам'яті.

Динамічний розподіл пам'яті здійснюється операціями new іdelete. Це 2 особливі унарні операції, що з'явилися в мові СІ + + (в мові СІцих операцій не було). Операція new імя_тіпа або new імя_тіпаініціалізатор дозволяє виділити і зробити доступним вільну ділянку восновної пам'яті, розміри якого відповідають типу даних, що визначаєтьсяім'ям типу. У виділена ділянка заноситься значення, яке визначаєтьсяініціалізатором, який не є обов'язковим елементом. У разіуспішного виконання операції new повертає адресу початку виділеногоділянки пам'яті. Якщо ділянка потрібних розмірів не може бути виділений (немаєпам'яті), то операція new повертає нульове значення адреси (NULL).
Синтаксис застосування операції: покажчик = new імя_тіпа ініціалізатор.

Тривалість існування виділеного за допомогою операції newділянки пам'яті - від точки створення до кінця програми або до явного йогозвільнення.

Для явного звільнення виділеного операцією new ділянки пам'ятівикористовується оператор delete покажчик, де покажчик адресуєзвільняється ділянка пам'яті, раніше виділений за допомогою операції new.

11
6. Розробка програми

6.1 Основна частина програми.
0 Початок. Описуємо глобальні змінні і типи даних
1 Очищаємо екран за допомогою оператора clrscr ()
2 Надаємо змінної а, яка є параметром наступного циклута оператора множинного вибору значення рівне одиниці: a = 1
3 Відкриваємо цикл з передумовою (умова: мінлива а не дорівнює 5); в циклібудуть виконуватися кроки з 4 по 11: while (a! = 5)
4 Вводимо змінну а: a = getch ()
5 Виконуємо оператор множинного вибору з параметром а; операторвключає кроки з 6 по 10: switch (a)
6 Якщо а = 1, викликаємо процедуру введення даних: case '1 ': vvod (); break
7 Якщо а = 2, викликаємо процедуру виведення даних: case '2 ': vivod (); break
8 Якщо а = 3, викликаємо процедуру видалення першого елемента: case '3 ': dele ();break;
9 Якщо а = 4, викликаємо процедуру зміни місць елементів, які заданіномерами: case '4 ': pomen (); break;
10 Якщо а не одно не одним із зазначених раннє значень, то а присвоюємозначення 5: default: a = 5; break;
11 Закриваємо оператор множинного вибору:)
12 Закриваємо цикл з передумовою:)
13 Кінець:)

6.2 Процедура введення даних
0 Початок процедури: void vvod (); Описываем локальні змінні
1 резервуємо область оперативної пам'яті розміром рівним розміром елемента іприсвоюємо вказівником на останній елемент q адресу цієї області:q = new (news)
2 Послідовно вводимо дані внутрішньої структури, на яку будевказувати покажчик q. Введення будемо здійснювати за допомогою послідовностіоператорів введення scanf

12
3 Надаємо вказівником на перший елемент списку un і вказівником на поточнийелемент p значення покажчика q. Надаємо змінної i, яка міститьдані про кількість записів у списку і змінної j, яка є параметромнаступних циклів значення рівне 1: un = q; p = q; j = 1; i = 1;
4 Відкриваємо цикл з передумовою (умова: мінлива j дорівнює 1); в циклібудуть виконуватися кроки з 5 по 9: while (j == 1)
5 Збільшуємо значення змінної i на одиницю: i + +
6 резервуємо область оперативної пам'яті розміром рівним розміром елемента іприсвоюємо вказівником q адресу цієї області: q = new (news);
7 Послідовно вводимо дані внутрішньої структури, на яку будевказувати покажчик q. Введення будемо здійснювати за допомогою послідовностіоператорів введення scanf
8 Встановлюємо покажчик введеного раніше елемента n на елемент, введенийкроком 7, а вказівником p значення покажчика q: p-> n = q; p = q;
9 Вводимо нове значення змінної j. Введення будемо здійснювати за допомогоюоператора введення scanf
10 Закриваємо цикл з передумовою:)
11 Встановлюємо покажчик n поточного елементу на NULL: p-> n = NULL;
12 Кінець процедури:)

6.3 Процедура виведення даних
0 Початок процедури: void vivod (); Описываем локальні змінні
1 Встановлюємо вказівник p на перший елемент списку, а змінну j,яка буде параметром наступного циклу, встановлюємо в 1: p = un; j = 1;
2 Відкриваємо цикл з передумовою (умова: мінлива j менше або рівне i);в циклі буде виконуватися кроки з 3 по 4: while (jn; j + +;
5 Закриваємо цикл з передумовою:)
6 Кінець процедури:)

6.4 Процедура видалення елемента заданого на ім'я
0 Початок процедури: void dele (); Описываем локальні змінні
1 Покажчик поточного елемента p встановлюємо на початок, а покажчик першимелемента в списку un встановлюємо на наступний елемент: p = un; un = un-> n;
2 Звільняємо область пам'яті, на яку вказує покажчик поточногоелемента p: delete p;
3 Значення змінної i, що містить дані про число елементів усписку, зменшуємо на 1: i = i-1;
4 Кінець процедури

6.5 Процедура зміни місць елементів, які задані номерами
0 Початок процедури: void pomen (); Описываем локальні змінні
1 Вводимо змінну k1, яка вказує на назву першого елемента воперації зміни місць. Введення будемо здійснювати за допомогою оператора введенняscanf
2 Встановлюємо вказівник p на перший елемент списку: p = un;
3 Відкриваємо цикл з заданим числом повторень (j = 0 ... k1); в циклі будевиконуватися крок 4: for (j = 1; jn;
5 Закриваємо цикл з заданим числом повторень:)
6 Вводимо змінну k2, яка вказує на назву другого елемента воперації зміни місць. Введення будемо здійснювати за допомогою оператора введенняscanf
7 Встановлюємо покажчик p2 на перший елемент списку: p2 = un
8 Відкриваємо цикл з заданим числом повторень (j = 0 ... k2); в циклі будевиконуватися крок 4: for (j = 1; jn;

14
10 Закриваємо цикл з заданим числом повторень:)
11 Змінній з присвоюємо дані внутрішньої структури, на яківказує вказівник поточного елемента p: з = p-> g;
12 Дані внутрішньої структури, на які вказує покажчик поточногоелемента p2, копіюємо в змінні внутрішньої структури, на яківказує вказівник поточного елемента p: p-> g = p2-> g;
13 Значення змінної g1 присвоюємо змінним внутрішньої структури, наякі вказує вказівник поточного елемента p2: p2-> g = с;
14 Кінець процедури:)

15
7. Налагодження та тестування програми

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

Statement missing; - відсутність знаку кінця оператора.

16
Список використаної літератури

1 В. В. Подбельський. Мова СІ + +. - М.: Фінанси і статистика, 2003.
2 Б. І. Березін, С. Б. Березін. Початковий курс С та С + +. - М.: Диалог-МИФИ,
1998.

ДОДАТОК 1

ДОДАТОК 2
# Include
# Include
# Include

struct gaseta (char n [30];char s [30];int st ;};

struct news (games g;play * n ;};

play * un, * p, * q;

int i;

void vvod ()
(int j;q = new (news);printf ( "Введіть дані про 1 статьеn");printf ( "Газета:");scanf ( "% s", & q-> g.n);printf ( "Стаття:");scanf ( "% d", & q-> g.s);printf ( "Сторінка:");scanf ( "% d", & q-> g.st);un = q;p = q;j = 1;i = 1;while (j == 1)
(i + +;q = new (news);printf ( "Введіть дані про% d", i);printf ( "ігреn");printf ( "Газета:");scanf ( "% s", & q-> g.n);printf ( "Стаття:");scanf ( "% d", & q-> g.s);printf ( "Сторінка:");scanf ( "% d", & q-> g.st);p-> n = q;p = q;printf ( "Бажаєте продовжити? 1-так, 2-нетn ");

22scanf ( "% d", & j);
)p-> n = NULL;
)

void vivod ()
(int j;p = un;j = 1;printf ( "Дані про статьеn");printf ("+---------------+--------------+--------------+ n ");printf ( "| газета | стаття

| сторінка | n");while (jg.n, p-> g.s, p-> g.st);p = p-> n;j + +;
) Printf ("+---------------+--------------+-------------+ n ");
)

void dele ()
(p = un;un = un-> n;delete p;i = i-1;printf ( "Обробка виполненаn");
)

void pomen ()
(int j;char k1 [30], k2 [30];gaseta c;news * p2;printf ( "введите перша назва газетиn");scanf ( "% s", & k1);p = un;while (strcmp (p-> g.n, k1)! = 0)p = p-> n;printf ( "введите друга назва газетиn");scanf ( "% s", & k2);p2 = un; while (strcmp (p2-> g.n, k2)! = 0)p2 = p2-> n;c = p-> g;p-> g = p2-> g;p2-> g = c;printf ( "Обробка виполненаn");
)

main ()
(int a;clrscr ();a = 1;while (a! = 5)
(printf ( "Натисніть одну з кнопокn");printf ( "Введення даних - 1n");printf ( "Висновок даних - 2n");printf ( "Видалення першого елемента - 3n");printf ( "зміна місць - 4n");printf ( "Вихід - 5n");a = getch ();switch (a)
(case '1 ': vvod (); break;case '2 ': vivod (); break;case '3 ': dele (); break;case '4 ': pomen (); break;default: a = 5; break;
)
)return 0;
)

ДОДАТОК 3
Натисніть одну з кнопок
Введення даних - 1
Висновок даних - 2
Видалення даних-3
Зміна місць - 4
Вихід - 5
1
Введіть дані про 1 статті
Газета: Комсомольская правда
Стаття: про шкоду куріння
Сторінка: 12
Введіть дані про 2 статті
Газета: Пенза плюс твстаття: проблеми
Сторінка: 6
Хочетепродовжити? 1-так, 2-ні
1
Газета: Молодий ленінець
Стаття: наркоманія
Сторінка: 8
Бажаєте продовжити? 1-так, 2-ні
1
Газета: СНІД інфо
Стаття: вагітність
Сторінка: 20
Бажаєте продовжити? 1-так, 2-ні
1
Газета: московський комсомолець
Стаття: пенсійна реформа
Сторінка: 9
Бажаєте продовжити? 1-так, 2-ні
2
Натисніть одну з кнопок
Введення даних - 1
Висновок даних - 2
Видалення даних - 3
Зміна місць - 4
Вихід - 5
2
Дані про газети
+---------------+--------------+--------------+< br>| Назва | рік випуску |займаний обсяг |
| Комсомольська правда | про шкоду куріння |

12 |
| Пенза плюс тв | проблеми |

6 |
| Молодий ленінець | наркоманія |

8 |
| СНІД інфо | вагітність |

20 |
| Московський комсомолець | пенсійна реформа |

9 |

Натисніть одну з кнопок
Введення даних - 1
Висновок даних - 2
Видалення даних - 3
Зміна місць-4
Вихід - 5
3
Видалення виконано
Натисніть одну з кнопок
Введення даних - 1
Висновок даних - 2
Видалення даних - 3
Зміна місць - 4
Вихід - 5
2
Дані про газети
+---------------+--------------+--------------+< br>| Назва | рік випуску |займаний обсяг |
| Пенза плюс тв | проблеми |

6 |
| Молодий ленінець | наркоманія |

8 |
| СНІД інфо | вагітність |

20 |
| Московський комсомолець | пенсійна реформа |

9 |

Натисніть одну з кнопок
Введення даних - 1
Висновок даних - 2
Видалення даних - 3
Зміна місць - 4
Вихід - 5
4
Введіть назву першої газети
Пенза плюс тв
Введіть назву другого газети
Молодий ленінець
Зміна місць виконана
Натисніть одну з кнопок
Введення даних - 1
Висновок даних - 2
Видалення даних - 3
Зміна місць - 4
Вихід - 5
2
Дані про газети
+---------------+--------------+--------------+< br>| Назва | рік випуску |займаний обсяг |
| Молодий ленінець | наркоманія |

8 |
| Пенза плюс тв | проблеми |

6 |
| СНІД інфо | вагітність |

20 |
| Московський комсомолець | пенсійна реформа |

9 |

Натисніть одну з кнопок
Введення даних - 1
Висновок даних - 2
Видалення даних - 3
Зміна місць - 4
Вихід - 5
5

-----------------------a

p-> n = q; p = q;

void vvod ()

q = new (news)

Введення q-> gn, q-> gs, q-> g.st

un = q; p = q; j = 1; i = 1;

Цикл 1

Поки (j == 1)

i + +; q = new (news);

Введення q-> gn, q-> gs, q-> g.st

Введення j

Цикл 1

p-> n = NULL;

Кінець

p = un; j = 1;

void vivod ()

Цикл 1

Поки (jg.n, q -> gs, q-> g.st

p = p-> n; j ++;

Цикл 1

Кінець

p = un; un = un-> n

void dele ()

Кінець

delete pi = i-1;

Цикл 1 j = 1 ... k1

p = un;

Введення k1

Цикл 1

void pomen ()

Цикл 1

p = p-> n;

p2 = un;

Введення k2

Цикл 2 j = 1 ... k2

p2 = p2-> n;

Кінець

c = p-> g; p-> g = p2-> g; p2-> g = c;

pomen ()

Кінець

Цикл 1

vvod ()

vivod ()

dele ()

Введення a

Цикл 1

Поки a! = 5

clrscr (); a = 1;

початок

Зміст

1 Постановка завдання 3

2 Розробка методу розв'язання задачі та його формалізація 4

3 Розробка складу структури вихідних даних і результату 7

4 Розробка алгоритму 8

5 Вибір мови програмування 12

6 Розробка програми 13

7 Налагодження та тестування програми 18

Список використаної літератури 19

Додаток 1: схема програми 20

Додаток 2: лістинг програми 25

Додаток 3: результати виконання програми 29

Маса

КР-2201-14-03-ПЗ

Літ.

Масштаб

ПТИ гр.02В2

Изм

Лист

№ докум.

Підпис

Дата

розробк.

Пров.

Н.-конт.

Утв.

Т.-конт.

Лист 2

Листів 27

Даніліна Н.П.

Новокшонов МС

Створення та обробка динамічного списку.

Пояснювальна записка

Покажчик на перший елемент

Внутрішняструктура

Покажчик на наступний елемент

Внутрішняструктура

NULL

Внутрішняструктура

Покажчик на наступний елемент