Хитрое бинарное дерево... - Компьютерный форум OSzone.net

Компьютерный форум OSzone.net (http://forum.oszone.net/index.php)

- Программирование и базы данных (http://forum.oszone.net/forumdisplay.php?f=21)

- - Хитрое бинарное дерево... (http://forum.oszone.net/showthread.php?t=174962)

Хитрое бинарное дерево...

Здравствуйте!
Мне нужно построить двоичное дерево на Си.
В узлах дерева хранится ключ - массив из символов (строка) и данные - указатель однонаправленный список.
В узлах списка хранится ключ - массив из символов (строка) и данные - указатель на однонаправленный список №2 (ещё один).
В узлах списка №2 хранится число и... всё :)
На Паскале я такое деревце закодить могу, а на Сях запутался... TT____TT Помогите пожалуйста распутаться.
Всего-то деревце, к узлам которого привязаны списки, к узлам которых привязаны списки...
Интересуют именно особенности написания кода для такой задачи на Си.

Код:

void AddToTree(struct tNode *ptr, char[] identName) {

    int cond;

    if (рtr == NULL) {  /* слово встречается впервые */

        ptr = talloc(); /* создается новый узел */

        ptr->name = strdup(identName);  /* заталкиваем строку */

        ... /* А вот здесь надо инициализировать новый список, привязанный к этой вершине и затолкнуть в него первый элемент. Как? */

        ptr->left = ptr->right = NULL; /* завершаем инициализацию новой вершины дерева путём установления указателей на её потомков в нули */

    } else if ((cond = strcmp(identName, ptr->name)) == 0)  /* это слово уже встречалось */

        ... /* Значит, для этой вершины уже есть список хотя бы с одним элементом => нужно затолкнуть в него ещё один */

    else if (cond < 0)        /* меньше корня левого поддерева */

        ptr->left = AddToTree(ptr->left, identName);

    else                      /* больше корня правого поддерева */

        ptr->right = AddToTree(ptr->right, identName);

    return ptr;

}

Помогите восполнить пробелы.
Хотя тут, наверно, можно ещё красивее написать, чем пугающие условия вида " if ((cond = strcmp(identName, ptr->name)) == 0) ", подскажите как..

Код:

void TraverseTree(struct tnode *ptr) {

    if (ptr != NULL) {

        treeprint(ptr->left);

        // Печать: сначала identName, потом элемент из первого списка и все элементы из 2-го списка, которые к нему привязаны, потом ещё один из 1-го и все, которые из егонного 2-го и т.д.

        treeprint(ptr->right);

    }

}

Аналогичный вопрос.

ManHack, например так

Код:

if ((cond = strcmp(identName, ptr->name)) == 0) -> if (!(cond = strcmp(identName, ptr->name)))

if (ptr != NULL) -> if (ptr)

А когда и где проводить инициализацию списков? Они ведь разные для каждой вершины дерева.

Если можно использовать стандартную библиотеку C++:

Код:

#include <string>

#include <map>

using namespace std;



// если я правильно понял, должно быть так:

// поиск по дереву ключ=строка(уникальная) ->

//    список из пар <строка, список чисел> ->

//       добавляем, удаляем всякую фигню, но не делаем быстрого поиска



// список чисел

typedef vector<int> number_list_type;

// список пар строка-number_list_type

typedef list<pair<string, number_list_type> > number_w_key_list_type;

// дерево для поиска по ключу

typedef map<string, number_w_key_list_type> key_list_by_str_type;



// эта переменная содержит нужную структуру (по идее задача уже выполнена)

key_list_by_str_type key_list_by_str;



// как ей пользоваться?

// заполняем

static const char s1[] = "s1";

static const int i1[] = {1, 2, 3, 4};

static const char s2[] = "s2";

static const int i2[] = {5, 6};

static const char s3[] = "s3";

static const int i3[] = {7, 8, 9};

static const char s4[] = "s4";

static const int i4[] = {10};



void add_str(number_w_key_list_type& result, char const* str, int const* first, unsigned count)

{

        // добавляем пустой список, потом заполняем его доюавлением массива в конец

        copy(first, first+count, back_inserter<number_list_type>(

                *result.insert(result.end(), make_pair(string(s1), number_list_type())));

}



// это место можно очень хорошо свернуть в один цикл



add_str(key_list_by_str["key1"], s1, i1, sizeof(i1)/sizeof(i1[0]));

add_str(key_list_by_str["key1"], s2, i2, sizeof(i2)/sizeof(i2[0]));

add_str(key_list_by_str["key1"], s3, i3, sizeof(i3)/sizeof(i3[0]));

add_str(key_list_by_str["key2"], s4, i4, sizeof(i4)/sizeof(i4[0]));

key_list_by_str["key4"]; // пустой

теперь вопрос: какая физическая постановка задачи? мне эта структура кажется громоздкой и неудобной. Есть ещё куча замечательных шаблонов, например multimap, который позволяет хранить в сортированном дереве дубли. Поясни смысли задачи, может подскажу более удобную структуру. Если внутри тоже надо поиск по строке, то можно сделать map<string, multimap<string, int> > или map<string, map<string, vector<int> > >. В последнем случае работа с такой структурой напоминает работу с массивом

Код:

map<string, map<string, vector<int> > > my_data;

my_data["outer key"]["inner key"].push_back(10);

единственное неудобство - это operator[] добавляет элемент, если такой не найден. А чтобы не добавлять, нужно делать сложнее:

Код:

map<string, map<string, vector<int> > >::iterator found_outer;

map<string, vector<int> >::iterator found_inner;



if (my_data.end()!=(found_outer=my_data.find("outer key")) &&

        found_outer->second.end()!=(found_inner=found_outer->second.find("inner key")))

{

        // работа с найденным вектором

        // found_inner->second - это LVALUE vector<int>

        cout << "{";



        vector<int>::iterator

                out_first = found_inner->second.begin(),

                out_last  = found_inner->second.end();



        if (out_first!=out_last)

        {

                if (out_first!=--out_last) copy(out_first, out_last, ostream_iterator<char>(cout, ", "));

                cout << out_last;

        }



        cout << "}";



}

else

{

        cout << "- not found -";

}



cout << "\n";

Библиотеки C++ использовать нельзя, даже стандартные. Пишется на чистом Си. Сишные библиотеки подключать можно (например так: #include <stdlib.h>) , но не более того.
Задача такова:
На вход программе подаётся входной поток из файлов (пользователь задаёт маску типа *.txt, по которой ищутся файлы в папке с программой с помощью FindFirst и FindNext).
В выходной файл он должна записать перечень идентификаторов из файлов входного потока в лексикографическом порядке (понятно, что в процессе чтения файлов создаётся структура [в человеческом смысле слова] хранения идентификаторов и только когда последний файл прочитан до конца эта структура выводится... ). Причём, к каждому идентификатору, записанному в выходной файл дописываются имена файлов, в которых он хранится (без повторений: если 2 одинаковых идент-ра в одном файле, то имя файла выводится единожды) и для каждого файла выводится список строк, в которых встречается данный идентификатор (с повторениями).
Под идентификатором понимаете любое слово не длиннее MAX_IDENT_LENGTH (условно, 31 символ) и состоящее из букв и цифр, начинающееся обязательно с буквы и не совпадающее с зарезервированными словами языка (не Си, другого :) ).
Если будет предложение получше, чем дерево со списками со списками, то буду очень признателен ^^"
Списки - потому, что ограничивать их длину (как делается в случае массива) считается неправомочным.

Написал так:

TREE.H:

Код:

/* ’ҐЄгй*п Ї®§ЁжЁп ў Ёбе®¤*®¬ вҐЄбвҐ (location.h) */

#ifndef TREE

#define TREE



#include "scan.h"



#define MAX_FILENAME_LENGTH 255

#define LIST_SIZE 10000



typedef char tKey[NAMELEN];

typedef char tFileName[MAX_FILENAME_LENGTH];

//typedef ListOfFiles tData;



struct tNode {

   tKey name;

   struct tListOfFilesItem* file[LIST_SIZE];

   //tData addresses;

   struct tNode* left;

   struct tNode* right;

   //constructor

   //tNode() {

   //   left = right = 0;

   //}

};



struct tListOfFilesItem {

        tFileName name;

        struct tListOfLinesItem* line;

        //struct tListOfLinesItem line[LIST_SIZE];

        //struct tListOfLinesItem line;

        //struct tListOfFilesItem* next;

}



struct tListOfFiles {

        struct tListOfFilesItem* first;

        struct tListOfFilesItem* last;

}



struct tListOfLinesItem {

        int line;

        //struct tListOfLinesItem* next;

}



struct tListOfLinesItem {

        struct tListOfLinesItem* first;

        struct tListOfLinesItem* last;

}*/



/* <---LIST---> */

/*

struct ListOfFiles {

        char fileName[MAX_FILENAME_LENGTH];

        struct ListOfLines* strings;

        struct ListOfFiles* next;

};



struct ListOfLines {

        int lineNumber;

        struct ListOfLines* next;

};



typedef struct list_el item;



void main() {

   item * curr, * head;

   int i;



   head = NULL;



   for(i=1;i<=10;i++) {

      curr = (item *)malloc(sizeof(item));

      curr->val = i;

      curr->next = head;

      head = curr;

   }



   curr = head;



   while(curr) {

      printf("%d\n", curr->val);

      curr = curr->next ;

   }

}

*/

/* <---/LIST---> */



/*void InitTree(void);

void AddToTree(void);

void TraverseTree(void);*/



//extern int Line;     /*Ќ®¬Ґа бва®ЄЁ          */

//extern int Pos;      /*Ќ®¬Ґа бЁ¬ў®«* ў бва®ЄҐ*/

//extern int LexPos;   /*Џ®§ЁжЁп **з*«* «ҐЄбҐ¬л*/

//extern char* Path;   /*Џгвм Є д*©«г          */



#endif

TREE.C:

Код:

#include <stdlib.h>

#include <stdio.h>

#include <string.h>



#include "tree.h"



#define TRUE      1

#define FALSE     0



char ResetError = TRUE;

char* Message = "”*©« *Ґ ®вЄалв";

int Ch = chEOT;



static FILE *f;



void InitTree(struct tNode*) {

        struct tNode *root;

    root = NULL;

}



void InitFileList(struct tListOfFiles *FileList) {

        FileList->first = NULL;

        FileList->last = NULL;

}



void InitLineList(struct tListOfLines *LineList) {

        LineList->first = NULL;

        LineList->last = NULL;

}



//void PushLine(struct tListOfLinesItem) {

//

//}



//void PushFile(struct tListOfFilesItem) {

//

//}



void AddToLineList(struct tListOfFiles Queue, int Line) {

        struct tListOfLinesItem *ptr

        ptr = talloc(); 

        ptr->line = Line;

        ptr->next = NULL;

        if (Queue.first == NULL) {

                Queue.first = ptr; 

                Queue.last = ptr;

        } else {

                Queue.last.next = ptr;

                Queue.last = ptr;

        }

}



void AddToFileList(struct tListOfFiles Queue, char* Path, int Line) {

        struct tListOfFilesItem *ptr

        ptr = talloc(); 

        ptr->name = strdup(Path);

        ptr->next = NULL;

        if (Queue.first == NULL) {

                Queue.first = ptr; 

                Queue.last = ptr;

        } else {

                Queue.last.next = ptr;

                Queue.last = ptr;

        }

        

        /*int i = 0;

        while (file[i] != NULL && i <= LIST_SIZE) {

                i++;

        }

        FileList.file[i] = path;*/

}



void AddToTree(struct tNode *ptr, char[] identName) {

        int cond;

    if (рtr == NULL) {  /* слово встречается впервые */

        ptr = talloc(); /* создается новый узел, эквив. new(ptr) в Паскале */

        ptr->name = strdup(identName); /* ptr^.name := identName */

        //ptr->count = 1;

                //InitFileList(struct tListOfFilesItem *FileList);

                AddToFileList(Path, Line);

        ptr->left = ptr->right = NULL;

        } else if ((cond = strcmp(identName, ptr->name)) < 0) {

                AddToTree(ptr->left, identName);

        } else if ((cond = strcmp(identName, ptr->name)) < 0) {

                AddToTree(ptr->right, identName);

        }



        //} else if ((cond = strcmp(identName, ptr->name)) == 0) 

    //    ptr->count++;           /* это слово уже встречалось */

    //else if (cond < 0)        /* меньше корня левого поддерева */

    //    ptr->left = AddToTree(ptr->left, identName);

    //else                      /* больше корня правого поддерева */

    //    ptr->right = AddToTree(ptr->right, identName);

    

        return ptr;

}



/*void TraverseTree(struct tnode *ptr) {

    if (ptr != NULL) {

        treeprint(ptr->left);

        // Печать: идент - файлы - строки

                //printf("%4d %s\n", ptr->count, ptr->word);

        treeprint(ptr->right);

    }

}*/

Но возникают ошибкаи:

Цитата:

1>Compiling...
1>TREE.C
1>d:\obercompiler3\tree.h(34) : error C2236: unexpected 'struct' 'tListOfFiles'. Did you forget a ';'?
1>d:\obercompiler3\tree.h(34) : error C2059: syntax error : '{'
1>d:\obercompiler3\tree.h(44) : error C2011: 'tListOfLinesItem' : 'struct' type redefinition
1> d:\obercompiler3\tree.h(39) : see declaration of 'tListOfLinesItem'
1>Build log was saved at "file://d:\OberCompiler3\OberonCompiler\OberonCompiler\Debug\BuildLog.htm"
1>OberonCompiler - 3 error(s), 0 warning(s)
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========

Вероятно, я запутался с Сишными ссылками.
Там вместо нормальных паскалевских птичек употребляются * и &, причёт * могут применяться как к типу, так и к переменной/константе (вроде) и при этом ставиться либо слева от её имени, либо справа (что должно быть немаловажно, а что значит, если * стоит слева? а справа в каких случаях ставится?)
Читал Кернигана-Ритчи, не распутался :(
Помогите пожалуйста.

Не понимаю ошибки:

Код:

1>Linking...

1>SCAN.obj : error LNK2005: _tree already defined in O.obj

1>TREE.obj : error LNK2005: _tree already defined in O.obj

1>D:\OberCompiler3\OberonCompiler\Debug\OberonCompiler.exe : fatal error LNK1169: one or more multiply defined symbols found

1>Build log was saved at "file://d:\OberCompiler3\OberonCompiler\OberonCompiler\Debug\BuildLog.htm"

1>OberonCompiler - 3 error(s), 8 warning(s)

========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========

В TREE.H:

Код:

...

typedef struct tNode* TREE;

extern TREE tree = NULL;



struct tNode {

...

tree больше нигде не объявлен.
В SCAN.H и TREE.H, естественно, прописано #include.h
Как исправить и убрать эти дурацкие ошибки линковки?

Цитата:

Цитата ManHack

Как исправить и убрать эти дурацкие ошибки линковки? »

во всех *.h сделай extern TREE tree;
в одном из *.cpp сделай TREE tree=NULL;