index tree

[ckyuen]

can anyone tell me how to do the following task:
input data:
surname <tab>firstname<tab>phonenumber
i need to construct
a randomized BST for the surname index
a BST for the phonenumber index
and find out the no ,of comparsion used in each of those

for example the record
smith john 98343344
would be found when searching the surname field on the key Smith

so the node in the tree store only the index in the data array of th item , not the actual record or any of the keys, e.g record[17] would be referred to in the index node simple as 17

do i have to sort them first, i think i should use a second array (say a) of item indices,
like this for (i=0;i<N ;i++) a[i] = &record[i];
but i have no idea how to implement it

#include <stdio.h>
#include <stdlib.h>

#define MAXITEM 2000
typedef struct
{
    char *sname;
    char *lname;
    char phone[10];
}elem;


int CompareBySurname(const void* arg1, const void* arg2);
void  usage( char *progname )
/***************************/
{
   fprintf( stderr,
            "Usage: %s \"source-file\"\n",
            progname );

   exit( EXIT_FAILURE );
}

int main (int argc, char *argv[])
{
    FILE *stream;
    elem record[MAXITEM];
    int i = 0, x;
    char temp_sname[100];
    char temp_lname[100];

    if (argc != 2)
        usage (argv[0]);
    if( (stream = fopen( argv[1], "r" )) != NULL )
    {
         while( !feof( stream ) )
         {
             fscanf( stream, "%s\t%s\t%s", temp_sname, temp_lname, record[i].phone );

             if( (record[i].sname = malloc( strlen( temp_sname ) + 1 )) != NULL )
             {
                 strcpy( record[i].sname, temp_sname );
             }

             if( (record[i].lname = malloc( strlen( temp_lname ) + 1 )) != NULL )
             {
                 strcpy( record[i].lname, temp_lname );
             }

             i++;
             if (i > MAXITEM)
             {
              fprintf(stderr,"too many items\n");
              exit (1);
             }
         }
         }
      else
          {
             printf( "Problem opening the file\n" );
           }
           qsort( record,i,sizeof(elem),CompareBySurname );

    for( x = 0; x < i; x++ )
         printf("%s\t%s\t%s\n",record[x].sname, record[x].lname, record[x].phone);
}

int CompareBySurname(const void* arg1, const void* arg2)
{

  elem* param1 = (elem*)arg1;
  elem* param2 = (elem*)arg2;

  return strcmp(param1->sname, param2->sname);
}

[Prelude]

>do i have to sort them first
If you were traversing the array sequentially and inserting records into the tree then this would be a bad idea, you would end up with a worst case scenario for binary trees. However, in this case it would be better to keep the array sorted if possible so that you can use that to your advantage if you need it later.

>i think i should use a second array (say a) of item indices
You could do that if you wanted, or you could use a min/max random number generation and simply save the used indices to an array while inserting in the binary tree:

#include <stdio.h>
#include <stdlib.h>

#define FILLED 1
#define LIMIT  5
#define LEN(x) sizeof (x) / sizeof (x[0])

void treeInsert(int record)
{
    printf("%d Inserted\n", record);
}

int main()
{
    int records[LIMIT] = {18,27,46,79,54};
    int indices[LIMIT] = {0};
    int x = 0;

    while (x < LEN(records))
    {
        int r = (int)(rand() / (double)RAND_MAX * LIMIT);

        if (indices[r] == FILLED)
            continue;

        x++;
        indices[r] = FILLED;

        treeInsert(records[r]);
    }
    
    return 0;
}

This way you get a decently randomized BST.

[ckyuen]

thanks very much, but i could implement your code with my program.....how can i do it...

[ckyuen]

is the following code right, if no , how could i change it, and what about the searching part....

#include <stdio.h>
#include <stdlib.h>
#define FILLED 1
#define LEN(x) sizeof (x) / sizeof (x[0])
#define MAXITEM 2000

typedef struct
{
    char *sname;
    char *lname;
    char phone[10];
}element;


void  usage( char *progname )
/***************************/
{
   fprintf( stderr,
            "Usage: %s \"source-file\"\n",
            progname );

   exit( EXIT_FAILURE );
}

int main (int argc, char *argv[])
{
    FILE *stream;
    element records[MAXITEM];
    int indices[MAXITEM];
    int i = 0, x , y;
    char temp_sname[100];
    char temp_lname[100];

    if (argc != 2)
        usage (argv[0]);
    if( (stream = fopen( argv[1], "r" )) != NULL )
    {
          while( !feof( stream ) )
          {
             if ( fscanf( stream, "%s\t%s\t%s", temp_sname, temp_lname, records[i].phone ) != 3 )
                 break;

             if( (records[i].sname = malloc( strlen( temp_sname ) + 1 )) != NULL )
             {
                 strcpy( records[i].sname, temp_sname );
             }

             if( (records[i].lname = malloc( strlen( temp_lname ) + 1 )) != NULL )
             {
                 strcpy( records[i].lname, temp_lname );
             }

             i++;

             if (i >= MAXITEM)
             {
              fprintf(stderr,"too many items\n");
              exit (1);
             }
           }
           while(y < LEN(records))
             {
                     int r = (int)(rand() / (double)RAND_MAX * MAXITEM);
                      if (indices[r] == FILLED)
                      continue;

                      y++;
                      indices[r] = FILLED;

            }
         }

      else
          {
             printf( "Problem opening the file\n" );
           }

}