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

[ManHack]

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

[ManHack]

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);
}
}
Аналогичный вопрос.

[Admiral]

ManHack, например так if ((cond = strcmp(identName, ptr->name)) == 0) -> if (!(cond = strcmp(identName, ptr->name)))
if (ptr != NULL) -> if (ptr)

[ManHack]

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

[pva]

Если можно использовать стандартную библиотеку 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";

[ManHack]

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

[ManHack]

Написал так:

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 ==========


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

[ManHack]

Не понимаю ошибки:
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
Как исправить и убрать эти дурацкие ошибки линковки?

[pva]

Как исправить и убрать эти дурацкие ошибки линковки? »
во всех *.h сделай extern TREE tree;
в одном из *.cpp сделай TREE tree=NULL;