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