VPF::С++ и строки - Форум программистов

LesnoyChelovek

Дата 1.4.2006, 17:27 (ссылка)

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

Загрузка ...

странник Интернета

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

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

Данна задача:"Удалить из строки все слова, которые не являются идентификаторами. "
В прочем идентификаторы вычисляються по правилу, что они не должны начинаться на цифру, на технические знаки и т.д. Это всё понятно, но не могу понять как написать код, слишком много переборов получаеться.
Прошу помочь с кодом... Пишу на Borland C++ 5.0

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

Делай добро и бросай его в воду... оно не утонет.. добром к тебе вернеться.
http://picasaweb.google.com/LesnoyChelovek/Photo

Fin

Дата 1.4.2006, 20:13 (ссылка)

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

Загрузка ...

Дракон->Спать();

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

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

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

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

Пролетал мимо.

LesnoyChelovek

Дата 1.4.2006, 23:12 (ссылка)

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

Загрузка ...

странник Интернета

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

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

Зачем все так сложно? Может попробывать ASCII кодом? Правда я все ещё стою на теории... А необходим код.

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

Делай добро и бросай его в воду... оно не утонет.. добром к тебе вернеться.
http://picasaweb.google.com/LesnoyChelovek/Photo

LesnoyChelovek

Дата 4.4.2006, 10:58 (ссылка)

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

Загрузка ...

странник Интернета

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

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

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

Делай добро и бросай его в воду... оно не утонет.. добром к тебе вернеться.
http://picasaweb.google.com/LesnoyChelovek/Photo

Fin

Дата 4.4.2006, 15:58 (ссылка)

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

Загрузка ...

Дракон->Спать();

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

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

Вот класс, реализуеший алгоритм дерева поиска

Код


// ------------------------------------------------------------------
// Author:   Fin
// Subject:  Tample Trees of Find (FindTree)
// Version    1.0
// Date       Begin 30/07/2005 End 02/08/2005
// ------------------------------------------------------------------
// int SetWord(char *ch, T *Date)
// Function Set word into Tree
// return value 0 - error, 1 - all OK
// ------------------------------------------------------------------
// int FindChar(char ch, T *Date)
// Function look for char in the tree and memory current point
// return value 0 - error, 1 - all OK
// ------------------------------------------------------------------
// int FindWord(char *ch, T *Date)
// Function look for word in the tree
// return value 0 - error, 1 - there is level on the tree
// 2 - there is word on the tree
// ------------------------------------------------------------------
// void SetNullPos(void)
// Erase current positon
// ------------------------------------------------------------------  
// int DeleteWord(char *ch)
// Erase Date of word on the tree
// return value 0 - Date don't erase, 1 - all OK
// ------------------------------------------------------------------ 

#ifndef FINDTREES_H
#define FINDTREES_H

#include <windows.h>

// ------ FindTree --------------------------------------------------

template < class T >
class FindTree
{
private:
    typedef struct List
    {
        List *Next;
        List *Prev;
        List *Level;
        char ch;
        T *Date;
    };
    List *Tree;
    List *Current;

    List *NewList(List *Dat)
    {
        List *temp = new List;
        if (temp == NULL) return temp;
        ZeroMemory(temp, sizeof(List));
        if (Dat != NULL)
        {
            temp->Prev=Dat;
            temp->Next=Dat->Next;
            Dat->Next=temp;
            if (temp->Next !=NULL) temp->Next->Prev=temp;
        }
        return temp;
    }

    void DeleteTree(List *Date)
    {
        List *temp=Date;
        List *old;
        while (temp != NULL)
        {
            if (temp->Date != NULL) delete temp->Date;
            if (temp->Level != NULL) DeleteTree(temp->Level);
            old=temp;
            temp=temp->Next;
            delete old;
        }
    }

public:

    FindTree(void)
    {
        Tree=NULL;
        Current=NULL;
    }


    ~FindTree()
    {
        DeleteTree(Tree);
    }
    
    int SetWord(char *ch, T *Date)
    {
        int res=0;
        if ((Date !=NULL) && (ch !=NULL) && (ch[0] != 0))
        {
            int i=0;
            if (Tree == NULL) 
            {
                Tree=NewList(NULL);
                if (Tree==NULL) return res;
                Tree->ch=ch[i];
            }
       List *temp=Tree;
            while (ch[i] !=0)
            {
                while ((temp->ch != ch[i]) && (temp->Next != NULL)) temp=temp->Next;
                if (temp->ch != ch[i]) 
                {
                    temp=NewList(temp);
                    if (temp == NULL) return res;
                    temp->ch=ch[i];
                }
                i++;
                if (ch[i] !=0)
                {
                    if (temp->Level==NULL)
                    {
                        temp->Level=NewList(NULL);
                        if (temp->Level==NULL) return res;
                        temp->Level->ch=ch[i];
                    }
                    temp=temp->Level;
                }
            }
            temp->Date=new T;
            if (temp->Date == NULL) return res;
            CopyMemory(temp->Date,Date, sizeof(T));
            res=1;
        }
        return res;
    }

    int FindChar(char ch, T *Date)
    {
        int res=0;
        if (Current == NULL) Current=Tree;
        else Current=Current->Level;
        if (Date == NULL) Current = NULL;
            

        while ((Current != NULL) && (Current->ch != ch)) Current=Current->Next;
        if (Current != NULL)
        {
            res=1;
            if (Current->Date != NULL) 
            {
                CopyMemory(Date, Current->Date, sizeof(T));
                res=2;
            }
        }
        return res;
    }

    int FindWord(char *ch, T *Date)
    {
        int res =-1;
        Current=NULL;
        int i=0;
        if (ch != NULL)
        {
            while ((ch[i] !=0) && (res !=0))
            {
                res=FindChar(ch[i], Date);
                i++;
            }
        }
        if (res==-1) res=0;
        return res;
    }

    void SetNullPos(void)
    {
        Current=NULL;
    }

    int DeleteWord(char *ch)
    {
        int res=0;
        T *temp;
        if (FindWord(ch, temp) == 2)
        {
            delete Current->Date;
            Current->Date=NULL;
            res=1;
        }
        return res;
    }
};

// ------------------------------------------------------------------

#endif //FINDTREES_H

Определяеш структуру, в которой будеш хранить информацию по каждому ключу.

Код


struct IDENT
{
    int id;
    int TypeKey;
} ;

Предупреждение: не рекомендуется использовать динамические переменные.

Затем определяеш экземпляр дерева.

Код


FindTree<IDENT> Trees;

Заводиш все свои ключи.

Код


IDENT iden;
iden.id=1;
iden.TypeKey=2;
Trees.SetWord("Integer", &iden);

Ну и сам поиск
Можно искать сразу все слово

Код


Trees.FindWord("Integer", &iden);

При этом: Функция возвратит
0 - если слово не найдено.
1 - если сушествует ветка, но не сушествует данного индефикатора
2 - Если слово найдено.

Можно искать и по буквенно.
Вначале поиска нужно сбросить дерево в начальное положение поиска.

Код


Trees. SetNullPos();

Затем уже вводить посимвольно каждую букву

Код


Trees.FindChar('I', &iden);

Возврат функции такой же, как и для всего слова.

Это сообщение отредактировал(а) Fin - 4.4.2006, 22:24

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

Пролетал мимо.

LesnoyChelovek

Дата 4.4.2006, 21:59 (ссылка)

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

Загрузка ...

странник Интернета

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

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

А нельзя как-то реализовать с помощью ASCII?

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

Делай добро и бросай его в воду... оно не утонет.. добром к тебе вернеться.
http://picasaweb.google.com/LesnoyChelovek/Photo

Dov

Дата 4.4.2006, 22:03 (ссылка)

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

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

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

Код

#include <stdio.h>
#include <string.h>

int main()
{ 
    char  str[] = "12strArray Hello,$point@ber world 4__hendl...";        
    char* word,                                              // выделенное слово    
        * delim = ".,:; ?!-()'[]{}",                         // разделители слов
        * noAllowed = "0123456789@#$%^&",                    // недопустимые символы(можно добавить ещё)
        * strCopy = new char[strlen(str) + 1];               // рабочая копия строки
    char* p;

    strcpy(strCopy, str);    
    printf("%s\n\n", str);                                    

    word = strtok(strCopy, delim);                              // выделяем первое слово        
    while(word)                                               // пока есть слова    
    {
        // если начальный символ слова - недопустимый
        if(strcspn(word, noAllowed) == 0)                          
        {
            p = strstr(str, word);                              // находим слово в строке
            strcpy(p, p + strlen(word));                      // удаляем его 
        }

        word = strtok(NULL, delim);                           // выделяем очередное слово     
    }
    
    printf("%s\n\n", str);                                    

    delete[] strCopy;                                        

    return 0; 
}

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

Тут вечности запах томительный,
И свежие фрукты дешевые,
А климат у нас – изумительный,
И только соседи – #уевые.
Игорь Губерман.

Fin

Дата 4.4.2006, 22:22 (ссылка)

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

Загрузка ...

Дракон->Спать();

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

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

LesnoyChelovek, Что ты понимаеш под

Цитата

А нельзя как-то реализовать с помощью ASCII?

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

Пролетал мимо.

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