Последовательный поиск в информационном массиве.

↑

▷ Содержание

⇐ ПредыдущаяСтр 4 из 5Следующая ⇒

Цель работы: изучение метода последовательного поиска.

Методические указания.

Последовательный поиск записей предполагает существование между элементами ИМ отношения следования. При поиске происходит просмотр записей в соответствии с алгоритмом. Для последовательного поиска в массиве К={K1,K2, …,Kn} имеется указатель массива I, 1 £ I £ n. Над указателем выполняются операции первоначального присвоения ему значения, увеличения или уменьшения.

Алгоритм последовательного поиска заключается в последовательном вводе N элементов массива и проверке значений их ключей на равенство аргументу поиска z. Элемент массива, для которого это равенство выполняется, является искомым. Соответствующее значение указателя i выводится на печать.

Если ни один элемент массива не имеет значения ключа, равного заданному аргументу поиска то выводится сообщение, что элемент не найден.

В данной работе в качестве ИМ используется последовательность целых чисел, разрядность которых с учетом знакового разряда не должна превышать 5, а количество элементов массива не должно превышать 50. Ключом элемента является само число. Для удачного поиска необходимо, чтобы значение аргумента поиска было равно значению какого-либо элемента из заданного массива чисел.

Приведем пример последовательного поиска в массиве из 6 чисел, проделанного вручную.

Дано: К={-50; 2; 7; 559; -37;10001}, z =7.

I=1             К(1)= -50               -50¹7

I=2             К(2)=2        2¹7

I=3             К(3)= 7                   7=7

Номер искомого элемента равен 3.

I=4             К(4)=-559              559¹7

I=5             К(5)= -37               -37¹7

I=6             К(6)=10001            10001¹7

Поиск окончен. Из заданного массива лишь элемент с номером 3 соответствует заданному аргументу поиска.

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

Если выбирать лишь первый встретившийся элемент, удовлетворяющий заданному аргументу поиска, то минимальное количество сравнений будет равно I, а максимальное n.

Среднее количество сравнений при одинаковой частоте использования элементов .

Если имеются статические данные о частоте использования элементов, то среднее количество сравнений , где di – частота использования i-той записи.

Если с каждым элементом ИМ связать счетчик числа обращений к нему, то в процессе функционирования эту статическую информацию можно использовать для реорганизации файла. Это приведет к существенному увеличению быстродействия, но потребует дополнительного объема памяти для организации программных структур счетчиков, а также для организации пересылок.

Использования дополнительной информации можно легко избежать, применяя схему “самоорганизующегося файла”. Она позволяет довольно хорошо упорядочить записи без вспомогательных полей для счетчиков путем нахождения нужной записи и перемещения ее в начало файла. Таким образом, часто используемые элементы будут располагаться в начале ИМ.

Блок-схема последовательного поиска представлена в Приложении 6.

Порядок выполнения работы.

1. Ознакомится с общими методическими указаниями и с описаниями данной работы. Ознакомиться по литературе с основными понятиями обработки ИМ, алгоритмами поиска и требованиями к ним

2. Изучить блок-схему метода последовательного поиска.

3. Каждому студенту взять из таблицы 2.1. массив из n ключей {K1,K2, …, Kn} и набор значений аргумента поиска Z которые задаются номером варианта.

4. Провести поиск в заданном массиве вручную (см. пример).

5. Провести поиск в заданном массиве на ЭВМ.

Содержание отчета.

1. Краткое изложение целей и задач лабораторной работы, задачи поиска в ИМ и рассматриваемого метода поиска.

2. Блок-схема алгоритма последовательного поиска.

3. Результаты поиска вручную.

4. Результаты поиска на ЭВМ (распечатка с комментариями).

Контрольные вопросы.

1. Что понимается под обработкой ИМ?

2. В чем заключаются задача поиска в ИМ?

3. Что такое удачный и неудачный поиск?

4. Что такое отношение следования?

5. Накладывается ли на ИМ требование упорядочивания между его элементами?

Таблица 2.1

Массив чисел (ключей)

Ключ поиска

К1

К2

К3

К4

К5

К6

К7

К8

К9

К10

К11

К12

К13

К14

2

1.

100

0

-50

6000

731

2

7

35

99543

-59

71

0

10

10

2.

55

1

357

991

-777

30

22

1

71890

-1

0

9

20

22

3.

75

2

43

765

651

2

35

14

54233

-28

17

7

18

35

4.

43

5

244

5935

-321

12

17

5

35555

-41

55

6

25

5

5.

132

7

-22

785

-431

7

23

48

83421

-91

73

0

8

23

6.

88

3

-69

435

893

27

1

3

12495

-12

38

2

17

3

7.

39

1

-144

350

-150

25

28

1

86901

-10

36

4

11

1

8.

34

4

450

734

534

13

91

85

12345

4

67

8

9

14

9.

121

6

752

843

251

6

63

74

19831

-19

21

5

14

63

10.

44

8

92

453

-675

89

33

8

85163

-84

52

0

26

8

11.

62

9

88

354

-897

19

48

93

63517

9

81

1

36

97

12.

651

0

22

278

-451

67

83

0

43273

-86

74

5

43

0

13.

99

5

671

935

431

5

42

78

69543

-97

89

6

96

79

14.

257

8

-23

5000

-978

22

34

8

27825

-3

62

7

63

8

15.

32

9

144

955

-1

68

2

89

93561

9

81

3

78

15

16.

400

7

35

671

-83

7

64

55

95672

-73

45

6

28

7

17.

95

4

68

732

-45

44

87

69

45682

4

97

8

99

4

18.

29

-6

81

-252

834

-6

58

72

10025

-68

93

1

13

51

19.

14

2

19

-86

238

89

75

63

98005

2

61

3

55

44

20.

88

5

84

-71

452

5

56

73

89504

-64

19

8

50

92