各种数据结构模板源代码.doc

各种数据结构模板源代码，有了它数据结构随意滴很，会了它，胜利哥哥也拿你没辙~~~~~无敌汇编著~~~~~学数据结构学生必备
无意中寻求的源代码，最近在学数据结构的同学对于严蔚敏教程的代码很头疼，完成代码也不好找，于是我便把我的宝贝珍藏都拿出来了，希望对大家有用！
其中可能有点小错误，自己改一下吧....我正在一点点的完善...

抽象数据类型的数组的实现。 

#include<iostream> 
using namespace std; 
#include<stdio.h> 
#define DefaultSize 100 

template <class Type >class Array{ 
public: 
Array(int Size =DefaultSize); 
Array(const Array<Type>&x); 
~Array(){delete []elements;} 
Array<Type>&operator=(const Array<Type>&A); 
Type &operator[](int i); 
Type *operator *()const{return elements;} 
int Length()const {return ArraySize;} 
void ReSize(int sz); 
  private: 
   Type *elements; 
   int ArraySize; 
   void getArray(); 
}; 

template <class Type> void Array<Type>::getArray(){ 
//获取一个数组 
elements =new Type[ArraySize]; 
if(elements==0) 
{ 
cerr<<"Memory Allocation error"<<endl; 
ArraySize=0; 
return ; 
} 
} 

template<class Type>Array<Type>::Array(int sz){ 
//带参数构造函数。 
if(sz<=0){cerr<<"invalid array size"<<endl;ArraySize=0;return;} 
ArraySize=sz; 
getArray(); 
} 

template<class Type>Array<Type>::Array(const Array<Type>&x){ 
//复制构造函数 
int n; 
int ArraySize=n=x.ArraySize; 
elements=new Type[n]; 

if(elements==0){cerr<<"Memory Allocation error"<<endl;ArraySize=0;return ;} 
Type *srcptr=x.elements; 
Type *destptr=elements; 
while(n--) *destptr++=*srcptr++; //好招啊。 
} 

template<class Type> Type &Array<Type>::operator[](int i){ if(i<0||i>ArraySize-1){cerr<<"index out of range"<<endl;return ;} 
return elements[i]; 
}//函数本身返回一个引用，指向第i个地址。 

template<class Type> void Array<Type>::ReSize(int sz){ 
if(sz<=0) cerr<<"invlid array size"<<endl; 
if(sz!=ArraySize){ 
Type *newarray =new Type[sz]; 
if(newarray==0){cerr<<"memory allocation error"<<endl;return ;} 
int n=(sz<=ArraySize)?sz:ArraySize; 
Type *srcptr=elements; 
Type *destptr =newarray; 
while(n--)*destptr++=*srcptr++; 
delete []elements; 
elements =newarray; 
ArraySize=sz; 
} 
} 

int main() 
{ 
Array<int> t(5); 
  t[3]=3;    
 //实际上是t【3】是指向elements【3】的，t【3】是elements【3】 
//的引用； 
  int a=t[3]; 
  cout<<a; 
cout<<t[3]; 
return 0; 
}
~~~~~~~~~~~~~~~~~~~~~~~~华丽分割~~~~~~~~~~~~~~~~~~~~~~~~~~~
顺序表的实现 

#include<iostream> 
using namespace std; 
#define defaultsize 10 

template <class type>class seqlist{ 
public: 
seqlist(int maxsize=defaultsize); //构造函数 
~seqlist(){delete []data;} //析构函数 
int length()const {return last+1;}//求长度 
int find(type &x)const; //查找 
int isin(type &x); //存在 
int insert(type &x,int i); //插入 
int remove(type &x); //删除 
int next(type &x); //下一个位置 
int prior(type &x); //前一个位置 
int isempty(){return last==maxsize-1;}//为空 
type get(int i){return i<0||i>last?NULL:data[i];}//得到第i个数 
private: 
type *data; 
int maxsize; 
int last; 
}; 

template<class type>seqlist<type>::seqlist(int sz){ 
if(sz>0){ 
maxsize =sz; 
last=-1; 
data=new type[maxsize]; 
 } 
} 

template <class type> int seqlist<type>::find(type &x)const{ 
int i=0; 
while(i<=last&&data[i]!=x) i++; //data[i]=x 或者i>last退 出。 
if(i>last) return -1; 
else return i; 
} 

template<class type>int seqlist<type>::isin(type &x){ 
int i=0,found=0; 
while(i<=last&&!found) 
if(data[i]!=x)i++; 
else found=1; 
return found; 
} 

template<class type>int seqlist<type>::insert(type &x,int i){ 
if(i<0||i>last+1||last==maxsize-1) 
{ 
cout<<"can't insert data"<<endl; 
 return 0;//判断边界 
 } 
else{ 
last++; 
for(int j=last;j>i;j--)data[j]=data[j-1];//后退法。 
data[i]=x; 
return 1; 
} 
} 
template<class type>int seqlist<type>::remove(type &x){ 
int i=find(x); 
if(i>=0){ 
last--; 
for(int j=i;j<=last;j++)data[j]=data[j+1];//前进法 
return 1; 
} 
} 

template <class type>int seqlist<type>::next(type &x){ 
int i=find(x); 
if(i>=0&&i<last)return i+1; //返回x的前一个位置。 
else return -1; 
} 

template <class type>int seqlist<type>::prior(type &x){ 
int i=find(x); 
if(i>=0&&i<=last)return i-1;//返回x的后一个位置。 
else return -1; 
} 
//使用顺序表的实例 
template <class type> void uniont(seqlist <type> &la,seqlist<type>&lb){ 
//合并顺序表la和lb，重复元素只留一个 
int n=la.length(); 
int m=lb.length(); 
for(int i=1;i<=m;i++){ 
type x=lb.get(i); 
int k=la.find(x); 
if(k==-1) 
{ 
la.insert(x,n+1);n++; 
} 
} 
} 
template <class type>void intersection(seqlist<type>&la,seqlist<type>&lb) 
{ 
//求顺序表la和lb的共有元素 
int n=la.length(); 
int m=lb.length(); 
int i=0; 
while(i<n){ 
type x=la.get(i); 
int k=lb.find(x); 
if(k==-1){la.remove(i);n--;} 
else i++; 
} 
} 

int main(){ 
seqlist<int> a; 
int b=6; 
a.insert(b,4); 
if(a.isin(b)) 
cout<<"b is in a"<<endl; 
return 0; 
}
~~~~~~~~~~~~~~~~~~~~~~~~华丽分割~~~~~~~~~~~~~~~~~~~~~~~~~~~字符串结构的实现 

#include<iostream> 
using namespace std; 

const int maxlen=128; 

class String{ 
public: 
String(const String &ob); 
String(const char *init); 
String(); 
~String(){delete[]ch;} 
int length()const {return curlen;} 
String &operator()(int pos,int len); 
int operator==(const String &ob)const{return strcmp(ch,ob.ch)==0;} 
int operator!=(const String &ob)const{return strcmp(ch,ob.ch)!=0;} 
int operator!()const{return curlen==0;} 
String &operator=(const String &ob); 
String &operator+=(const String &ob); 
char &operator[](int i); 
int find(String &pat)const; 
private: 
int curlen; 
char *ch; 
}; 

String::String(const String &ob) 
{//串复制构造函数 
ch=new char[maxlen+1]; 
if(!ch){cerr<<"allcation error\n";exit(1);} 
curlen=ob.curlen; 
strcpy(ch,ob.ch); 
} 

String ::String(const char *init){ 
 //串构造函数 
ch =new char[maxlen+1]; 
if(!ch){cerr<<"allocation failed\n";exit(1);} 
curlen=strlen(init); 
strcpy(ch,init); 
} 

String::String(){ 
//默认构造函数 
ch=new char[maxlen+1]; 
if(!ch){cerr<<"allocation error\n";exit(1);} 
curlen=0; 
ch[0]='\0'; 
} 

String &String::operator()(int pos,int len){ 
//求子串 
String *tmp=new String; 
if(pos<0||pos+len-1>=maxlen||len<0){ 
tmp->curlen=0;tmp->ch[0]='\0'; 
} 
else{ 
if(pos +len-1>=curlen)len=curlen-pos; 
tmp->curlen=len; 
for(int i=0,j=pos;i<len;i++,j++) 
tmp->ch[i]=ch[j]; 
tmp->ch[len]='\0'; 
} 
 return *tmp; 
} 

String &String::operator=(const String &ob){ 
//串赋值 
if(&ob!=this) 
{ 
delete []ch; 
ch=new char[maxlen+1]; 
if(!ch){cerr<<"out of memory \n";exit(1);} 
curlen=ob.curlen; 
strcpy(ch,ob.ch); 
} 
else cout<<"attempted assignment of a String to itself"<<endl; 
return *this; 
} 

String &String::operator+=(const String &ob){ 
//串连接 
char *tmp=ch; 
curlen+=ob.curlen; 
ch =new char[maxlen+1]; 
if(!ch){cerr<<"out of memory!"<<endl;exit(1);} 
strcpy(ch,tmp); 
strcat(ch,ob.ch); 
delete[]tmp; 
return *this; 
} 

char &String ::operator[](int i){ 
//取×this的第i个字符 
if(i<0&&i>=curlen){cout<<"out of memory"<<endl;exit(1); 
return ch[i]; 
} 
} 
int String::find(String &pat) const{ 
//查找子串 
char *p=pat.ch,*s=ch; 
int i=0; 
if(*p&&*s) 
while(i<=curlen-pat.curlen) 
if(*p++==*s++){ 
if(!*p)return i; 
} 
else {i++;s=ch+i;p=pat.ch;} 
return -1; 
} 
int main() 
{ 
String ss; 
 return 0; 
}
~~~~~~~~~~~~~~~~~~~~~~~~~~~华丽分割~~~~~~~~~~~~~~~~~~~~~~~
顺序栈的实现 

#include<assert.h> 
#include<iostream> 
using namespace std; 

template<class type> class Sstack{ 
public: 
Sstack(int =10); 
~Sstack(){delete[]elements;} 
void Push(const type &item); 
type Pop(); 
type GetTop(); 
void MakeEmpty(){top=-1;} 
int IsEmpty()const {return top==-1;} 
int IsFull()const {return top==maxSize-1;} 
private: 
int top; 
type *elements; 
int maxSize; 
}; 

template <class type> Sstack<type>::Sstack(int s):top(-1),maxSize(s){ 
elements=new type[maxSize]; 
assert(elements!=0); 
} 

template<class type>void Sstack<type>::Push(const type &item){ 
assert(!IsFull()); 
elements[++top]=item; 
} 

template<class type>type Sstack<type>::GetTop(){ 
assert(!IsEmpty()); 
return elements[top]; 
} 
int main(){ 
Sstack<int> a; 
return 0; 
}
~~~~~~~~~~~~~~~~~~~~~~华丽分割~~~~~~~~~~~~~~~~~~~~~~~~~~~
链栈的实现。 

#include<assert.h> 
#include<iostream> 
using namespace std; 

template<class type>class Lstack; 
template<class type>class StackNode{ 
friend class Lstack<type>; 
private: 
type data; 
StackNode<type>*link; 
StackNode(type d=0,StackNode<type>*l=NULL):data(d),link(l){} 
}; 

template <class type>class Lstack{ 
public: 
Lstack():top(NULL){} 
~Lstack(); 
void Push(const type &item); 
type Pop(); 
type GetTop(); 
void MakeEmpty(); 
int IsEmpty()const{ return top==NULL;} 
private: 
StackNode<type>*top; 
}; 

template<class type> Lstack<type>::~Lstack(){ 
StackNode<type>*p; 
while(top!=NULL){p=top;top=top->link;delete p;} 
} 

template<class type> void Lstack<type>::Push(const type &item){ 
top=new StackNode<type>(item,top); 
} 

template <class type>type Lstack<type>::Pop(){ 
assert(!IsEmpty()); 
StackNode<type> *p=top; 
type value=p->data; 
top=top->link; 
delete p; 
return value; 
} 
template<class type> type Lstack<type>::GetTop(){ 
assert(!IsEmpty()); 
return top->data; 
} 

int main(){ 
Lstack<int> a; 
return 0; 
}
~~~~~~~~~~~~~~~~~~~~~~华丽分割~~~~~~~~~~~~~~~~~~~~~~~~~~~
循环队列的实现 

#include<assert.h> 
#include<iostream> 
using namespace std; 

template<class type>class Queue{ 
public: 
Queue(int=10); 
~Queue(){delete[]elements;} 
void EnQueue(const type &item); 
type DeQueue(); 
type GetFront(); 
void MakeEmpty(){front=rear=0;} 
int IsEmpty()const {return front==rear;} 
int IsFull()const {return (rear+1)%maxSize==front;} 
int Length()const {return (rear-front+maxSize)%maxSize;} 
private: 
int rear,front; 
type *elements; 
int maxSize; 
}; 

template <class type> Queue<type>::Queue(int sz):front(0),rear(0),maxSize(sz) 
{ 
elements=new type[maxSize]; 
assert(elements!=0); 
} 

template<class type>void Queue<type>::EnQueue(const type&item){ 
assert(!IsFull()); 
rear=(rear+1)%maxSize; 
elements[rear]=item; 
} 

template<class type>type Queue<type>::DeQueue(){ 
assert(!IsEmpty()); 
front=(front+1)%maxSize; 
return elements[front]; 
} 

template<class type>type Queue<type>::GetFront(){ 
assert(!IsEmpty()); 
return elements[(front+1)%maxSize]; 
} 

int main() 
{ 
return 0; 
}
~~~~~~~~~~~~~~~~~~~~~~~~~~~华丽分割~~~~~~~~~~~~~~~~~~~~~~
链式队列的实现 

#include<assert.h> 
#include<iostream> 
using namespace std; 

template<class type> class Lqueue; 

template<class type>class QueueNode{ 
friend class Lqueue<type>; 
private: 
type data; 
QueueNode<type> *link; 
QueueNode(type d=0,QueueNode *l=NULL):data(d),link(l){} 
}; 

template<class type>class Lqueue{ 
public: 
Lqueue():rear(NULL),front(NULL){} 
~Lqueue(); 
void EnQueue(const type&item); 
type DeQueue(); 
type GetFront(); 
void MakeEmpty(); 
int IsEmpty()const{return front==NULL;} 
private: 
QueueNode<type>*front,*rear; 
}; 

template<class type> Lqueue<type>::~Lqueue(){ 
QueueNode<type> *p; 
while(front!=NULL){ 
p=front;front=front->link; delete p; 
} 
} 

template<class type>void Lqueue<type>::EnQueue(const type &item){ 
if(front==NULL) front=rear=new QueueNode<type>(item,NULL); 
else 
rear=rear->link=new QueueNode<type>(item,NULL); 
} 

template<class type>type Lqueue<type>::DeQueue(){ 
assert(!IsEmpty()); 
QueueNode<type>*p=front; 
type value=p->data; 
front=front->link; 
delete p; 
return value; 
} 

template<class type>type Lqueue<type>::GetFront(){ 
assert(!IsEmpty()); 
return front->data; 
} 

int main() 
{ 
Lqueue<char> a; 
return 0; 
}
~~~~~~~~~~~~~~~~~~~~~~~~~~~华丽分割~~~~~~~~~~~~~~~~~~~~~~
模板单链表的实现 

#include<iostream> 
using namespace std; 

template <class type> class List; 

template <class type>class ListNode{ //定义节点类 
friend class List<type>; 
public: 
ListNode(); 
ListNode(const type&item); 
ListNode<type> *NextNode(){return link;} 
void InsertAfter(ListNode<type>*p); 
ListNode<type>*GetNode(const type&item,ListNode<type>*next); 
ListNode<type> *RemoveAfter(); 
private: 
type data; 
ListNode<type> *link; 
}; 

template <class type>class List { //定义链表类 
public: 
List(const type &value){last=first=new ListNode<type>(value);} 
~List(); 
 void MakeEmpty(); 
 int Length()const; 
 ListNode<type>*Find(type value); 
 ListNode<type>*Find(int i); 
 int Insert(type value,int i); 
 type * Remove(int i); 
 type * Get(int i); 
 private: 
 ListNode<type> *first,*last; 
}; 

//★★★★★★★★★★★ListNode的成员函数。 
template <class type>ListNode<type>:: 
ListNode():link(NULL){} //无参数构造函数 

template <class type>ListNode<type>:: 
ListNode(const type & item):data(item),link(NULL){} 
 //有参数构造函数 
template<class type>void ListNode<type>::InsertAfter(ListNode<type>*p) 
{ 
p->link=link; 
link=p; 
} 

template<class type> ListNode<type> *ListNode<type>::GetNode(const type& item, 
ListNode<type>*next =NULL){ 
ListNode<type>*newnode=new ListNode<type>(item); 
newnode->link=next->link; 
 next->link=newnode; 
return newnode; 
} 
template<class type> ListNode<type> *ListNode<type>::RemoveAfter(){ 
 ListNode<type>*tempptr=link; 
if(link==NULL)return NULL; 
link=tempptr->link; 

return tempptr; 
} 
//★★★★★★★★★★List 的成员函数。 
template<class type>List<type>::~List(){//析构函数 
MakeEmpty(); 
delete first; 
} 

template <class type>void List<type>::MakeEmpty(){ 
ListNode<type>*q; //清空链表 
while(first->link!=NULL){ 
q=first->link; 
first->link=q->link; 
delete q; 
 } 
 last=first; 
} 

template <class type >int List<type>::Length()const{ 
ListNode<type>*p=first->link; //求链表长度 
int count=0; 
while(p!=NULL) 
{ 
p=p->link; 
count++; 
} 
return count; 
} 

template <class type>ListNode<type>*List<type>::Find(type value){ 
 ListNode<type>*p=first->link; //查找某一类型的值 
 while(p!=NULL&&p->data!=value) 
 { 
 p=p->link; 
 } 
 return p; 
} 

template <class type>ListNode<type> *List<type>::Find(int i){ 
 if(i<-1)return NULL; //查找第i个元素的节点 
 if(i==-1)return first; 
 ListNode<type>*p=first->link;int j=0; 
 while(p!=NULL&&j<i) 
 { 
 p=p->link; 
 j=j++; 
 } 
 return p; 
} 

template <class type>int List <type>::Insert(type value,int i){ 
ListNode<type> *p=Find(i-1); //插入一个节点 
if(p==NULL) return 0; 
ListNode<type>*newnode=GetNode(value,p->link); 
if(p->link==NULL)last =newnode; 
if(p->link=newnode) 
 return 1; 
} 

template<class type> type *List<type>::Remove(int i){ 
ListNode<type>*p=Find(i-1),*q; //删除一个元素，并返回其值 
if(p==NULL||p->link==NULL)return NULL; 
q=p->link; 
p->link=q->link; 
type value =new type(q-