Issues implementing a skip list (so far just insertion)

[Judicator01]

I'm having trouble implementing a skip list. It's supposed to store rectangles and order them by a key which is a character array, using strcmp to order them correctly.

Obviously its screwed up somewhere but I'm not sure what's wrong. I step through and it breaks on the line right after the first if statement in the insert function, giving me an access violation.

It tells me....

Unhandled exception at 0x00414630 in SkipList.exe: 0xC0000005: Access violation reading location 0xfdfdfe15.

I look at the forward array in the debugger while stepping through the code. Here

		if(pos->forward[i] == NIL || strcmp( pos->forward[i]->key, myKey) > 0){//if the node to the right is NIL or is bigger, add a pointer and go down a level
			inserted->forward[i] = pos->forward[i]; //the node being inserted points to the node pos pointed to
			pos->forward[i] = inserted; //the position prior to that node now points to it
			i--;

And for some reason forward[i] is filled with garbage, even though I think it should always point to something, since the head's forward array initially points to NIL, and everything after that should be inserted before NIL.

This is what I have so far:

int randomH(){
	int h=1;//h must be at least 1
	while((rand() % 2) == 1){//with a coin flip, increase h
		h++;
	}
	return h;
}

node::node(char *myKey, int myX, int myY, int myH, int myW){
	key = myKey;
	x=myX;
	y=myY;
	h=myH;
	w=myW;

	height = randomH();
	forward = new node*[height];
}

skiplist::skiplist(){
	NIL = new node("THE_END",-1,-1,-1,-1);
	head = new node("THE_HEAD",-1,-1,-1,-1);
	listheight = head->height;
	for(int i=0;i<listheight;i++){
		head->forward[i] = NIL;
	}
}

void skiplist::insert(char *myKey, int myX, int myY, int myH, int myW){
	node *inserted = new node(myKey, myX, myY, myH, myW);//make the node to insert

	int i = inserted->height - 1;//track the height (start at the top)
	node *pos = head;//track the position (start at the head)

	while(i > -1){//until we try to drop "below" the tree
		if(pos->forward[i] == NIL || strcmp( pos->forward[i]->key, myKey) > 0){//if the node to the right is NIL or is bigger, add a pointer and go down a level
			inserted->forward[i] = pos->forward[i]; //the node being inserted points to the node pos pointed to
			pos->forward[i] = inserted; //the position prior to that node now points to it
			i--;
		}
		else if( strcmp( pos->forward[i]->key, myKey) < 0){//if the node to the right is smaller, go forward one
			pos = pos->forward[i];
		}
		else{//otherwise they're equal
			inserted->forward[i] = pos->forward[i]; //the node being inserted points to the node pos pointed to
			pos->forward[i] = inserted; //the position prior to that node now points to it			
		}
	}

	
	if(inserted->height > listheight){//and if the new node has a height in excess of the existing structure....
		node **tempForward = new node*[inserted->height]; //make a new array
		tempForward = head->forward; //store the existing head's forward array in it

		delete head->forward;//delete the old one
		head->forward = new node*[inserted->height];//remake it
		head->forward = tempForward;//copy old data to the new one

		for(int k = inserted->height - 1; k > listheight - 1; k--){
			head->forward[k] = inserted;
		}
	}

}

[Hammurabi]

In the skiplist constructor, do you really want head to have a random height that could just be 1? Doesn't that kind of defeat the purpose of a skip list? Maybe fix the head at a height of 4 and pick random heights for the other nodes like so:

int randomH(){
	// Note the distribution of these numbers (eight 1's, four 2's, two 3's, one 4)
	const int n[] = { 1,2,1,2,1,3,1,4,1,3,1,2,1,2,1 };
	return n[ rand() % (sizeof(n)/sizeof(*n)) ];
}

Make another node constructor that takes two params (or one if you don't need the string), where the numeric parameter is the requested height:

NIL  = new node( "NIL",  0 ); // doesn't need any pointers
head = new node( "HEAD", 4 ); // fixed at 4 

Also, please try to keep your line lengths reasonable. You can put comments before the line instead of at the end, for instance.