Рацеев С.М. Программирование на языке Си
.pdfmax = malloc((h + 1)*sizeof(int));
/* инициализируем начальные значения: */
InitMinMax(root, 0, min, max);
/*ищем на каждом уровне минимальное и максимальное значение:*/
MinMax(root, 0, min, max); return 0;
}
Пример 12 (Частотный словарь). Используя дерево поиска,
создать частотный словарь, содержащий слова и количество появлений каждого слова в текстовом файле в лексикографическом порядке.
I способ. Будем построчно считывать текстовый файл и строки разбивать на слова с помощью функции my_strtok2 (построенной в параграфе «Разбиение строки на лексемы»).
Каждый элемент дерева поиска будет иметь такой вид:
struct ELEMENT
{
char *key; /* динамическая строка */ long count;
struct ELEMENT *left, *right;
};
Вспомним, что функция my_strtok2 использует функцию malloc и для каждого слова выделяет необходимое количество памяти. Поэтому поле key структуры ELEMENT будет содержать адрес текущего слова в динамической области памяти. Такой подход хранения слов в дереве поиска обладает тем преимуществом, что происходит экономия памяти и для каждого слова выделяется памяти ровно столько, сколько это слово того требует.
За добавление очередного слова в дерево поиска будет отвечать функция Insert. Данная функция является логической и возвращает 1, если добавляемого слова не было в дереве поиска, в противном случае функция возвращает 0. Возвращаемое значение нужно вот для чего. Пусть word – очередное выделенное слово с помощью функции my_strtok2. Если в дереве поиска такого слова
291
еще не было, то в нем создается новая вершина, поле key которой будет содержать адрес этого слова. Если же слово word уже имеется в дереве поиска, то следует почистить динамическую память, занимаемую данным словом.
Функция CreateSearchTree будет принимать имя текстового файла, адрес корневой вершины дерева поиска и строить собственно это дерево поиска, вызывая для каждого слова функцию Insert.
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define DELIMITERS " .,:;\n\t" /* символы-разделители */ #define N 1024
typedef struct ELEMENT
{
char *key; long count;
struct ELEMENT *left, *right; } ELEMENT;
/* Вставка строки в дерево поиска */ int Insert(ELEMENT **q, char *ps)
{
if (*q == NULL)
{
*q = (ELEMENT *)malloc(sizeof(ELEMENT)); (*q)->key = ps;
(*q)->count = 1;
(*q)->left = (*q)->right = NULL; return 1;
}
else
{
int rez = strcmp((*q)->key, ps); if (rez == 0)
{
292
((*q)->count)++; return 0;
}
else
if (rez > 0)
return Insert(&((*q)->left), ps); else return Insert(&((*q)->right), ps);
}
}
/* вывод на экран элементов дерева поиска в лексикографическом порядке */
void Display(ELEMENT *q)
{
if (q != NULL)
{
Display(q->left);
printf("%s : %d\n", q->key, q->count); Display(q->right);
}
}
void Init(int *flag, const char *s)
{
int i;
for (i = 0; i < 256; i++) flag[i] = 0;
for(i = 0; s[i]; i++) flag[s[i]] = 1;
}
char *my_strtok2(char *s, const int *flag)
{
static char *beg = NULL; char *pstr, *pword = NULL; int len;
if (s != NULL)
293
{
for(pstr = s; *pstr && flag[*pstr]; ++pstr)
;
beg = pstr;
}
else
pstr = beg;
for( ; *beg && !flag[*beg]; ++beg)
;
if (*pstr)
{
pword = (char *)malloc(beg - pstr + 1); if (pword != NULL)
{
len = (beg - pstr) / sizeof(char); strncpy(pword, pstr, len); pword[len] = '\0';
}
}
for( ; *beg && flag[*beg]; ++beg)
;
return pword;
}
/* построение дерева поиска */
int CreateSearchTree(ELEMENT **root, char *fname)
{
FILE *f;
char s[N], *word; int flag[256];
if ((f = fopen(fname, "r")) == NULL) return 1;
Init(flag, DELIMITERS); while(fgets(s, N, f) != NULL)
{
word = my_strtok2(s, flag); while(word != NULL)
294
{
if (!Insert(root, word)) free(word);
word = my_strtok2(NULL, flag);
}
}
fclose(f); return 0;
}
int main( )
{
ELEMENT *root = NULL;
/* построение дерева поиска */
CreateSearchTree(&root, "c:\\a.txt");
/* вывод на экран слов в лексикографическом порядке */
Display(root); return 0;
}
II способ. Если же ключевое поле key структуры ELEMENT является массивом символов, то для решения задачи подойдет функция my_strtok1 (построенной в параграфе «Разбиение строки на лексемы»). Тогда алгоритм построения частотного словаря будет выглядеть следующим образом.
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define DELIMITERS " .,:;\n\t" /* символы-разделители */ #define N 1024
typedef struct ELEMENT
{
char key[50]; long count;
struct ELEMENT *left, *right;
295
} ELEMENT;
/* Вставка строки в дерево поиска */ int Insert(ELEMENT **q, char *ps)
{
if (*q == NULL)
{
*q = (ELEMENT *)malloc(sizeof(ELEMENT)); strcpy((*q)->key, ps);
(*q)->count = 1;
(*q)->left = (*q)->right = NULL; return 1;
}
else
{
int rez = strcmp((*q)->key, ps); if (rez == 0)
{
((*q)->count)++; return 0;
}
else
if (rez > 0)
return Insert(&((*q)->left), ps); else return Insert(&((*q)->right), ps);
}
}
/* вывод на экран элементов дерева поиска в лексикографическом порядке */
void Display(ELEMENT *q)
{
if (q != NULL)
{
Display(q->left);
printf("%s : %d\n", q->key, q->count); Display(q->right);
296
}
}
void Init(int *flag, const char *s)
{
int i;
for (i = 0; i < 256; i++) flag[i] = 0;
for(i = 0; s[i]; i++) flag[s[i]] = 1;
}
char *my_strtok1(char *s, const int *flag)
{
static char *beg = NULL; char *pword, *pbuf;
if (s != NULL)
{
for(pword = s; *pword && flag[*pword]; ++pword)
;
beg = pword;
}
else
pword = beg;
for( ; *beg && !flag[*beg]; ++beg)
;
pbuf = beg;
for( ; *beg && flag[*beg]; ++beg)
;
*pbuf = '\0';
return *pword ? pword : NULL;
}
/* построение дерева поиска */
int CreateSearchTree(ELEMENT **root, char *fname)
{
FILE *f;
297
char s[N], *word; int flag[256];
if ((f = fopen(fname, "r")) == NULL) return 1;
Init(flag, DELIMITERS); while(fgets(s, N, f) != NULL)
{
word = my_strtok1(s, flag); while(word != NULL)
{
Insert(root, word);
word = my_strtok1(NULL, flag);
}
}
fclose(f); return 0;
}
int main( )
{
ELEMENT *root = NULL;
/* построение дерева поиска */
CreateSearchTree(&root, "c:\\a.txt");
/* вывод на экран слов в лексикографическом порядке */
Display(root); return 0;
}
14.10.Задачи на бинарные деревья
1.Найти сумму элементов бинарного дерева.
2.Найти вершины, у которых количество потомков в левом поддереве не равно количеству потомков в правом поддереве.
3.Найти вершины, для которых высота левого поддерева не равна высоте правого поддерева.
298
4.Написать функцию, которая определяет число вхождений элемента x в бинарное дерево.
5.Найти максимальный элемент бинарного дерева и количество повторений максимального элемента в данном дереве.
6.Написать функцию, которая определяет, есть ли в бинарном дереве хотя бы два одинаковых элемента.
7.Написать функцию, определяющую максимальное количество одинаковых элементов бинарного дерева.
8.Написать функцию, которая определяет, является ли бинарное дерево симметричным.
9.Написать функцию, которая определяет, является ли бинарное дерево деревом поиска.
10.Вывести все листья дерева поиска в порядке возрастания.
11.Пусть имеется бинарное дерево T. Сформировать два идеально сбалансированных дерева из отрицательных и неотрицательных элементов дерева T.
12.Вывести на экран все пути, ведущие от корня к листьям бинарного дерева, у которых суммарный вес элементов минимальный.
13.Найти последний номер из всех уровней бинарного дерева, на которых есть положительные элементы.
14.На каждом уровне бинарного дерева найти максимальный элемент.
15.На каждом уровне дерева найти количество внутренних вершин и количество листьев.
16.Найти суммы элементов всех нечетных уровней.
17.Найти минимальный и максимальный пути между листьями бинарного дерева.
18.Удалить из бинарного дерева наименьшее количество вершин таким образом, чтобы полученное дерево было строго бинарным.
19.Пусть имеется текстовый файл. Используя дерево поиска, создать другой текстовый файл – частотный словарь, содержащий слова и количество появлений каждого слова в исходном файле.
20.Написать функцию, которая осуществляет послойный обход бинарного дерева, при котором значения вершин печатаются от уровня к уровню, начиная с корневой вершины. Значения вершин дерева на каждом уровне печатаются слева направо. Для
299
реализации алгоритма использовать структуру очередь следующим образом. На первом шаге вставить в очередь корневую вершину. Затем прописать цикл, работающий по такому принципу.
Пока очередь не пуста:
1)берем из очереди первый элемент q;
2)выводим значение элемента q на экран;
3)если у вершины q есть левая вершина-потомок в дереве, то добавляем этот потомок в очередь;
4)если у вершины q есть правая вершина-потомок в дереве, то добавляем этот потомок в очередь;
5)удаляем из очереди элемент q.
300