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.

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