[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;