这些天,本人把以前所学的数据结构做了下总结,现在贴出来,希望能对大家的学习有所帮助,这些都是最基本的算法和结构,本人采用C++面向对象的写法,对每个结构都用类封装起来,要修改或者运用直接调用成员函数即可,同时,为了更广泛应用,本人已经全部修改成了模板,为了能让大家编译通过,本人尽量写成完整的程序,应该在大部分C++编译器上都能通过!以下非注明均能在大部分C++编译器上通过,其排序算法跟C语言写法一样...   -------------------------------------------------------------------------------- 首先先介绍排序: 1,大家都知道的冒泡排序: #include#includeusing namespace std;templatevoid swap(type x[],int,int);templatevoid 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;}templatevoid 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; }}templatevoid swap(type x[],int n,int m){  int temp=x[n];   x[n]=x[m];   x[m]=temp;}   -------------------------------------------------------------------------------- 2,简单的选择排序 #include#includeusing namespace std;templatevoid swap(type x[],int,int);templatevoid 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;}templatevoid swap(type x[],int n,int m){  int temp=x[n];   x[n]=x[m];   x[m]=temp;}templatevoid 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;}     -------------------------------------------------------------------------------- 10,利用二叉树的中序遍历的排序 先省略,在以下的二叉检索树类中将给出   -------------------------------------------------------------------------------- 以下是一些常用的数据结构: 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.1,链表小应用:约瑟夫问题的解法（单相循环链表） #include#includeusing 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<<"第"<value<<"号玩家"<   head=head->next;  }  else  { numbergame *temp=NULL;  for(int i=1;i      current=current->next;  head=current->next;  temp=head;  head=head->next;current->next=head;  current=head;  head=current->next;  cout<<"第"<value<<"号玩家"<    delete temp;      }  times++; }}int main(){ dealgame first; first.creat(); first.print();        system("pause");               return 0;}   14.2双向循环链表解约瑟夫问题 #include<iostream>using namespace std;class Node{ public:  int value; Node *Next; Node *Forward; Node(int _value):value(_value),Forward(0),Next(0){}};class DoubleLink{private: Node *Head; Node *Rear; int Size; Node *GetNew(int );public: DoubleLink():Head(0),Rear(0),Size(0){} void Insert(int ); int GetSize(){  return Size;  } bool IsEmpty(); void Remove(Node *,int); void Create();};Node *DoubleLink::GetNew(int _value){ Node *p=new Node(_value); return p;}void DoubleLink::Insert(int _val){   Node *q=GetNew(_val); if(IsEmpty()) {  Head=q;  Rear=Head;  ++Size;  return; } Rear->Next=q; q->Forward=Rear; Rear=Rear->Next; Rear->Next=Head; Head->Forward=Rear; ++Size;}void DoubleLink::Remove(Node *s,int n){   if(IsEmpty()) return; for(int i=1;i<n;++i)  s=s->Next; cout<<"  "<<s->value; Node *q=s; s=s->Next;//s->Forward->Next=s->Next; q->Forward->Next=s;//s->Next->Forward=s->Forward; s->Forward=q->Forward; --Size; delete q; Remove(s,n);}bool DoubleLink::IsEmpty(){ return Size==0?1:0;}void DoubleLink::Create(){   int gn,size; cout<<"此为循环报数试验程序,请根据提示输入!"<<endl; cout<<"请输入游戏人数:";cin>>gn; cout<<"请输入报数值:";cin>>size;    for(int i=1;i<=gn;++i) Insert(i); cout<<"依次淘汰队员号:"; Remove(Head,size);}int main(){ DoubleLink s; s.Create();}     -------------------------------------------------------------------------------- 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];  }    

评论