Очереди, стеки, связанные списки и деревья
Как известно, программы состоят из двух частей — алгоритмов и структур данных. В хорошей программе эти составляющие эффективно дополняют друг друга. Выбор и реализация структуры данных насколько же важны, как и процедуры для обработки данных. Способ организации и доступа к информации обычно определяется природой программируемой задачи. Таким образом, для программиста важно иметь в своем распоряжении приемы, подходящие для различных ситуаций.
Степень привязки типа данных к своему машинному представлению находится в обратной зависимости от его абстракции. Другими словами, чем более абстрактными становятся типы данных, тем больше концептуальное представление о способе хранения этих данных отличается от реального, фактического способа их хранения в памяти компьютера Простые типы, например, char или int, тесно связаны со своим машинным представлением. Например, машинное представление целочисленного значения хорошо аппроксимирует соответствующую концепцию программирования. По мере своего усложнения типы данных становятся концептуально менее похожими на свои машинные эквиваленты. Так, действительные числа с плавающей точкой более абстрактны, чем целые числа. Фактическое представление типа float в машине весьма приблизительно соответствует представлению среднего программиста о действительном числе. Еще более абстрактной является структура, принадлежащая к составным типам данных.
На следующем уровне абстракции сугубо физические аспекты данных отходят на второй план вследствие введения механизма доступа (data engine) к данным, то есть механизма сохранения и получения информации. По существу, физические данные связываются с механизмом доступа, который управляет работой с данными из программы. Именно механизмам доступа к данным и посвящена эта глава.
Существует четыре механизма доступа:
==>> Очередь (queue)
==>> Стек (stack)
==>> Связанный список (linked list)
==>> Двоичное дерево (binary tree)
Каждый из этих методов дает возможность решать задачи определенного класса. Эти методы по существу являются механизмами, выполняющими определенные операции сохранения и получения передаваемой им информации на основе получаемых ими запросов. Они все сохраняют и получают элемент, здесь под элементом подразумевается информационная единица. В этой главе показано, как создавать такие механизмы доступа на языке С. При этом проиллюстрированы некоторые распространенные приемы программирования в С, включая динамическое выделение памяти и использование указателей.
Очереди
Очередь — это линейный список информации, работа с которой происходит по принципу "первым пришел — первым вышел" (first-in, first-out); этот принцип (и очередь как структура данных) иногда еще называется FIFO[1]. Это значит, что первый помещенный в очередь элемент будет получен из нее первым, второй помещенный элемент будет извлечен вторым и т.д. Это единственный способ работы с очередью; произвольный доступ к отдельным элементам не разрешается.
Очереди очень часто встречаются в реальной жизни, например, около банков или ресторанов быстрого обслуживания. Чтобы представить себе работу очереди, давайте введем две функции: qstore() и qretrieve() (от "store"— "сохранять", "retrieve" — "получать"). Функция qstore() помещает элемент в конец очереди, а функция qretrieve() удаляет элемент из начала очереди и возвращает его значение. В табл. 22.1 показано действие последовательности таких операций.
Действие Содержимое очереди
qstore(A) A
qstore(B) А В
qstore(C) A B C
qretrieve() возвращает А В С
qstore(D) B C D
qretrieve() возвращает В C D
qretrieve() возвращает С D
Следует иметь в виду, что операция извлечения удаляет элемент из очереди и уничтожает его, если он не хранится где-нибудь в другом месте. Поэтому после извлечения всех элементов очередь будет пуста.
В программировании очереди применяются при решении многих задач. Один из наиболее популярных видов таких задач — симуляция. Очереди также применяются в планировщиках задач операционных систем и при буферизации ввода/вывода.
Чтобы проиллюстрировать работу очереди, мы напишем простую программу планирования встреч. Эта программа позволяет сохранять информацию о некотором количестве встреч; потом по мере прохождения каждой встречи она удаляется из списка. Для упрощения описание встреч ограничено 255 символами, а количество встреч — произвольным числом 100.
При разработке этой простой программы планирования необходимо прежде всего реализовать описанные здесь функции qstore() и qretrieve(). Они будут хранить указатели на строки, содержащие описания встреч.
#define MAX 100
char *p[MAX];
int spos = 0;
int rpos = 0;
/* Сохранение встречи. */
void qstore(char *q)
{
if(spos==MAX) {
printf("Список переполнен\n");
return;
}
p[spos] = q;
spos++;
}
/* Получение встречи. */
char *qretrieve()
{
if(rpos==spos) {
printf("Встреч больше нет.\n");
return '\0';
}
rpos++;
return p[rpos-1];
}
Обратите внимание, что этим двум функциям требуются две глобальные переменные: spos, в которой хранится индекс следующего свободного места в списке, и rpos, в которой хранится индекс следующего элемента, подлежащего выборке. С помощью этих функций можно организовать очередь данных другого типа, просто поменяв базовый тип обрабатываемого ими массива.
Функция qstore() помещает описания новых встреч в конец списка и проверяет, не переполнен ли список. Функция qretrieve() извлекает встречи из очереди, если таковые имеются. При назначении встреч увеличивается значение переменной spos, а по мере их прохождения увеличивается значение переменной rpos. По существу, rpos "догоняет" spos в очереди. На рис 22.1 показано, что может происходить в памяти при выполнении программы. Если rpos и spos равны, назначенные события отсутствуют. Даже несмотря на то, что функция qretrieve() не уничтожает хранящуюся в очереди информацию физически, эту информацию можно считать уничтоженной, так как повторно получить доступ к ней невозможно.
Начальное сосотояние очереди
↓spos
+---+---+---+---+---+---+---+---+---+---+---+
| | | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
↑rpos
qstore('A')
↓spos
+---+---+---+---+---+---+---+---+---+---+---+
| A | | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
↑rpos
qstore('B')
↓spos
+---+---+---+---+---+---+---+---+---+---+---+
| A | B | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
↑rpos
qretrive()
↓spos
+---+---+---+---+---+---+---+---+---+---+---+
| | B | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
↑rpos
qretrive()
↓spos
+---+---+---+---+---+---+---+---+---+---+---+
| | | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
↑rpos
qstore('A')
↓spos
+---+---+---+---+---+---+---+---+---+---+---+
| | | C | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
↑rpos
Текст программы простого планировщика встреч целиком приведен ниже. Вы можете доработать эту программу по своему усмотрению.
/* Мини-планировщик событий */
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#define MAX 100
char *p[MAX], *qretrieve(void);
int spos = 0;
int rpos = 0;
void enter(void), qstore(char *q), review(void), delete_ap(void);
int main(void)
{
char s[80];
register int t;
for(t=0; t < MAX; ++t) p[t] = NULL; /* иницилизировать массив
пустыми указателями */
for(;;) {
printf("Ввести (E), Список (L), Удалить (R), Выход (Q): ");
gets(s);
*s = toupper(*s);
switch(*s) {
case 'E':
enter();
break;
case 'L':
review();
break;
case 'R':
delete_ap();
break;
case 'Q':
exit(0);
}
}
return 0;
}
/* Вставка в очередь новой встречи. */
void enter(void)
{
char s[256], *p;
do {
printf("Введите встречу %d: ", spos+1);
gets(s);
if(*s==0) break; /* запись не была произведена */
p = (char *) malloc(strlen(s)+1);
if(!p) {
printf("Не хватает памяти.\n");
return;
}
strcpy(p, s);
if(*s) qstore(p);
} while(*s);
}
/* Просмотр содержимого очереди. */
void review(void)
{
register int t;
for(t=rpos; t < spos; ++t)
printf("%d. %s\n", t+1, p[t]);
}
/* Удаление встречи из очереди. */
void delete_ap(void)
{
char *p;
if((p=qretrieve())==NULL) return;
printf("%s\n", p);
}
/* Вставка встречи. */
void qstore(char *q)
{
if(spos==MAX) {
printf("List Full\n");
return;
}
p[spos] = q;
spos++;
}
/* Извлечение встречи. */
char *qretrieve(void)
{
if(rpos==spos) {
printf("Встречь больше нет.\n");
return NULL;
}
rpos++;
return p[rpos-1];
}
Циклическая очередь
При изучении предыдущего примера программы планирования встреч, вероятно, вам в голову мог прийти следующий способ ее улучшения: при достижении конца массива, в котором хранится очередь, можно не останавливать программу, а устанавливать индексы вставки (spos) и извлечения (rpos) так, чтобы они указывали на начало массива. Это позволит помещать в очередь любое количество элементов при условии их своевременного извлечения. Такая реализация очереди называется циклической очередью, поскольку массив используется так, будто он представляет собой не линейный список, а кольцо.
Чтобы организовать в программе-планировщике циклическую очередь, функции qstore() и qretrieve() необходимо переписать следующим образом:
void qstore(char *q)
{
/* Очередь переполняется, когда spos на единицу
меньше rpos, либо когда spos указывает
на конец массива, а rpos - на начало.
*/
if(spos+1==rpos || (spos+1==MAX && !rpos)) {
printf("Список полон\n");
return;
}
p[spos] = q;
spos++;
if(spos==MAX) spos = 0; /* установить на начало */
}
char *qretrieve(void)
{
if(rpos==MAX) rpos = 0; /* установить на начало */
if(rpos==spos) {
printf("Встреч больше нет.\n");
return NULL;
}
rpos++;
return p[rpos-1];
}
В данной версии программы очередь переполняется, когда индекс записи находится непосредственно перед индексом извлечения; в противном случае еще есть место для вставки события. Очередь пуста, когда rpos равняется spos.
Вероятно, чаще всего циклические очереди применяются в операционных системах для хранения информации, учитываемой и записываемой в дисковые файлы или на консоль. Циклические очереди также используются в программах обработки реального времени, которые должны продолжать обрабатывать информацию, буферизируя при этом запросы на ввод/вывод. Многие текстовые процессоры используют этот прием во время переформатирования абзаца или выравнивания строки. Вводимый текст не отображается на экране до окончания процесса. Для этого прикладная программа должна проверять нажатие клавиш во время выполнения другой задачи. Если какая-либо клавиша была нажата, введенный символ быстро помещается в очередь, и процесс продолжается. После его завершения символы извлекаются из очереди.
Чтобы ощутить на практике данное применение циклических очередей, давайте рассмотрим простую программу, состоящую из двух процессов. Первый процесс в программе выводит на экран числа от 1 до 32 000. Второй процесс помещает символы в очередь по мере их ввода, не отображая их на экране, пока пользователь не нажмет <Enter>. Вводимые символы не отображаются, поскольку первому процессу дан приоритет в отношении вывода на экран. После нажатия <Enter> символы из очереди извлекаются и печатаются.
Чтобы программа работала, как описано выше, в ней необходимо использовать две функции, не определенные в стандартном языке С: _kbhit() и _getch(). Функция _kbhit() возвращает значение ИСТИНА, если на клавиатуре была нажата клавиша; в противном случае она возвращает ЛОЖЬ. Функция _getch() считывает введенный символ, но не дублирует его на экране. В стандарте языка С не предусмотрены функции для проверки состояния клавиатуры или считывания символов без отображения на экране, поскольку эти функции зависят от операционной системы. Тем не менее, в большинстве библиотек компиляторов есть функции, выполняющие данные задачи. Приведенная здесь небольшая программа компилируется с помощью компилятора Microsoft.
/* Пример циклической очереди в качестве буфера клавиатуры. */
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define MAX 80
char buf[MAX+1];
int spos = 0;
int rpos = 0;
void qstore(char q);
char qretrieve(void);
int main(void)
{
register char ch;
int t;
buf[80] = '\0';
/* Принимать вводимые символы до нажатия < Enter >. */
for(ch=' ',t=0; t < 32000 && ch!='\r'; ++t) {
if(_kbhit()) {
ch = _getch();
qstore(ch);
}
printf("%d ", t);
if(ch == '\r') {
/* Вывести на экран содержимое буфера клавиатуры
и освободить буфер. */
printf("\n");
while((ch=qretrieve()) != '\0') printf("%c", ch);
printf("\n");
}
}
return 0;
}
/* Занесение символа в очередь. */
void qstore(char q)
{
if(spos+1==rpos || (spos+1==MAX && !rpos)) {
printf("Список полон\n");
return;
}
buf[spos] = q;
spos++;
if(spos==MAX) spos = 0; /* установить на начало */
}
/* Получение символа из очереди. */
char qretrieve(void)
{
if(rpos==MAX) rpos = 0; /* установить на начало */
if(rpos==spos) return '\0';
rpos++;
return buf[rpos-1];
}
Стеки
Стек (stack) является как бы противоположностью очереди, поскольку он работает по принципу "последним пришел — первым вышел" (last-in, first-out, LIFO). Чтобы наглядно представить себе стек, вспомните стопку тарелок. Первая тарелка, стоящая на столе, будет использована последней, а последняя тарелка, положенная наверх — первой. Стеки часто применяются в системном программном обеспечении, включая компиляторы и интерпретаторы.
При работе со стеками операции занесения и извлечения элемента являются основными. Данные операции традиционно называются "затолкать в стек" (push) и "вытолкнуть из стека" (pop). Поэтому для реализации стека необходимо написать две функции: push(), которая "заталкивает" значение в стек, и pop(), которая "выталкивает" значение из стека. Также необходимо выделить область памяти, которая будет использоваться в качестве стека. Для этой цели можно отвести массив или динамически выделить фрагмент памяти с помощью функций языка С, предусмотренных для динамического распределения памяти. Как и в случае очереди, функция извлечения получает из списка элемент и удаляет его, если он не хранится где-либо еше. Ниже приведена общая форма функций push() и pop(), работающих с целочисленным массивом. Стеки данных другого типа можно организовывать, изменив базовый тип данных массива.
int stack[MAX];
int tos=0; /* вершина стека */
/* Затолкать элемент в стек. */
void push(int i)
{
if(tos >= MAX) {
printf("Стак полон\n");
return;
}
stack[tos] = i;
tos++;
}
/* Получить верхний элемент стека. */
int pop(void)
{
tos--;
if(tos < 0) {
printf("Стек пуст\n");
return 0;
}
return stack[tos];
}
Переменная tos ("top of stack" — "вершина стека") содержит индекс вершины стека. При реализации данных функций необходимо учитывать случаи, когда стек заполнен или пуст. В нашем случае признаком пустого стека является равенство tos нулю, а признаком переполнения стека — такое увеличение tos, что его значение указывает куда-нибудь за пределы последней ячейки массива. Пример работы стека показан в табл.
Действие Содержимое стека
push(A) A
push(B) В А
push(C) C B A
рор() извлекает С В А
push(F) F В А
рор() извлекает F В А
рор() извлекает В А
рор() извлекает А пусто
Прекрасный пример использования стека — калькулятор с четырьмя действиями. Большинство современных калькуляторов воспринимают стандартную запись выражений, называемую инфиксной записью[5], общая форма которой выглядит как операнд-оператор-операнд. Например, чтобы сложить 100 и 200, необходимо ввести 100, нажать кнопку "плюс" ("+"), затем ввести 200 и нажать кнопку "равно" ("="). Напротив, во многих ранних калькуляторах (и некоторых из производимых сегодня) применяется постфиксная запись[6], в которой сначала вводятся оба операнда, а затем оператор. Например, чтобы сложить 100 и 200 в постфиксной записи, необходимо ввести 100, затем 200, а потом нажать клавишу "плюс". В этом методе операнды при вводе заталкиваются в стек. При вводе оператора операнды извлекаются (выталкиваются) из стека, а результат помещается обратно в стек. Одно из преимуществ постфиксной формы заключается в легкости ввода длинных сложных выражений.
Следующий пример демонстрирует использование стека в программе, реализующей постфиксный калькулятор для целочисленных выражений. Для начала необходимо модифицировать функции push() и pop(), как показано ниже. Следует знать, что стек будет размешаться в динамически распределяемой памяти, а не в массиве фиксированного размера. Хотя применение динамического распределения памяти и не требуется в таком простом примере, мы увидим, как использовать динамическую память для хранения данных стека.
int *p; /* указатель на область свободной памяти */
int *tos; /* указатель на вершину стека */
int *bos; /* указатель на дно стека */
/* Занесение элемента в стек. */
void push(int i)
{
if(p > bos) {
printf("Стек полон\n");
return;
}
*p = i;
p++;
}
/* Получение верхнего элемента из стека. */
int pop(void)
{
p--;
if(p < tos) {
printf("Стек пуст\n");
return 0;
}
return *p;
}
Перед использованием этих функций необходимо выделить память из области свободной памяти с помощью функции malloc() и присвоить переменой tos адрес начала этой области, а переменной bos — адрес ее конца.
Текст программы постфиксного калькулятора целиком приведен ниже.
/* Простой калькулятор с четырмя действиями. */
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
int *p; /* указатель на область свободной памяти */
int *tos; /* указатель на вершину стека */
int *bos; /* указатель на дно стека */
void push(int i);
int pop(void);
int main(void)
{
int a, b;
char s[80];
p = (int *) malloc(MAX*sizeof(int)); /* получить память для стека */
if(!p) {
printf("Ошибка при выделении памяти\n");
exit(1);
}
tos = p;
bos = p + MAX-1;
printf("Калькулятор с четырьмя действиями\n");
printf("Нажмите 'q' для выхода\n");
do {
printf(": ");
gets(s);
switch(*s) {
case '+':
a = pop();
b = pop();
printf("%d\n", a+b);
push(a+b);
break;
case '-':
a = pop();
b = pop();
printf("%d\n", b-a);
push(b-a);
break;
case '*':
a = pop();
b = pop();
printf("%d\n", b*a);
push(b*a);
break;
case '/':
a = pop();
b = pop();
if(a==0) {
printf("Деление на 0.\n");
break;
}
printf("%d\n", b/a);
push(b/a);
break;
case '.': /* показать содержимое вершины стека */
a = pop();
push(a);
printf("Текущее значение на вершине стека: %d\n", a);
break;
default:
push(atoi(s));
}
} while(*s != 'q');
return 0;
}
/* Занесение элемента в стек. */
void push(int i)
{
if(p > bos) {
printf("Стек полон\n");
return;
}
*p = i;
p++;
}
/* Получение верхнего элемента из стека. */
int pop(void)
{
p--;
if(p < tos) {
printf("Стек пуст\n");
return 0;
}
return *p;
}
Связанные списки
Очереди и стеки имеют две характерные особенности: обе структуры данных имеют строгие правила доступа к хранящимся в них данным, причем в результате выполнения операций извлечения данные, в сущности, уничтожаются. Другими словами, доступ к элементу в стеке или очереди приводит к его удалению, и если этот элемент не сохранить где-либо в другом месте, он теряется. Кроме того, и в стеке, и в очереди используется один последовательный участок памяти. В отличие от стека или очереди, связанный список допускает гибкие способы доступа, поскольку каждый фрагмент информации имеет ссылку на следующий элемент данных в цепочке. Кроме того, операция извлечения не приводит к удалению из списка и уничтожению элемента данных. В принципе, для этой цели необходимо ввести дополнительную специальную операцию удаления.
Связанные списки могут быть односвязными и двусвязными[1]. Односвязный список содержит ссылку на следующий элемент данных. Двусвязный список содержит ссылки как на последующий, так и на предыдущий элементы списка. Выбор типа применяемого списка зависит от конкретной задачи.
Односвязные списки
В односвязном списке каждый элемент информации содержит ссылку на следующий элемент списка. Каждый элемент данных обычно представляет собой структуру, которая состоит из информационных полей и указателя связи. Концептуально односвязный список выглядит так.
+---------+ +---------+ +---------+
| данные | | данные | | данные |
+---------+ +---------+ +---------+
|указатель|--->|указатель|--->| 0 |
+---------+ +---------+ +---------+
Существует два основных способа построения односвязного списка. Первый способ — помещать новые элементы в конец списка[1]. Второй — вставлять элементы в определенные позиции списка, например, в порядке возрастания. От способа построения списка зависит алгоритм функции добавления элемента. Давайте начнем с более простого способа создания списка путем помещения элементов в конец.
Как правило, элементы связанного списка являются структурами, так как, помимо данных, они содержат ссылку на следующий элемент. Поэтому необходимо определить структуру, которая будет использоваться в последующих примерах. Поскольку списки рассылки обычно хранятся в связанных списках, хорошим выбором будет структура, описывающая почтовый адрес. Ее описание показано ниже:
struct address {
char name[40];
char street[40];
char city[20];
char state[3];
char zip[11];
struct address *next; /* ссылка на следующий адрес */
} info;
Приведенная ниже функция slstore() создает односвязный список путем помещения каждого очередного элемента в конец списка. В качестве параметров ей передаются указатель на структуру типа address, содержащую новую запись, и указатель на последний элемент списка. Если список пуст, указатель на последний элемент должен быть равен нулю.
void slstore(struct address *i,
struct address **last)
{
if(!*last) *last = i; /* первый элемент в списке */
else (*last)->next = i;
i->next = NULL;
*last = i;
}
Несмотря на то, что созданный с помощью функции slstore() список можно отсортировать отдельной операцией уже после его создания, легче сразу создавать упорядоченный список, вставляя каждый новый элемент в нужное место в последовательности. Кроме того, если список уже отсортирован, имеет смысл поддерживать его упорядоченность, вставляя новые элементы в соответствующие позиции. Для вставки элемента таким способом требуется последовательно просматривать список до тех пор, пока не будет найдено место нового элемента, затем вставить в найденную позицию новую запись и переустановить ссылки.
При вставке элемента в односвязный список может возникнуть одна из трех ситуаций: элемент становится первым, элемент вставляется между двумя другими, элемент становится последним. На рис. 22.3 показана схема изменения ссылок в каждом случае.
Вставка в начало списка
+----+ п +----+
|new | р |new |
+----+ е +----+
| | в .------------| |
+----+ р | +----+
а |
+----+ +----+ +----+ щ в | +----+ +----+ +----+
|info| |info| |info| а | |info| |info| |info|
\/\/\->+----+ +----+ +----+ е | +----+ +----+ +----+
| |--->| |--->| 0 | т '->| |--->| |--->| 0 |
+----+ +----+ +----+ с +----+ +----+ +----+
я
Вставка в середину списка
+----+ п +----+
|new | р |new |
+----+ е +----+
| | в .---------->| |
+----+ р | .--+----+
а | |
+----+ +----+ +----+ щ в | +----+ | +----+ +----+
|info| |info| |info| а | |info| | |info| .->|info|
\/\/\->+----+ +----+ +----+ е \/\/\->+----+ | +----+ | +----+
| |--->| |--->| 0 | т '-| | '->| |-' | 0 |
+----+ +----+ +----+ с +----+ +----+ +----+
я
Вставка в конец списка
+----+ п +----+
|new | р |new |<----------.
+----+ е +----+ |
| | в | 0 | |
+----+ р +----+ |
а |
+----+ +----+ +----+ щ в +----+ +----+ +----+ |
|info| |info| |info| а |info| .->|info| |info| |
\/\/\->+----+ +----+ +----+ е \/\/\->+----+ | +----+ +----+ |
| |--->| |--->| 0 | т | |-' | |--->| |-'
+----+ +----+ +----+ с +----+ +----+ +----+
я
Следует помнить, что при вставке элемента в начало (первую позицию) списка необходимо также изменить адрес входа в список где-то в другом месте программы. Чтобы избежать этих сложностей, можно в качестве первого элемента списка хранить служебный сторожевой элемент[2]. В случае упорядоченного списка необходимо выбрать некоторое специальное значение, которое всегда будет первым в списке, чтобы начальный элемент оставался неизменным. Недостатком данного метода является довольно большой расход памяти на хранение сторожевого элемента, но обычно это не столь важно.
Следующая функция, sls_store(), вставляет структуры типа address в список рассылки, упорядочивая его по возрастанию значений в поле name. Функция принимает указатели на указатели на первый и последний элементы списка, а также указатель на вставляемый элемент. Поскольку первый или последний элементы списка могут измениться, функция sls_store() при необходимости автоматически обновляет указатели на начало и конец списка. При первом вызове данной функции указатели first и last должны быть равны нулю.
/* Вставка в упорядоченный односвязный список. */
void sls_store(struct address *i, /* новый элемент */
struct address **start, /* начало списка */
struct address **last) /* конец списка */
{
struct address *old, *p;
p = *start;
if(!*last) { /* первый элемент в списке */
i->next = NULL;
*last = i;
*start = i;
return;
}
old = NULL;
while(p) {
if(strcmp(p->name, i->name) < 0) {
old = p;
p = p->next;
}
else {
if(old) { /* вставка в середину */
old->next = i;
i->next = p;
return;
}
i->next = p; /* вставка в начало */
*start = i;
return;
}
}
(*last)->next = i; /* вставка в конец */
i->next = NULL;
*last = i;
}
Последовательный перебор элементов связанного списка осуществляется очень просто: начать с начала и следовать указателям. Обычно фрагмент кода перебора настолько мал, что его вставляют в другую процедуру — например, функцию поиска, удаления или отображения содержимого. Так, приведенная ниже функция выводит на экран все имена из списка рассылки:
void display(struct address *start)
{
while(start) {
printf("%s\n", start->name);
start = start->next;
}
}
При вызове функции display() параметр start должен быть указателем на первую структуру в списке. После этого функция переходит к следующему элементу, на который указывает указатель в поле next. Процесс прекращается, когда next равно нулю.
Для получения элемента из списка нужно просто пройти по цепочке ссылок. Ниже приведен пример функции поиска по содержимому поля
name:
struct address *search(struct address *start, char *n)
{
while(start) {
if(!strcmp(n, start->name)) return start;
start = start->next;
}
return NULL; /* подходящий элемент не найден */
}
Поскольку функция search() возвращает указатель на элемент списка, содержащий искомое имя, возвращаемый тип описан как указатель на структуру address. При отсутствии в списке подходящих элементов возвращается нуль (NULL).
Удаление элемента из односвязного списка выполняется просто. Так же, как и при вставке, возможны три случая: удаление первого элемента, удаление элемента в середине, удаление последнего элемента.
Удаление первого элемента списка
+------+ +------+ +------+
|данные| |данные| |данные|
\/\/\->+------+ +------+ +------+
| |--->| |--->| 0 |
+------+ +------+ +------+
превращается в
+------+ +------+ +------+
|удален| \/\/\->|данные| .->|данные|
+------+ +------+ | +------+
| 0 | | |-' | 0 |
+------+ +------+ +------+
Удаление среднего элемента списка
+------+ +------+ +------+
|данные| |данные| |данные|
\/\/\->+------+ +------+ +------+
| |--->| |--->| 0 |
+------+ +------+ +------+
превращается в
+------+ +------+ +------+
|данные| |удален| |данные|
\/\/\->+------+ +------+ +------+
| | | 0 | .->| 0 |
+------+ +------+ | +------+
\______________|
Удаление последнего элемента списка
+------+ +------+ +------+
|данные| |данные| |данные|
\/\/\->+------+ +------+ +------+
| |--->| |--->| 0 |
+------+ +------+ +------+
превращается в
+------+ +------+ +------+
|данные| |данные| |удален|
\/\/\->+------+ +------+ +------+
| |--->| 0 | | 0 |
+------+ +------+ +------+
Ниже приведена функция, удаляющая заданный элемент из списка структур address.
void sldelete(
struct address *p, /* предыдущий элемент */
struct address *i, /* удаляемый элемент */
struct address **start, /* начало списка */
struct address **last) /* конец списка */
{
if(p) p->next = i->next;
else *start = i->next;
if(i==*last && p) *last = p;
}
Функции sldelete() необходимо передавать указатели на удаляемый элемент, предшествующий удаляемому, а также на первый и последний элементы. При удалении первого элемента указатель на предшествующий элемент должен быть равен нулю (NULL). Данная функция автоматически обновляет указатели start и last, если один из них ссылается на удаляемый элемент.
У односвязных списков есть один большой недостаток: односвязный список невозможно прочитать в обратном направлении. По этой причине обычно применяются двусвязные списки.
Двусвязные списки
Двусвязный список состоит из элементов данных, каждый из которых содержит ссылки как на следующий, так и на предыдущий элементы.
+-------+ +-------+ +-------+
|данные | .->|данные | .->|данные |
+---+---+ | +---+---+ | +---+---+
| 0 | |-' | | |-' | | 0 |
| | |<---| | |<---| | |
+---+---+ +---+---+ +---+---+
Наличие двух ссылок вместо одной предоставляет несколько преимуществ. Вероятно, наиболее важное из них состоит в том, что перемещение по списку возможно в обоих направлениях. Это упрощает работу со списком, в частности, вставку и удаление. Помимо этого, пользователь может просматривать список в любом направлении. Еще одно преимущество имеет значение только при некоторых сбоях. Поскольку весь список можно пройти не только по прямым, но и по обратным ссылкам, то в случае, если какая-то из ссылок станет неверной, целостность списка можно восстановить по другой ссылке.
При вставке нового элемента в двусвязный список могут быть три случая: элемент вставляется в начало, в середину и в конец списка.
Вставка элемента в начало списка
+-----+ +-----+
| new | \/\/\->| new |
+--+--+ п +--+--+
| | | р .----------->|0 | |
| | | е | | | |
+--+--+ в | +--+|-+
р | _____|
а | |
+-----+ +-----+ +-----+ щ в | +-----+ | +-----+ +-----+
|info | |info | |info | а \/\/\->|info |<-' |info | |info |
\/\/\->+--+--+ +--+--+ +--+--+ т | +--+--+ +--+--+ +--+--+
|0 | |--->| | |--->| |0 | с | | | |--->| | |--->| |0 |
| | |<---| | |<---| | | я '-| | |<---| | |<---| | |
+--+--+ +--+--+ +--+--+ +--+--+ +--+--+ +--+--+
Вставка элемента в середину списка
+-----+ +-----+
| new | | new |
+--+--+ п +--+--+
| | | р .---------| | |
| | | е | .--->| | |
+--+--+ в | | +--+A|+
р | | _____||
а | | | |
+-----+ +-----+ +-----+ щ в +--V--+ | | +--+-V+ +-----+
|info | |info | |info | а \/\/\->|info | | | |info | |info |
\/\/\->+--+--+ +--+--+ +--+--+ т +--+--+ | | +--+--+ +--+--+
|0 | |--->| | |--->| |0 | с |0 | |-' '-| | |--->| |0 |
| | |<---| | |<---| | | я | | | | | |<---| | |
+--+--+ +--+--+ +--+--+ +--+--+ +--+--+ +--+--+
Вставка элемента в конец списка
+-----+ +-----+
| new | | new |
+--+--+ п +--+--+
| | | р | |0 |
| | | е | | |<-----------.
+--+--+ в +|-+--+ |
р |____________ |
а | |
+-----+ +-----+ +-----+ щ в +-----+ +-----+ +--V--+ |
|info | |info | |info | а \/\/\->|info | |info | |info | |
\/\/\->+--+--+ +--+--+ +--+--+ т +--+--+ +--+--+ +--+--+ |
|0 | |--->| | |--->| |0 | с |0 | |--->| | |--->| | |-'
| | |<---| | |<---| | | я | | |<---| | |<---| | |
+--+--+ +--+--+ +--+--+ +--+--+ +--+--+ +--+--+
Построение двусвязного списка выполняется аналогично построению односвязного за исключением того, что необходимо установить две ссылки. Поэтому в структуре данных должны быть описаны два указателя связи. Возвращаясь к примеру списка рассылки, для двусвязного списка структуру address можно модифицировать следующим образом:
struct address {
char name[40];
char street[40] ;
char city[20];
char state[3];
char zip[11];
struct address *next;
struct address *prior;
} info;
Следующая функция, dlstore(), создает двусвязный список, используя структуру address в качестве базового типа данных:
void dlstore(struct address *i, struct address **last)
{
if(!*last) *last = i; /* вставка первого элемента */
else (*last)->next = i;
i->next = NULL;
i->prior = *last;
*last = i;
}
Функция dlstore() помещает новые записи в конец списка. В качестве параметров ей необходимо передавать указатель на сохраняемые данные; а также указатель на конец списка, который при первом вызове должен быть равен нулю (NULL).
Подобно односвязным, двусвязные списки можно создавать с помощью функции, которая будет помещать элементы в определенные позиции, а не только в конец списка. Показанная ниже функция dls_store() создает список, упорядочивая его по возрастанию имен:
/* Создание упорядоченного двусвязного списка. */
void dls_store(
struct address *i, /* новый элемент */
struct address **start, /* первый элемент в списке */
struct address **last /* последний элемент в списке */
)
{
struct address *old, *p;
if(*last==NULL) { /* первый элемент в списке */
i->next = NULL;
i->prior = NULL;
*last = i;
*start = i;
return;
}
p = *start; /* начать с начала списка */
old = NULL;
while(p) {
if(strcmp(p->name, i->name) < 0){
old = p;
p = p->next;
}
else {
if(p->prior) {
p->prior->next = i;
i->next = p;
i->prior = p->prior;
p->prior = i;
return;
}
i->next = p; /* новый первый элемент */
i->prior = NULL;
p->prior = i;
*start = i;
return;
}
}
old->next = i; /* вставка в конец */
i->next = NULL;
i->prior = old;
*last = i;
}
Поскольку первый и последний элементы списка могут меняться, функция dls_store() автоматически обновляет указатели на начало и конец списка посредством параметров start и last. При вызове функции необходимо передавать указатель на сохраняемые данные и указатели на указатели на первый и последний элементы списка. В первый раз параметры start и last должны быть равны нулю (NULL).
Как и в односвязных списках, для получения элемента данных двусвязного списка необходимо переходить по ссылкам до тех пор, пока не будет найден искомый элемент
При удалении элемента двусвязного списка могут возникнуть три случая: удаление первого элемента, удаление элемента из середины и удаление последнего элемента. При этом изменяются ссылки. Показанная ниже функция dldelete() удаляет элемент двусвязного списка:
void dldelete(
struct address *i, /* удаляемый элемент */
struct address **start, /* первый элемент */
struct address **last) /* последний элемент */
{
if(i->prior) i->prior->next = i->next;
else { /* new first item */
*start = i->next;
if(start) start->prior = NULL;
}
if(i->next) i->next->prior = i->prior;
else /* удаление последнего элемента */
*last = i->prior;
}
Поскольку первый или последний элементы списка могут быть удалены, функция dldelete() автоматически обновляет указатели на начало и конец списка посредством параметров start и last. При вызове ей передаются указатель на удаляемый элемент и указатели на указатели на начало и конец списка.
Удаление первого элемента списка
+-------+ +-------+ +-------+
\/\/\->|данные | |данные | |данные |
+---+---+ +---+---+ +---+---+
| 0 | |--->| | |--->| | 0 |
+---+-A-+ +-|-+-A-+ +-|-+---+
|________| |________|
превращается в
+-------+ +-------+ +-------+
|удален | \/\/\->|данные | |данные |
+---+---+ +---+---+ +---+---+
| 0 | 0 | | 0 | |--->| | 0 |
+---+---+ +---+-A-+ +-|-+---+
|________|
Удаление элемента из середины списка
+-------+ +-------+ +-------+
\/\/\->|данные | |данные | |данные |
+---+---+ +---+---+ +---+---+
| 0 | |--->| | |--->| | 0 |
+---+-A-+ +-|-+-A-+ +-|-+---+
|________| |________|
превращается в
___________________
| |
+-------+ | +-------+ +---V---+
\/\/\->|данные | | |удален | |данные |
+---+---+ | +---+---+ +---+---+
| 0 | |-' | 0 | 0 |--->| | 0 |
+---+-A-+ +---+---+ +-|-+---+
|_____________________|
Удаление первого элемента списка
+-------+ +-------+ +-------+
\/\/\->|данные | |данные | |данные |
+---+---+ +---+---+ +---+---+
| 0 | |--->| | |--->| | 0 |
+---+-A-+ +-|-+-A-+ +-|-+---+
|________| |________|
превращается в
+-------+ +-------+ +-------+
\/\/\->|данные | |данные | |удален |
+---+---+ +---+---+ +---+---+
| 0 | |--->| | 0 |--->| 0 | 0 |
+---+-A-+ +-|-+---+ +---+---+
|________|
Пример списка рассылки
Чтобы завершить обсуждение двусвязных списков, в данном разделе представлена простая, но законченная программа для работы со списком рассылки. Во время работы весь список хранится в оперативной памяти. Тем не менее, его можно сохранять в файле и загружать для дальнейшей работы.
/* Простая программа для обработки списка рассылки
иллюстрирующая работу с двусвязными списками.
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct address {
char name[30];
char street[40];
char city[20];
char state[3];
char zip[11];
struct address *next; /* указатель на следующую запись */
struct address *prior; /* указатель на предыдущую запись */
};
struct address *start; /* указатель на первую запись списка */
struct address *last; /* указатель на последнюю запись */
struct address *find(char *);
void enter(void), search(void), save(void);
void load(void), list(void);
void mldelete(struct address **, struct address **);
void dls_store(struct address *i, struct address **start,
struct address **last);
void inputs(char *, char *, int), display(struct address *);
int menu_select(void);
int main(void)
{
start = last = NULL; /* инициализация указателей на начало и конец */
for(;;) {
switch(menu_select()) {
case 1: enter(); /* ввод адреса */
break;
case 2: mldelete(&start, &last); /* удаление адреса */
break;
case 3: list(); /* отображение списка */
break;
case 4: search(); /* поиск адреса */
break;
case 5: save(); /* запись списка в файл */
break;
case 6: load(); /* считывание с диска */
break;
case 7: exit(0);
}
}
return 0;
}
/* Выбор действия пользователя. */
int menu_select(void)
{
char s[80];
int c;
printf("1. Ввод имени\n");
printf("2. Удаление имени\n");
printf("3. Отображение содержимого списка\n");
printf("4. Поиск\n");
printf("5. Сохранить в файл\n");
printf("6. Загрузить из файла\n");
printf("7. Выход\n");
do {
printf("\nВаш выбор: ");
gets(s);
c = atoi(s);
} while(c < 0 || c>7);
return c;
}
/* Ввод имени и адресов. */
void enter(void)
{
struct address *info;
for(;;) {
info = (struct address *)malloc(sizeof(struct address));
if(!info) {
printf("\nНет свободной памяти");
return;
}
inputs("Введите имя: ", info->name, 30);
if(!info->name[0]) break; /* завершить ввод */
inputs("Введите улицу: ", info->street, 40);
inputs("Введите город: ", info->city, 20);
inputs("Введите штат: ", info->state, 3);
inputs("Введите почтовый индекс: ", info->zip, 10);
dls_store(info, &start, &last);
} /* цикл ввода */
}
/* Следующая функция вводит с клавиатуры строку
длинной не больше count и предотвращает переполнение
строки. Кроме того, она выводит на экран подсказку. */
void inputs(char *prompt, char *s, int count)
{
char p[255];
do {
printf(prompt);
fgets(p, 254, stdin);
if(strlen(p) > count) printf("\nСлишком длинная строка\n");
} while(strlen(p) > count);
p[strlen(p)-1] = 0; /* удалить символ перевода строки */
strcpy(s, p);
}
/* Создание упорядоченного двусвязного списка. */
void dls_store(
struct address *i, /* новый элемент */
struct address **start, /* первый элемент списка */
struct address **last /* последний элемент списка */
)
{
struct address *old, *p;
if(*last==NULL) { /* первый элемент списка */
i->next = NULL;
i->prior = NULL;
*last = i;
*start = i;
return;
}
p = *start; /* начать с начала списка */
old = NULL;
while(p) {
if(strcmp(p->name, i->name) < 0){
old = p;
p = p->next;
}
else {
if(p->prior) {
p->prior->next = i;
i->next = p;
i->prior = p->prior;
p->prior = i;
return;
}
i->next = p; /* новый первый элемент */
i->prior = NULL;
p->prior = i;
*start = i;
return;
}
}
old->next = i; /* вставка в конец */
i->next = NULL;
i->prior = old;
*last = i;
}
/* Удаление элемента из списка. */
void mldelete(struct address **start, struct address **last)
{
struct address *info;
char s[80];
inputs("Введите имя: ", s, 30);
info = find(s);
if(info) {
if(*start==info) {
*start=info->next;
if(*start) (*start)->prior = NULL;
else *last = NULL;
}
else {
info->prior->next = info->next;
if(info!=*last)
info->next->prior = info->prior;
else
*last = info->prior;
}
free(info); /* освободить память */
}
}
/* Поиск адреса. */
struct address *find( char *name)
{
struct address *info;
info = start;
while(info) {
if(!strcmp(name, info->name)) return info;
info = info->next; /* перейти к следующему адресу */
}
printf("Имя не найдено.\n");
return NULL; /* нет подходящего элемента */
}
/* Отобразить на экране весь список. */
void list(void)
{
struct address *info;
info = start;
while(info) {
display(info);
info = info->next; /* перейти к следующему адресу */
}
printf("\n\n");
}
/* Данная функция выполняет собственно вывод на экран
всех полей записи, содержащей адрес. */
void display(struct address *info)
{
printf("%s\n", info->name);
printf("%s\n", info->street);
printf("%s\n", info->city);
printf("%s\n", info->state);
printf("%s\n", info->zip);
printf("\n\n");
}
/* Поиск имени в списке. */
void search(void)
{
char name[40];
struct address *info;
printf("Введите имя: ");
gets(name);
info = find(name);
if(!info) printf("Не найдено\n");
else display(info);
}
/* Сохранить список в дисковом файле. */
void save(void)
{
struct address *info;
FILE *fp;
fp = fopen("mlist", "wb");
if(!fp) {
printf("Невозможно открыть файл.\n");
exit(1);
}
printf("\nСохранение в файл\n");
info = start;
while(info) {
fwrite(info, sizeof(struct address), 1, fp);
info = info->next; /* перейти к следующему адресу */
}
fclose(fp);
}
/* Загрузка адресов из файла. */
void load()
{
struct address *info;
FILE *fp;
fp = fopen("mlist", "rb");
if(!fp) {
printf("Невозможно открыть файл.\n");
exit(1);
}
/* освободить память, если в памяти уже есть список */
while(start) {
info = start->next;
free(info);
start = info;
}
/* сбросить указатели на начало и конец */
start = last = NULL;
printf("\nЗагрузка из файла\n");
while(!feof(fp)) {
info = (struct address *) malloc(sizeof(struct address));
if(!info) {
printf("Нет свободной памяти");
return;
}
if(1 != fread(info, sizeof(struct address), 1, fp)) break;
dls_store(info, &start, &last);
}
fclose(fp);
}
Двоичные деревья
Напоследок мы рассмотрим структуру данных, которая называется двоичное дерево (binary tree). Несмотря на то, что бывает много различных типов деревьев, двоичные деревья играют особую роль, так как в отсортированном состоянии позволяют очень быстро выполнять вставку, удаление и поиск. Каждый элемент двоичного дерева состоит из информационной части и указателей на левый и правый элементы. На рис. 22.8 показано небольшое двоичное дерево.
корень
↙
+-------+
|данные |
+---+---+
левое | | | правое
поддерево +---+---+ поддерево
↘ ↙ ↘ ↙
+-------+ +-------+
|данные | |данные |
+---+---+ +---+---+
| | | | 0 | |
+---+---+ +---+---+
↙ ↘ ↘
+-------+ +-------+ +-------+
|данные | |данные | |данные |
+---+---+ +---+---+ +---+---+
| 0 | 0 | | 0 | 0 | | 0 | 0 |
+---+---+ +---+---+ +---+---+
↑ ↑ ↑
'----------------листья-----------------'
При обсуждении деревьев применяется специальная терминология. Программисты не являются специалистами в области филологии, и поэтому терминология, применяемая в теории графов (а ведь деревья представляют собой частный случай графов!), является классическим примером неправильного употребления слов. Первый элемент дерева называется корнем (root). Каждый элемент данных называется вершиной дерева (node), а любой фрагмент дерева называется поддеревом (subtree). Вершина, к которой не присоединены поддеревья, называется заключительным узлом (terminal node) или листом (leaf). Высота (height) дерева равняется максимальному количеству уровней от корня до листа. При работе с деревьями можно допустить, что в памяти они существуют в том же виде, что и на бумаге. Но помните, что дерево — всего лишь способ логической организации данных в памяти, а память линейна.
В некотором смысле двоичное дерево является особым видом связанного списка. Элементы можно вставлять, удалять и извлекать в любом порядке. Кроме того, операция извлечения не является разрушающей. Несмотря на то, что деревья легко представить в воображении, в теории программирования с ними связан ряд сложных задач. В данном разделе деревья затрагиваются лишь поверхностно.
Большинство функций, работающих с деревьями, рекурсивны, поскольку дерево по своей сути является рекурсивной структурой данных. Другими словами, каждое поддерево, в свою очередь, является деревом. Поэтому разрабатываемые здесь функции будут рекурсивными. Существуют и не рекурсивные версии этих функций, но их код понять намного сложнее.
Способ упорядочивания дерева зависит от того, как к нему впоследствии будет осуществляться доступ. Процесс поочередного доступа к каждой вершине дерева называется обходом (вершин) дерева (tree traversal). Рассмотрим следующее дерево:
d
↙ ↘
b f
↙ ↘ ↙ ↘
a c e g
Существует три порядка обхода дерева: обход симметричным способом, или симметричный обход (inorder), обход в прямом порядке, прямой обход, упорядоченный обход, обход сверху, или обход в ширину (preorder) и обход в обратном порядке, обход в глубину, обратный обход, обход снизу (postorder). При симметричном обходе обрабатывается сначала левое поддерево, затем корень, а затем правое поддерево. При прямом обходе обрабатывается сначала корень, затем левое поддерево, а потом правое. При обходе снизу сначала обрабатывается левое поддерево, затем правое и, наконец корень. Последовательность доступа при каждом методе обхода показана ниже:
Симметричный обход a b c d e f g
Прямой обход d b a c f e g
Обход снизу a c b e g f d
Несмотря на то, что дерево не должно быть обязательно упорядоченным, в большинстве задач используются именно такие деревья. Конечно, структура упорядоченного дерева зависит от способа его обхода. В оставшейся части данной главы предполагается симметричный обход. Поэтому упорядоченным двоичным деревом будет считаться такое дерево, в котором левое поддерево содержит вершины, меньшие или равные корню, а правое содержит вершины, большие корня.
Приведенная ниже функция stree() создает упорядоченное двоичное дерево:
struct tree {
char info;
struct tree *left;
struct tree *right;
};
struct tree *stree(
struct tree *root,
struct tree *r,
char info)
{
if(!r) {
r = (struct tree *) malloc(sizeof(struct tree));
if(!r) {
printf("Не хватает памяти\n");
exit(0);
}
r->left = NULL;
r->right = NULL;
r->info = info;
if(!root) return r; /* первый вход */
if(info < root->info) root->left = r;
else root->right = r;
return r;
}
if(info < r->info)
stree(r,r->left,info);
else
stree(r,r->right,info);
return root;
}
Приведенный выше алгоритм просто следует по ссылкам дерева, переходя к левой или правой ветви очередной вершины на основании содержимого поля info до достижения места вставки нового элемента. Чтобы использовать эту функцию, необходимо иметь глобальную переменную-указатель на корень дерева. Этот указатель изначально должен иметь значение нуль (NULL). При первом вызове функция stree() возвращает указатель на корень дерева, который нужно присвоить глобальной переменной. При последующих вызовах функция продолжает возвращать указатель на корень. Допустим, что глобальная переменная, содержащая корень дерева, называется rt. Тогда функция stree() вызывается следующим образом:
/* вызов функции street() */
rt = street(rt, rt, info);
Функция stree() использует рекурсивный алгоритм, как и большинство процедур работы с деревьями. Точно такая же функция, основанная на итеративных методах, была бы в несколько раз длиннее. Функцию stree() необходимо вызывать со следующими параметрами (слева направо): указатель на корень всего дерева, указатель на корень следующего поддерева, в котором осуществляется поиск, и сохраняемые данные. При первом вызове оба первых параметрах указывают на корень всего дерева. Для простоты в вершинах дерева хранятся одиночные символы. Тем не менее, вместо них можно использовать любой тип данных
Чтобы обойти созданное функцией stree() дерево в симметричном порядке и распечатать поле info в каждой вершине, можно применить приведенную ниже функцию inorder():
void inorder(struct tree *root)
{
if(!root) return;
inorder(root->left);
if(root->info) printf("%c ", root->info);
inorder(root->right);
}
Данная рекурсивная функция завершает работу тогда, когда находит заключительный узел (нулевой указатель).
В следующем листинге показаны функции, выполняющие обход дерева в ширину и в глубину.
void preorder(struct tree *root)
{
if(!root) return;
if(root->info) printf("%c ", root->info);
preorder(root->left);
preorder(root->right);
}
void postorder(struct tree *root)
{
if(!root) return;
postorder(root->left);
postorder(root->right);
if(root->info) printf("%c ", root->info);
}
Теперь давайте рассмотрим короткую, но интересную программу, которая строит упорядоченное двоичное дерево, а затем, обходя его симметричным образом, отображает его на экране боком. Для отображения дерева требуется лишь слегка модифицировать функцию inorder(). Поскольку на экране дерево распечатывается боком, для корректного отображения правое поддерево необходимо печатать прежде левого. (Технически это противоположность симметричного обхода.) Новая функция называется printtree(), а ее код показан ниже:
void print_tree(struct tree *r, int l)
{
int i;
if(r == NULL) return;
print_tree(r->right, l+1);
for(i=0; iinfo);
print_tree(r->left, l+1);
}
Далее следует текст всей программы печати дерева. Попробуйте вводить различные деревья, чтобы увидеть, как они строятся.
/* Эта программа выводит на экран двоичное дерево. */
#include <stdlib.h>
#include <stdio.h>
struct tree {
char info;
struct tree *left;
struct tree *right;
};
struct tree *root; /* начальная вершина дерева */
struct tree *stree(struct tree *root,
struct tree *r, char info);
void print_tree(struct tree *root, int l);
int main(void)
{
char s[80];
root = NULL; /* инициализация корня дерева */
do {
printf("Введите букву: ");
gets(s);
root = stree(root, root, *s);
} while(*s);
print_tree(root, 0);
return 0;
}
struct tree *stree(
struct tree *root,
struct tree *r,
char info)
{
if(!r) {
r = (struct tree *) malloc(sizeof(struct tree));
if(!r) {
printf("Не хватает памяти\n");
exit(0);
}
r->left = NULL;
r->right = NULL;
r->info = info;
if(!root) return r; /* первый вход */
if(info < root->info) root->left = r;
else root->right = r;
return r;
}
if(info < r->info)
stree(r, r->left, info);
else
stree(r, r->right, info);
return root;
}
void print_tree(struct tree *r, int l)
{
int i;
if(!r) return;
print_tree(r->right, l+1);
for(i=0; iinfo);
print_tree(r->left, l+1);
}
По существу, данная программа сортирует вводимую информацию. Метод сортировки является одной из разновидностей сортировки методом вставок, которая была рассмотрена в предыдущей главе. В среднем случае производительность может быть вполне хорошей.
Если вы запускали программу печати дерева, вы, вероятно, заметили, что некоторые деревья являются сбалансированными (balanced), т.е. каждое поддерево имеет примерно такую же высоту, как и остальные, а некоторые деревья очень далеки от этого состояния. Например, дерево a⇒b⇒c⇒d выглядит следующим образом:
a
↘
b
↘
c
↘
d
В этом дереве нет левых поддеревьев. Такое дерево называется вырожденным, поскольку фактически оно выродилось в линейный список. В общем случае, если при построении дерева вводимые данные являются случайными, то получаемое дерево оказывается близким к сбалансированному. Если же информация предварительно отсортирована, создается вырожденное дерево. (Поэтому иногда при каждой вставке дерево корректируют так, чтобы оно было сбалансированным, но этот процесс довольно сложен и выходит за рамки данной главы.)
В двоичных деревьях легко реализовываются функции поиска. Приведенная ниже функция возвращает указатель на вершину дерева, в которой информация совпадает с ключом поиска, либо нуль (NULL), если такой вершины нет.
struct tree *search_tree(struct tree *root, char key)
{
if(!root) return root; /* пустое дерево */
while(root->info != key) {
if(keyinfo) root = root->left;
else root = root->right;
if(root == NULL) break;
}
return root;
}
К сожалению, удалить вершину дерева не так просто, как отыскать. Удаляемая вершина может быть либо корнем, либо левой, либо правой вершиной. Помимо того, к вершине могут быть присоединены поддеревья (количество присоединенных поддеревьев может равняться 0, 1 или 2). Процесс переустановки указателей подсказывает рекурсивный алгоритм, приведенный ниже:
struct tree *dtree(struct tree *root, char key)
{
struct tree *p,*p2;
if(!root) return root; /* вершина не найдена */
if(root->info == key) { /* удаление корня */
/* это означает пустое дерево */
if(root->left == root->right){
free(root);
return NULL;
}
/* или если одно из поддеревьев пустое */
else if(root->left == NULL) {
p = root->right;
free(root);
return p;
}
else if(root->right == NULL) {
p = root->left;
free(root);
return p;
}
/* или есть оба поддерева */
else {
p2 = root->right;
p = root->right;
while(p->left) p = p->left;
p->left = root->left;
free(root);
return p2;
}
}
if(root->info < key) root->right = dtree(root->right, key);
else root->left = dtree(root->left, key);
return root;
}
Необходимо также следить за правильным обновлением указателя на корень дерева, описанного вне данной функции, поскольку удаляемая вершина может быть корнем. Лучше всего с этой целью указателю на корень присваивать значение, возвращаемое функцией dtree():
root = dtree(root, key);
Двоичные деревья — исключительно мощное, гибкое и эффективное средство. Поскольку при поиске в сбалансированном дереве выполняется в худшем случае log2n сравнений, оно намного лучше, чем связанный список, в котором возможен лишь последовательный поиск.