Population

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.

    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. 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

    กก