manoftoday: Data Structure And Algorithm

Data Structure And Algorithm

fold

Table of Contents

1. data structure and algorithm questions

1. data structure and algorithm questions

2. good websites

stanford cs library

http://cslibrary.stanford.edu/

3. classified

hash table

resolve collision: chain or open address.

http://en.wikipedia.org/wiki/Open_addressing

one example of hashing:
the Bible has only 29,131 distinct words. We'll follow the old lore of using a prime number near that for our hash table size, and the popular multiplier of 31. Our hash function maps a string to a positive integer less than NHASH:

typedef struct node *nodeptr;
typedef struct node {
    char *word;
    int count;
    nodeptr next;
} node;
 
#define NHASH 29989
#define MULT 31
 
nodeptr bin[NHASH];
 
unsigned int hash(char *p)
{
    unsigned int h = 0
    for ( ; *p; p++)
        h = MULT * h + *p
    return h % NHASH
}

Using unsigned integers ensures that h remains positive.

random

http://stackoverflow.com/questions/136474/best-way-to-pick-a-random-subset-from-a-collection

void gensets(int m, int n) 
{
initialize set S to be empty

size = 0;
while size < m do
      t = bigrand() %n
      if t is not in S
              insert t into S
              size ++
end

print the elements of S
}

void genknuth(int m, int n) 
{
    for(int i=0; i<n; i++)
    {
              // select m of remaining n-i
              if( (bigrand() % (n-i)) < m )
              {
                      count << i << "\n";
                      m --;
               } 
     }
}

Random number

RAND_MAX is often 32767(16 bits). If you want to make use of the full 32 bits of mantissa then:
Code:

const unsigned long RAND_MAX_PLUS_1 = RAND_MAX + 1; 
unsigned long bigRand() { 
  return rand() * (RAND_MAX_PLUS_1) + rand(); 
}

the new RAND_MAX will be (RAND_MAX+1)2-1
Code:

const unsigned long BIG_RAND_MAX = RAND_MAX_PLUS_1 * RAND_MAX_PLUS_1 - 1; 
float rand0to1() { 
  return static_cast<float>(bigRand() ) / BIG_RAND_MAX; 
}

(You can also make BIG_RAND_MAX a float or a double instead of an unsigned long).
Note if you want to make use of the precision of double, you could require 4 calls to rand().

int rand_between_a_and_b(int a, int b)
{
  return a+ bigrand() % (b-a+1);
}

void srand (unsigned int seed)
This function establishes seed as the seed for a new series of pseudo-random numbers. If you call rand before a seed has been established with srand, it uses the value 1 as a default seed.

To produce a different pseudo-random series each time your program is run, do srand (time (0)).

heap

like BST, Insertion and deletion are still O(log(n)) , but lookup becomes O(n). It is not possible to find the next-higher node to a given node in 0(log(n)) time or to print out the nodes in sorted order in
O(n) time as in a BST.

the advantage is find max_value in O(1);

4. More questions

misc questions