Data Structure Practice(2)

A.Second Edition
This is second edition of my practice of data structure, some of them are just a kind of copy of algorithms in 
text. Actually not exact copying, I am trying to understand it by re-write by myself. Of course, for the unfamiliar
ones, I need to refer to text.  
B.The problem
To write those data structure and  algorithms for practice. 
C.The idea of program
 

I am just practice by myself.

D.The major functions
1. BinNode<int>* createTree(int size)
2. void insertElem(BinNode<int>* root, int key)
These two function create a tree and return the root node pointer. The BST class actually wrapped 
the whole operations, and you cannot access the root. All you can do is issue a command and the BST
finish it in a kind of "black box", like "print", "find", "insert". So, I have to write "insert" 
by myself, otherwise you can never get the "root" pointer. In order to check my algorithm, I let 
a BST object to print out the tree by inserting same data into it which makes it an mirror of my tree.
3. void displayTree(BinNode<int>* root)
This function tries to display the tree level by level and it is quite painful! I used an array to 
record number of nodes of each level. But the boundary condition is always a tricky part.
4. int heightTree(BinNode<int>* root)
5. int levelTree(BinNode<int>* root, int level, bool belowLevel)
These functions are supposed to find out the height of tree or number of nodes in a specific level.
The second one also combines the function of sum up total number of nodes below specific level 
(inclusive).
 
C.Further improvement
 
#include <iostream>
#include <iomanip>
#include <time.h>
#include "Link.h"
#include "AList.h"
#include "BST.h"
#include "AQueue.h"
#include "Queue.h"

using namespace std;

class KEComp
{
public:
	static bool lt(int key, int elem) {return key<elem;}
	static bool eq(int key, int elem) {return key==elem;}
	static bool gt(int key, int elem) {return key>elem;}
};

const int Range=100;

const int MaxArraySize=35;

int array[MaxArraySize]={0};

Link<int>* list[MaxArraySize];

void displayList(Link<int>* ptr);

Link<int>* createList(int* array, int size);

Link<int>* reverseList(Link<int>* ptr);

void quksort(Link<int>** ptr, int size);

int partition(Link<int>**ptr, int l, int r);

void displayArray(Link<int>**ptr, int size);

void buildHeap(Link<int>**ptr, int size);

void swap(Link<int>** ptr, int x, int y);

void siftDown(Link<int>**ptr, int index, int size);

void heapSort(Link<int>**ptr, int size);

AList<int>* eliminate(AList<int>* l1, AList<int>* l2);

void getTwoList(AList<int>*& l1, AList<int>*& l2);

void createList(AList<int>*& l, int array[], int size);

void displayList(AList<int>* lst);

void mergeSort(int array[], int size);

bool findVal(AList<int>* l, int key);

AList<int>* eliminate2(AList<int>* l1, AList<int>* l2);

void displayTree(BinNode<int>* root);

BinNode<int>* createTree(int size);

void insertElem(BinNode<int>* root, int key);

int heightTree(BinNode<int>* root);

int numberTree(BinNode<int>* root);

int levelTree(BinNode<int>* root, int level, bool belowLevel=false);

int max(int i, int j);

int main()
{
	srand(time(0));
	/*
	//this is a strange combination, a link list with pointer also resided in
	//an sorted array
	int size=MaxArraySize;
	Link<int>* pHead;
	pHead=createList(array, size);
	displayList(pHead);
	cout<<"try to reverse\n";
	pHead = reverseList(pHead);
	displayList(pHead);
	cout<<"now try to build heap\n";
	buildHeap(list, size);
	heapSort(list, size);
	displayArray(list, size);
	//try quick sort of link list
	cout<<"now try to sort the array, before sort\n";
	displayArray(list, size);
	quksort(list, size);

	displayArray(list, size);

	//this is a problem proposed by professor in review class:
	//given two lists to generate a third list without those common element of two
	//and keep two lists unchanged.
	AList<int>*l1, *l2, *l3;
	createList(l1, array, 10);
	cout<<"l1 is:\n";
	displayList(l1);
	cout<<"l2 is:\n";
	createList(l2, array, 15);
	displayList(l2);
	cout<<"now l3 is:\n";
	l3=eliminate2(l1, l2);//this is second approach
	displayList(l3);
	*/
	BinNode<int>* root;
	int height=0;

	root = createTree(25);
	cout<<"now display my way\n";
	displayTree(root);

	cout<<"tree data\n";
	height=heightTree(root);
	cout<<"the height of tree:"<<height<<endl;
	cout<<"the total number of nodes:"<<numberTree(root)<<endl;
	for (int i=0; i<height; i++)
	{
		cout<<"level "<<i<<" has number of nodes"<<levelTree(root, i)<<endl;
		cout<<"and below level "<<i<<" has number of nods:"<<levelTree(root, i, true)<<endl;
	}

	cout<<endl;

	return 0;
}

int levelTree(BinNode<int>* root, int level, bool belowLevel)
{
	int levelCount[MaxArraySize]={0};
	BinNode<int>* temp;
	int lvl=0, total=0;
	AQueue<BinNode<int>*> Q;
	if (!belowLevel)
	{
		if (root!=NULL&&level==0)
		{
			return 1;
		}
	}
	Q.enqueue(root);
	levelCount[lvl]=1;
	do
	{
		Q.dequeue(temp);
		levelCount[lvl]--;
		if (lvl>=level)
		{
			total++;
		}
		if (temp->left()!=NULL)
		{
			Q.enqueue(temp->left());
			levelCount[lvl+1]++;
		}
		if (temp->right()!=NULL)
		{
			Q.enqueue(temp->right());
			levelCount[lvl+1]++;
		}
		if (levelCount[lvl]==0)
		{
			lvl++;
		}
		if (!belowLevel)
		{
			if (lvl==level)
			{
				return levelCount[lvl];
			}
		}
	}while (Q.length()!=0);
	if (!belowLevel)
	{
		return 0; //as there is no such level
	}
	else
	{
		return total;
	}
}

int numberTree(BinNode<int>* root)
{
	if (root==NULL)
	{
		return 0;
	}
	else
	{
		return 1+ numberTree(root->left())+numberTree(root->right());
	}
}

int max(int i, int j)
{
	return i>j?i:j;
}

int heightTree(BinNode<int>* root)
{
	if (root==NULL)
	{
		return 0;
	}
	else
	{
		return 1+ max(heightTree(root->left()), heightTree(root->right()));
	}
}

void insertElem(BinNode<int>* root, int key)
{
	BinNode<int>* temp;
	if (key<root->val())
	{
		if (root->left()==NULL)
		{
			temp=new BinNodePtr<int>(key);
			root->setLeft(temp);
			return;
		}
		else
		{
			insertElem(root->left(), key);
		}
	}
	else
	{
		if (root->right()==NULL)
		{
			temp=new BinNodePtr<int>(key);
			root->setRight(temp);
			return ;
		}
		else
		{
			insertElem(root->right(), key);
		}
	}
}


BinNode<int>* createTree(int size)
{
	BinNode<int>* root;
	BST<int, int, KEComp, KEComp> tree;

	//make sure the root is not null
	root=new BinNodePtr<int>(rand()%100);
	tree.insert(root->val());
	for (int i=0; i<size-1; i++)
	{		
		int k=rand()%100;
		insertElem(root, k);
		tree.insert(k);
	}
	tree.print();
	return root;
}

void displayTree(BinNode<int>* root)
{
//	const int middle=35;
//	const int width=8;
	AQueue<BinNode<int>*> Q;
	BinNode<int>* current;
	int levelCounter[10]={0};
	int level=0;
//	Q.clear();
	Q.enqueue(root);
	current=root;
	levelCounter[level]++;
//	cout<<setw(middle);
	do
	{
		Q.dequeue(current);
		cout<<current->val()<<"  ";
		levelCounter[level]--;

		if (current->left()!=NULL)
		{
			Q.enqueue(current->left());
			levelCounter[level+1]++;
		}
		if (current->right()!=NULL)
		{
			Q.enqueue(current->right());
			levelCounter[level+1]++;
		}
	


		if (levelCounter[level]==0)
		{
			level++;
			cout<<"\n";
//			cout<<setw(middle-level*width);
		}
	}while (Q.length()!=0);
}


	


AList<int>* eliminate2(AList<int>* l1, AList<int>* l2)
{
	int i;
	AList<int>* l;

	l1->setStart();
	l2->setStart();
	l =new AList<int>(l1->rightLength()+l2->rightLength());
	while (l1->getValue(i))
	{
		if (!findVal(l2, i))
		{
			l->append(i);
		}
		l1->next();
	}

	l2->setStart();
	while (l2->getValue(i))
	{
		if (!findVal(l1, i))
		{
			l->append(i);
		}
		l2->next();
	}
	return l;
}



void createList(AList<int>*& l, int array[], int size)
{
	l=new AList<int>;
	for (int i=0; i<size; i++)
	{
		array[i]=rand()%Range;
	}
	mergeSort(array, size);
	for (i=0; i<size; i++)
	{
		l->append(array[i]);
	}
}



void doMergeSort(int array[], int temp[], int left, int right)
{
	int mid= (left+right)/2;
	int n1, n2;
	if (left==right)
	{
		return;
	}
	doMergeSort(array, temp, left, mid);
	doMergeSort(array, temp, mid+1, right);
	for (int i=left; i<=right; i++)
	{
		temp[i]=array[i];
	}
	n1=left; 
	n2=mid+1;
	for (i=left; i<=right; i++)
	{
		if (n1==mid+1)
		{
			array[i]=temp[n2];
			n2++;
		}
		else
		{
			if (n2==right+1)
			{
				array[i]=temp[n1];
				n1++;
			}
			else
			{
				if (temp[n1]<temp[n2])
				{
					array[i]=temp[n1];
					n1++;
				}
				else
				{
					array[i]=temp[n2];
					n2++;
				}
			}
		}
	}
}

void mergeSort(int array[], int size)
{
	void doMergeSort(int array[], int temp[], int left, int right);
	int temp[MaxArraySize];
	doMergeSort(array, temp, 0, size-1);
}

void displayList(AList<int>* lst)
{
	int i;
	lst->setStart();
	while (lst->getValue(i))
	{
		cout<<i<<"  ";
		lst->next();
	}
	cout<<endl;
}


void getTwoList(AList<int>*& l1, AList<int>*& l2)
{
	l1=new AList<int>;
	l2=new AList<int>;
	for (int i=0; i<10; i++)
	{
		l1->append(rand()%100);
		l2->append(rand()%100);
	}
	//make l1 longer
	for (i=0; i<5; i++)
	{
		l1->append(rand()%100);
	}
}


bool findVal(AList<int>* l, int key)
{
	int i;
	l->setStart();
	while (l->getValue(i))
	{
		if (key==i)
		{
			return true;
		}
		else
		{
			if (key<i)
			{
				return false;
			}
		}
		l->next();
	}
	return false;
}


int min(int i, int j)
{
	if (i<j)
	{
		return i;
	}
	else
	{
		return j;
	}
}

//the idea is quite similar to merge operation of merge sort.
AList<int>* eliminate(AList<int>* l1, AList<int>* l2)
{

	int min(int i, int j);

	bool leftDone=false;
	int i, j, same;

	//assume both list has at least one element
	l1->setStart();
	l2->setStart();

	AList<int>* l =new AList<int>(l1->rightLength()+l2->rightLength());
	l->setStart();

	l1->getValue(i);
	l2->getValue(j);
	while (true)
	{	
		//if they are not equal, so it should be added, 
		//but the only smaller one we are sure, as the smaller 
		//has no more chance to get equal from other list.
		//And we push the list with the smaller one to 
		//get more value. 
		if (i!=j)
		{
			if (i<j)
			{
				if (i!=same)
				{
					l->append(i);
				}
				l1->next();//keep left moving
				//also push the ball going always from the smaller side
				if (!l1->getValue(i))
				{
					leftDone=true;//book keeping which side makes the while loop end
					break;
				}
			
			}
			else
			{
				if (j!=same)
				{
					l->append(j);
				}
				l2->next();//keep right moving
				if (!l2->getValue(j))
				{
					leftDone=false; //make sure it is false
					break;				
				}
				
			}
		}
		else
		{
			same=i;//same just to record the last same number
			//in case they get same value, we know, we have to push both side going
			l1->next();
			l2->next();
			if (!l1->getValue(i))
			{
				leftDone=true;//book keeping which side makes the while loop end
				break;
			}
			if (!l2->getValue(j))
			{
				leftDone=false;
				break;
			}
		
		}
	}
	if (leftDone)
	{
		if (i!=j)//this means last time, we have not insert j.
		{
			l->append(j);			
		}
		l2->next();
		while (l2->getValue(j))
		{
			if (i!=j)//this means last time, we have not insert j.
			{
				l->append(j);			
			}
			l2->next();
		}
	}
	else
	{
		if (i!=j)//this means last time, we have not insert i.
		{
			l->append(i);			
		}
		l1->next();//we need move even i==j
		while (l1->getValue(i))
		{
			if (i!=j)//this means last time, we have not insert j.
			{
				l->append(i);			
			}
			l1->next();
		}
	}
	return l;
}


void heapSort(Link<int>**ptr, int size)
{
	for (int i=size-1; i>0; i--)
	{
		swap(ptr, i, 0);
		siftDown(ptr, 0, i);
	}
}


void buildHeap(Link<int>**ptr, int size)
{
	for (int i=size/2-1; i>=0; i--)
	{
		siftDown(ptr, i, size);
	}
}

void siftDown(Link<int>**ptr, int index, int size)
{
	int l, r;
	l=index*2+1;
	r=index*2+2;
	if (size==1)
	{
		return;
	}
	if (r<size)
	{
		if (ptr[l]->element<ptr[r]->element)
		{
			l=r;	
		}
	}
	if (ptr[index]->element<ptr[l]->element)
	{
		swap(ptr, index, l);
		if (l<=size/2-1)
		{
			siftDown(ptr, l, size);
		}
	}

}

void displayArray(Link<int>**ptr, int size)
{
	for (int i=0; i<size; i++)
	{
		cout<<ptr[i]->element<<"  ";
	}
	cout<<endl;
}

void doQukSort(Link<int>** ptr, int l, int r)
{
	if (r>l)
	{
		int mid;
		mid=partition(ptr, l, r);
		doQukSort(ptr, 0, mid-1);
		doQukSort(ptr, mid+1, r);
	}
}

void quksort(Link<int>** ptr, int size)
{
	void doQukSort(Link<int>** ptr, int l, int r);

	doQukSort(ptr, 0, size-1);
}

void swap(Link<int>** ptr, int x, int y)
{
	Link<int>* temp=ptr[x];
	ptr[x]=ptr[y]; 
	ptr[y]=temp;
}

int partition(Link<int>** ptr, int start, int end)
{
	
	Link<int>* pivot=ptr[end];
	int l=-1, r=end-1;
	while (r>l)
	{
		do 
		{
			l++;
		} while (l<end&&ptr[l]->element<=pivot->element);
		do 
		{
			r--;
		} while (r>=0&&ptr[r]->element>=pivot->element);
		swap(ptr, l, r);
	}
	swap(ptr, l, r);
	swap(ptr, l, end);
	return l;
}



void displayList(Link<int>* ptr)
{
	Link<int>* temp=ptr;
	while (temp!=NULL)
	{
		cout<<temp->element<<"  ";
		temp=temp->next;
	}
	cout<<endl;
}

Link<int>* reverseList(Link<int>* ptr)
{
	Link<int>* head,* pre=NULL, *nxt;
	if (ptr==NULL)
	{
		cout<<"empty list!\n";
		return NULL;
	}
	head=ptr->next;
	if (head==NULL)
	{
		return ptr;
	}
	nxt=head->next;
	pre=ptr;
	head->next=pre;
	pre->next=NULL;

	while (nxt!=NULL)
	{
		pre=head;
		head=nxt;
		nxt=nxt->next;
		head->next=pre;
	}
	return head;
}

Link<int>* createList(int* array, int size)
{
	Link<int>* head, *ptr, *temp;
	if (size<=0)
	{
		return NULL;
	}

	for (int i=0; i<size; i++)
	{
		array[i]=rand()%100;
		ptr =new Link<int>(array[i]);
		if (i==0)
		{
			head=ptr;
		}
		else
		{
			temp->next=ptr;		
		}
		temp = ptr;
		list[i]=ptr;
	}
	return head;
}


Here is the result:
        0
      3
        3
    8
        10
          11
      13
            13
          16
            27
        29
  31
35
    48
          50
        52
          52
      58
        62
          73
  77
      82
    90
      94
        94
now display my way
35
31  77
8  48  90
3  13  58  82  94
0  3  10  29  52  62  94
11  16  50  52  73
13  27
tree data
the height of tree:7
the total number of nodes:25
level 0 has number of nodes1
and below level 0 has number of nods:25
level 1 has number of nodes2
and below level 1 has number of nods:24
level 2 has number of nodes3
and below level 2 has number of nods:22
level 3 has number of nodes5
and below level 3 has number of nods:19
level 4 has number of nodes7
and below level 4 has number of nods:14
level 5 has number of nodes5
and below level 5 has number of nods:7
level 6 has number of nodes2
and below level 6 has number of nods:2

Press any key to continue
 

 



	


                                 back.gif (341 bytes)       up.gif (335 bytes)         next.gif (337 bytes)