首先先介绍排序:

1,大家都知道的冒泡排序:

#include #include using namespace std; template void swap(type x[],int,int); template void BubbleSort(type x[],int); int main() { srand(time(0)); const int n=10; int x[n]; for(int i=0;i x[ i]=rand()%99; for(int i=0;i cout<<" "< BubbleSort(x,n); cout<<"\nAfter Sort:"< for(int i=0;i cout<<" "<; system("pause"); return 0; } template void BubbleSort(type x[],int n) { for(int i=n-1;i>=0;i--) { int flag=0; for(int j=0;j if(x[ j]>x[ j+1]) { swap(x,j,j+1); flag=1; } if(flag==0) return; } } template void swap(type x[],int n,int m) { int temp=x[n]; x[n]=x[m]; x[m]=temp; }

2,简单的选择排序

#include #include using namespace std; template void swap(type x[],int,int); template void SlectSort(type x[],int); int main() { srand(time(0)); const int n=10; int x[n]; for(int i=0;i x[ i]=rand()%99; for(int i=0;i cout<<" "< SlectSort(x,n); cout<<"\nAfter Sort:"< for(int i=0;i cout<<" "< system("pause"); return 0; } template void swap(type x[],int n,int m) { int temp=x[n]; x[n]=x[m]; x[m]=temp; } template void SlectSort(type x[],int n) { for(int i=0;i { for(int j=i+1;j if(x[ j] swap(x,i,j); } }

3,插入排序

#include<iostream> #include<cstdlib> using namespace std; template<class type> void swap(type x[],int,int); template<class type> void InsertSort(type x[],int); int main() { srand(time(0)); const int n=10; int x[n]; for(int i=0;i<n;i++) x[ i]=rand()%99; for(int i=0;i<n;i++) cout<<" "<<x[ i]; InsertSort(x,n); cout<<"\nAfter Sort:"<<endl; for(int i=0;i<n;i++) cout<<" "<<x[ i]; system("pause"); return 0; } template<class type> void swap(type x[],int n,int m) { int temp=x[n]; x[n]=x[m]; x[m]=temp; } template<class type> void InsertSort(type x[],int n) { for(int i=1;i<n;i++) for(int j=i;j>0;j--) if(x[ j]<x[ j-1]) swap(x,j,j-1); }

4:希尔排序

#include<iostream> #include<cstdlib> using namespace std; template<class type> void swap(type x[],int,int); template<class type> void ShellSort(type x[],int); template<class type> void ShellSorthelper(type x[],int,int); int main() { srand(time(0)); const int n=10; int x[n]; for(int i=0;i<n;i++) x[ i]=rand()%99; for(int i=0;i<n;i++) cout<<" "<<x[ i]; ShellSort(x,n); cout<<"\nAfter Sort:"<<endl; for(int i=0;i<n;i++) cout<<" "<<x[ i]; system("pause"); return 0; } template<class type> void swap(type x[],int n,int m) { int temp=x[n]; x[n]=x[m]; x[m]=temp; } template<class type> void ShellSort(type x[],int n) { for(int i=n/2;i>=1;i/=2) for(int j=0;j<i;j++) ShellSorthelper(&x[ j],i,n-j); } template<class type> void ShellSorthelper(type x[],int len,int n) { for(int i=len;i<n;i+=len) for(int j=i;j>0;j-=len) if(x[ j]<x[ j-len]) swap(x,j,j-len); }

5,快速排序

#include<iostream> #include<cstdlib> using namespace std; template<class type> void QuicklySort(type x[],int n); template<class type> void QuicklySorthelper(type x[],int,int); template<class type> void swap(type x[],int,int); int main() { srand(time(0)); const int n=10; int x[ n]; for(int i=0;i<n;i++) x[ i]=rand()%99; for(int i=0;i<n;i++) cout<<" "<<x[ i]; QuicklySort(x,n); cout<<"\nAfter Sort:"<<endl; for(int j=0;j<n;j++) cout<<" "<<x[ j]; system("pause"); return 0; } template<class type> void QuicklySort(type x[],int n) { QuicklySorthelper(x,0,n-1); } template<class type> void QuicklySorthelper(type x[],int l,int r) { if(r>l) { swap(x,l,(l+r)/2);//尽量找出好的轴值; int i=l;int j=r+1;type pivot=x[l]; while(i<j) { while(x[--j]>pivot && i<j); if(i<j) swap(x,i,j); while(x[++i]<pivot && i<j); if(i<j) swap(x,i,j); } x[ i]=pivot; QuicklySorthelper(x,l,i-1); QuicklySorthelper(x,i+1,r); } } template<class type> void swap(type x[],int n,int m) { type temp=x[n]; x[n]=x[m]; x[m]=temp; }

6,归并排序(2路)

#include<iostream> #include<cstdlib> using namespace std; template<class type> void swap(type x[],int,int); template<class type> void MegicSort(type x[],int); template<class type> void MegicSorthelper(type x[],type y[],int,int); template<class type> void MegicSortPass(type x[],type y[],int,int,int); int main() { srand(time(0)); const int n=10; int x[n]; for(int i=0;i<n;i++) x[ i]=rand()%99; for(int i=0;i<n;i++) cout<<" "<<x[ i]; MegicSort(x,n); cout<<"\nAfter Sort:"<<endl; for(int i=0;i<n;i++) cout<<" "<<x[ i]; system("pause"); return 0; } template<class type> void swap(type x[],int m,int n) { type temp=x[m]; x[m]=x[n]; x[n]=temp; } template<class type> void MegicSort(type x[],int n) { type *y=new type[n]; int len=1; while(len<n) { MegicSorthelper(x,y,len,n);len*=2; MegicSorthelper(y,x,len,n);len*=2; } delete []y; } template<class type> void MegicSorthelper(type x[],type y[],int len,int n) { int i; for(i=0;i+2*len<n;i+=2*len) MegicSortPass(x,y,i,i+len,i+2*len); if(i+len<n) MegicSortPass(x,y,i,i+len,n); else for(;i<n;i++) y[ i]=x[ i]; } template<class type> void MegicSortPass(type x[],type y[],int l,int m,int n) { int i=l,j=m,k=l; for(;i<m && j<n;k++) { if(x[ i]>x[ j]) y[ k]=x[ j++]; else y[ k]=x[ i++]; } for(;i<m;i++) y[ k++]=x[ i]; for(;j<n;j++) y[ k++]=x[ j]; }

7,堆排序(不用Heap类)

#include<iostream> #include<cstdlib> using namespace std; template<class type> void swap(type x[],int,int); template<class type> void HeapSort(type x[],int); template<class type> void SiftDown(type x[],int,int); int main()

{ srand(time(0)); const int n=10; int x[n]; for(int i=0;i<n;i++) x[ i]=rand()%99; for(int i=0;i<n;i++) cout<<" "<<x[ i]; HeapSort(x,n); cout<<"\nAfter Sort:"<<endl; for(int i=0;i<n;i++) cout<<" "<<x[ i]; system("pause"); return 0; } template<class type> void SiftDown(type x[],int i,int n) { int cur=2*i+1; while(cur<n) { if(cur+1<n && x[cur+1]>x[cur]) cur++; if(x[cur]>x[(cur-1)/2]) swap(x,(cur-1)/2,cur); cur=2*cur+1; } } template<class type> void swap(type x[],int n,int m) { int temp=x[n]; x[n]=x[m]; x[m]=temp; } template<class type> void HeapSort(type x[],int n) { for(int cur=(n-2)/2;cur>=0;cur--) SiftDown(x,cur,n); for(int i=n-1;i>0;i--) { swap(x,i,0); for(int cur=(i-2)/2;cur>=0;cur--) SiftDown(x,cur,i); } }

8,基数排序

#include<iostream> #include<cstdlib> #include"Queue.h" using namespace std; template<class type> void RadixSort(type x[],int); template<class type> void RadixSorthelper(type x[],int,int); int main() { srand(time(0)); const int n=10; int x[n]; for(int i=0;i<n;i++) x[ i]=rand()%99; for(int i=0;i<n;i++) cout<<" "<<x[ i]; RadixSort(x,n); cout<<"\nAfter Sort:"<<endl; for(int i=0;i<n;i++) cout<<" "<<x[ i]; system("pause"); return 0; } template<class type> void RadixSort(type x[],int n) { int key=1; while(key<=10000) { RadixSorthelper(x,n,key); key*=10; } } template<class type> void RadixSorthelper(type x[],int n,int key) { int temp,k=0; Queue<int> *a=new Queue<int>[10]; for(int i=0;i<n;i++) { temp=x[ i]/key%10; a[temp].In(x[ i]); } for(int j=0;j<10;j++) { while(!a[ j].IsEmpty()) { a[ j].Out(x[ k++]); } } }

基数排序中用到的队列:

#include<iostream> template<class type> class QueueNode { public: QueueNode<type> *next; type data; QueueNode(type _data):data(_data),next(0){} ~QueueNode(){} }; template<class type> class Queue { private: QueueNode<type> *front; QueueNode<type> *rear; QueueNode<type> *getnew(type); public: Queue():front(0),rear(0){} ~Queue(); bool IsEmpty(); void In(type); void Out(type &); }; template<class type> void Queue<type>::Out(type &temp) { if(IsEmpty()) return; QueueNode<type> *cur=front; front=front->next; temp=cur->data; delete cur; } template<class type> void Queue<type>::In(type value) { QueueNode<type> *newptr=getnew(value); if(front==0) front=rear=newptr; else { rear->next=newptr; rear=rear->next; } } template<class type> bool Queue<type>::IsEmpty() { return front==0; } template<class type> QueueNode<type> *Queue<type>::getnew(type value) { QueueNode<type> *temp=new QueueNode<type>(value); return temp; }

9,链表排序(非模板编写,自己想到的,其实也算一种插入排序

只是实现方式不同)

#include<iostream> #include<iomanip> #include<cstdlib> using namespace std; class node { friend class listnode; private: int number; node *next; node *forward; public: node(int); }; node::node(int m) :number(m),next(0),forward(0) { } class listnode { private: node *firstpoint; node *getnewpoint(int); int n; public: listnode(int m):firstpoint(0),n(m){} void print(); void creat(); void insertpoint(int); }; void listnode::creat() { int i;int value; node *temp; cout<<"please cin the number:"<<endl; for(i=1;i<=n;i++) { cin>>value; insertpoint(value); } } void listnode::insertpoint(int value) { node *newpoint=getnewpoint(value); if(firstpoint==0) firstpoint=newpoint; else { node *temp=firstpoint;node *current; if(temp->number>value && temp->forward==0) { newpoint->next=temp; temp->forward=newpoint; firstpoint=firstpoint->forward; } else { while(temp->next!=0 && temp->number<value) temp=temp->next; if(temp->next==0 && temp->number<value) { temp->next=newpoint; newpoint->forward=temp; } else { current=temp; temp=temp->forward; current->forward=newpoint; newpoint->forward=temp; temp->next=newpoint; newpoint->next=current; } } } } node *listnode::getnewpoint(int value) { node *newptr=new node(value); return newptr; } void listnode::print() { cout<<"the sorted number is:"<<endl; while(firstpoint!=0) { cout<<" "<<firstpoint->number<<endl; firstpoint=firstpoint->next; } } int main() { listnode first(10); first.creat(); first.print(); system("pause"); return 0; }

11,线性表

#include<iostream> #include<cstdlib> using namespace std; template<class T> class SeqList { private: T *data; int size; int MaxSize; public: SeqList(int sz=100); ~SeqList() { delete []data; } int Length() const { return size; } bool IsEmpty() const { return size==0; } void Insert(const T &x, int k); void Delete(int k); T GetData(int k) const; int Find(const T &x) const; void Output(ostream &out) const; };

template<class T> SeqList<T>::SeqList(int sz) { MaxSize=sz; data=new T[MaxSize]; size=0; }

template<class T> void SeqList<T>::Insert(const T &x, int k) { if( k<1 || k>size+1 ) { cerr<<"越界出错"; exit(1); } if(size==MaxSize) { cerr<<"顺序表已满"; exit(1); } for(int i=size-1; i>=k-1; i--) data[ i+1]=data[ i]; data[ k-1]=x; size++;

}

template<class T> void SeqList<T>::Delete(int k) { if(size==0) { cerr<<"顺序表空"; exit(1); } if( k<1 || k>size ) { cerr<<"越界出错"; exit(1); } for(int i=k; i<size; i++) data[ i-1]=data[ i]; size--; }

template<class T> T SeqList<T>::GetData(int k) const { if( k<1 || k>size ) { cerr<<"越界出错"; exit(1); } return data[ k-1]; }

template<class T> int SeqList<T>::Find(const T &x) const { int i=0; while(i<size && data[ i]!=x) i++; if(i<size) return i+1; else return 0; }

template<class T> void SeqList<T>::Output(ostream &out) const { for(int i=0; i<size; i++) out<<data[ i]<<" "; }

template<class T> ostream& operator<<(ostream &out, const SeqList<T> &x) { x.Output(out); return out; } int main() {SeqList<int> a(20),b(30); a.Insert(90,1); a.Insert(80,2); a.Output(cout); a.Delete(2); a.Output(cout); cout<<a.Length(); system("pause"); return 0; }

12,链表类(模板编写,无主函数)

template<class T> struct Node { T data; Node<T>* next; };

template<class T> class LinkList { private: Node<T>* head; public: LinkList(); ~LinkList(); int Length() const; bool IsEmpty() const; void Insert(const T &x,int k); void Delete(int k); T GetData(int k) const; Node<T> * Find(const T &x) const; void ClearList(); void Output(ostream &out) const; };

template<class T> LinkList<T>::LinkList() { head = new Node<T>; head->next = NULL; }

template<class T> LinkList<T>::~LinkList() { Node<T> *p; while(head) { p = head; head = head->next; delete p; } }

template<class T> int LinkList<T>::Length() const { Node<T>* p = head->next; int k=0; while(p) { k++; p=p->next; } return k; } template<class T> bool LinkList<T>::IsEmpty() const { return head->next == NULL; }

template<class T> void LinkList<T>::Insert( const T& x,int k) { if(k<1) { cerr<<"错误！"; exit(1); } Node<T> *p = head; int i=0; while(p && i<k-1) { p=p->next; i++; } if(!p) { cerr<<"错误！"; exit(1); } Node<T> *s = new Node<T>; s->data = x; s->next = p->next; p->next=s; } template<class T> void LinkList<T>::Delete(int k) { if(k<1){cerr<<"出错！"<<endl; exit(1);} Node<T>* p = head; int i=0; while(p->next && i<k-1) { p=p->next; i++; } if(p->next==NULL) { cerr<<"出错！"; exit(1); } Node<T> *q = p->next; p->next = q->next; delete q; }

template<class T> T LinkList<T>::GetData(int k) const { if(k<1) { cerr<<"出错！"; exit(1); } Node<T> *p=head; int i=0; while(p && i<k) { p=p->next; i++; } if(!p) { cerr<<"出错！"; exit(1); } return p->data; }

template<class T> Node<T>* LinkList<T>::Find(const T& x) const { Node<T> *p = head->next; while(p && p->data != x) p=p->next; return p; }

/*或 template<class T> Node<T>* LinkList<T>::Find(const T& x) const { Node<T> *p = head->next; while(p) if(p->data == x) return p; else p=p->next; return NULL; } //*/

template<class T> void LinkList<T>::ClearList() { Node<T> *p, *q; p = head->next; while(p) { q = p; p = p->next; delete q; } head->next = NULL; }

template<class T> void LinkList<T>::Output(ostream &out) const { Node<T> *p = head->next; while(p) { cout<<p->data<<" "; p=p->next; } }

template<class T> ostream & operator<<(ostream &out, const LinkList<T> &x) { x.Output(out); return out; }

13,也是链表类(带SIZE的写法,模板编写,无主函数)

template<class T> struct Node { T data; Node<T>* next; };

template<class T> class LinkList { private: Node<T>* head; int size; public: LinkList(); ~LinkList(); int Length() const { return size; } bool IsEmpty() const { return size==0; } void Insert(const T &x,int k); void Delete(int k); T GetData(int k) const; Node<T> * Find(const T &x) const; };

template<class T> LinkList<T>::LinkList() { head = new Node<T>; head->next = NULL; size=0; }

template<class T> LinkList<T>::~LinkList() { Node<T> *p; while(head) { p = head; head = head->next; delete p; } }

template<class T> void LinkList<T>::Insert( const T& x,int k) { if( k<1 || k>size+1 ) { cerr<<"错误！"; exit(1); } Node<T> *p = head; for(int i=1; i<k; i++) p = p->next; Node<T> *s = new Node<T>; s->data = x; s->next = p->next; p->next = s; size++; }

template<class T> void LinkList<T>::Delete(int k) { if( k<1 || k>size ){ cerr<<"出错！"; exit(1);} Node<T>* p = head; for(int i=1; i<k; i++) p = p->next; Node<T> *q = p->next; p->next = q->next; delete q; size--; }

template<class T> T LinkList<T>::GetData(int k) const { if( k<1 || k>size ){ cerr<<"出错！"; exit(1);} Node<T> *p=head; for(int i=1; i<=k; i++) p = p->next; return p->data; }

template<class T> Node<T>* LinkList<T>::Find(const T& x) const { Node<T> *p = head->next; while(p && p->data != x) p=p->next; return p; } 14,链表小应用:约瑟夫问题的解法

#include<iostream> #include<cstdlib> using namespace std; class numbergame { private: int value; numbergame *next; public: numbergame(int ); friend class dealgame; }; numbergame::numbergame(int number) :value(number),next(0){} class dealgame { private: numbergame *head; numbergame *current; int m; int n; public: dealgame(); void set(int ,int); void insert(int ); void creat(); numbergame *getnew(int); void print(); }; dealgame::dealgame() :head(0),current(0){} void dealgame::set(int n1,int m1) { n=n1;m=m1; } void dealgame::insert(int value1) { if(current==NULL) { current=getnew(value1); head=current; } else { current->next=getnew(value1); current=current->next; } } numbergame *dealgame::getnew(int value1)//能够返回指针 ？ { numbergame *ptr=NULL; ptr=new numbergame(value1); return ptr; } void dealgame::creat() { int mm,nn; cout<<"请输入玩游戏的人数:"; cin>>nn; cout<<"请输入报数的大小:"; cin>>mm; set(nn,mm); for(int i=1;i<=nn;i++) insert(i); current->next=head; current=head; } void dealgame::print() { int times=1; for(int j=1;j<=n;j++) { if(m==1) { cout<<"第"<<times<<"次"<<"离开的游戏的是:"<<head->value<<"号玩家"<<endl; head=head->next; } else { numbergame *temp=NULL; for(int i=1;i<m-1;i++) current=current->next; head=current->next; temp=head; head=head->next;current->next=head; current=head; head=current->next; cout<<"第"<<times<<"次"<<"离开的游戏的是:"<<temp->value<<"号玩家"<<endl; delete temp; } times++; } } int main() { dealgame first; first.creat(); first.print(); system("pause"); return 0; }

15,顺序栈(模板编写,无主函数)

template class SeqStack { private: int top; int MaxSize; T *data; public: SeqStack(int size=100); ~SeqStack(){delete[] data;} bool IsEmpty() const { return top==-1; } bool IsFull() const {return top==MaxSize-1; } void Push(const T& item); T Pop(); T GetTop() const; };

template SeqStack::SeqStack(int size) { MaxSize=size; data=new T[MaxSize]; top=-1; }

template void SeqStack::Push(const T& item) { if(IsFull()) { cerr<<"堆栈已满！"< exit(1); } data[++top]=item; }

template T SeqStack::Pop() { if(top==-1) { cerr<<"堆栈空！"< exit(1); } return data[top--]; }

template T SeqStack::GetTop()const { return data[top];

}

16,链栈(模板编写,无主函数)

template<class T> struct Node { T data; Node<T> *next; };

template<class T> class LinkStack { private: Node<T> *top; public: LinkStack() { top=NULL; } ~LinkStack(); bool IsEmpty() const { return top==NULL; } void Push(const T& x); T Pop(); T GetTop() const; };

template<class T> LinkStack<T>::~LinkStack() { Node<T> *p; while(top) { p=top; top=top->next; delete p; } }

template<class T> void LinkStack<T>::Push(const T& x) { Node<T> *s=new Node<T>; s->data=x; s->next=top; top=s; }

template<class T> T LinkStack<T>::Pop() { if(IsEmpty()) { cerr<<"堆栈空！";exit(1); } T temp=top->data; Node<T> *p=top; top=top->next; delete p; return temp; }

template<class T> T LinkStack<T>::GetTop() const { if(IsEmpty()) { cerr<<"堆栈空！";exit(1); } return top->data; }

17,队列（数组存储的循环队列）

template<class T> class Queue { private: int front, rear; int MaxSize; T *data; public: Queue(int size=100); ~Queue() { delete [] data; } bool IsEmpty() const { return front == rear; } bool IsFull() const { return (rear+1) % MaxSize == front; } void Add(const T& x); void Delete(T& x); T First() const; };

template<class T> Queue<T>::Queue(int size) { MaxSize = size+1; data = new T[MaxSize]; front = rear = 0; }

template<class T> void Queue<T>::Add(const T& x) { if(IsFull()) { cerr<<"队列满！"; exit(1); } data[rear] = x; rear = (rear+1) % MaxSize; }

template<class T> void Queue<T>::Delete(T& x) { if(IsEmpty()) { cerr<<"队列空！"; exit(1); } x = data[front]; front = (front+1) % MaxSize; }

template<class T> T Queue<T>::First() const { if(IsEmpty()) { cerr<<"队列空！"; exit(1); } return data[front]; }

18,链式队列(模板编写,无主函数)

template<class T> struct Node { T data; Node<T> *next; }; template<class T> class LinkQueue { private: Node<T> *front, *rear; public: LinkQueue(); ~LinkQueue(); bool IsEmpty() const { return front == NULL; } void Add(const T& x); void Delete(T& x); T First() const; };

template<class T> LinkQueue<T>::~LinkQueue(int size) { Node<T> *p; while(front) { p = front; front = front->next; delete p; } }

template<class T> void LinkQueue<T>::Add(const T& x) { Node<T> *s = new Node<T>; s->data = x; s->next = NULL; if(front == NULL) { rear->next = s; r = s; } else { front = s; r = s; } }

template<class T> void LinkQueue<T>::Delete(T& x) { if(IsEmpty()) { cerr<<"队列空！";exit(1); } x = front->data; Node<T> *p = front; front = front->next; delete p; if(front == NULL) rear = NULL; }

template<class T> T LinkQueue<T>::First() const { if(IsEmpty()) { cerr<<"队列空！";exit(1); } return front->data; }

19,比较完整的二叉检索树(模板编写,有主函数,编译通过)

#include<iostream> #include<cstdlib> #include"Stack.h" #include"Queue.h" using namespace std; template<class type> class treenode { public: type data; treenode<type> *leftptr; treenode<type> *rightptr; treenode(type); }; template<class type> treenode<type>::treenode(type _data) :data(_data),leftptr(0),rightptr(0) {} template<class type> class tree { private: treenode<type> *root; treenode<type> *getnew(type); void Tpreorderhelper(treenode<type> *); void Tinorderhelper(treenode<type> *); void Tpostorderhelper(treenode<type> *); int Height(treenode<type> *); int Leaf(treenode<type> *); int Size(treenode<type> *); void Change(treenode<type> *); void Swap(treenode<type> *,treenode<type> *); void MaxValuehelper(treenode<type> *,type &); public: tree(); void create(); void insert(treenode<type> *&,type); void preorder();//非递归写法,前序遍历; void inorder();//非递归写法,中序遍历,排序算法; void postorder();//非递归写法,后序遍历; void Tpreorder() {Tpreorderhelper(root);}//递归写法,前序遍历; void Tinorder() {Tinorderhelper(root);}//递归写法,中序遍历; void Tpostorder(){Tpostorderhelper(root);}//递归写法,后序遍历; int Height() { return Height(root); } //二叉树高度 int Leaf() { return Leaf(root); } //叶子结点数 int Size() { return Size(root); } //结点数 void Change(){ Change(root); }//交换左右子树; type MaxValue();//返回树的最大值; void levelprint();//按层遍历 }; template<class type> type tree<type>::MaxValue() { type temp=root->data; MaxValuehelper(root,temp); return temp; } template<class type> void tree<type>::MaxValuehelper(treenode<type> *_root,type &temp) { if(_root!=0) { if(temp<_root->data) temp=_root->data; MaxValuehelper(_root->leftptr,temp); MaxValuehelper(_root->rightptr,temp); } } template<class type> int tree<type>::Height(treenode<type> *p) { if(p==0) return 0; return Height(p->leftptr)+1>Height(p->rightptr)+1 ? Height(p->leftptr)+1:Height(p->rightptr)+1; } template<class type> int tree<type>::Leaf(treenode<type> *p) { if(p==0) return 0; if(p->leftptr==0 && p->rightptr==0) return 1; return Leaf(p->leftptr)+Leaf(p->rightptr); } template<class type> int tree<type>::Size(treenode<type> *p) { if(p==0) return 0; return Size(p->leftptr)+Size(p->rightptr)+1; } template<class type> void Swap(treenode<type> *left,treenode<type> *right) { treenode<type> *temp=left; left=right; right=temp;temp=0; } template<class type> void tree<type>::Change(treenode<type> *p) { if(p==0) return; if(p->leftptr==0 && p->rightptr==0) return; swap(p->leftptr,p->rightptr); Change(p->leftptr); Change(p->rightptr); } template<class type> void tree<type>::Tpreorderhelper(treenode<type> *p) { if(p!=0) { cout<<" "<<p->data; Tpreorderhelper(p->leftptr); Tpreorderhelper(p->rightptr); } } template<class type> void tree<type>::Tinorderhelper(treenode<type> *p) { if(p!=0) { Tinorderhelper(p->leftptr); cout<<" "<<p->data; Tinorderhelper(p->rightptr); } } template<class type> void tree<type>::Tpostorderhelper(treenode<type> *p) { if(p!=0) { Tpostorderhelper(p->leftptr); Tpostorderhelper(p->rightptr); cout<<" "<<p->data; } } template<class type> tree<type>::tree() :root(0){} template<class type> void tree<type>::create() { cout<<"start to build the tree:"<<endl; type value; for(int i=0;i<10;i++) { cout<<"integer the value"<<i+1<<":"; cin>>value; insert(root,value); } } template<class type> treenode<type> *tree<type>::getnew(type _data) { treenode<type> *cur=new treenode<type>(_data); return cur; } template<class type> void tree<type>::insert(treenode<type> *&_root,type _data) { treenode<type> *temp=getnew(_data); if(_root==0) _root=temp; else { if(_data<=_root->data) insert(_root->leftptr,_data); else insert(_root->rightptr,_data); } } template<class type> void tree<type>::preorder() { treenode<type> *p=root;cout<<"Preorder:"; Stack<treenode<type> *> q;treenode<type> *temp; while(p||!q.IsEmpty()) { if(p) { q.Push(p); cout<<" "<<p->data; p=p->leftptr; } else { q.Del(temp); p=temp->rightptr; } } } template<class type> void tree<type>::inorder() { treenode<type> *p=root;cout<<"Inorder:"; Stack<treenode<type> *> q;treenode<type> *temp; while(p||!q.IsEmpty()) { if(p) { q.Push(p); p=p->leftptr; } else { q.Del(temp); cout<<" "<<temp->data; p=temp->rightptr; } } } template<class type> void tree<type>::postorder() { treenode<type> *p=root;cout<<"Postorder:"; Stack<treenode<type> *> q; Stack<int> t;int n; treenode<type> *temp; while(p||!q.IsEmpty()) { if(p) { q.Push(p); t.Push(1); p=p->leftptr; } else { q.Del(temp); t.Del(n); if(n==1) { q.Push(temp); t.Push(2); p=temp->rightptr; } else { cout<<" "<<temp->data; p=0; } } } } template<class type> void tree<type>::levelprint() { cout<<"LevelPrint:"; treenode<type> *p=root;treenode<type> *temp; if(p==0)return; Queue<treenode<type> *> q;q.In(p); while(!q.IsEmpty()) { q.Out(temp); cout<<" "<<temp->data; if(temp->leftptr)q.In(temp->leftptr); if(temp->rightptr)q.In(temp->rightptr); } } int main() { tree<int> first; first.create(); first.preorder();cout<<endl; first.inorder();cout<<endl; first.postorder();cout<<endl; first.levelprint();cout<<endl; cout<<"The Tree Hight is:"<<first.Height()<<endl; cout<<"The Tree Leaves is:"<<first.Leaf()<<endl; cout<<"The Tree Nodes is:"<<first.Size()<<endl; cout<<"The Max Value is:"<<first.MaxValue()<<endl; system("pause"); return 0; }

此二叉树中用到的栈:

//**********************************//

#include<iostream> using namespace std; template<class type> class Stacknode { public: type data; Stacknode<type> *next; Stacknode(type _data):data(_data),next(0){} }; template<class type> class Stack { private: Stacknode<type> *top; Stacknode<type> *getnew(type); public: Stack():top(0){} void Push(type); void Del(type &); bool IsEmpty(); }; template<class type> bool Stack<type>::IsEmpty() { return top==0;} template<class type> Stacknode<type> *Stack<type>::getnew(type _data) { Stacknode<type> *cur=new Stacknode<type>(_data); return cur; } template<class type> void Stack<type>::Push(type _data) { Stacknode<type> *temp=getnew(_data); if(top==0) top=temp; else { temp->next=top; top=temp; } } template<class type> void Stack<type>::Del(type &temp) { Stacknode<type> *cur=top; if(IsEmpty()) return; else { temp=top->data; top=top->next; delete cur; } }

此二叉树中用到的队列:

//***************************************//

#include<iostream> using namespace std; template<class type> class Queuenode { public: type data; Queuenode<type> *next; Queuenode(type _data):data(_data),next(0){} }; template<class type> class Queue { private: Queuenode<type> *front; Queuenode<type> *rear; Queuenode<type> *getnew(type); public: Queue():front(0),rear(0){} void In(type); void Out(type &); bool IsEmpty(); }; template<class type> bool Queue<type>::IsEmpty() { return front==0;} template<class type> Queuenode<type> *Queue<type>::getnew(type _data) { Queuenode<type> *cur=new Queuenode<type>(_data); return cur; } template<class type> void Queue<type>::In(type _data) { Queuenode<type> *temp=getnew(_data); if(front==0) { rear=temp;front=rear;} else { rear->next=temp; rear=rear->next; } } template<class type> void Queue<type>::Out(type &temp) { Queuenode<type> *cur=front; if(IsEmpty()) return; else { temp=front->data; front=front->next; delete cur; } }

******八皇后问题******

#include<iostream> #include<cstdlib> using namespace std; class Queen { private: int k; bool x[9];//1...8 bool a[15];//0...14 bool b[17];//2...16 int s[9][9]; public: Queen(); void test(int); }; Queen::Queen() { for(int i=1;i<9;i++) x[ i]=true; for(int i=0;i<15;i++) a[ i]=true; for(int i=2;i<17;i++) b[ i]=true; for(int i=1;i<=8;i++) for(int j=1;j<=8;j++) s[ i][ j]=0; k=0; } void Queen::test(int i) { for(int j=1;j<=8;j++) { if(x[ j]==true && a[ i-j+7]==true && b[ i+j]==true) { s[ i][ j]=1;k++; x[ j]=false; a[ i-j+7]=false; b[ i+j]=false; if(i<8) test(i+1); if(i==8) { cout<<"the result is:"<<endl; for(int ci=1;ci<=8;ci++) { for(int cj=1;cj<=8;cj++) cout<<" "<<s[ ci][cj]; cout<<endl; } return; } x[ j]=true; a[ i-j+7]=true; b[ i+j]=true; s[ i][ j]=0; } } } int main() { Queen first; first.test(1); system("pause"); return 0; }