1.2 Множество
Множество — это структура данных, содержащая конечный набор элементов некоторого типа. Каждый элемент содержится только в одном экземпляре, т.е. разные элементы множества не равны между собой. Элементы множества никак не упорядочены. В множество M можно добавить элемент x, из множества M можно удалить элемент x. Если при добавлении элемента x он уже содержится в множестве M, то ничего не происходит. Аналогично, никакие действия не совершаются при удалении элемента x, когда он не содержится в множестве M. Наконец, для заданного элемента x можно определить, содержится ли он в множестве M. Множество — это потенциально неограниченная структура, оно может содержать любое конечное число элементов.
В программировании довольно часто рассматривают структуру чуть более сложную, чем просто множество: нагруженное множество. Пусть каждый элемент множества содержится в нем вместе с дополнительной информацией, которую называют нагрузкой элемента. При добавлении элемента в множество нужно также указывать нагрузку, которую он несет. В разных языках программирования и в различных стандартных библиотеках такие структуры называют Отображением (Map) или Словарем (Dictionary). Действительно, элементы множества как бы отображаются на нагрузку, которую они несут (заметим, что в математике понятие функции или отображения определяется строго как множество пар; первым элементом каждой пары является конкретное значение аргумента функции, вторым — значение, на которое функция отображает аргумент). В интерпретации Словаря элемент множества — это иностранное слово, нагрузка элемента — это перевод слова на русский язык (разумеется, перевод может включать несколько вариантов, но здесь перевод рассматривается как единый текст).
Все элементы содержатся в нагруженном множестве в одном экземпляре, т.е. разные элементы множества не могут быть равны друг другу. В отличие от самих элементов, их нагрузки могут совпадать (так, различные иностранные слова могут иметь одинаковый перевод). Поэтому иногда элементы нагруженного множества называют ключами, их нагрузки — значениями ключей. Каждый ключ уникален. Принято говорить, что ключи отображаются на их значения.
Наиболее часто применяемая операция в нагруженном множестве — это определение нагрузки для заданного элемента x (значения ключа x). Реализация этой операции включает поиск элемента x в множестве, поэтому эффективность любой реализации множества определяется прежде всего быстротой поиска.
1.3 Интерфейс динамических информационных структур
Интерфейсом здесь называется минимальный набор функций, реализующих стандартные задачи обработки данных. Среди них:
Insert – вставить новый элемент,
TakeOut – удаление элемента из списка,
Is_present – определение содержания в списке заданного элемента,
Display – вывод всех элементов списка,
Destroy – освобождение памяти, занятой под список,
1.4 Реализация списков
1.4.1 Односвязный список
Структура элемента
struct node
{
char w[10]; // любая информационная часть элемента
struct node *next;
};
Структура заголовка
struct head
{
char info[100]; // любая информационная часть всего списка
struct node *begin;
};
1.4.2 Двусвязный список
Структура элемента
struct node
{
char w[10]; // любая информационная часть элемента
struct node *next;
struct node *prev;
};
Структура заголовка
struct head
{
char info[100]; // любая информационная часть всего списка
struct node *begin;
};
1.4.3 Прототипы интерфейсных функций
Предложим примерные прототипы стандартных интерфейсных функций.
void Insert(struct head h, char * text);
int TakeOut(struct head h, struct *ptrnode);
int Is_present(struct head h, char *text);
void Display(struct head h);
void Destroy(struct head h);
1.5 Реализация деревьев
1.5.1 Бинарное дерево
Структура элемента
struct node
{
char w[10]; // любая информационная часть элемента
struct node *left;
struct node *right;
};
Деревья, как правило, не имеют заголовка.
1.5.2 n-арное дерево
Структура элемента
#define N 3
struct node
{
char w[10]; // любая информационная часть элемента
struct node childs[N];
};
1.5.3 Дерево произвольной арности
Структура элемента
struct node
{
char w[10]; // любая информационная часть элемента
struct node *childs; // указатель на дочерние узлы
int N; // количество дочерних узлов
};
1.6 Реализация бинарных деревьев
Рассмотрим задачу определения числа появления всех слов в некотором файле. Список слов заранее неизвестен. Слова будем запоминать в бинарном дереве. Используем рекурсивный алгоритм для работы с деревом.
struct node{
char word[20];
int count;
node *left, *right;
};
#define node* T;
T tree(T, char*);
void main()
{
node *root;
char word[20];
root = NULL;
while(getword(word) != EOF)
root = tree(root, word);
treeprint(root);
}
T tree(T p, char *w)
{
int cond;
if(p==NULL)//новое слово
{
p=(T)malloc(sizeof(node));
//проверка
strcpy(p->word, 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 = tree(p->left, w);
else //правое дерево
p->right – tree(p->right, w);
return p;
}
//--------------------
void treeprint(T p)
{
if(p != NULL)
{
treeprint(p->left);
print(%4d %s \n”, p->count, p->word);
treeprint(p->right);
}
}