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

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

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

#include 
using namespace std; 
#include 
#define DefaultSize 100 

template s Type >class Array{ 
public: 
Array(int Size =DefaultSize); 
Array(const Array&x); 
~Array(){delete []elements;} 
Array&operator=(const Array&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  void Array::getArray(){ 
//获取一个数组 
elements =new Type[ArraySize]; 
if(elements==0) 
{ 
cerr<<"Memory Allocation error"< 
} 

templateArray::Array(int sz){ 
//带参数构造函数。 
if(sz<=0){cerr<<"invalid array size"<Array::Array(const Array&x){ 
//复制构造函数 
int n; 
int ArraySize=n=x.ArraySize; 
elements=new Type[n]; 

if(elements==0){cerr<<"Memory Allocation error"< Type &Array::operator[](int i){ if(i<0||i>ArraySize-1){cerr<<"index out of range"< void Array::ReSize(int sz){ 
if(sz<=0) cerr<<"invlid array size"<dl;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 t(5); 
  t[3]=3;    
 //实际上是t【3】是指向elements【3】的，t【3】是elements【3】 
//的引用； 
  int a=t[3]; 
  cout< 
using namespace std; 
#define defaultsize 10 

template 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; 
}; 

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

template  int seqlist::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; 
} 

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

templateint seqlist::insert(type &x,int i){ 
if(i<0||i>last+1||last==maxsize-1) 
{ 
cout<<"can't insert data"<i;j--)data[j]=data[j-1];//后退法。 
data[i]x; 
return 1; 
} 
} 
templateint seqlist::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 int seqlist::next(type &x){ 
int i=find(x); 
if(i>=0&&ieturn i+1; //返回x的前一个位置。 
else return -1; 
} 

template int seqlist::prior(type &x){ 
int i=find(x); 
if(i>=0&&i<=last)return i-1;//返回x的后一个位置。 
else return -1; 
} 
//使用顺序表的实例 
template  void uniont(seqlist  &la,seqlist&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 void intersection(seqlist&la,seqlist&lb) 
{ 
//求顺序表la和lb的共有元素 
int n=la.length(); 
int m=lb.length(); 
int i=0; 
while(i a; 
int b=6; 
a.insert(b,4); 
if(a.isin(b)) 
cout<<"b is in a"<~~~华丽分割~~~~~~~~~~~~~~~~~~~~~~~~~~~字符串结构的实现 

#include 
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;ich[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!"<operator[](int i){ 
//取×this的第i个字符 
if(i<0&&i>=curlen){cout<<"out of memory"< 
else {i++;s=ch+i;p=pat.ch;} 
return -1; 
} 
int main() 
{ 
String ss; 
 return 0; 
}
~~~~~~~~~~~~~~~~~~~~~~~~~~~华丽分割~~~~~~~~~~~~~~~~~~~~~~~
顺序栈的实现 

#include 
#include 
using namespace std; 

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

templatevoid Sstack::Push(const type &item){ 
assert(!IsFull()); 
elements[++top]=item; 
} 

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

#include 
#include 
using namespace std; 

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

template 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*top; 
}; 

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

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

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

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

#include 
#include 
using namespace std; 

templateclass 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  Queue::Queue(int sz):front(0),rear(0),maxSize(sz) 
{ 
elements=new type[maxSize]; 
assert(elements!=0); 
} 

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

templatetype Queue::DeQueue(){ 
assert(!IsEmpty()); 
front=(front+1)%maxSize; 
return elements[front]; 
} 

templatetype Queue::GetFront(){ 
assert(!IsEmpty()); 
return elements[(front1)%maxSize]; 
} 

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

#include 
#include 
using namespace std; 

template class Lqueue; 

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

templateclass 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*front,*rear; 
}; 

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

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

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

templatetype Lqueue::GetFront(){ 
assert(!IsEmpty()); 
return front->data; 
} 

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

#include 
using namespace std; 

template  class List; 

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

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

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

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

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

return tempptr; 
} 
//★★★★★★★★★★List 的成员函数。 
templateList::~List(){//析构函数 
MakeEmpty(); 
delete first; 
} 

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

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

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

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

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

template type *List::Remove(int i){ 
ListNode*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-