Looking for a convenient datastructure for checkingexistence

[svar]

Consider a set of possible combinations with order important, e.g.
(1,7,8,-1,6,3,5)
(2,6,1,4,7,-1,5)
......

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?

 

[SamBones]

This really sounds like a homework assignment. Is it?

 

[svar]

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?

 

[SamBones]

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.

 

[svar]

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.

root
|
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---------