Search an array of structs

[jamescpp]

I need to search an array of structs, looking for a match of one of the struct items.

The struct is:
struct user_info {
char user [30];
char password[30];
char networkAddr[20];
char day[03];
char systime[15];
};
struct user_info *cache[1000];

I need to search for cache[]->user equals some username that is passed. The array can have anywhere from 0-1000 entries initially, possibly more using realloc when needed.

I'm trying to write a search based on one of my c books, but it's not working. I think it has trouble because in my testing I have only one entry in the array. I'm keeping a counter, user_count, so I always no how many entries should be in it. Here's what I have, can anyone help? I'm getting weird results.

searchCache(char user[30]) //binary search
{
int low, high, mid;
low = 0;
high = user_count - 1;
while (low <= high)
{
mid = (low + high)/2;
if (user < cache[mid]->user)
high = mid - 1;
else if (user > cache[mid]->user)
low = mid + 1;
else
return mid; /* found */
}
return -1;
}

Thanks,
James

 

[Lim]

This algorithm is to find element in sorted array (all elements should be in increasing order or in alphabetic for strings).
It should work fine with one element also.
May be error in other place. Post all code and input/output for your program.

 

[CaKiwi]

Unless performance is critical for this routine, I would just use a linear search, something like this:

searchCache(char user[30]) //linear search
{
int i, j;
for (i=0, j=-1; i<user_count; i++)
{
if (!strcmp(cache->user,user)
{
j = i;
break;
}
}
return j;
}

Hope this helps.

CaKiwi

 

[CaKiwi]

I just read your posts in thread205-142934 so maybe performance is important. In your binary search it seems to me that you need to use strcmp().

searchCache(char user[30]) //binary search
{
int k, low, high, mid;
low = 0;
high = user_count - 1;
while (low <= high)
{
mid = (low + high)/2;
k = strcmp(user, cache->user);
if k==0) return mid;
if (k < 0)
high = mid - 1;
else
low = mid + 1;
}
return -1;
}


Hope this helps.

CaKiwi

 

[jamescpp]

CaKiwi,

Yes, performance is important on this one. I'm now using strcmp, but my results are inconsistent. Sometimes it seems to work, sometimes it doesn't. I actually have a bigger problem that is driving me crazy. Once I fix it, I want to come back to the search problem.

My array of structs start out with no elements, all NULL. I'm trying to write a function that will insert new entries into the array in ascending order. I figured that would be better than sticking it at the end and then sorting. I just can't get it. It's driving me crazy. I'm trying to base it off the Binary Search to find the right position, but I'm missing something(s). Can you help? Here's the code for the current insertUser function. Maybe it would be better to sort?

void insertUser(char user[30], char password[30], char networkAddr[20], char day[03], char systime[15])
{
int low, high, mid, size, result, done, below, above;
int x;

done = 0; above = 0; below = 0; result = 0;
size = strlen(user);
low = 0;
high = user_count;
printf(&quot;Insert User\n&quot;
while (low <= high && done == 0)
{
mid = (low + high)/2;
result = strncmp(user, cache[mid].user, size);
printf(&quot;high=%d mid=%d user=%s cache[mid].user=%s result=%d\n&quot;,high,mid,user,cache[mid].user,result);
if (result == 1)
{
if ((high - low) > 1)
high = mid - 1;
else
done = 1;
//above = mid;
}
else if (result == -1)
{
if ((high - low) > 1)
low = mid +1;
else
done =1;
//below = mid - 1;
}
else
done = 1;
}
printf(&quot;high = %d low=%d\n&quot;,high,low);
if (user_count == 0)
{
strcpy(cache[0].user, user);
strcpy(cache[0].password, password);
strcpy(cache[0].networkAddr, networkAddr);
strcpy(cache[0].day, day);
strcpy(cache[0].systime, systime);
}
else
{
for (x = user_count; x >= below; x--)
{
strcpy(cache[x].user, cache[x - 1].user);
strcpy(cache[x].password, cache[x - 1].password);
strcpy(cache[x].networkAddr, cache[x - 1].networkAddr);
strcpy(cache[x].day, cache[x - 1].day);
strcpy(cache[x].systime, cache[x - 1].systime);
}
strcpy(cache[below].user, user);
strcpy(cache[below].password, password);
strcpy(cache[below].networkAddr, networkAddr);
strcpy(cache[below].day, day);
strcpy(cache[below].systime, systime);
}

for (x = 0; x <= user_count; x++)
{
printf(&quot;%s\n&quot;, cache[x].user);
}
user_count = user_count + 1;
}

Thanks,
James

 

[CaKiwi]

I just noticed that the definition of your array of structures should not have an *.

struct user_info cache[1000];

If you are still having problems, post what you have so far and I will take a look at it.

CaKiwi