Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Последовательный поиск в информационном массиве.
Цель работы: изучение метода последовательного поиска. Методические указания. Последовательный поиск записей предполагает существование между элементами ИМ отношения следования. При поиске происходит просмотр записей в соответствии с алгоритмом. Для последовательного поиска в массиве К={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 | 1 | 2 | |||||||||||||||||||||||||
1. | 100 | 0 | -50 | 6000 | 731 | 2 | 7 | 35 | 99543 | -59 | 71 | 0 | 21 | 10 | 7 | 10 | |||||||||||||||||||||||||
2. | 55 | 1 | 357 | 991 | -777 | 30 | 22 | 1 | 71890 | -1 | 0 | 9 | -3 | 20 | 1 | 22 | |||||||||||||||||||||||||
3. | 75 | 2 | 43 | 765 | 651 | 2 | 35 | 14 | 54233 | -28 | 17 | 7 | 19 | 18 | 2 | 35 | |||||||||||||||||||||||||
4. | 43 | 5 | 244 | 5935 | -321 | 12 | 17 | 5 | 35555 | -41 | 55 | 6 | 13 | 25 | 17 | 5 | |||||||||||||||||||||||||
5. | 132 | 7 | -22 | 785 | -431 | 7 | 23 | 48 | 83421 | -91 | 73 | 0 | 15 | 8 | 81 | 23 | |||||||||||||||||||||||||
6. | 88 | 3 | -69 | 435 | 893 | 27 | 1 | 3 | 12495 | -12 | 38 | 2 | 20 | 17 | 20 | 3 | |||||||||||||||||||||||||
7. | 39 | 1 | -144 | 350 | -150 | 25 | 28 | 1 | 86901 | -10 | 36 | 4 | 1 | 11 | 23 | 1 | |||||||||||||||||||||||||
8. | 34 | 4 | 450 | 734 | 534 | 13 | 91 | 85 | 12345 | 4 | 67 | 8 | 32 | 9 | 4 | 14 | |||||||||||||||||||||||||
9. | 121 | 6 | 752 | 843 | 251 | 6 | 63 | 74 | 19831 | -19 | 21 | 5 | -5 | 14 | 6 | 63 | |||||||||||||||||||||||||
10. | 44 | 8 | 92 | 453 | -675 | 89 | 33 | 8 | 85163 | -84 | 52 | 0 | -93 | 26 | 52 | 8 | |||||||||||||||||||||||||
11. | 62 | 9 | 88 | 354 | -897 | 19 | 48 | 93 | 63517 | 9 | 81 | 1 | -67 | 36 | 48 | 97 | |||||||||||||||||||||||||
12. | 651 | 0 | 22 | 278 | -451 | 67 | 83 | 0 | 43273 | -86 | 74 | 5 | -87 | 43 | 83 | 0 | |||||||||||||||||||||||||
13. | 99 | 5 | 671 | 935 | 431 | 5 | 42 | 78 | 69543 | -97 | 89 | 6 | 48 | 96 | 42 | 79 | |||||||||||||||||||||||||
14. | 257 | 8 | -23 | 5000 | -978 | 22 | 34 | 8 | 27825 | -3 | 62 | 7 | 85 | 63 | 22 | 8 | |||||||||||||||||||||||||
15. | 32 | 9 | 144 | 955 | -1 | 68 | 2 | 89 | 93561 | 9 | 81 | 3 | 22 | 78 | 89 | 15 | |||||||||||||||||||||||||
16. | 400 | 7 | 35 | 671 | -83 | 7 | 64 | 55 | 95672 | -73 | 45 | 6 | 97 | 28 | 64 | 7 | |||||||||||||||||||||||||
17. | 95 | 4 | 68 | 732 | -45 | 44 | 87 | 69 | 45682 | 4 | 97 | 8 | 76 | 99 | 87 | 4 | |||||||||||||||||||||||||
18. | 29 | -6 | 81 | -252 | 834 | -6 | 58 | 72 | 10025 | -68 | 93 | 1 | -87 | 13 | 58 | 51 | |||||||||||||||||||||||||
19. | 14 | 2 | 19 | -86 | 238 | 89 | 75 | 63 | 98005 | 2 | 61 | 3 | -94 | 55 | 19 | 44 | |||||||||||||||||||||||||
20. | 88 | 5 | 84 | -71 | 452 | 5 | 56 | 73 | 89504 | -64 | 19 | 8 | -36 | 50 | 73 | 92 | |||||||||||||||||||||||||
6. Что такое ключ записи и аргумент поиска?
7. Каково возможное минимальное и максимальное число сравнений при последовательном поиске?
8. Что такое “самоорганизующийся файл”?
9. Чем различаются первичные и вторичные ключи?
Лабораторная работа № 6.
| Поделиться: |
Читайте также:
Последнее изменение этой страницы: 2021-01-08; просмотров: 128; Нарушение авторского права страницы; Мы поможем в написании вашей работы!
infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.117.227.194 (0.117 с.)