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

Question

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

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

compareStrings ("alpha", "altered")

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

compareStrings ("zioty", "yucca");

возвращает значение 1, потому что «zioty» лексикографически больше, чем «юкка».

#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;

}

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

Answer 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;