ЗНАЙ ИНТУИТ, Лекция, Търсене
Последователно търсене
За последователно търсене в таблицата приемаме, че има указател, чиято стойност принадлежи на сегмента или, вероятно,. На този указател са разрешени само следните операции; първоначално му присвоява стойността 1 или (или, ако е по-удобно, 0 или, увеличава и/или намалява с един и го сравнява с 0, 1 или. С такива конвенции най-очевидният алгоритъм за намиране на първото появяване на дадено име в таблицата е Алгоритъм 13.1. Тук, както и при всички други алгоритми за търсене, описани в тази лекция, приемаме, че алгоритъмът спира незабавно след намиране или установяване, че таблицата не съдържа.
Алгоритъм 13.1. Последователно търсене
намерено: показва, че не е намерено: не е включено в
Нека разгледаме някои аспекти на ефективността на последователното търсене, започвайки със стандартни техники за програмиране. В програма, изградена като един цикъл, като Алгоритъм 13.1, всяко значително ускорение трябва да се дължи на подобрения в кода в цикъла. За да видите какви операции се извършват в цикъла, е необходимо да пренапишете алгоритъм 13.1 във форма, близка до машинния език:
За една итерация се изпълняват до четири инструкции: две сравнения, едно увеличение и едно прехвърляне.
За да се ускори вътрешният цикъл, често срещан трик е добавянето на специални редове към таблицата, които правят незадължително изричното проверяване дали указателят е достигнал границите на таблицата. Това може да се направи в алгоритъм 13.1. Ако преди търсене добавим желаното име в края на таблицата, тогава цикълът винаги ще завършва с намиране на запис; по този начин не е нужно да правим проверката всеки път в цикъла. В края на цикъла проверете условието n "style =" display: inline; ">, изпълнява се само веднъж, казва дали намереният запис е истински или специален запис в таблицата. Това е показано в алгоритъм 13.2.
Алгоритъм 13.2. Подобрено последователно търсене
Подобрението на алгоритъм 13.1 ще бъде най-очевидно, ако пренапишем алгоритъм 13.2 в същата машинна нотация, използвана преди: