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

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

Восстановить пароль Регистрация
 
Grovello
 Аватар для Grovello
12 / 12 / 0
Регистрация: 09.06.2012
Сообщений: 92
23.12.2013, 18:28     Интерполирующий поиск в массиве структур типа char #1
Добрый вечер, дано задание сделать Интерполирующий поиск в массиве структур по полю 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;
  }
//------------------------------------------------------
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ShadowFirst
54 / 47 / 1
Регистрация: 31.10.2013
Сообщений: 161
23.12.2013, 19:31     Интерполирующий поиск в массиве структур типа char #2
Возможно ли вообще использовать Интерполирующий поиск с массивом не числовых значений?
Сейчас посмотрю что такое Интерполирующий поиск, но не зная что это могу ответить на ваш вопрос, все что вне зависимости от типа данных является числом.
Grovello
 Аватар для 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
Ответ Создать тему
Опции темы

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