Search attributes in one structure using the values from another structure

dhanamurthy · #1 (**permalink**) 03-26-2008

Hello Groups

I am trying to find out ways of comparing a value from a 'c' structure to a value in another 'C' structure. the 'C' structure can be a List or liked list as it contains lot many records.

if we loop it in both the structures it is going to consume time.
I am looking for a simple algorithm where i can implement it easily.

For eg)

struct x
{
char empname[20] ;
int empno;
int deptno;
}x1;

struct y
{
char deptname[20];
int deptno;

}y1;

Structure x can be in a list where it contains say 1000 records and similaraly y.
I need to search the deptno of x in deptno of y.

Reply me if you have ideas.

Regards
Dhanamurthy

ramen_noodle · #2 (**permalink**) 03-26-2008

I don't see any way to avoid this being an O(n) operation with linked lists.
Using a chained hash table based on the character string would cut the overhead drastically.

dhanamurthy · #3 (**permalink**) 03-26-2008

I also have another idea as to
put the two files in a List and do a binary search from the input of one of the List. Not sure if there is a performance issue in this way.

Can you please let me know what is chain hashing by an example?
I am not clear on how to avoid the overhead.

Regards
Dhanamurthy

ramen_noodle · #4 (**permalink**) 03-27-2008

The idea of a chained hash table is simple.
Given a key (character array) compute in a 'table' the location to which
the character string hashes using a hash value derived from the key.

Code:

void placenode(void **arr, void *node, char *key, int arrsz) {
int p = 0;
struct typewhatever *datum;

                   while (*key != '\0') {p += (31 + *key); key++;}
                   datum = arr[p % arrsz];
                   append_node(datum,node); 
}

From this one can search the array and 'bucket' for matches based on a restricted
subset of identically hashed values.

HTH.

More UNIX and Linux Forum Topics You Might Find Helpful
Thread	Thread Starter	Forum	Replies	Last Post
Need help in Directory Structure	murtaza	Shell Programming and Scripting	5	03-29-2007 11:14 AM
MV files from one directory structure(multiple level) to other directory structure	srmadab	UNIX for Advanced & Expert Users	4	09-13-2006 04:01 PM
Copying a Directory Structure to a new structure	jhansrod	UNIX for Dummies Questions & Answers	8	07-27-2005 06:24 AM
if then else structure	props	UNIX for Dummies Questions & Answers	4	12-27-2003 06:50 AM
Ram structure	Dorian	HP-UX	1	11-05-2002 09:48 AM

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Display Modes	Rate This Thread
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode	Rate This Thread:


	Powered by