C: обойти бинарное дерево рекурсией
От: Аноним  
Дата: 09.06.08 12:41
Оценка:
Покажите примерчик для системы поиска.
т.е у меня есть строка с начальным символом A, B или C
и мне нужно в зависимости от первого символа выбрать в структуре слова начитающиеся на эту букву на С, не на С++.
Apple
Acer

Beer
Beep

Clean
Clear
Call
Только так, что-бы если я ввожу не один символ, а например два Ap, то вывелось только Apple
На С++ можно вот так, а как на С?

И еще подскажите с вот такой регуляркой \x — это что такое?

typedef std::list<std::string>          StringList;
typedef smart_ptr<StringList>           StringListPtr;
typedef std::map<char, StringListPtr>   StringTable;
typedef std::pair<char, StringListPtr>  StringTablePair;

void Init(StringTable & Table)
{
       StringListPtr H_List = new StringList;
       H_List.push_back("hi");
       H_List.push_back("hello");
       H_List.push_back("hacker");

       StringListPtr W_List = new StringList;
       W_List.push_back("world");
       W_List.push_back("word");

       StringListPtr C_List = new StringList;
       C_List.push_back("c++");

       Table.insert(StringTablePair('h', H_List));
       Table.insert(StringTablePair('w', W_List));
       Table.insert(StringTablePair('c', C_List));
}

bool IsMatch(const std::string & sStr, StringList & List)
{
       for (StringList::iterator it = List.begin(), end = List.end(); it != end; ++it)
             if (sStr == *it)
                   return true;
       return false;
}

bool IsMatch(const std::string & sStr, StringTable & Table)
{
       if (sStr.size() == 0)
            return false;

       StringTable::iterator it = Table.find(sStr[0]);
       if (it == Table.end())
            return false;

       return IsMatch(sStr, *(*it));
}
Re: C: обойти бинарное дерево рекурсией
От: Кодт Россия  
Дата: 09.06.08 13:48
Оценка:
Здравствуйте, <Аноним>, Вы писали:

А>На С++ можно вот так, а как на С?


На С++ можно проще.
using namespace std; // чтоб в глазах не рябило

typedef set<string> dict_type;
dict_type dictionary;
void init()
{
    dictionary.insert("hi");
    dictionary.insert("hello");
    .....
}

string coprefix(string s) // лексикографически следующая строка за строками с префиксом s
{
    while(!s.empty() && s.back()=='\xFF')
        s.pop_back();
    if(!s.empty())
        ++s.back();
    return s;
}
// работа этой функции очень проста:
// "ABCяяя" --> "ABD" (где, в некоей кодировке, 'я'==0xFF)
// "ABCDEF" --> "ABCDEG"
// "" --> "" - особый случай, пустой префикс накрывает весь диапазон
// "яяя" --> "" - не существует бОльшей строки, поэтому тоже превращаем в особый случай

typedef dict_type::const_iterator dict_iter;
pair<dict_iter,dict_iter> find_by_prefix(string s)
{
    dict_iter const i = dict.lower_bound(s);
    
    string const s1 = coprefix(s);
    dict_iter const j = next.empty() ? dict.end() : dict.lower_bound(s1);
}


А>И еще подскажите с вот такой регуляркой \x — это что такое?


Это 16-ричный код символа, '\xhh'. Например, '\x1B' = char(27) = ESC.
А '\ooo' где o=0..7 — восьмеричный код. '\33', '\033' = char(27) = ESC.
... << RSDN@Home 1.2.0 alpha rev. 655>>
Перекуём баги на фичи!
Re[2]: C: обойти бинарное дерево рекурсией
От: Кодт Россия  
Дата: 09.06.08 14:05
Оценка:
А>>На С++ можно вот так, а как на С?

На Си, если у тебя отсортированный массив строк, делается так же.
Только алгоритм lower_bound нужно перепереть
char const* lower_bound(char const* begin, char const* end, char const* str)
{
    // [begin,end) - диапазон поиска
    while(begin != end)
    {
        char const* median = begin + (end-begin)/2; // begin <= median < end
        if(strcmp(median,str)<0)
            begin = median+1;
        else
            end = median;
    }
}
... << RSDN@Home 1.2.0 alpha rev. 655>>
Перекуём баги на фичи!
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.