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