Linear search demo

This program demonstrates the linear search algorithm in BB4W.

The first job is to count the number of records in the input file.  Once we know this, we can set up an array of records to hold the data.  Once we have this array dimensioned we can read the data in from the file.

Once the array is populated with data, we ask the user to enter a search term.  The algorithm searches through the array linearly until the index to the required record is either found or the end of the array is reached.  We can then do useful things with this index number, for example: to display the distance from the sun.

The input file.

The output of the program.


     REM demonstrates
     REM (a) setting up a record structure
     REM (b) reading from a file
     REM (c) performing a linear search

     
INSTALL @lib$+"stringlib" : REM used by FN_removeCRLF()

     
file$ = @dir$+"planetsInput.txt"

     NumRecords% = FN_countRecordsInFile( file$  )


     REM now we know how many records there are
     REM we can set up a record structure
     
DIM Planet{(NumRecords%-1) name$, distance }

     PROC_readDataIn( file$, Planet{()}, NumRecords% )

     REM main loop
     
REPEAT
       INPUT 
"Enter planet name : " myplanet$
       index% = FN_search( Planet{()}, NumRecords%, myplanet$ )
       IF index%<>-999 THEN
         PRINT 
"Planet "Planet{(index%)}.name$
         PRINT "Distance from sun : " STR$( Planet{(index%)}.distance/1000 )" thousand km"
         PRINT "---------------------------------------------------"''
       ELSE
         PRINT 
"No record found"''
       ENDIF
     UNTIL FALSE


     STOP


     
DEFFN_countRecordsInFile( filepath$ )
     REM opens a file for reading and counts the number of records in the file
     
LOCAL file%
     LOCAL mycount%
     LOCAL dummy$
     file% = OPENIN( filepath$ )
     WHILE (NOT(EOF#file%))
       REM I know that each record has two fields
       
INPUT#file%, dummy$, dummy$
       mycount% += 1 : REM count one record
     
ENDWHILE
     
REM REMEMBER to close the file once we are done
     
CLOSE#file%
     = mycount%



     DEFPROC_readDataIn( filepath$, this{()}, n%)
     REM reads data from the file into a the data structure
     
LOCAL i%
     LOCAL file%
     LOCAL name$, distance$
     file% = OPENIN( filepath$ )
     FOR i% = 0 TO n% -1
       INPUT#file%, name$, distance$
       REM remove the Carriage returns/Linefeeds
       REM and store in the structure
       
this{(i%)}.name$ = FN_removeCRLF(name$)
       this{(i%)}.distance = VALFN_removeCRLF(distance$))
     NEXT
     
REM REMEMBER to close the file once we are done
     
CLOSE#file%
     ENDPROC



     
DEFFN_search( this{()}, n%, key$ )
     REM performs a linear search for the key in the
     REM array of records
     
LOCAL found%
     LOCAL i%
     LOCAL a%  : a% = -999 : REM assume record wont be found
     
WHILE NOT(found%) AND i% < n%
       REM is the current record the one with matching key?
       
IF this{(i%)}.name$ = key$ THEN
         
REM yes, then found it!
         
found% = TRUE
         
a% = i% : REM return the index for the found record
       
ELSE
         
REM no
         
i% += 1 : REM look for the next one
       
ENDIF
     ENDWHILE
     
= a%



     DEFFN_removeCRLF(t$)
     REM returns the text passed with carriage returns and line feeds removed
     
LOCAL dummy%
     dummy% = FN_findreplace(t$,CHR$(13),"",0)
     dummy% = FN_findreplace(t$,CHR$(10),"",0)
     = t$



#linearSearch
#algorithms
#computing