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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Grovello
12 / 12 / 0
Регистрация: 09.06.2012
Сообщений: 92
#1

Интерполирующий поиск в массиве структур типа char - C++

23.12.2013, 18:28. Просмотров 503. Ответов 3
Метки нет (Все метки)

Добрый вечер, дано задание сделать Интерполирующий поиск в массиве структур по полю char типа.
Возможно ли вообще использовать Интерполирующий поиск с массивом не числовых значений?
Я реализовал только бинарный поиск, но в интерполирующем необходимо брать модуль от разности значений, а они у меня строковые. Как приспособить алгоритм?
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
 int l = 0;
 int jk;
 int u = or_count - 1;
 string Key = SearchN->Text.c_str();
 bool set = FALSE;
 
  while (l <= u) {
      int m = (l + u) / 2;
      ORDER* q = &mOrder[m];
      CUSTOMER* w = SetCustomer(q->num_name);
 
    string name2 = w->name2;
    const char *c1 = Key.c_str();
    const char *c2 = name2.c_str();
 
    if (strstr(c2,c1))
    {
        jk = m;
        set = TRUE;
        break;
    }
    if (strcmp(c1,c2)>0) l = m + 1;
    if (strcmp(c1,c2)<0) u = m - 1;
  }
//------------------------------------------------------
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.12.2013, 18:28     Интерполирующий поиск в массиве структур типа char
Посмотрите здесь:
C++ Как найти заданный элемент (типа char) в массиве структур?
C++ Реализовать сортировку и поиск данных в массиве структур типа School
C++ Реализовать сортировку и поиск данных в массиве структур типа School
Реализовать поиск по заданному полю в массиве структур типа "Student" C++
C++ Интерполирующий поиск в символьных строках
C++ Найти количество чисел в массиве типа char
Поиск в массиве структур. C++
Удалить начальные пробелы в !символьном массиве (типа char) C++
как поменять слова местами в массиве типа char? C++
Поиск объекта в классе по строке типа char C++
C++ Поиск в отсортированном массиве структур
Добавление в массив типа char * одного элемента типа char C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ShadowFirst
54 / 47 / 1
Регистрация: 31.10.2013
Сообщений: 161
23.12.2013, 19:31     Интерполирующий поиск в массиве структур типа char #2
Возможно ли вообще использовать Интерполирующий поиск с массивом не числовых значений?
Сейчас посмотрю что такое Интерполирующий поиск, но не зная что это могу ответить на ваш вопрос, все что вне зависимости от типа данных является числом.
Grovello
12 / 12 / 0
Регистрация: 09.06.2012
Сообщений: 92
23.12.2013, 19:42  [ТС]     Интерполирующий поиск в массиве структур типа char #3
Цитата Сообщение от ShadowFirst Посмотреть сообщение
Сейчас посмотрю что такое Интерполирующий поиск, но не зная что это могу ответить на ваш вопрос, все что вне зависимости от типа данных является числом.
Да при преобразовании они имеют числовое значение. Но как приспособить алгоритм?
ShadowFirst
54 / 47 / 1
Регистрация: 31.10.2013
Сообщений: 161
23.12.2013, 20:26     Интерполирующий поиск в массиве структур типа char #4
Просто обдумывание этого у меня займет немного времени, но пока могу посоветовать посмотреть информацию по этой ссылке, может тебя быстрее осенит.
http://kvodo.ru/interpoliruyushhiy-poisk.html

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

Вот мы имеем для числа такой поиск:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int interpolationSearch(int *A, int n, int x)
{
    int m; int l=0; int r=n-1;
    while (A[l]<x && A[r]>x)
    {
        m=l+(x-A[l])/(A[r]-A[l])*(r-l);
        if (A[m]<x) l=m+1;
       else if (A[m]>x) r=m-1;
           else return m;
    }
    if (A[l]==x) return l;
    else if (A[r]==x) return r;
        else return -1;
}
Теперь на вход его вместо массива для поиска числа передаем то где у тебя хранятся данные и ключи, какой то массив структур упорядоченный уже по ключам, назовем его Massiv, так же его размер и ключ который нужно найти, а вернуть можно указатель на этот элимент, либо само значение не знаю что там у тебя хранится.
C++
1
const Massiv *interpolationSearch(Massiv *A, int size, string key)
Теперь действуем также как было приведено в том алгоритме:
C++
1
2
3
4
5
6
7
8
    int m; int l=0; int r=n-1;
    while (A[l]->at(0) < key.at(0) && A[r]->at(0) > key.at(0))
    {
        m=l+(x-A[l])/(A[r]-A[l])*(r-l);
        if (A[m]->at(0)<key.at(0)) l=m+1;
       else if (A[m]->at(0)>key.at(0)) r=m-1;
           else //Здесь мы найдем нужную букву ключа;
    }
Еще раз предупрежу это только наработки и общие рассуждения, если что то еще надумаю еще напишу.
По идее это нужно повторять все в цикле в зависимости от количества букв в ключе, но конечно нужно учитывать что длины некоторых ключей могут быть меньше чем тот который задан.
Yandex
Объявления
23.12.2013, 20:26     Интерполирующий поиск в массиве структур типа char
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru