//快速排序#include <iostream>using namespace std;#define N 10240template< typename T >void sort( T* a, int n ){ if(n<=0) return; if(n==2) { if(a[1] < *a) swap(a[1],*a); return; } swap( *a,a[n>>1] ); T v = *a; T* left = a+1; T* right = a+n-1; while( left<right ){ while( left<right&&*left<v ) ++left; while( *right>v&&right>a ) --right; if( left<right ) swap(*left,*right ); } swap( *a, *right ); sort( a, right-a ); sort( right+1, n-1-(right-a) );}int main(){ int a[N]; for( int i=0; i<N; i++) a[i] = N-i; time_t t = time(NULL); sort(a,N); cout << "Time : " << time(NULL)-t << endl; for( int i=0; i<10; i++) cout << a[i] << ' ' ; cout << endl;}
//二叉树#include <iostream>using namespace std;template< typename T >class BanaryTree{private: struct Node{ T data; Node* left; Node* right; Node():data(T()),left(NULL),right(NULL){ } Node(const T& t):data(t),left(NULL),right(NULL){ } }; // the end of struct Node* root;public: BanaryTree():root(NULL){ } ~BanaryTree(){ clear(root); cout << "~BanaryTree()" << endl; } void push(const T& t ){ Node* p = new Node(t); insert(root, p ); } bool empty(){ return root==NULL; } void travel(){ show(root); cout << endl; } int size(){ return size(root); } bool find( const T& t ){ Node* p = new Node(t); return find(root, p)!=NULL; } void erase( const T& t ){ Node* p = new Node(t); Node*& q = find(root,p); if(!q) return; Node* r = q; insert( q->right, q->left ); q = q->right; delete r; } void update(const T& o, const T& n){ if( !find(o) ) return; erase(o); push(n); }private: Node*& find( Node*& tree,Node*& p ){ if(!tree) return tree; else if(!p) return p; else if( tree->data == p->data ) return tree; else if(p->data < tree->data ) return find( tree->left, p); else return find( tree->right, p); } int size( Node* tree ){ if(!tree) return 0; return size(tree->left) + size(tree->right) + 1; } void show(const Node* tree){ if(!tree) return; show(tree->left); cout << tree->data << ' '; show(tree->right); } void insert( Node*& tree,Node* p){ if(!tree) tree = p; else if(p->data<tree->data) insert(tree->left,p); else insert(tree->right, p); } void clear(Node*& tree){ if( empty() ) return; if( !tree ) return; clear( tree->left ); clear( tree->right ); delete tree; tree = NULL; }}; //the end of classint main(){ BanaryTree<int> bi; for(int i=0; i<10; i++) bi.push(10-i); bi.travel(); cout << "size() : " << bi.size() << endl; cout << "find(5) : " << bi.find(5) << endl; cout << "find(100) : " << bi.find(100) << endl; bi.erase(6); bi.travel(); bi.erase(50); bi.travel(); bi.update(10,11); bi.travel(); bi.update(10,11); bi.travel();}
相关资源：C++实现二叉搜索树（BST），通过控制台能够实现增删改查
