VPF::Сортировка слов двоичным деревом

ZimOne

Дата 18.4.2015, 18:01 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 1.12.2013

Репутация: нет
Всего: нет

Пишу программу для сортировки списка слов в алфавитном порядке через двоичное дерево. Сначала написал аналогичную программу для сортировки последовательности целых чисел по возрастанию, все работает. Попытался переделать под строки, не работает, не могу найти ошибку, программа ничего не печатает.
Код прокомментирован, так же напротив некоторых строк есть в комментарии строка, которая была на этом месте для сортировки чисел. Заранее спасибо за помощь.

Код


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
typedef char item_type; /* typedef int item_type */
 
typedef struct tree {
    item_type item; /*Элемент данных*/
    struct tree *parent; /*Указатель на родительский узел*/
    struct tree *left; /*Указатель на левый дочерний узел*/
    struct tree *right; /*Указатель на правый дочерний узел*/
}tree;
 
/*Функция печати дерева, получает на вход указатель на дерево*/
void print_tree (tree *l);
 
/*Функция вставки узла x в дерево l, с родительским узлом parent, содержащим l*/
void insert_tree (tree **l, item_type x, tree *parent);
 
/*Функция инициализации дерева*/
tree *init_tree (void);
 
/*Функция поиска минимального элемента в дереве l*/
tree *find_minimum (tree *l);
 
/*Функция определения числа пробелов в строке str*/
int spaceNumber (char str[256]);
 
int main(void)
{
    FILE *fin; char str[256]; int num, i;
    tree *l; char filename[256];
    l = init_tree();
    scanf("%s", &filename); /* scanf("%d", &filename); */
    fin = fopen(filename, "r"); /*Открываем файл, из которого считываем слова (ранее числа)*/
    num = spaceNumber(str) - 1;
    for (i = 0; i < num; ++i)                   /* while (fscanf(fin, "%d", &x) == 1) insert_tree(&l, x, NULL); */
        while (fscanf(fin, "%s", &str) == 1) 
            insert_tree(&l, str, NULL);
    print_tree(l);
    return 0;   
}
 
/*Функция печати дерева, получает на вход указатель на дерево*/
void print_tree (tree *l)
{
    if (l != NULL) {
        print_tree (l -> left);
            printf ("%s ", l -> item); /* printf ("%d", l->item}; */
        print_tree (l -> right);
    }
}
 
/*Функция вставки узла x в дерево l, с родительским узлом parent, содержащим l*/
void insert_tree (tree **l, item_type x, tree *parent)
{
    tree *p;
    if (*l == NULL) {
        p = malloc (sizeof (tree));
        p->item = x;
        p->left = p->right = NULL;
        p->parent = parent;
        *l = p;
        return;
    }
    if (x < (*l)->item)
        insert_tree (&((*l)->left), x, *l);
    else
        insert_tree (&((*l)->right), x, *l);
    
}
 
/*Функция инициализации дерева*/
tree *init_tree (void)
{
    return (NULL);
}
 
/*Функция поиска минимального элемента в дереве l*/
tree *find_minimum (tree *l)
{
    tree *min;
    if (l == NULL) return NULL;
    min = l;
    while (min->left != NULL)
        min = min->left;
    return min;
}
 
/*Функция определения числа пробелов в строке str*/
int spaceNumber (char str[256])
{
    int i, s = 0, l = strlen(str);
    for (i = 0; i < l; ++i)
        if (str[i] == ' ')
            s++;
    return s;
}

feodorv

Дата 18.4.2015, 19:50 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 11
Всего: 45

Ну ещё бы...

Цитата(ZimOne @ 18.4.2015, 18:01

)

typedef char item_type; /* typedef int item_type */

typedef struct tree {
item_type item; /*Элемент данных*/

Один-единственный char - это не строка, это просто один символ. Если хотите строку и не хотите возиться с выделением под неё памяти, можно в элементе дерева прописать массив символов максимального для строк (а это у Вас 256 символов) размера:

Код

typedef struct tree {
    char string[256]; /*Элемент данных*/
    struct tree *parent; /*Указатель на родительский узел*/
    struct tree *left; /*Указатель на левый дочерний узел*/
    struct tree *right; /*Указатель на правый дочерний узел*/
}tree;

(вообще, элемент дерева называют leaf'ом, tree - это уже всё дерево целиком).

Соответственно, присвоение символу значения указателя никак не сохраняет прочтённую строку в памяти для дальнейшего использования:

Цитата(ZimOne @ 18.4.2015, 18:01

)

void insert_tree (tree **l, item_type x, tree *parent)
{
    ...
    p->item = x;
    ...

Так можно делать с int, но так не получиться со строками. Схема a la шаблоны C++ здесь никак не сработает. Тогда для нашего простого случая всё это будет иметь такой вид:

Код

void insert_tree (tree **l, char *string, tree *parent)
{
    ...
    strncpy( p->string, string, 256);
    p->string[255] = '\0';
    ...

(здесь константы могут быть переписаны через sizeof(p->string)).

Ну и печать символа как строки:

Цитата(ZimOne @ 18.4.2015, 18:01

)

printf ("%s ", l -> item); /* printf ("%d", l->item}; */

может привести программу к краху. Удивительно, что она у Вас лишь ничего не печатает.

--------------------

Напильник, велосипед, грабли и костыли - основные инструменты программиста...

feodorv

Дата 18.4.2015, 20:17 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 11
Всего: 45

Ах, да, забыл про сравнения.

Цитата(ZimOne @ 18.4.2015, 18:01

)

    if (x < (*l)->item)
        insert_tree (&((*l)->left), x, *l);
    else
        insert_tree (&((*l)->right), x, *l);

Строки сравниваются не указателями, а посимвольно. Обычно для этого используют функцию strcmp.

--------------------

Напильник, велосипед, грабли и костыли - основные инструменты программиста...

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »