лексикографически сортировать в C

Я не понимаю, как это работает. Почему это так? И как мы сравниваем символы в C , как я могу понять, какой из них меньше или больше другого? Это из книги.

Вызовите функцию compareStrings и верните значение –1, если первая строка лексикографически меньше второй строки, 0, если две строки равны, и 1, если первая строка лексикографически больше второй строки. Итак, вызов функции

compareStrings ("alpha", "altered")

возвращает значение –1, так как первая строка лексикографически меньше второй строки (представьте, что это означает, что первая строка находится перед второй строкой в ​​словаре). И вызов функции

compareStrings ("zioty", "yucca");

возвращает значение 1, так как "zioty" лексикографически больше, чем "yucca".

#include <stdio.h>
#include <stdbool.h>

struct entry
{
    char word[15];
    char definition[50];
};

bool equalStrings(char s1[], char s2[])
{
    bool areEqual = false;
    int i = 0;

    while(s1[i] != '\0' && s2[i] != '\0' && s1[i] == s2[i])
        i++;

    if(s1[i] == '\0' && s2[i] == '\0')
        areEqual = true;
    else
        areEqual = false;

    return areEqual;
}

int lookup (struct entry dictionary[], char search[],int entries)
{
    int low = 0;
    int high = entries - 1;
    int mid, result;

    while (low <= high)
    {
        mid = (low + high) / 2;
        result = compareStrings (dictionary[mid].word, search);

        if(result == -1)
            low = mid + 1;
        else if(result == 1)
            high = mid - 1;
        else 
            return mid;
    }

    return -1;
}

int compareStrings(char s1[], char s2[])
{
    int i = 0, answer;

    while(s1[i] == s2[i] && s1[i] != '\0' && s2[i] != '\0')
        i++;

    if(s1[i] < s2[i])
        answer = -1;
    else if(s1[i] == s2[i])
        answer = 0;
    else 
        answer = 1;

    return answer;
}

int main()
{
    struct entry dictionary[100] = 
    {
        {"aardvark", "a burrowing African mammal" },
        {"acumen", " a bottomless pit  "},
        {"addle", "to become confused "},
        {"agar", "a jelly made from seaweed" }
        {"affix", "to append; attach"}
    };

    char word[15];
    int entries = 10;
    int entry;

    printf("Enter word: ");
    scanf("%14s", word);
    entry = lookup (dictionary, word, entries);

    if(entry != -1)
        printf("%s\n", dictionary[entry].definition);
    else
        printf("Sorry, the word %s is not in my dictionary.\n", word);

    return 0;

}

Как понять, что одно больше другого? Спасибо.


person Little Max    schedule 02.07.2018    source источник
comment
Это самые основные алгоритмы проверки равенства, сравнения и поиска. Вы не поняли алгоритмы или то, как вы их реализуете на C? Я бы посоветовал вам провести больше исследований, прежде чем обращаться за помощью к эксперту.   -  person M. Azyoksul    schedule 02.07.2018
comment
Я не понимаю, почему мы сравниваем последний символ в строке. И почему он вызывается лексикографически?   -  person Little Max    schedule 02.07.2018
comment
@LittleMax не обязательно последний символ. Подумай об этом, while(s1[i] == s2[i] && s1[i] != '\0' && s2[i] != '\0') i++;, когда заканчивается петля?   -  person Stan    schedule 02.07.2018
comment
@Stan Когда персонажи будут другими. Но как же тогда сравнивать этих персонажей? Все равно спасибо   -  person Little Max    schedule 02.07.2018
comment
@Little Max, на самом деле char - это байт. Что ты не можешь понять?   -  person purec    schedule 02.07.2018
comment
Мы сравниваем байты? Или мы используем коды ASCII для сравнения символов?   -  person Little Max    schedule 02.07.2018
comment
Один байт может содержать значение в диапазоне от 0 до 255. Каждое значение представляет собой соответствующий символ, то есть ASCII.   -  person purec    schedule 02.07.2018
comment
@Маленький Макс, если ты все еще не можешь понять, значит, ты немного на уровне абстракции. C вообще не имеет ничего общего с абстракциями. Каждый символ - это число. Это полезно для сортировки по алфавиту. «В» идет после «А», потому что 66 › 65.   -  person purec    schedule 02.07.2018


Ответы (1)


Лексикографический порядок подобен порядку словаря, a предшествует b... с дополнительным поведением, которое имеет значение регистра, прописные буквы идут перед строчными, а неалфавитные символы также сравниваются на основе их кодировки.

Это сравнение выполняется посимвольно. Если все символы в обеих строках равны, строки сравниваются равными, возвращаемое значение равно 0, в противном случае относительный порядок определяется сравнением первого несовпадающего символа. Если s1[i] < s2[i], строка s1 предшествует s2, возвращаемое значение отрицательное, иначе s1 идет после s2, возвращаемое значение положительное.

Обратите внимание, однако, что реализация этой книги неоптимальна и потенциально неверна:

  • если s1[i] == s2[i] и s1[i] != '\0', сравнение s2[i] с '\0' излишне.
  • символы следует сравнивать как unsigned char, чтобы расширенные символы шли после обычных символов. strcmp указывается таким образом.

Вот упрощенная версия:

int compareStrings(const char *s1, const char *s2) {
    size_t i;

    for (i = 0; s1[i] == s2[i]; i++) {
        if (s1[i] == '\0')
            return 0;
    }
    if ((unsigned char)s1[i] < (unsigned char)s2[i])
        return -1;
    else
        return 1;
}

Дополнительные примечания:

  • dictionary, определенное в main, не сортируется, agar должно идти после affix. Функция lookup использует массив сортируемых структур entry. Он может не найти правильную запись для некоторых входных слов.

  • функция lookup использует алгоритм бинарного поиска. Этот метод очень эффективен, но в реализации есть классическая ошибка: mid = (low + high) / 2; может переполняться для больших массивов, что приводит к неопределенному поведению. Должно быть написано:

    mid = low + (high - low) / 2;
    
person chqrlie    schedule 02.07.2018