Population

Data Structure Practice(3)

    A. Third Edition

    This is third edition of my practice of data structure, or whatever you like to call it. It is trivial and I just

    don't want to keep all functions messed up.

    B.The problem

    To write those data structure and  algorithms for practice.

    1. To write a function to print all data of a binary tree by a specific level.

    2. To sort a stack and all you can use is other stacks.กกThe result should be like this: from the

    top of stack to bottom of it, the element is in ascending order.

C.The idea of program
กก

I am just practicing by myself.

    D.The major functions

    1. void print(int array[], int l, int level, int index)

    This is a somewhat variant edition of previous implementation as I use an array to implement tree.

    2. void sortStack(Stack& stack)

    I sort this stack by insert-sort with help of two extra stack. And stack has such a property that you

    have to sort them in ascending and descending orders alternatively. That is once I sort part of stack

    in ascending order, by increment length of stack by one, I have to insert the new element into stack

    by descending order because I am moving data from one stack to another. That is why before return the

    sorted stack I have to do an extra reversing-order job by help of a temporary stack.

    C.Further improvement

    กก

    #include <iostream>

    using namespace std;

    const int Length=20;

    int array[Length];

    //print specific level of a binary tree
    void print(int array[], int l, int level, int index);

    struct Node
    {
    	int data;
    	Node* next;
    };

    class Stack
    {
    private:
    	Node* top;
    public:
    	Stack();
    	~Stack();
    	bool push(int num);
    	bool pop(int& num);
    	bool empty() const;
    	void print() const;
    };
    void doSort(Stack& input, Stack& output, int num, bool ascending);
    void sortStack(Stack& stack);
    void copyStack(Stack& source, Stack& target);

    int main()
    {
    	const int Length=10;
    	/*
    	for (int i=0; i<Length; i++)
    	{
    		array[i]=rand()%100;
    		cout<<"  "<<array[i];
    	}
    	cout<<"\nthe array is like this\n";
    	print(array, 0, 3, 0);
    	*/
    	Stack S;
    //	int num;
    	for (int i=0; i<Length; i++)
    	{
    		S.push(rand()%100);
    	}
    	S.print();
    	cout<<"sorting...\n";
    	sortStack(S);
    	S.print();
    	return 0;
    }

    void copyStack(Stack& source, Stack& target)
    {
    	int num;
    	Stack temp;
    	while (source.pop(num))
    	{
    		temp.push(num);
    	}
    	while (temp.pop(num))
    	{
    		target.push(num);
    	}
    }

    void doSort(Stack& input, Stack& output, int num, bool ascending)
    {
    	int hold;
    	bool inserted=false;
    	while (input.pop(hold))
    	{
    		if (!inserted)
    		{
    			if (ascending&&num>hold||!ascending&&num<hold)
    			{
    				output.push(num);
    				inserted=true;
    			}
    		}
    		output.push(hold);
    	}
    	//not inserted, so place it at the end
    	if (!inserted)
    	{
    		output.push(num);
    	}

    }

    //require stack has at least one element
    void sortStack(Stack& stack)
    {
    	int num;
    	Stack ascend, descend;
    	stack.pop(num);
    	descend.push(num);
    	while (true)
    	{
    		if (stack.pop(num))
    		{
    			doSort(descend, ascend, num, true);
    		}
    		else
    		{
    			copyStack(descend, stack);
    			break;
    		}
    		if (stack.pop(num))
    		{
    			doSort(ascend, descend, num, false);
    		}
    		else
    		{
    			copyStack(ascend, stack);
    			break;
    		}
    	}
    }

    void Stack::print() const
    {
    	Node* temp=top;
    	while (temp!=NULL)
    	{
    		cout<<temp->data<<"  ";
    		temp=temp->next;
    	}
    	cout<<endl;
    }

    bool Stack::empty() const
    {
    	return top==NULL;
    }

    Stack::Stack()
    {
    	top=NULL;
    }

    Stack::~Stack()
    {
    	Node* temp=top;
    	while (top!=NULL)
    	{
    		temp=top->next;
    		delete top;
    		top=temp;
    	}
    }

    bool Stack::push(int num)
    {
    	Node* temp=top;
    	top=new Node;
    	top->data=num;
    	top->next=temp;
    	return true;
    }

    bool Stack::pop(int& num)
    {
    	Node* temp=top;
    	if (top==NULL)
    	{
    		return false;
    	}
    	else
    	{
    		num=top->data;
    		top=top->next;
    		delete temp;//even it is NULL
    		return true;
    	}
    }

    void print(int array[], int l, int level, int index)
    {
    	//index is like the pointer to test NULL
    	if (index==Length)
    	{
    		return;
    	}
    	if (l==level)
    	{
    		cout<<" "<<array[index];
    	}
    	else
    	{
    		print(array, l+1, level, index*2+1);
    		print(array, l+1, level, index*2+2);
    	}
    }

    Here is the result:

     64 62 58 78 24 69 0 34 67 41
    sorting...
    0 24 34 41 58 62 64 67 69 78
    Press any key to continue

    กก