Как найти всю строку в три в C - PullRequest
Новая
       9

Как найти всю строку в три в C

0 голосов
/ 06 января 2019

Я вставил около 10 тыс. Строк в Trie, и теперь мне нужно найти 1, сравнить с другими и снова для каждой отдельной строки. Так что этот поиск должен быть быстрым, и я не думаю, что моя функция - лучшее решение. 

#include <stdio.h>
#include <locale.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include "trie.h"
#include "lcs.h"

#define WORD_SIZE 64
#define CHAR_SIZE 256
#define FILE_NAME "file.txt"

char words[WORD_SIZE] = {0};
char defWord[WORD_SIZE] = {0};
int firstWord = 0;
int j = 0;

void searchStrings(struct Trie *head) {
struct Trie *curr = head;
int i, k;

    for (i = 0; i < CHAR_SIZE - 1; i++) {
        if (curr->character[i] != NULL && !curr[i].isProcessed) {
            if (curr[i].isLeaf) {
                if (!firstWord) {
                    for (k = 0; k < WORD_SIZE; k++) {
                        defWord[k] = words[k];
                        if (words[k] == '\0') break;
                    }
                    firstWord = 1;
                    continue;
                }
                curr[i].isProcessed = 1;
                //compareStrings(words); TODO: complete that function
            } else {
                words[j] = i;
                searchStrings(curr);
            }
        }
    }
}

void parseData(FILE *text) {
    int c = 0, wordIter = 0;
    char word[WORD_SIZE] = {0};
    struct Trie *head = getNewTrieNode();

    if (!head) {
        printf("Error! Structure is not created.");
        return;
    }

    setlocale(LC_ALL, "");

    while (c != EOF) {
        c = getc(text);

        if (!isalpha(c)) {
            insert(&head, word);
            memset(word, 0, strlen(word));
            wordIter = 0;
            continue;
        }
        word[wordIter++] = c;
    }
    searchStrings(head);
    free(head);
}

int loadFile() {
    FILE *text;

    text = fopen(FILE_NAME, "r");

    if (!text) {
        printf("Error! Cannot open file.");
        return EXIT_FAILURE;
    }

    parseData(text);

    fclose(text);

    return EXIT_SUCCESS;
}

Это файл Три. 

#include <stdio.h>
#include <stdlib.h>
#include "trie.h"

#define CHAR_SIZE 256

struct Trie {
    int isLeaf;    // 1 when node is a leaf node
    int isProcessed; // 1 when leaf node is processed
    struct Trie *character[CHAR_SIZE];
};

// Function that returns a new Trie node
struct Trie *getNewTrieNode() {
    int i;
    struct Trie *node = (struct Trie *) malloc(sizeof(struct Trie));
    node->isLeaf = 0;
    node->isProcessed = 0;

    for (i = 0; i < CHAR_SIZE; i++)
        node->character[i] = NULL;

    return node;
}

// Iterative function to insert a string in Trie.
void insert(struct Trie **head, char *str) {
    // start from root node
    struct Trie *curr = *head;
    int numb = 0;

    while (*str) {
        numb = *str - 'A';

        if (numb < 0) { // for negative numbers
            numb += CHAR_SIZE;
        }
        // create a new node if path doesn't exists
        if (curr->character[numb] == NULL)
            curr->character[numb] = getNewTrieNode();

        // go to next node
        curr = curr->character[numb];

        // move to next character
        str++;
    }

    // mark current node as leaf
    curr->isLeaf = 1;
}

Основной файл 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "parser.h"

int main(void) {

    loadFile();

    return 0;
}

Я ищу param isLeaf. Если это параметр 1, это означает, что конец строки. Поэтому, когда я нахожу первый символ, который не обрабатывается, я могу добавить его в глобальный массив. Когда я нахожу первый символ Leaf, я могу сохранить его и отправить в следующую функцию. Но есть проблема с гласными. Я могу добавить оператор if, когда длина> 3. Могу ли я сделать это проще? Или есть лучший алгоритм? Размер 256 символов, потому что мне нужны все символы чешского алфавита, включая заглавные буквы, а некоторые символы 128+ в CP1250 ascii.

...