Виконання операцій пошуку. Визначення часу пошуку

ЛАБОРАТОРНА РОБОТА № 3

3.1. Тема: Пошук

            3.2. Мета: Одержання навичок та закріплення знань при виконанні операцій пошуку.

3.3. Теми для попередньої роботи

3.3.1. Подання числових масивів.

3.3.2. Подання рядків.

3.3.3. Подання таблиць.

3.3.4. Алгоритми пошуку:

-  лінійний,

-  лінійний з бар’єром,

-  двійковий,

-  прямий пошук рядка,

-  КМП-пошук (алгоритм Кнута, Морриса, Пратта),

-  БМ-пошук (алгоритм Боуера, Мура).

3.4. Індивідуальне завдання

            Розробити та налагодити програму, в якій реалізувати алгоритми пошуку у відповідності до завдання. Визначити час пошуку, зробити висновки.

 Варіант індивідуального завдання  n визначається  так:

n = N mod 12

де N – номер студента у журналі групи.

0)  Двійковий та лінійний пошуки у таблиці по символьному ключу.

1)  Двійковий та лінійний пошуки у числовому масиві по числовому ключу.

2)  Лінійний пошук у числовому масиві з бар’єром та без бар’єра по числовому ключу.

3)  Прямий пошук та КМП-пошук підрядка S1 в рядку S.

4)  Прямий пошук та БМ-пошук підрядка S1 в рядку S.

5)  КМП-пошук та БМ-пошук підрядка S1 в рядку S.

6)  Двійковий та лінійний пошуки у таблиці по числовому ключу.

7)  Лінійний та двійковий пошуки рядка у таблиці.

8)  Лінійний пошук по числовому ключу у масиві та списку.

9)  Двійковий пошук по числовому ключу у масиві та списку.

10)  Лінійний пошук рядка у таблиці за умови подання таблиці масивом та списком.

11)  Двійковий пошук рядка у таблиці за умови подання таблиці масивом та списком.

3.5.  Типове завдання

Реалізувати алгоритм лінійного пошуку ключа в масиві чисел.

3.5.1. Текст програми

#include <iostream.h>

#include <conio.h>

int linearSearch(int[],int,int);

main()

{

 clrscr();

 const int arraySize=100;

 int a[arraySize],searchKey,element;

 for (int x=0;x<arraySize;x++)

     a[x]=2*x;

 cout<<"Введіть ключ пошуку - ціле число: "<<endl;

 cin>>searchKey;

 element=linearSearch(a,searchKey,arraySize);

 if (element!=-1)

   cout<<"Знайдено значення в елементі "<<element<<endl;

 else

   cout<<"Значення не знайдено"<<endl;

  getch();

return 0;

}

 int linearSearch(int array[],int key,int sizeOfArray)

 {

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

     if (array[n]==key)

   return -1;

  }

 return 0;

}

3.5.2. Результат роботи програми

Введіть ключ пошуку - ціле число:   6

Знайдено значення в елементі 3

Введіть ключ пошуку - ціле число:  5

Значення не знайдено