tailieunhanh - Thuật toán Algorithms (Phần 19)

Tham khảo tài liệu 'thuật toán algorithms (phần 19)', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | ELEMENTARY SEARCHING METHODS 173 then look through the array sequentially each time a record is sought. The following code shows an implementation of the basic functions using this simple organization and illustrates sone of the conventions that we ll use in implementing searching methods. type node record key info integer end var a array axN of node N integer procedure initialize begin er d function seqseareh v integer x integer integer begin a N l .key v if and then repeat x x f until v a x .key seqsearch x end function integer integer begin N N 1 a N .key v seqinsert N end The code above processes records that have integer keys key and associated information info . As with sorting it will be necessary in many applications to extend the programs to handle complicated records and keys but this won t fundamentally change the algorithms. For example info could be made into a pointer to an arbitrarily complicated record structure. In such a case this field can serve as the unique identifier for the record for use in distinguishing among records with equal keys. The search procedure takes two arguments in this implementation the key value being sought and an index x into the array. The index is included to handle the case where several records have the same key value by successively executing starting at we can successively set to the index of each record with key value v. A sentinel record containing the value being sought is used which ensures that the search will always terminate and therefore involves only one completion test within the inner After the inner loop has finished testing whether the index returned is than N will tell whether the search found the sentinel or a key from the table. This is analogous to our use of a sentinel record containing the smallest or largest key value to simplify 174 CHAPTER 14 the coding of the inner loop of various sorting algorithms. This method takes about N steps for an unsuccessful search every record must be examined to