Форум программистов, компьютерный форум CyberForum.ru

Вывод нескольких значений в бинарном поиске из массива структур - C++

Восстановить пароль Регистрация
 
Novichock123
1 / 1 / 0
Регистрация: 25.04.2015
Сообщений: 41
04.07.2015, 12:20     Вывод нескольких значений в бинарном поиске из массива структур #1
Существует массив структур. Структура:
C++
1
2
3
4
5
struct StructWords
{
char Word[32];
char Name[32];
};
В этой структуре отсортированы по алфавиту элементы Word. К примеру как выглядит сам массив можно посмотреть в миниатюрах.
Суть в том, чтобы бинарный поиск после того, как нашёл элемент (как правило первый из нужных), вывести все имена, которые связаны с этим словом.
То есть вводим к примеру слово: "русский". Программа через двоичный поиск должна вывести: Айвазовский, Репин, Перов.
Пробовал использовать код с Википедии, так как она умеет находить первый элемент из множества искомых. Переделал его под свои нужды. Вместо сравнения чисел поставил strcmp, возвращал не структуру, как в примере от Вики, а индекс.
Код с вики:
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
struct Result { size_t pos; int isFound; };
 
struct Result makeResult(size_t pos, int isFound)
{
    struct Result r;
    r.pos = pos;
    r.isFound = isFound;
    return r;
}
 
/* Макросы, означающие «найдено в позиции i» и «не найдено, если нужно
 * вставить со сдвигом, то в позицию i».
 */
#define FOUND(i)    makeResult(i, 1)
#define NOTFOUND(i) makeResult(i, 0)
 
struct Result binarySearch(size_t n, int a[], int x)
{
    /* Номер первого элемента в массиве */
    size_t first = 0;
    /* Номер элемента в массиве, СЛЕДУЮЩЕГО ЗА последним */
    size_t last = n;
 
    /* Начальная проверка, которую, в принципе, можно опустить — но тогда см. ниже! */
    if (n == 0) {
        /* массив пуст */
        return NOTFOUND(0);
    } else if (a[0] > x) {
        /* искомый элемент меньше всех в массиве */
        return NOTFOUND(0);
    } else if (a[n - 1] < x) {
        /* искомый элемент больше всех в массиве */
        return NOTFOUND(n);
    }
 
    /* Если просматриваемый участок непустой, first < last */
    while (first < last) {
        /* ВНИМАНИЕ! В отличие от более простого (first + last) / 2,
         * этот код устойчив к переполнениям.
         *
         * Если first и last знаковые, возможен код:
         * ((unsigned)first + (unsigned)last) >> 1.
         * Соотвественно в Java: (first + last) >>> 1.
         */
        size_t mid = first + (last - first) / 2;
 
        if (x <= a[mid])
            last = mid;
        else
            first = mid + 1;
    }
 
    /* Если условный оператор if (n == 0) и т.д. в начале опущен -
     * значит, тут раскомментировать!
     */
    if (/* last < n && */ a[last] == x) {
        /* Искомый элемент найден. last - искомый индекс */
        return FOUND(last);
    } else {
        /* Искомый элемент не найден. Но если вам вдруг надо его
         * вставить со сдвигом, то его место - last.
         */
        return NOTFOUND(last);
    }
}
 
int main()
{
    int a[] = { 1, 3, 5, 7, 9 };
    struct Result r = binarySearch(5, a, 12);
    /* Вторая подстановка соответствует соглашениям Windows; на Unix %zu */
    printf("%s at %Iu\n", r.isFound ? "Found" : "Not found", r.pos);
    return 0;
}
Переделанный код:
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/* Номер первого элемента в массиве */
//massiv инициализирован
int binarySearch(char *key)
    {
        size_t first = 0;
        /* Номер элемента в массиве, СЛЕДУЮЩЕГО ЗА последним */
        size_t last = Number; //Number равен последнему индексу
 
        /* Начальная проверка, которую, в принципе, можно опустить — но тогда см. ниже! */
        if (Number == 0) {
            /* массив пуст */
            return -1;
        }
        else if (strcmp(massiv[0].Word, key)>0) {
            /* искомый элемент меньше всех в массиве */
            return -1;
        }
        else if (strcmp(massiv[Number - 1].Word, key)<0) {
            /* искомый элемент больше всех в массиве */
            return Number;
        }
 
        /* Если просматриваемый участок непустой, first < last */
        while (first < last) {
            /* ВНИМАНИЕ! В отличие от более простого (first + last) / 2,
            * этот код устойчив к переполнениям.
            *
            * Если first и last знаковые, возможен код:
            * ((unsigned)first + (unsigned)last) >> 1.
            * Соотвественно в Java: (first + last) >>> 1.
            */
            size_t mid = first + (last - first) / 2;
 
            if (strcmp(key, massiv[mid].Word) <= 0)
                last = mid;
            else
                first = mid + 1;
        }
 
        /* Если условный оператор if (n == 0) и т.д. в начале опущен -
        * значит, тут раскомментировать!
        */
        if (strcmp(massiv[last].Word, key) == 0) {
            /* Искомый элемент найден. last - искомый индекс */
            return last;
        }
        else {
            /* Искомый элемент не найден. Но если вам вдруг надо его
            * вставить со сдвигом, то его место - last.
            */
            return last;
        }
         }

Но при любом слове, возвращает пока номер последнего индекса массива структур.

После хотел вместо возвращения индекса элемента, поставить цикл while (пока имя Name не не изменится, выводить слова с нужным именем из структур с шагом i++), который выводил бы имена художников (могут быть и страны и так далее, так как всё считывается из таблицы).

Немного заморочено, но задание такое)

P.S. В изображении номер элемента начинается с 1, а не с нуля.
Миниатюры
Вывод нескольких значений в бинарном поиске из массива структур  
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Novichock123
1 / 1 / 0
Регистрация: 25.04.2015
Сообщений: 41
04.07.2015, 13:02  [ТС]     Вывод нескольких значений в бинарном поиске из массива структур #2
Вот ещё пример бинарного поиска
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
int binarySearch(char *key)
    {
//massiv инициализирован в классе
        int left = 0, right = Number, mid;
        while (left <= right)
        {
            mid = left + (right - left) / 2;
            if (strcmp(key,massiv[mid].Word)<0) right = mid - 1;
            else if (strcmp(key,massiv[mid].Word)>0) left = mid + 1;
            else return mid;
        }
        return -1;
    }
Возвращает всегда -1. Печально

Добавлено через 5 минут
C++
1
2
3
4
5
6
7
8
    void Search(char *key)
    {
        for (int i = 0; i < Number; i++)
        {
            if (strcmp(key, massiv[i].Word) == 0)
                cout << "Нашёл!" << endl;
        }
    }
Даже при обычном поиске ничего не происходит(
Novichock123
1 / 1 / 0
Регистрация: 25.04.2015
Сообщений: 41
04.07.2015, 13:16  [ТС]     Вывод нескольких значений в бинарном поиске из массива структур #3
C++
1
2
3
4
5
6
7
8
9
10
void Search(char *key)
    {
        for (int i = 0; i < Number - 1; i++)
        {
            cout <<i<<" индекс в массиве: "<< massiv[i].Word << endl;
            cout << "Искомое слово: " << key << endl;
            if (strcmp(key, massiv[i].Word) == 0)
                cout << "Нашёл!" << endl;
        }
    }
Запустил код, на выходе получил это.
Почему-то key не правильное принимает значение.
Если искомое слово написать по-русски, на консоль выводится белиберда.
Если искомое слово написать по-английски, то проблем не будет.

Взял не тот массив, этот массив на изображениях не удалил запятые, на другом массиве их нет.
Миниатюры
Вывод нескольких значений в бинарном поиске из массива структур  
Изображения
 
Novichock123
1 / 1 / 0
Регистрация: 25.04.2015
Сообщений: 41
04.07.2015, 13:29  [ТС]     Вывод нескольких значений в бинарном поиске из массива структур #4
Решил так. Подавал значение через string, после в самой функции преобразовывал до char*. Проблема решилась.
Yandex
Объявления
04.07.2015, 13:29     Вывод нескольких значений в бинарном поиске из массива структур
Ответ Создать тему
Опции темы

Текущее время: 05:43. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru