Contact US

Log In

Come Join Us!

Are you a
Computer / IT professional?
Join Tek-Tips Forums!
  • Talk With Other Members
  • Be Notified Of Responses
    To Your Posts
  • Keyword Search
  • One-Click Access To Your
    Favorite Forums
  • Automated Signatures
    On Your Posts
  • Best Of All, It's Free!

*Tek-Tips's functionality depends on members receiving e-mail. By joining you are opting in to receive e-mail.

Posting Guidelines

Promoting, selling, recruiting, coursework and thesis posting is forbidden.

Students Click Here

Looking for a convenient datastructure for checkingexistence

Looking for a convenient datastructure for checkingexistence

Looking for a convenient datastructure for checkingexistence

Consider a set of possible combinations with order important, e.g.

The problem is: First, create(that's not the issue here) and store such a combination in an appropriate datastructure
Second, when later on one generates a nw combination, search efficiently to see if the combination is among the ones already found.

Possible solutions:
a) serialize , e.g. (1,7,8,-1,6,3,5)->'1,7,8,-1,6,3,5' and store the string;
use a hash table(struct in C) or array to store the string, sort and keep the array sorted. Search might be ineffective
b) create a tree(but not a binary one), where every node is an array pointer, so that at each stage one has to search an array the dimension of the combination

Anyone have a better suggestion?

RE: Looking for a convenient datastructure for checkingexistence

This really sounds like a homework assignment. Is it?

RE: Looking for a convenient datastructure for checkingexistence

Why would anyone ask for a better suggestion in a hoewwork assignemnent when one has at least 2 ways of doing it and searches a still better one and NO code?

RE: Looking for a convenient datastructure for checkingexistence

Just the way it was worded sounded like a homework assignment. You left out so much detail that it was a pretty abstract question. This is very much the way home work questions are asked.

How much data are you talking about? A couple dozen? Couple hundred? A couple million? Terabytes? You say create and store. does that mean the program needs to access it in memory while running, or can it (should it) be stored on disk and accessed there?

Whether a solution is "better" or not depends a lot on all those details. Glad to help you out, but with the amount of detail you gave, your solutions seem good enough.

I personally like linked lists of malloc'd structures. They're easy to sort and only use the memory required. They're a lot easier to manage than arrays if you don't know how much data you have coming in. But, if you're talking huge amounts of data, they may not be practical.

P.S. You still didn't say if it was homework or not. bigsmile

RE: Looking for a convenient datastructure for checkingexistence

Obviously if the data is too big for the memory, one would use a database. So the data must fit in some datastructure in memory. You need to both search and update fairly quickly, so this is why I was thinking of a tree or a sorted hash table.  i.e.



        0----------------1--------------2------------------------- 3--------------------------N---------------
        |                |              |                          |                          |
   0----1---2        0---1---2     0----1----2            0--1--2--3--            0---1---2---3---4---5        
        |                                                                             |     
  0--1--2---3                                                                0--1--2--3--4---------

Red Flag This Post

Please let us know here why this post is inappropriate. Reasons such as off-topic, duplicates, flames, illegal, vulgar, or students posting their homework.

Red Flag Submitted

Thank you for helping keep Tek-Tips Forums free from inappropriate posts.
The Tek-Tips staff will check this out and take appropriate action.

Reply To This Thread

Posting in the Tek-Tips forums is a member-only feature.

Click Here to join Tek-Tips and talk with other members! Already a Member? Login

Close Box

Join Tek-Tips® Today!

Join your peers on the Internet's largest technical computer professional community.
It's easy to join and it's free.

Here's Why Members Love Tek-Tips Forums:

Register now while it's still free!

Already a member? Close this window and log in.

Join Us             Close