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

各种数据结构模板源代码，有了它数据结构随意滴很，会了它，胜利哥哥也拿你没辙无敌汇编著学数据结构学生必备无意中寻求的源代码，最近在学数据结构的同学对于严蔚敏教程的代码很头疼，完成代码也不好找，于是我便把我的宝贝珍藏都拿出来了，希望对大家有用！其中可能有点小错误，自己改一下吧.我正在一点点的完善.抽象数据类型的数组的实现。 #include usingnamespacestd; #include #defineDefaultSize100 templateclassArray public: Array(intSize=DefaultSize); Array(constArray&x); Array()deleteelements; Array&operator=(constArray&A); Type&operator(inti); Type*operator*()constreturnelements; intLength()constreturnArraySize; voidReSize(intsz); private: Type*elements; intArraySize; voidgetArray(); ; templatevoidArray:getArray() /获取一个数组 elements=newTypeArraySize; if(elements=0) cerrMemoryAllocationerrorendl; ArraySize=0; return; templateArray:Array(intsz) /带参数构造函数。 if(sz=0)cerrinvalidarraysizeendl;ArraySize=0;return; ArraySize=sz; getArray(); templateArray:Array(constArray&x) /复制构造函数 intn; intArraySize=n=x.ArraySize; elements=newTypen; if(elements=0)cerrMemoryAllocationerrorendl;ArraySize=0;return; Type*srcptr=x.elements; Type*destptr=elements; while(n-)*destptr+=*srcptr+;/好招啊。 templateType&Array:operator(inti)if(iArraySize-1)cerrindexoutofrangeendl;return; returnelementsi; /函数本身返回一个引用，指向第i个地址。 templatevoidArray:ReSize(intsz) if(sz=0)cerrinvlidarraysizeendl; if(sz!=ArraySize) Type*newarray=newTypesz; if(newarray=0)cerrmemoryallocationerrorendl;return; intn=(sz=ArraySize)?sz:ArraySize; Type*srcptr=elements; Type*destptr=newarray; while(n-)*destptr+=*srcptr+; deleteelements; elements=newarray; ArraySize=sz; intmain() Arrayt(5); t3=3; /实际上是t【3】是指向elements【3】的，t【3】是elements【3】 /的引用； inta=t3; couta; coutt3; return0; 华丽分割顺序表的实现 #include usingnamespacestd; #definedefaultsize10 templateclassseqlist public: seqlist(intmaxsize=defaultsize);/构造函数 seqlist()deletedata;/析构函数 intlength()constreturnlast+1;/求长度 intfind(type&x)const;/查找 intisin(type&x);/存在 intinsert(type&x,inti);/插入 intremove(type&x);/删除 intnext(type&x);/下一个位置 intprior(type&x);/前一个位置 intisempty()returnlast=maxsize-1;/为空 typeget(inti)returnilast?NULL:datai;/得到第i个数 private: type*data; intmaxsize; intlast; ; templateseqlist:seqlist(intsz) if(sz0) maxsize=sz; last=-1; data=newtypemaxsize; templateintseqlist:find(type&x)const inti=0; while(ilast退 出。 if(ilast)return-1; elsereturni; templateintseqlist:isin(type&x) inti=0,found=0; while(i=last&!found) if(datai!=x)i+; elsefound=1; returnfound; templateintseqlist:insert(type&x,inti) if(ilast+1|last=maxsize-1) coutcantinsertdatai;j-)dataj=dataj-1;/后退法。 datai=x return1; templateintseqlist:remove(type&x) inti=find(x); if(i=0) last-; for(intj=i;j=last;j+)dataj=dataj+1;/前进法 return1; templateintseqlist:next(type&x) inti=find(x); if(i=0&ilast)returni+1;/返回x的前一个位置。 elsereturn-1; templateintseqlist:prior(type&x) inti=find(x); if(i=0&i=last)returni-1;/返回x的后一个位置。 elsereturn-1; /使用顺序表的实例 templatevoiduniont(seqlist&la,seqlist&lb) /合并顺序表la和lb，重复元素只留一个 intn=la.length(); intm=lb.length(); for(inti=1;i=m;i+) typex=lb.get(i); intk=la.find(x); if(k=-1) la.insert(x,n+1);n+; templatevoidintersection(seqlist&la,seqlist&lb) /求顺序表la和lb的共有元素 intn=la.length(); intm=lb.length(); inti=0; while(in) typex=la.get(i); intk=lb.find(x); if(k=-1)la.remove(i);n-; elsei+; intmain() seqlista; intb=6; a.insert(b,4); if(a.isin(b) coutbisinaendl; return0; 华丽分割字符串结构的实现 #include usingnamespacestd; constintmaxlen=128; classString public: String(constString&ob); String(constchar*init) String(); String()deletech; intlength()constreturncurlen; String&operator()(intpos,intlen); intoperator=(constString&ob)constreturnstrcmp(ch,ob.ch)=0; intoperator!=(constString&ob)constreturnstrcmp(ch,ob.ch)!=0; intoperator!()constreturncurlen=0; String&operator=(constString&ob); String&operator+=constString&ob); char&operator(inti); intfind(String&pat)const; private: intcurlen; char*ch; ; String:String(constString&ob) /串复制构造函数 ch=newcharmaxlen+1; if(!ch)cerrallcationerrorn;exit(1); curlen=ob.curlen; strcpy(ch,ob.ch); String:String(constchar*init) /串构造函数 ch=newcharmaxlen+1; if(!ch)cerrallocationfailedn;exit(1); curlen=strlen(init); strcpy(ch,init); String:String() /默认构造函数 ch=newcharmaxlen+1; if(!ch)cerrallocationerrorn;exit(1); curlen=0; ch0=0; String&String:operator()(intpos,intlen) /求子串 String*tmp=newString; if(pos=maxlen|lencurlen=0;tmp-ch0=0; else if(pos+len-1=curlen)len=curlen-pos; tmp-curlen=len; for(inti=0,j=pos;ichi=chj; tmp-chlen=0; return*tmp; String&String:operator=(constString&ob) /串赋值 if(&ob!=this) deletech; ch=newcharmaxlen+1; if(!ch)cerroutofmemoryn;exit(1); curlen=ob.curlen; strcpy(ch,ob.ch); elsecoutattemptedassignmentofaStringtoitselfendl; return*this; String&String:operator+=(constString&ob) /串连接 char*tmp=ch; curlen+=ob.curlen; ch=newcharmaxlen+1; if(!ch)cerroutofmemory!endl;exit(1); strcpy(ch,tmp); strcat(ch,ob.ch); deletetmp; return*this; char&String:operator(inti) /取this的第i个字符 if(i=curlen)coutoutofmemoryendl;exit(1); returnchi; intString:find(String&pat)const /查找子串 char*p=pat.ch,*s=ch; inti=0; if(*p&*s) while(i=curlen-pat.curlen) if(*p+=*s+) if(!*p)returni; elsei+;s=ch+i;p=pat.ch; return-1; intmain() Stringss; return0; 华丽分割顺序栈的实现 #include #include usingnamespacestd; templateclassSstack public: Sstack(int=10); Sstack()deleteelements; voidPush(consttype&item); typePop(); typeGetTop(); voidMakeEmpty()top=-1; intIsEmpty()constreturntop=-1; intIsFull()constreturntop=maxSize-1; private: inttop; type*elements; intmaxSize; ; templateSstack:Sstack(ints):top(-1),maxSize(s) elements=newtypemaxSize; assert(elements!=0); templatevoidSstack:Push(consttype&item) assert(!IsFull(); elements+top=item; templatetypeSstack:GetTop() assert(!IsEmpty(); returnelementstop; intmain() Sstacka; return0; 华丽分割链栈的实现。 #include #include usingnamespacestd; templateclassLstack; templateclassStackNode friendclassLstack; private: typedata; StackNode*link; StackNode(typed=0,StackNode*l=NULL):data(d),link(l) ; templateclassLstack public: Lstack():top(NULL) Lstack(); voidPush(consttype&item); typePop(); typeGetTop(); voidMakeEmpty(); intIsEmpty()constreturntop=NULL; private: StackNode*top; ; templateLstack:Lstack() StackNode*p; while(top!=NULL)p=top;top=top-link;deletep; templatevoidLstack:Push(consttype&item) top=newStackNode(item,top); templatetypeLstack:Pop() assert(!IsEmpty(); StackNode*p=top; typevalue=p-data; top=top-link; deletep; returnvalue; templatetypeLstack:GetTop() assert(!IsEmpty(); returntop-data; intmain() Lstacka; return0; 华丽分割循环队列的实现 #include include usingnamespacestd; templateclassQueue public: Queue(int=10); Queue()deleteelements; voidEnQueue(consttype&item); typeDeQueue(); typeGetFront(); voidMakeEmpty()front=rear=0; intIsEmpty()constreturnfront=rear; intIsFull()constreturn(rear+1)%maxSize=front; intLength()constreturn(rear-front+maxSize)%maxSize; private: intrear,front; type*elements; intmaxSize; ; templateQueue:Queue(intsz):front(0),rear(0),maxSize(sz) elements=newtypemaxSize; assert(elements!=0); templatevoidQueue:EnQueue(consttype&item) assert(!IsFull(); rear=(rear+1)%maxSize; elementsrear=item; templatetypeQueue:DeQueue() assert(!IsEmpty(); front=(front+1)%maxSize; returnelementsfront; templatetypeQueue:GetFront() assert(!IsEmpty(); returnelements(front+1)%maxSize; intmain() return0; 华丽分割链式队列的实现 #include #include usingnamespacestd; templateclassLqueue; templateclassQueueNode friendclassLqueue; private: typedata; QueueNode*link; QueueNode(typed=0,QueueNode*l=NULL):data(d),link(l) ; templateclassLqueue public: Lqueue():rear(NULL),front(NULL) Lqueue(); voidEnQueue(consttype&item); typeDeQueue(); typeGetFront(); voidMakeEmpty(); intIsEmpty()constreturnfront=NULL; private: QueueNode*front,*rear; ; templateLqueue:Lqueue() QueueNode*p; while(front!=NULL) p=front;front=front-link;deletep; templatevoidLqueue:EnQueue(consttype&item) if(front=NULL)front=rear=newQueueNode(item,NULL); else rear=rear-link=newQueueNode(item,NULL); templatetypeLqueue:DeQueue() assert(!IsEmpty(); QueueNode*p=front; typevalue=p-data; frontfront-link; deletep; returnvalue; templatetypeLqueue:GetFront() assert(!IsEmpty(); returnfront-data; intmain() Lqueuea; return0; 华丽分割模板单链表的实现 #include usingnamespacestd; templateclassList; templateclassListNode/定义节点类 friendclassList; public: ListNode(); ListNode(consttype&item); ListNode*NextNode()returnlink; voidInsertAfter(ListNode*p); ListNode*GetNode(consttype&item,ListNode*next); ListNode*RemoveAfter(); private: typedata; ListNode*link; ; templateclassList/定义链表类 public: List(consttype&value)last=first=newListNode(value); List(); voidMakeEmpty(); intLength()const; ListNode*Find(typevalue) ListNode*Find(inti); intInsert(typevalue,inti); type*Remove(inti); type*Get(inti); private: ListNode*first,*last; ; /ListNode的成员函数。 templateListNode: ListNode():link(NULL)/无参数构造函数 templateListNode: ListNode(consttype&item):data(item),link(NULL) /有参数构造函数 templatevoidListNode:InsertAfter(ListNode*p) p-link=link; link=p; templateListNode*ListNode:GetNode(consttype&item, ListNode*next=NULL) ListNode*newnode=newListNode(item); newnode-link=next-link; next-link=newnode; returnnewnode; templateListNode*ListNode:RemoveAfter() ListNode*tempptr=link; if(link=NULL)returnNULL; link=tempptr-link; returntempptr; /List的成员函数。 templateList:List()/析构函数 MakeEmpty(); deletefirst; templatevoidList:MakeEmpty() ListNode*q;/清空链表 while(first-link!=NULL) q=first-link; first-link=q-link; deleteq; last=first; templateintList:Length()const ListNode*p=first-link;/求链表长度 intcount=0; while(p!=NULL) p=p-link; count+; returncount; templateListNode*List:Find(typevalue) ListNode*p=first-link;/查找某一类型的值 while(p!=NULL&p-data!=value) p=p-link; returnp; templateListNode*List:Find(inti) if(i-1)returnNULL;/查找第i个元素的节点 if(i=-1)returnfirst; ListNode*p=first-link;intj=0; while(p!=NULL&jlink; j=j+; returnp; templateintList:Insert(typevalue,inti) ListNode*p=Find(i-1);/插入一个节点 if(p=NULL)return0; ListNode*newnode=GetNode(value,p-link); if(p-link=NULL)last=newnode; if(p-link=newnode) return1; templatetype*List:Remove(inti) ListNode*p=Find(i-1),*q;/删除一个元素，并返回其值 if(p=NULL|p-link=NULL)returnNULL; q=p-link; p-link=q-link; typevalue=newtype(q-