Двунаправленный динамічний список

Задание.

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

У програмному виробі передбачити роботу з списком, яка включає у собі: 1. Введення даних; 2. Видалення даних із списку; 3. Висновок списку на дисплей; 4. Сортування списку по фамилии.

Написати програмне на двома мовами програмування: З, Pascal.

Опис алгоритму програми з структурою данных.

Взаємодія програми з користувачем має бути реалізовано по наступному алгоритму:

Вибір зі головного меню одній з наступних функцій: а) Додати; б) Видалити; в) Переглянути; р) Сортувати; буд) Выход.

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

При виборі функції «Вихід» робота програми завершается.

При виборі функції «Додати», виділяється пам’ять для зберігання даних, потім користувачеві пропонується запровадити прізвище, ім'я, по батькові та дату народження людини, ці дані заносять у пам’ять, після чого автоматично визначається знак зодіаку по західному календареві і заноситься в память.

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

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

При виборі функції «Сортувати», відбувається сортування списку по прізвища. Якщо у списку зустрічаються дві однакові прізвища, тоді порівнюються імена; при збігу імен порівнюються отчества.

Опис программы.

Задля реалізації динамічного списку на програмі застосований тип покажчиків, який би на запис «Inform», що містить прізвище «fam», ім'я «name», по батькові «fanem», дня народження «bethday», знак зодіаку «zodiak» і покажчики наступного року «next» попередній «prev» елементи списка.

З допомогою цього «Ukazat» описані перемінні: «temp» — для зберігання покажчика сучасний елемент; «first» — для зберігання покажчика на перший елемент у списку; «cut» — для зберігання на останній елемент в списку. Змінна «ch» використовується для вибору процедури; «s1», «s2», «n» — для обчислення знака зодіаку; «m» — для перевірки умови, при сортування; «ffam», «fname», «ffanem» — для тимчасового зберігання прізвища, імені, по батькові, під час видалення елемента із списка.

Програма починає виконуватися з присвоєння покажчику перший елемент (first) значення «nil». Після цього користувачеві пропонується вибрати дію: «1-Добавить», «2-Удалить», «3-Просмотреть», «4- Сортувати», «0-Выход». Залежно від цього, яке дію вибере користувач, почне виконуватися та чи інша процедура, чи відбудеться вихід із програми. Це реалізовано з допомогою операції вибору «case».После виконання деякою процедури користувачеві знову пропонується вибрати одне з вищевказаних дій, поки що не обраний вихід із програми. Це реалізовано з допомогою циклу «repeat until».

Процедура додавання «Dobav».

Спочатку виділяється пам’ять під поточний елемент (new (temp)), потім у цей елемент записується прізвище, ім'я, по батькові та дата народження. По дати народження обчислюється знак зодіаку. І тому в s2 записується число народження, а s1 перші три літери місяці народження, потім, шляхом порівняння цих змінних з числами і частинами слів перебуває відповідний знак зодіаку, і заноситься в поточний елемент. Після введення інформації, перевіряється наявність елементів у списку. Якщо вони самі відсутні, то поточному елементі, покажчикам наступного року (next) попередній (prev) елементи присвоюється значення «nil»; а покажчик на сам елемент (temp) присвоюється покажчикам перший (first) і другий (cut) елементи у списку. Якщо список не порожній, то поточному елементі, покажчику наступного року елемент (next) присвоюється значення «nil», а покажчику подібний до попереднього елемент (prev) присвоюється покажчик на останній елемент (cut) у списку; а покажчику на наступний елемент (next) останнього елемента у списку і покажчику на останній елемент (cut) присвоюється покажчик сучасний елемент (temp). Після цього процедура додавання завершается.

Процедура видалення «Udal».

У цьому процедурі спочатку перевіряється наявність елементів у списку. Якщо список порожній, то виводиться повідомлення: «Таблиця порожня». Якщо ж у списку містить елементи, то користувачеві пропонується запровадити прізвище, ім'я і по батькові удаляемого, записуючи в ffam, fname, ffanem відповідно. Після відбувається пошук удаляемого елемента у списку. Це реалізовано з допомогою циклу, виконуваному, поки елемент не знайдено або переглянутий весь список. Якщо шуканий елемент відсутня, то виводиться повідомлення: «Такого немає». Якщо ж шуканий елемент знайдено, то поточний покажчик (temp) показує нею, й відбувається його удаление.

Якщо покажчики перший (first) і другий (cut) елементи нерівні, це відбувається пошук місцезнаходження елемента у списку. Якщо всередині поточного елемента покажчик подібний до попереднього елемент (prev) дорівнює nil, тоді покажчику подібний до попереднього елемент (prev) всередині наступного за поточним елементом присвоюється покажчик подібний до попереднього елемент всередині поточного, а покажчику перший елемент (first) у списку присвоюється покажчик наступного року елемент. Якщо всередині поточного елемента покажчик наступного року елемент (next) дорівнює nil, тоді покажчику наступного року елемент (next) всередині попереднього перед поточним елементом присвоюється покажчик наступного року елемент всередині поточного, а покажчику на останній елемент (cut) у списку присвоюється покажчик подібний до попереднього елемент. Якщо поточний елемент виявився «всередині» списку, тоді покажчику наступного року елемент (next) всередині попереднього перед поточним елементом присвоюється покажчик на наступний елемент всередині поточного, а покажчику подібний до попереднього елемент (prev) всередині наступного за поточним елементом присвоюється покажчик на попередній елемент всередині текущего.

Якщо ж покажчики перший (first) і другий (cut) елементи рівні, то покажчику перший елемент у списку (first) присвоюється nil.

Після перетворень всередині списку відбувається звільнення пам’яті поточного елемента (dispose (temp)). У цьому процедура видалення завершается.

Процедура перегляду «Prosm».

Цю процедуру виконує висновок вмісту списку на вигляді таблицы.

Спочатку на дисплей виводиться шапка таблиці, яка містить: «Прізвище Ім'я По батькові», «Дата народження» і «Знак зодіаку». Після висновку про шапки перевіряється наявність елементів в списке.

Якщо список містить елементи, це відбувається їх порядковий висновок. Це реалізовано з допомогою циклу, виконуваному, поки покажчик сучасний елемент (temp) не переберёт все елементи списку. У циклі обчислюється довжина прізвища, імені Ілліча та по батькові, після що вони виводяться на дисплей, а й за ними виводяться дата його й знак зодіаку; потім покажчику сучасний елемент (temp) присвоюється покажчик наступного року його элемент.

Якщо список виявиться порожній, то виводиться повідомлення: «Таблиця пуста».

Після закінчення циклу, або виведення повідомлення, процедура перегляду завершается.

Процедура сортування «Sortir».

З цією процедури застосована локальна змінна «tmp» типу «ukazat». Тут спочатку перевіряється наявність елементів в списке.

Якщо список містить елементи, то перемінної «m» присвоюється значення «true», потім виконується цикл, поки «m=true». У циклі перемінної «m» присвоюється значення «false», покажчику сучасний елемент (temp) присвоюється покажчик перший елемент у списку (first), і виконується вкладений цикл, поки покажчик наступного року елемент всередині поточного не дорівнює «nil». У цьому вся циклі перевіряється який елемент больше.

Якщо поточний елемент виявиться більш ніж наступний його елемент, тоді перемінної «m» присвоюється значення «true», та перевіряється місцезнаходження поточного елемента у списку. Якщо буде на початку списку, то покажчику перший елемент у списку (first) присвоюється покажчик наступного року елемент за поточним, а інакше покажчику наступного року елемент (next) всередині попереднього перед поточним елементом присвоюється покажчик наступного року елемент всередині поточного. Якщо ж поточний елемент опиниться у кінці списку, тоді покажчику на останній елемент у списку присвоюється покажчик сучасний елемент, а локальної перемінної «tmp» присвоюється значення «nil», а інакше покажчику подібний до попереднього елемент (prev) наступного елемента після наступного за поточним елементом присвоюється покажчик сучасний елемент, а локальної перемінної (tmp) присвоюється покажчик наступного року елемент після наступного за поточним елементом. Після з’ясування місцеположення і виконання деяких команд, покажчику наступного року елемент після наступного за поточним елементом присвоюється покажчик сучасний елемент, покажчику подібний до попереднього елемент наступного за поточним елементом присвоюється покажчик подібний до попереднього елемент перед поточним; а всередині поточного елемента покажчику подібний до попереднього перед поточним присвоюється покажчик наступного року елемент за поточним, і покажчику наступного року елемент за поточним присвоюється локальна змінна «tmp». Якщо ж поточний елемент не буде більш ніж наступний його елемент, тоді покажчику сучасний елемент (temp) присвоюється покажчик наступного року його елемент (next). У цьому виконання вкладеного циклу завершается.

Перемінної «m» знову присвоюється значення «false», а покажчику на поточний елемент (temp) присвоюється покажчик на останній елемент в списку (cut), і виконується ще одне вкладений цикл, поки покажчик на попередній елемент всередині поточного не дорівнює «nil». У цьому вся циклі перевіряється який елемент меньше.

Якщо поточний елемент виявиться менш як попередній проти нього елемент, тоді перемінної «m» присвоюється значення «true», та перевіряється місцезнаходження поточного елемента у списку. Якщо буде наприкінці списку, то покажчику на останній елемент у списку (cut) присвоюється покажчик подібний до попереднього елемент перед поточним, а інакше покажчику на попередній елемент (prev) всередині наступного за поточним елементом присвоюється покажчик подібний до попереднього елемент всередині поточного. Якщо ж поточний елемент опиниться у початку списку, тоді покажчику перший елемент у списку присвоюється покажчик сучасний елемент, а локальної перемінної «tmp» присвоюється значення «nil», а інакше покажчику наступного року елемент (next) попереднього елемента перед попереднім до поточного елемента присвоюється покажчик сучасний елемент, а локальної перемінної (tmp) присвоюється покажчик подібний до попереднього елемент перед попереднім до поточного елемента. Після з’ясування місцеположення і виконання деяких команд, покажчику подібний до попереднього елемент перед попереднім до поточного елемента присвоюється покажчик сучасний елемент, покажчику наступного року елемент попереднього перед поточним елементом присвоюється покажчик наступного року після поточного; а всередині поточного елемента покажчику наступного року елемент присвоюється покажчик подібний до попереднього елемент, і покажчику подібний до попереднього елемент присвоюється локальна змінна «tmp». Якщо ж поточний елемент не буде менш як попередній проти нього елемент, тоді покажчику на поточний елемент (temp) присвоюється покажчик подібний до попереднього проти нього елемент (prev). У цьому виконання вкладеного циклу завершается.

Якщо під час перевірки наявності елементів у списку виявиться, що він порожній, то виводиться повідомлення: «Таблиця порожня». Після закінчення циклу, або виведення повідомлення, процедура сортування завершается.