[lnkForumImage]
TotalShareware - Download Free Software

Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.c

Re: An algorithm questions

Gene

6/1/2011 3:52:00 AM

The advice to use bitmaps for N=200 is good.

I'll point out however, that your method can be made simpler and probably faster by implementing the linked list in the same array you use to indicate membership.

in other words, use something like the following (UNTESTED) cod:

// Sets hold 1 .. SET_SIZE
#define SET_SIZE 200

typedef unsigned char INDEX; // big enough for N < 256

typedef struct {
INDEX next, prev;
} SET_NODE;

// Use 0'th element for list header...
typedef SET_NODE SET[SET_SIZE];

// Initialize each item to a self-circular list. There are other
// possibilities, but this has a nice symmetry, and 0 won't work.
void init(SET set)
{
INDEX i;
for (i = 0; i < SET_SIZE; i++)
set[i].next = set[i].prev = i;
}

// If item is not self-circular, it's in the set.
int is_member(SET set, int item)
{
return set[item].next != item;
}

// Join item's list to head's list.
void add(SET set, int item)
{
if (!is_member(set, item)) {
INDEX head = set[0].next;
set[item].prev = (INDEX)0;
set[item].next = head;
set[0].next = set[head].prev = (INDEX)item;
}
}

// Unlink item from head's list and restore it's self-loop.
void remove(SET set, int item)
{
if (is_member(set, item)) {
set[set[item].next].prev = set[item].prev;
set[set[item].prev].next = set[item].next;
set[item].prev = set[item].next = (INDEX)item;
}
}

// Returns 0 if there is no member, else the last member added.
int get_member(SET set)
{
return set[0].head;
}
1 Answer

Ian Collins

6/1/2011 4:00:00 AM

0

On 06/ 1/11 03:52 PM, Gene wrote:
> The advice to use bitmaps for N=200 is good.

Which advice was that?

The new sociopathic google interface looses all context and starts new
threads, please avoid!

--
Ian Collins