С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

23.12.2013, 18:28. Просмотров 554. Ответов 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;
  }
//------------------------------------------------------
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.12.2013, 18:28
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Интерполирующий поиск в массиве структур типа char (C++):

Как найти заданный элемент (типа char) в массиве структур? - C++
Есть массив структур в виде адресной книги с 10 записями с уже введёнными данными (фамилия, имя, улица, номер дома и номер квартиры). ...

Реализовать сортировку и поиск данных в массиве структур типа School - C++
Описать структуру с именем SCHOOL, что содержит следующие поля: NAME - фамилия и имя ученика, GROUP - номер класса, SUBJECT -...

Реализовать сортировку и поиск данных в массиве структур типа School - C++
Описать структуру с именем SCHOOL, что содержит следующие поля: NAME - фамилия и имя ученика, GROUP - номер класса, SUBJECT -...

Реализовать поиск по заданному полю в массиве структур типа "Student" - C++
не могу понять почему не работает цикл void init?? Срабатывает только один раз(то есть могу ввести одно имя,а несколько не получается)...

Интерполирующий поиск в символьных строках - C++
Задание: найти заданный элемент в отсортированном массиве символьных строк Нужно переделать программу с последовательным поиском в...

Найти количество чисел в массиве типа char - C++
задание полностью стоит следующее: в массиве типа char вывести только те слова, которые состоят из латинских букв и вывести количество...

3
ShadowFirst
55 / 48 / 1
Регистрация: 31.10.2013
Сообщений: 161
23.12.2013, 19:31 #2
Возможно ли вообще использовать Интерполирующий поиск с массивом не числовых значений?
Сейчас посмотрю что такое Интерполирующий поиск, но не зная что это могу ответить на ваш вопрос, все что вне зависимости от типа данных является числом.
1
Grovello
12 / 12 / 0
Регистрация: 09.06.2012
Сообщений: 92
23.12.2013, 19:42  [ТС] #3
Цитата Сообщение от ShadowFirst Посмотреть сообщение
Сейчас посмотрю что такое Интерполирующий поиск, но не зная что это могу ответить на ваш вопрос, все что вне зависимости от типа данных является числом.
Да при преобразовании они имеют числовое значение. Но как приспособить алгоритм?
0
ShadowFirst
55 / 48 / 1
Регистрация: 31.10.2013
Сообщений: 161
23.12.2013, 20:26 #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 //Здесь мы найдем нужную букву ключа;
    }
Еще раз предупрежу это только наработки и общие рассуждения, если что то еще надумаю еще напишу.
По идее это нужно повторять все в цикле в зависимости от количества букв в ключе, но конечно нужно учитывать что длины некоторых ключей могут быть меньше чем тот который задан.
1
23.12.2013, 20:26
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.12.2013, 20:26
Привет! Вот еще темы с ответами:

Поиск в массиве структур. - C++
Кто может,пожалуйста,гляньте. Вот мой массив: #include &lt;iostream.h&gt; #include &lt;conio.h&gt; #include &lt;stdio.h&gt; #include &lt;string.h&gt; ...

как поменять слова местами в массиве типа char? - C++
нужно поменять введенный текс в массиве типа char так, чтобы менялись местами два соседних слова.то есть первое со вторым .третье с...

Удалить начальные пробелы в !символьном массиве (типа char) - C++
Дается символьный массив, надо удалить в нём начальные пробелы. Мне нужен хотя бы алгоритм, никак не могу правильно построить цикл... ...

Поиск объекта в классе по строке типа char - C++
Есть такая задача : Описать класс с именем PRICE, содержащий следующие поля: - название товара; - название магазина, в котором...


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

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

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