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.
To write those data structure and algorithms for practice.
I am just practice by myself.
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