home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / magazine / pcmagazi / 1989 / 06 / srchnif.c < prev    next >
C/C++ Source or Header  |  1988-12-05  |  6KB  |  142 lines
  1. /*
  2.     SRCHNIF.C   Searches file previously created by MAKENIF.EXE
  3.     Copyright (c) 1989 Ziff Communications Co.
  4.     PC Magazine * Ray Duncan
  5.  
  6.     The user is prompted to enter a search key.  The first
  7.     8 characters of the key are used to search TESTFILE.DAT,
  8.     using both the sequential and binary search algorithms.
  9.     The success or failure of the search is reported along
  10.     with the number of records inspected by each method.
  11.  
  12.     Each record in TESTFILE.DAT is RSIZE bytes long.  Bytes 
  13.     0 to (KSIZE-1) of the record are the ASCII key for searches
  14.     by SRCHNIF.C.  Bytes KSIZE to (RSIZE-1) of the record
  15.     are initialized to zero and are not used.  RSIZE and KSIZE
  16.     must be kept synchronized with their definitions in MAKENIF.C.
  17. */
  18.  
  19. #include <stdio.h>
  20. #include <string.h>
  21. #include <stdlib.h>
  22. #include <fcntl.h>
  23. #include <sys\types.h>
  24. #include <sys\stat.h>
  25. #include <io.h>
  26.  
  27. #define RSIZE   64                      /* fixed record size */
  28. #define KSIZE    8                      /* maximum key length */
  29.  
  30. static int inspected;                   /* records inspected counter */
  31.  
  32. main()
  33. {
  34.     int i, j;                           /* some scratch variables */
  35.     int fh;                             /* handle for data file */
  36.     long fsize;                         /* size of file in bytes */
  37.     int frecs;                          /* number of records in file */
  38.     char key[80];                       /* key entered by user */
  39.     char rec[RSIZE];                    /* scratch record buffer */
  40.  
  41.                                         /* open our data file */
  42.     fh = open("TESTFILE.DAT", O_RDONLY | O_BINARY);
  43.  
  44.     if(fh == -1)                        /* terminate if open failed */
  45.     {
  46.         puts("\nCan't find TESTFILE.DAT.");
  47.         exit(1);
  48.     }
  49.  
  50.     fsize = lseek(fh, 0L, SEEK_END);    /* find file size */
  51.     frecs = fsize / RSIZE;              /* calculate number of records */
  52.  
  53.     printf("\nTESTFILE.DAT contains %ld bytes, %d records.", fsize, frecs);
  54.  
  55.     while(1)                    
  56.     {
  57.         printf("\n\nEnter key: ");      /* prompt user and */   
  58.         gets(key);                      /* input record key */
  59.  
  60.         if(key[0] == 0) break;          /* terminate if empty line */
  61.  
  62.         if(strlen(key) > KSIZE) 
  63.             printf("\nWarning:  key truncated to %d characters.", KSIZE);
  64.  
  65.         inspected = 0;                  /* reset record counter */
  66.  
  67.                                         /* perform sequential search */
  68.                                         /* and display results */
  69.         printf("\nSequential search result:  ");
  70.         if((i = seqsearch(fh, key)) == -1) printf("record not found,");
  71.         else printf("record number is %d,", i);
  72.         printf("  %d records inspected.", inspected);
  73.  
  74.         inspected = 0;                  /* reset record counter */
  75.  
  76.                                         /* perform binary search */
  77.                                         /* and display results */
  78.         printf("\nBinary search result:      ");
  79.         if((i = binsearch(fh, key, 0, frecs-1)) == -1) 
  80.             printf("record not found,");
  81.         else printf("record number is %d,", i);
  82.         printf("  %d records inspected.", inspected);
  83.     }
  84.  
  85.     close(fh);                          /* release file handle */
  86. }
  87.  
  88. /*
  89.     Search the file sequentially to match the specified key.
  90.     Called with a file handle and key address.  Returns the record 
  91.     number if match found, or -1 to indicate no match.
  92. */
  93. int seqsearch(int fh, char *kptr)
  94. {
  95.     int i;                              /* scratch variable */
  96.     char fbuff[RSIZE];                  /* file record buffer */
  97.  
  98.     lseek(fh, 0L, SEEK_SET);            /* rewind to start of file */
  99.  
  100.     while(read(fh, fbuff, RSIZE) != 0)  /* do until end of file found */
  101.     {
  102.         inspected++;                    /* count records inspected */
  103.         
  104.         i = strncmp(kptr, fbuff, KSIZE);    /* compare keys */
  105.  
  106.         if(i == 0) return(inspected-1); /* if matched, return record no. */
  107.         else if(i < 0) break;           /* if record absent, end search */
  108.     }
  109.  
  110.     return(-1);                         /* no match, return -1 */
  111. }
  112.  
  113. /*
  114.     Binary search the file to match the specified key.
  115.     Called with a file handle, key address, and the first 
  116.     and last record numbers of the file segment being 
  117.     inspected.  Returns the record number if match found, 
  118.     or -1 to indicate no match.
  119. */
  120. int binsearch(int fh, char *kptr, int left, int right)
  121. {
  122.     int i, j;                           /* scratch variables */
  123.     char fbuff[RSIZE];                  /* file record buffer */
  124.  
  125.     if(left > right) return(-1);        /* end search if record absent */
  126.  
  127.     i = (left + right) / 2;             /* calculate record number */
  128.                                         
  129.     inspected++;                        /* count records inspected */
  130.     lseek(fh, (long) (i * RSIZE), SEEK_SET);
  131.     read(fh, fbuff, RSIZE);             /* read the record */
  132.  
  133.     j = strncmp(kptr, fbuff, KSIZE);    /* compare keys */
  134.  
  135.     if(j == 0) return(i);               /* if matched, return record no. */
  136.  
  137.                                         /* otherwise bisect file, recurse
  138.                                            to inspect next record */
  139.     if(j < 0) binsearch(fh, kptr, left, i-1);
  140.     else      binsearch(fh, kptr, i+1, right);
  141. }
  142.