МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ Національний університет “Львівська політехніка” Кафедра ІСМ Звіт Лабораторна робота №11 “ Динамічні структури даних ” Львів – 2007 Мета роботи: Вивчити способи створення динамічних структур даних (списків, стеків, дерев, ...) та виконання операцій над ними. Методичні вказівки: Згідно з індивідуальним завданням розробити необхідні структури даних. Сформувати структури даних у динамічній пам’яті та проініціалізувати їх введеними з клавіатури значеннями. При відсутності в умові завдання наперед заданої кількості елементів спискових структур в якості ознаки завершення їх формування вибрати імітацію кінця файла клавіатурного введення (натискування клавіш Ctrl/Z), або ввести деяке обумовлене число чи символ. Виконати над елементами списку операції перетворення (формування, включення, виключення, пошук, виведення елементів), необхідні для розв’язування задачі. Операції над списком оформити у вигляді окремих функцій. Перед завершенням роботи програми звільнити виділену для списку динамічну пам’ять. Завдання: Ввести з клавіатури речення та переписати його слова в однонаправлений лінійний список. За допомогою списку підрахувати кількості повторень кожного слова. Текст програми: #include <stdio.h> #include <conio.h> #include <string.h> typedef struct SWORD *PSWORD; struct SWORD { char sz_word[20]; int i_repeats; PSWORD p_next; }; PSWORD addword(PSWORD *pp_list, char *sz_word) { while (*pp_list) pp_list = &((*pp_list)->p_next); *pp_list = new SWORD; strcpy((*pp_list)->sz_word, sz_word); (*pp_list)->i_repeats = 1; (*pp_list)->p_next = NULL; return *pp_list; } PSWORD remword(PSWORD p_word) { PSWORD p_next; p_next = p_word->p_next; delete p_word; return p_next; } void countrepeats(PSWORD p_list) { while (p_list) { if (p_list->i_repeats) { PSWORD p_cur = p_list->p_next; while (p_cur) { if (!strcmpi(p_list->sz_word, p_cur->sz_word)) { p_list->i_repeats++; p_cur->i_repeats = 0; } p_cur = p_cur->p_next; } } p_list = p_list->p_next; } } void printwords(PSWORD p_list) { while (p_list) { if (p_list->i_repeats) printf("%s - %d\n", p_list->sz_word, p_list->i_repeats); p_list = p_list->p_next; } } void main() { char sz_s[80], *sz_word; PSWORD p_list = NULL, p_cur = NULL; clrscr(); printf("Input string:\n"); gets(sz_s); sz_word = strtok(sz_s, " "); if (sz_word) addword(&p_list, sz_word); p_cur = p_list; while (sz_word = strtok(NULL, " ,;:-.")) p_cur = addword(&p_cur, sz_word); countrepeats(p_list); printf("\nResult:\n"); printwords(p_list); while (p_list = remword(p_list)); printf("\nPress any key to exit.\n"); getch(); } Висновок: В даній лабораторній роботі я закріпив знання в роботі з одно направленими списками. Повторив спосіб пошуку інформації.