Скажімо, ми хотіли би справитися з більш узагальненою проблемою підрахунку всіх слів вводу. Оскільки список слів невідомий заздалегідь, нам не вдасться зручно посортувати та використати бінарний пошук. Одночасно, використання лінійного пошуку для порівняння кожного нового слова з попередніми не є ефективним; програма займе забагато часу. (Якщо точніше, то час обігу програми зросте в квадраті до кількості введених слів.) Як можна організувати дані для того, щоб можна було ефективно упоратись зі списком довільних слів?
Одним з виходів із даного становища є збереження сортованого набору зустрінутих слів через розміщення кожного слова одразу у відповідне положення під час надходження. Однак, це не слід робити шляхом зміщення слів у лінійному масиві — це також забирає забагато часу. Натомість ми використаємо структуру даних під назвою бінарне дерево.
Дерево містить по одному «вузлу» на окреме слово; кожний вузол включає
- покажчик на текст слова,
- відлік випадків цього слова,
- покажчик на лівий дочірній вузол,
- покажчик на правий дочірній вузол.
Жоден вузол не може мати більш ніж двоє дочірніх вузлів; він може також мати нуль або один.
Вузли зберігаються в такий спосіб, що будь-який вузол у лівій частині відгалуження містить тільки слова, лексиграфічно менші за слово вузла, а праві відгалуження — лексикографічно більші. Ось дерево для речення «now is the time for all good men to come to the aid of their party» побудоване шляхом додавання кожного слова під час його знаходження:
now
/ \
is the
/ \ / \
for men of time
/ \ \ / \
all good party their to
/ \
aid come
Щоб дізнатися, чи нове слово вже було внесено в дерево, розпочніть з кореня і порівняйте нове слово зі словом, збереженим у цьому вузлі. Якщо вони збіглися, відповідь є стверджувальною. Якщо нове слово менше за вузлове, шукайте далі в лівому дочірньому вузлі, у протилежному випадку — в правому. Якщо не залишилось дочірніх відгалужень у заданому напрямку, нове слово не було внесено в дерево, і дійсно, порожній сегмент і буде тим місцем, де потрібно зберегти нове слово. Цей процес є рекурсивним, оскільки пошук з будь-якого вузла розпочинає новий з одного зі своїх дочірніх. Відповідно, натуральнішою буде рекурсивна функція для додання і виводу.
Повертаючись назад до опису вузла, найзручнішим буде представити його як структуру з чотирьох складових:
struct tnode { /* вузол дерева: */
char *word; /* покажчик на ланцюжок */
int count; /* кількість його повторень */
struct tnode *left; /* лівий дочірній вузол */
struct tnode *right; /* правий дочірній вузол */
};
Це рекурсивне оголошення вузла може виглядати складеним навмання, але воно правильне. Структурі не дозволяється включати копію самої себе, але
struct tnode *left;
оголошує left як покажчик на tnode, а не саму tnode.
Інколи, вам можуть знадобитися дві зворотньо-звернені структури: дві структури, що посилаються одна на одну. Щоб добитися цього, потрібно
struct t {
...
struct s *p; /* p є покажчиком на s */
};
struct s {
...
struct t *q; /* q є покажчиком на t */
};
Код самої програми — на дивовижу короткий, маючи жменю вже написаних нами допоміжних функцій, таких як getword. Функція main читає слова, користуючись getword, і розміщає їх у дереві за допомогою addtree.
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#define MAXWORD 100
struct tnode *addtree(struct tnode *, char *);
void treeprint(struct tnode *);
int getword(char *, int);
/* word frequency count */
main()
{
struct tnode *root;
char word[MAXWORD];
root = NULL;
while (getword(word, MAXWORD) != EOF)
if (isalpha(word[0]))
root = addtree(root, word);
treeprint(root);
return 0;
}
Наступна функція, adtree, — рекурсивна. Функція main розмістить перше слово на найвищому рівні (корені) дерева. На кожній стадії, нове слово порівнюватиметься зі вже збереженим вузловим словом, і буде переміщено вниз до правого або лівого відгалуження через рекурсивний виклик adtree. Зрештою, слово може збігтися з чимось, вже привнесеним у дерево (тоді просто збільшується відлік цього слова), або відбудеться зіткнення з нульовим покажчиком, що вказуватиме, що потрібно створити вузол і додати його до дерева. Коли створено новий вузол, addtree повертає покажчик на нього, що буде розміщено у батьківському вузлі.
struct tnode *talloc(void);
char *strdup(char *);
/* addtree: додає вузол із w, в або нижче p */
struct tnode *addtree(struct tnode *p, char *w)
{
int cond;
if (p == NULL) { /* надійшло нове слово */
p = talloc(); /* створити новий вузол */
p->word = strdup(w);
p->count = 1;
p->left = p->right = NULL;
} else if ((cond = strcmp(w, p->word)) == 0)
p->count++; /* повторне слово */
else if (cond < 0) /* якщо менше - ліве відгалуження */
p->left = addtree(p->left, w);
else /* якщо більше - праве відгалуження */
p->right = addtree(p->right, w);
return p;
}
Місце для зберігання нового вузла забезпечується функцією talloc, яка повертає покажчик на вільне місце, придатне для утримання вузла дерева, і нове слово копіюється до прихованого місця за допомогою strdup. (Ми розглянемо ці функції за якусь мить.) Ініціалізується count(змінна відліку), два дочірніх вузли отримають значення NULL. Ця частина коду виконується тільки в «кроні» дерева, під час додання нового вузла. Ми (нерозумно) пропустили перевірку на помилки щодо значень повернутих strdup і talloc.
treeprint виводить дерево в сортованому вигляді; для кожного вузла, вона виводить ліве відгалуження (всі слова менші за дане), потім саме слово, потім праве відгалуження (всі слова більші за дане). Якщо ви почуваєтесь невпевнено, щодо того, як працює рекурсія, можете симулювати роботу treeprint, як показано нижче.
/* treeprint: впорядкований вивід дерева p */
void treeprint(struct tnode *p)
{
if (p != NULL) {
treeprint(p->left);
printf("%4d %s\n", p->count, p->word);
treeprint(p->right);
}
}
Практичне зауваження: якщо дерево стає «незбалансованим» від того, що слова не надходять у довільній послідовності, час обігу програми може суттєво збільшитись. У найгіршому випадку, коли слова вже знаходяться в правильній послідовності, ця програма здійснить ресурсоємку симуляцію лінійного пошуку. Існують більш узагальнені версії бінарного дерева, що не страждають від цього найгіршого випадку, але ми не обговорюватимемо їх тут.
Перед тим як залишити цей приклад, варто зробити невеличкий відступ щодо розподільників пам'яті. Очевидно, що бажано мати тільки один розподільник у програмі, навіть якщо від розподіляє під різнорідні об'єкти. Але якщо існує тільки один розподільник для обробки запитів щодо, скажімо, покажчиків на char, і покажчики на struct tnode, тоді виникають два питання. Перш за все, як він виконуватиме вимогу більшості машин щодо того, що об'єкти певних типів повинні вдовольняти обмеження по вирівнюванню (наприклад, що цілі, часто, повинні знаходитись у парних адресах)? Друге, які оголошення можуть справитись із фактом того, що розподільник повинен обов'язково повернути різні типи покажчиків?
Вимоги по вирівнюванню, загалом, можна легко вдовольнити ціною деякого змарнованого простору, впевнившись, що розподільник завжди повертає покажчик, що відповідає всім обмеженням по вирівнюванню. Функція alloc з Розділу 5 не гарантує жодного вирівнювання, тож ми скористаємося з функції стандартної бібліотеки malloc, яка упорається з цим. У Розділі 8, ми покажемо один із способів втілення malloc.
Питання, щодо оголошення типу для таких функцій як malloc, є головною біллю для будь-якої мови, що піклується про перевірку типів. У C, чинним є оголосити, що malloc повертає покажчик на void, що дозволяє перетворити покажчик на бажаний тип за допомогою зведення типу. malloc і споріднені функції оголошено в файлі заголовка <stdlib.h>. Тож, функціюtalloc можна написати як
#include <stdlib.h>
/* talloc: створює tnode */
struct tnode *talloc(void)
{
return (struct tnode *) malloc(sizeof(struct tnode));
}
strdup просто копіює, наданий їй як аргумент, ланцюжок у безпечне місце, здобуте викликомmalloc:
char *strdup(char *s) /* копіює s */
{
char *p;
p = (char *) malloc(strlen(s)+1); /* +1 для '\0' */
if (p != NULL)
strcpy(p, s);
return p;
}
malloc поверне NULL, якщо не залишилось місця; strdup передасть це значення далі, залишаючи обробку помилок тому, хто її викликав.
Місце, відведене malloc можна звільнити для перевикористання за допомогою free.
Вправа 6-2. Напишіть програму, що читатиме вихідний текст на C і виводитиме в алфавітній послідовності кожну групу назв змінних, перші 6 літер яких збігаються. Нехай вона не бере до уваги ланцюжки і коментарі. Зробіть 6 параметром, який можна встановити з командного рядка.
Вправа 6-3. Напишіть програму перехресного посилання, яка би виводила список усіх слів у документі, і для кожного слова, список номерів рядків, де воно з'являється. Не звертайте уваги на «шум», такі слова як «the», «for» тощо.
Вправа 6-4. Напишіть програму, яка би виводила окремі слова вводу, сортовані у спадаючій послідовності за кількістю повторень. Додайте число повторень кожного слова попереду.
