Data Structure Practice(1)
A.First Edition
This is first 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. void buildHeap(Link<int>**ptr, int size)
2. void heapSort(Link<int>**ptr, int size)
3. void siftDown(Link<int>**ptr, int index, int size)
These functions are used to build Max-heap and heap-sort.The boundary conditions are really painful.
4. void mergeSort(int array[], int size)
5. void doMergeSort(int array[], int temp[], int left, int right)
These are standard merge-sort algorithms. The boundary conditions are really painful.
6. AList<int>* eliminate(AList<int>* l1, AList<int>* l2)
7. AList<int>* eliminate2(AList<int>* l1, AList<int>* l2)
These are two ways to solve a problem proposed by professor during review class: Given two sorted list,
to generate a third list such that it contains all elements of two list that is not common existing
in both list. The first way is quite an efficient way as it solves the problem in one shot and the
new list is also in sorted manner. However, it is more complicated than I expected and cost me a couple
of hours of debugging. It is impossible to figure out during exam. It is quite like merge operation
of merge sort as you always merge two list. But there is a little trick to see that if there are
repeating elements in two lists and when you encounter the common element in both list, you are supposed
move current cursor of both list, then you have to make sure that the next repeated element won't be
selected!
C.Further improvement
กก
#include <iostream>
#include <time.h>
#include "Link.h"
#include "AList.h"
using namespace std;
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);
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);
return 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:
84 58 63 43 68 19 13 12 21 3 26 78 27 60 85 29 77 57 14 59 28 27 56 70 38 2 4 47 46 84 74 6 47 73 13 4 try to reverse 4 13 73 47 6 74 84 46 47 24 38 70 56 27 28 59 14 57 77 29 85 60 27 78 26 3 21 12 13 19 68 43 63 58 84 now try to build heap 3 4 6 12 13 13 14 19 21 24 26 27 27 28 29 38 43 46 47 47 56 57 58 59 60 63 68 70 73 74 77 78 84 84 85 now try to sort the array, before sort 3 4 6 12 13 13 14 19 21 24 26 27 27 28 29 38 43 46 47 47 56 57 58 59 60 63 68 70 73 74 77 78 84 84 85 3 4 6 12 13 13 14 19 21 24 26 27 27 28 29 38 43 46 47 47 56 57 58 59 60 63 68 70 73 74 77 78 84 84 85 l1 is: 3 7 16 18 37 51 53 64 77 79 l2 is: 2 9 19 31 37 40 52 55 59 64 85 91 91 95 97 now l3 is: 3 7 16 18 51 53 77 79 2 9 19 31 40 52 55 59 85 91 91 95 97 Press any key to continue
กก