Применение бинарного поиска в текстовом файле в c для построчного текста - PullRequest
Новая
       102

Применение бинарного поиска в текстовом файле в c для построчного текста

0 голосов
/ 01 марта 2019

Я пытаюсь найти слово в текстовом файле, и мне это удалось, но код не всегда работает.Просто я не понимаю, почему это не работает внутри цикла, а работает, когда я делаю это вручную.

Я знаю, на что мне нужно смотреть, но, пожалуйста, кто-нибудь может мне помочь. 

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

void main()
{
    FILE *fp;
    fp=fopen("testdictionary.txt","r");

    char word[]="her";
    char line[7];
    int n;
    int upper_limit=48;
    int lower_limit=0;
    int result=-1;

    while(result!=0) {
        n=(upper_limit+lower_limit)/2;
        printf("Value of n:%d ",n);
        fseek(fp,n,SEEK_SET);

        // setting the file pointer to the beginning of the word. --
        fseek(fp,-1,SEEK_CUR);
        char tst;
        do {
            fseek(fp,-1,SEEK_CUR);
            if(ftell(fp)==0) {
                break;
            }

            tst=fgetc(fp);
            if(tst=='\n') {
                break;
            }

            fseek(fp,-1,SEEK_CUR);
        } while(tst!='\n');
        //----------------------------------------------------------

        fgets(line,7,fp);
        result=strcmp(line,strcat(word,"\n"));
        printf(" Result:%d ",result);

        if(result==1) {
            upper_limit=n;
            printf("Required 'word' is above the line of text.\n");
        }
        else if(result==-1) {
            lower_limit=n;
            printf("Required 'word' is below the line of text.\n");
        }
        else if(result==0) {
            printf("Word found");
        }
    }
}

Мой текстовый файл 

aoo
bpp
cas
dzx
edf
fvb
gty
her
iwe
jqw

Вывод (когда я запускаю вышеуказанный код.) 

Value of n:24  Result:-1 Required 'word' is below the line of text.
Value of n:36  Result:-1 Required 'word' is below the line of text.
Value of n:1322  Result:1 Required 'word' is above the line of text.
Value of n:329639  Result:1 Required 'word' is above the line of text.
Value of n:84052197

Часть, которую я не понимаю, состоит в том, что, если я вручную введу n = 36, результат говорит о 0, и слово найдено. Но когда я пытаюсь искать автоматически, даже когда значение n становится 36 после 2-го шага, циклне ломается и дает странные и большие значения n.

Поэтому, когда я сам ставлю n = 36 (показано ниже), я получаю ожидаемый вывод, что слово "her" найдено. 

while(result!=0)
{
    // n=(upper_limit+lower_limit)/2;
    n=36;
    printf("Value of n:%d ",n);
    fseek(fp,n,SEEK_SET);

Вывод 

Value of n:36  Result:0 Word found
Process returned 10 (0xA)   execution time : 0.141 s
Press any key to continue.

Я не знаю, так ли это, как вы должны делать бинарный поиск, но это то, что я знаю.Я только начинающий в программировании.

1 Ответ

0 голосов
/ 01 марта 2019

Функция strcmp не возвращает , в частности -1 или 1 (хотя это может произойти).Он возвращает значение 0, < 0 или > 0.

Также в 

result = strcmp(line, strcat(word, "\n"));

вы не можете ничего объединить с 

char word[] ="her";

, потому чтоМассив не имеет места.Лучше удалить символ новой строки из строки файла, чем добавить его в целевую строку.

Даже если бы вы могли, вы добавляете еще одну новую строку в каждой итерации.Поэтому я предлагаю 

fgets(line, 7, fp);
line [ strcspn(line, "\r\n") ] = '\0';      // truncate any newline
result = strcmp(line, word);
if(result > 0) {
    upper_limit = n;
    printf("Required 'word' is above the line of text.\n");
}
else if(result < 0) {
    lower_limit = n;
    printf("Required 'word' is below the line of text.\n");
}
else {   // no other possibility
    printf("Word found");
}
...