Population

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

    ¡¡

    ¡¡