Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Массив строк






Итак, в С/С++ массив строк мы создаем следующим образом

char ** b = new char*[n];

for (int i = 0; i < n; ++i)

b[i] = new char[m];

Передача массива строк в функцию

 

void func(int **b, int count) {

b- массив строк

count – размер

 

 

Билет. Задача поиска.

а0, а1...аn-1 < - найти х - аргумент поиска

0, а1...аn-1} i: (0< =i< n): ai==x

Результаты:

Ǝ i: (0< =i< n): ai==x - успех: i

Для любого (0< =i< n): ai! ==x - неуспех: -1

 

Const n = 100; int a[n]; int x;

Линейный поиск Данный алгоритм является простейшим алгоритмом. Поиск значения функции осуществляется простым сравнением очередного рассматриваемого значения (как правило, поиск происходит слева направо, то есть от меньших значений аргумента к большим) и, если значения совпадают (с той или иной точностью), то поиск считается завершённым.

Int LS(int k, int a[], int x)

{for (int I = 0; i< k; i++)

If (a[i] == x) return I;

Return -1; }

С барьером К массиву добавляется один элемент и в него записывается искомое значение. Тогда при поиске в условии цикла не нужно проверять индекс на количество. Достаточно проверять просто найден элемент или нет - а он по-любому будет найден, так как мы поставили его в конце. На каждом цикле экономится одно сравнение.

Int LsBr(int k, int a[], int x)

{int R = a[k-1];

a[k-1]=x;

int i=0;

while(a[i]! =x) i++;

a[k-1] = R;

if (a[i]==x) return i;

else return -1; }

Бинарный -совокупность нужно упорядочить. Алгоритм двоичного поиска исключает половину еще непроверенных элементов массива после каждого сравнения. Алгоритм определяет местоположение среднего элемента массива и сравнивает его с ключом поиска. Если они равны, то ключ поиска найден и выдается индекс этого элемента. В противном случае задача сокращается на половину элементов массива. Если ключ поиска меньше, чем средний элемент массива, то дальнейший поиск осуществляется в первой половине массива, а если больше, то во второй половине. Если ключ поиска не совпадает со средним элементом выбранного подмассива (части исходного массива), то алгоритм повторно применяется и сокращает область поиска до четверти исходного массива. Поиск продолжается до тех пор, пока ключ поиска не станет равным среднему элементу или пока оставшийся подмассив содержит хотя бы один элемент, не равный ключу поиска.

Int BS1(int k, int a[], int x)

{int l=0, r=k-1;

While (l< =r)

{int m=(l+r)/2;

If (a[m]==x) return m;

If (a[m]> x) r=m-1;

Else l=m+1; }

Return -1; }

 

Int BS2(int k, int a[], int x)

{int l=0, r=k-1;

While(l< r)

{int m=(l+r)/2;

If(a[m]< x) l=m+1;

Else r=m; }

Return a[r]==x? r: -1}

 

Int BS3(int k, int a[], int x)

{int l=0, r=k-1;

While(l< r)

{int m = (l+r+1)/2;

If(a[m]> x) r=m-1;

Else l=m; }

If(a[l]==x) return l;

Else return -1; }

 

LS: O(n); BS: O(log2n)

 

Поиск по ключу

Struct TS

{t1 p1;

t2 p2;

……………….

tk pk; - поле ключа

………………

tn pn;

}

 

TS a[n];

tk x;

a[i].pk==x?

a[i]==x

 

Обобщенный поиск

A[0]a[1]…a[n-1]

F(a[i])=x

 






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.