Для ілюстрації деяких міркувань щодо покажчиків на структури та масивів структур, напишімо нашу програму підрахунку ключових слів знову, цього разу використовуючи покажчики замість індексів масиву.
Зовнішнє оголошення keytab не потребує змін, зате main і binsearch — так.
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#define MAXWORD 100
int getword(char *, int);
struct key *binsearch(char *, struct key *, int);
/* лічить ключові слова C; версія з покажчиками */
main()
{
char word[MAXWORD];
struct key *p;
while (getword(word, MAXWORD) != EOF)
if (isalpha(word[0]))
if ((p=binsearch(word, keytab, NKEYS)) != NULL)
p->count++;
for (p = keytab; p < keytab + NKEYS; p++)
if (p->count > 0)
printf("%4d %s\n", p->count, p->word);
return 0;
}
/* binsearch: знаходить слово у tab[0]...tab[n-1] */
struct key *binsearch(char *word, struck key *tab, int n)
{
int cond;
struct key *low = &tab[0];
struct key *high = &tab[n];
struct key *mid;
while (low < high) {
mid = low + (high-low) / 2;
if ((cond = strcmp(word, mid->word)) < 0)
high = mid;
else if (cond > 0)
low = mid + 1;
else
return mid;
}
return NULL;
}
Тут існує декілька речей, вартих, щоб на них звернути увагу. Перш за все, оголошенняbinsearch повинно вказувати, що функція повертає покажчик на struct key, замість цілого; це оголошено в обох місцях, прототипові функції, та самій binsearch. Коли binsearchзнаходить слово, вона повертає покажчик на нього; якщо зазнала невдачі — NULL.
Друге — елементи keytab тепер досяжні через покажчики. Це вимагає істотних змінbinsearch.
Ініціалізатори low і high тепер покажчики на початок і поза кінець таблиці.
Обчислення середнього елемента тепер не може бути звичайним
mid = (low+high) / 2 /* НЕПРАВИЛЬНО */
оскільки додавання покажчиків заборонено. Віднімання, однак, дозволено, тож high-lowдорівнюватиме кількості елементів, таким чином
mid = low + (high-low) / 2
встановить mid покажчиком на елемент посередині між low і high.
Найважливішою зміною є поправка алгоритму, щоб впевнитися, що він не видасть недійсного покажчика або намагатиметься дістатися до елемента поза межами масиву. Проблема в тому, що&tab[- 1] і &tab[n], обидва, знаходяться зовні масиву tab. Перший вираз просто недійсний, тоді як на другий не дозволено посилатися. Проте означення мови гарантує, що арифметика покажчиків, що стосується першого елемента поза межами масиву (тобто tab[n]) працюватиме правильно.
У main ми написали
for (p = keytab; p < keytab + NKEYS; p++)
Якщо p, це покажчик на структуру, то арифметика з p бере до уваги розмір структури, тож p++збільшує p на потрібне значення, щоб дістатися до наступного елемента масиву структур, а тестова умова зупиняє цикл у потрібну мить.
Не гадайте, однак, що розмір структури рівний сумі розмірів її членів. Через вимоги вирівнювання різноманітних об'єктів, можуть існувати безіменні «дірки» в структурі. Таким чином, наприклад, якщо розмір char рівний одному байтові, а int — чотирьом, структура
struct {
char c;
int i;
};
може, тим не менш, вимагати восьми байтів, а не п'яти. Оператор sizeof поверне справжнє значення. І, нарешті, відступ щодо формату програми: коли функція повертає складний тип на зразок покажчика на структуру, як от
struct key *binsearch(char *word, struct key *tab, int n)
назву функції може бути важко побачити або знайти в текстовому редакторі. Відповідно, часом використовується альтернативний стиль запису:
struct key *
binsearch(char *word, struct key *tab, int n)
Це залежить від особистих уподобань; виберіть ту форму, яка вам до вподоби та дотримуйтеся її.
