Основы программирования ФИСТ 1 курс Власенко Олег Федосович

структур данных.

двоичное дерево, для которого выполняются следующие дополнительные условия (свойства дерева

https://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE

* right;
};





struct NodeTree * root = NULL;

NULL, NULL };
struct NodeTree node2 = { 2, NULL, NULL

{
printTree(p->left);
printf("(%d)\n", p->data);
printTree(p->right);
}
}

= 0; i < shift; i++) {
printf(" ");
}
}
void printTreeShifted(struct NodeTree

value)
{
if (p == NULL) {
p = (struct NodeTree*)malloc(
sizeof(struct NodeTree));
p->data

addElement(root, 40);
root = addElement(root, 20);
root = addElement(root, 10);
root = addElement(root,

addElement(root, 40);
root = addElement(root, 20);
root = addElement(root, 10);
root = addElement(root,

NULL;
...

int value)
{
if (p == NULL) {
return 0;
} else if (value

addElement(root, 60);
root = addElement(root, 40);
root = addElement(root, 20);
root = addElement(root,

– в каждой строке по 1 слову

Файл 2: Текстовый файл

#include
#include

25

struct Dictionary {
char words[MAX_WORDS][MAX_LEN];
int cnt_words;
};

struct Dictionary * create();
void destroy(struct Dictionary

Dictionary * dict = (struct Dictionary *)
malloc(sizeof(struct Dictionary));
dict->cnt_words =

dict, char * word)
{
if (dict->cnt_words < MAX_WORDS) {
strncpy(dict->words[dict->cnt_words],
word, MAX_LEN -

dict, char * word)
{
int i;
for (i = 0; i

dict,
char * filename) {
// открыть файл
FILE * fin;
char s[MAX_LEN];

fin

всех строк
while (!feof(fin)) {
// загрузить строку
if (fgets(s, MAX_LEN - 1,

dict,
char * text_in_filename,
char * text_out_filename)
{
char s[MAX_LEN];

// открыть

"wt");
if (fout == NULL)
{
fclose(fin);
return 0;
}
fprintf(fout, "");
fprintf(fout, "");
fprintf(fout, "");
fprintf(fout, "

0;
char word[81];
int word_len = 0;

while ((ch = getc(fin)) != EOF)

(!isalpha(ch)) {
if (is_letter) {
word[word_len] = '\0';
if (contains(dict, word))
fprintf(fout, "%s ",

= getc(fin)) != EOF)
fclose(fin);

fprintf(fout, "");
fprintf(fout, "");
fclose(fout);
return 1;
} // convertTextToHtml- конец!!!

t1, t2;
t0 = clock();
printf("t0 = %f sec \n", t0 /

%f sec \n",
t2 / (float)CLOCKS_PER_SEC);

printf("Run time = t2 -

639 байт ( Alice.txt x 7,06)
Tolkien2.txt – 5 043 195

next;
};

struct Dictionary {
struct Node * first;
int cnt_words;
};

struct Dictionary * create();
void

= (struct Dictionary *)
malloc(sizeof(struct Dictionary));
dict->first = NULL;
dict->cnt_words = 0;
return

word)
{
struct Node * newNode = (struct Node*)
malloc(sizeof(struct Node));

newNode->next =

!= NULL)
{
struct Node * delNode = dict->first;
dict->first = dict->first->next;

free(delNode->word);
free(delNode);
}
free(dict);

}

word)
{
struct Node * ptr = dict->first;
while (ptr != NULL) {
if

clock();
printf("t0 = %f sec \n", t0 / (float)CLOCKS_PER_SEC);

struct Dictionary *dict

639 байт ( Alice.txt x 7,06)
Tolkien2.txt – 5 043 195

left;
struct NodeTree * right;
};
struct Dictionary {
struct NodeTree * root;
int cnt_words;
};

struct

= (struct Dictionary *)
malloc(sizeof(struct Dictionary));
dict->root = NULL;
dict->cnt_words = 0;
return

word)
{
int cond;

if (p == NULL) {
p = (struct NodeTree*)malloc(

0) {
// вставляемое слово совпадает
// с уже имеющимся - ничего

word)
{
dict->root = addElement(dict->root, word);
dict->cnt_words++;
}

{
clearTree(p->left);
clearTree(p->right);
free(p->word);
free(p);
}
}

void destroy(struct Dictionary * dict) {
clearTree(dict->root);
free(dict);
}

cond;
if (p == NULL) {
return 0;
} else if ((cond =

word)
{
return containElement(dict->root, word);
}

clock();
printf("t0 = %f sec \n", t0 / (float)CLOCKS_PER_SEC);

struct Dictionary *dict

639 байт ( Alice.txt x 7,06)
Tolkien2.txt – 5 043 195

– 142 800 байт
Tolkien.txt – 1 008 639 байт (

его площади – O(N)

«найти имя в телефонной книге» требует всего

O(N)


O(N) = «асимптотическая оценка сложности»

элементов в списке?
– какая зависимость времени поиска от количества элементов

O(N)
Поиск в двоичном дереве поиска: O(log N)

Поиск в отсортированном массиве