这些天,本人把以前所学的数据结构做了下总结,现在贴出来,希望能对大家的学习有所帮助,这些都是最基本的算法和结构,本人采用C++面向对象的写法,对每个结构都用类封装起来,要修改或者运用直接调用成员函数即可,同时,为了更广泛应用,本人已经全部修改成了模板,为了能让大家编译通过,本人尽量写成完整的程序,应该在大部分C++编译器上都能通过!以下非注明均能在大部分C++编译器上通过,其排序算法跟C语言写法一样...
--------------------------------------------------------------------------------
首先先介绍排序:
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;
}
--------------------------------------------------------------------------------
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
#include
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<<"第"<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];
}
评论