C++数据结构实例代码

C++数据结构实例代码下载文档可编辑1/2下载文档可编辑下载文档可编辑1线性表的顺序表示#include"iostream"#include"malloc.h"usingnamespacestd;typedefstruct{ int*elem; intlength; intlistsize;}SqList;intInit_Sq(SqList&L){ L.elem=(int*)malloc(100*sizeof(int)); if(!L.elem) exit(-2); L.length=0; L.listsize=100; return1;}intListInsert(SqList&L,inti,inte){ if(i<1||i>L.length+1) return0; if(L.length>=L.listsize){C++数据结构实例代码全文共35页，当前为第1页。 int*newbase=(int*)realloc(L.elem,(L.listsize+10)*sizeof(int));C++数据结构实例代码全文共35页，当前为第1页。 if(!newbase) exit(-2); L.elem=newbase; L.listsize+=10; } int*q=&(L.elem[i-1]); int*p=&(L.elem[L.length-1]); for(p;p>=q;--p){ *(p+1)=*p; } *q=e; ++L.length; return1;}intListDelete(SqList&L,inti,int&e){ if(i<1||i>L.length) return0; int*p=&(L.elem[i-1]); e=*p; int*q=L.elem+L.length-1;C++数据结构实例代码全文共35页，当前为第2页。 for(++p;p<=q;++p){C++数据结构实例代码全文共35页，当前为第2页。 *(p-1)=*p; } --L.length; returne;}intmain(){ inta[6]={1,2,3,4,5}; int*q=&a[1]; int*p=&a[4]; for(p;p>=q;--p){ *(p+1)=*p; } *q=3; for(inti=0;i<6;i++){ cout<<a[i]<<""; } cout<<endl; SqListlx; Init_Sq(lx); for(intj=1;j<10;j++){ ListInsert(lx,j,j);C++数据结构实例代码全文共35页，当前为第3页。C++数据结构实例代码全文共35页，当前为第3页。 ListInsert(lx,3,55); inte_return; ListDelete(lx,4,e_return); for(intm=0;m<10;m++){ cout<<*(lx.elem+m)<<""; } cout<<endl; cout<<e_return; system("pause"); return0;}132345125545678993请按任意键继续...2线性表的链性表示#include"iostream"#include"malloc.h"usingnamespacestd;typedefstructLNode{ intdata;C++数据结构实例代码全文共35页，当前为第4页。 structLNode*next;C++数据结构实例代码全文共35页，当前为第4页。}LNode,*LinkList;intInitList(LinkList&L){ L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; return1;}intListInsert(LinkList&L,inti,inte){ LinkListp=L; intj=0; while(p&&j<i-1){ p=p->next; ++j; } if(!p||j>i-1) return0; LinkLists=(LinkList)malloc(sizeof(LNode)); s->data=e; s->next=p->next; p->next=s;C++数据结构实例代码全文共35页，当前为第5页。 return1;C++数据结构实例代码全文共35页，当前为第5页。}intListDelete(LinkList&L,inti){ LinkListp=L; intj=0; while(p->next&&j<i-1){ p=p->next; ++j; } if(!(p->next)||j>i-1) return0; LinkListq=p->next; p->next=q->next; free(q); return1;}intGetElem(LinkListL,inti){ LinkListp=L->next; intj=1; while(p&&j<i)C++数据结构实例代码全文共35页，当前为第6页。 {C++数据结构实例代码全文共35页，当前为第6页。 p=p->next; ++j; } if(!p||j<i) return0; inte=p->data; returne;}intmain(){ LinkListlx; InitList(lx); for(inti=1;i<6;i++){ ListInsert(lx,i,i); } ListDelete(lx,2); for(intj=1;j<5;j++) { cout<<GetElem(lx,j)<<""; } cout<<endl;C++数据结构实例代码全文共35页，当前为第7页。 LinkListlx1,lx2;C++数据结构实例代码全文共35页，当前为第7页。 InitList(lx1); InitList(lx2); for(intm=1;m<6;m++){ ListInsert(lx1,m,m); } for(intn=1;n<6;n++){ ListInsert(lx2,n,2*n); } for(intj=1;j<6;j++) { cout<<GetElem(lx1,j)<<""; } system("pause"); return0;}134512345请按任意键继续...3双向链表#include"iostream"#include"malloc.h"usingnamespacestd;C++数据结构实例代码全文共35页，当前为第8页。typedefstructdlistC++数据结构实例代码全文共35页，当前为第8页。{ intdata; structdlist*prior; structdlist*next;}DList,*DLinkList;voidInitList(DLinkList&L){ L=(DLinkList)malloc(sizeof(DList)); L->next=L; L->prior=L;}intListInsert(DLinkList&L,inti,inte){ DLinkListp,s; p=L->next; intj=1; while(p&&j<i){ p=p->next; ++j; } if(!p||j>i)C++数据结构实例代码全文共35页，当前为第9页。 return0;C++数据结构实例代码全文共35页，当前为第9页。 s=(DLinkList)malloc(sizeof(DList)); s->data=e; s->prior=p->prior; p->prior->next=s; s->next=p; p->prior=s; return1;}intListDelete(DLinkList&L,inti,int&e){ DLinkListp; p=L->next; intj=1; while(p&&j<i){ p=p->next; ++j; } if(!p||j>i) return0; e=p->data; p->prior->next=p->next;C++数据结构实例代码全文共35页，当前为第10页。 p->next->prior=p->prior;C++数据结构实例代码全文共35页，当前为第10页。 free(p); return1;}intGetElem(DLinkList&L,inti){ DLinkListp,s; p=L->next; intj=1; while(p&&j<i){ p=p->next; ++j; } if(!p||j>i) return0; inte=p->data; returne;}intmain(){ DLinkListlx; InitList(lx);C++数据结构实例代码全文共35页，当前为第11页。 for(inti=1;i<6;i++)C++数据结构实例代码全文共35页，当前为第11页。 { ListInsert(lx,i,2*i-1); } for(intj=1;j<6;j++){ cout<<GetElem(lx,j)<<""; } cout<<endl; inte; ListDelete(lx,2,e); cout<<e<<endl; for(intj=1;j<5;j++){ cout<<GetElem(lx,j)<<""; } system("pause"); return0;}1357931579请按任意键继续...4顺序栈#include"iostream"C++数据结构实例代码全文共35页，当前为第12页。#include"malloc.h"C++数据结构实例代码全文共35页，当前为第12页。usingnamespacestd;#defineSTACK_INIT_SIZE100//存ä?储ä¡é空?间?初?始º?分¤?配?量¢?#defineSTACKINCREMENT10//存ä?储ä¡é空?间?分¤?配?增?量¢?typedefstruct{ int*base; int*top; intstacksize;}Stack;intInitStack(Stack&S){ S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int)); if(!S.base) exit(-2); S.top=S.base; S.stacksize=STACK_INIT_SIZE; return1;}intGetTop(Stack&S,int&e){ if(S.top==S.base)C++数据结构实例代码全文共35页，当前为第13页。 return0;C++数据结构实例代码全文共35页，当前为第13页。 e=*(S.top-1); return1;}intPush(Stack&S,inte){ if(S.top-S.base>=S.stacksize){ S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int)); if(!S.base) exit(-2); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *S.top++=e;}intPop(Stack&S,int&e){ if(S.top==S.base) return0; e=*--S.top; return1;C++数据结构实例代码全文共35页，当前为第14页。}C++数据结构实例代码全文共35页，当前为第14页。intmain(){ Stacklx; InitStack(lx); for(inti=1;i<6;i++) { Push(lx,i); } inte; GetTop(lx,e); cout<<e<<endl; inte1; Pop(lx,e1); cout<<e1<<endl; GetTop(lx,e1); cout<<e1<<endl; system("pause"); return0;}55C++数据结构实例代码全文共35页，当前为第15页。4C++数据结构实例代码全文共35页，当前为第15页。请按任意键继续...5队列#include"iostream"#include"malloc.h"usingnamespacestd;typedefstructQNode{ intdata; structQNode*next;}QNode,*QueuePtr;typedefstruct{ QueuePtrfront; QueuePtrrear;}LinkQueue;intInitQueue(LinkQueue&Q){ Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q.front) exit(-2); Q.front->next=NULL; return1;}C++数据结构实例代码全文共35页，当前为第16页。intDestroyQueue(LinkQueue&Q)C++数据结构实例代码全文共35页，当前为第16页。{ while(Q.front){ Q.rear=Q.front->next; free(Q.front); Q.front=Q.rear; } return1;}intInsert(LinkQueue&Q,inte){ QueuePtrp=(QueuePtr)malloc(sizeof(QNode)); if(!p) exit(-2); p->data=e; p->next=NULL; Q.rear->next=p; Q.rear=p; return1;}intGetFront(LinkQueue&Q,int&e){C++数据结构实例代码全文共35页，当前为第17页。 if(Q.front==Q.rear)C++数据结构实例代码全文共35页，当前为第17页。 return0; e=Q.front->next->data; return1;}intGetRear(LinkQueue&Q,int&e){ if(Q.front==Q.rear) return0; e=Q.rear->data; return1;}intDelete(LinkQueue&Q,int&e){ if(Q.front==Q.rear) return0; QueuePtrp; p=Q.front->next;e=p->data; Q.front->next=p->next; if(Q.rear==p) Q.rear=Q.front;C++数据结构实例代码全文共35页，当前为第18页。 free(p);C++数据结构实例代码全文共35页，当前为第18页。 return1;}intmain(){ LinkQueuelx; InitQueue(lx); for(inti=1;i<6;i++){ Insert(lx,i); } intfront; GetFront(lx,front); cout<<front<<endl; intrear; GetRear(lx,rear); cout<<rear<<endl; inte; Delete(lx,e); cout<<e<<endl; GetFront(lx,front); cout<<front<<endl; system("pause");C++数据结构实例代码全文共35页，当前为第19页。 return0;C++数据结构实例代码全文共35页，当前为第19页。}1512请按任意键继续...6循环队列#include"iostream"#include"malloc.h"usingnamespacestd;#defineMAXSIZE100typedefstruct{ int*base; intfront; intrear;}SqQueue;intInit(SqQueue&Q){ Q.base=(int*)malloc(MAXSIZE*sizeof(int)); if(!Q.base) exit(-2);C++数据结构实例代码全文共35页，当前为第20页。 Q.front=Q.rear=0;C++数据结构实例代码全文共35页，当前为第20页。 return1;}intQueueLength(SqQueue&Q){ return(Q.rear-Q.front+MAXSIZE)%MAXSIZE;}intEnQueue(SqQueue&Q,inte){ if((Q.rear+1)%MAXSIZE==Q.front) return0; Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MAXSIZE; return1;}intDeQueue(SqQueue&Q,int&e){ if(Q.front==Q.rear) return0; e=Q.base[Q.front]; Q.front=(Q.front+1)%MAXSIZE; return1;C++数据结构实例代码全文共35页，当前为第21页。}C++数据结构实例代码全文共35页，当前为第21页。intGetFront(SqQueue&Q){ inte=Q.base[Q.front]; returne;}intGetrear(SqQueue&Q){ inte=Q.base[Q.rear-1]; returne;}intmain(){ SqQueuelx; Init(lx); for(inti=1;i<6;i++){ EnQueue(lx,i); } cout<<QueueLength(lx)<<endl; cout<<GetFront(lx)<<endl; cout<<Getrear(lx)<<endl; intm;C++数据结构实例代码全文共35页，当前为第22页。 DeQueue(lx,m);C++数据结构实例代码全文共35页，当前为第22页。 cout<<m<<endl; cout<<GetFront(lx)<<endl; system("pause"); return0;}51512请按任意键继续...7顺序表字符串#include"iostream"#include"malloc.h"usingnamespacestd;#defineOK1#defineERROR0typedefstruct{ char*ch; intlength;}HString;C++数据结构实例代码全文共35页，当前为第23页。intStrAssign(HString&T,char*chars)C++数据结构实例代码全文共35页，当前为第23页。{ T.ch=(char*)malloc(sizeof(char)); if(T.ch) free(T.ch); //inti=strlen(chars); inti=0; char*c; for(c=chars;*c;++i,++c);//判D断?条¬?件t为a*c!='\0' if(!i){ T.ch=NULL; T.length=0; } T.ch=(char*)malloc(i*sizeof(char)); for(intj=0;j<i;j++) { T.ch[j]=chars[j]; } T.length=i; returnOK;0}intStrLength(HString&S)C++数据结构实例代码全文共35页，当前为第24页。{C++数据结构实例代码全文共35页，当前为第24页。 returnS.length;}intConcat(HString&T,HString&S1,HString&S2){ T.ch=(char*)malloc((S1.length+S2.length)*sizeof(char)); for(inti=0;i<S1.length;i++){ T.ch[i]=S1.ch[i]; } T.length=S1.length+S2.length; for(intj=0;j<S2.length;j++) { T.ch[S1.length+j]=S2.ch[j]; } returnOK;}intSubString(HString&Sub,HString&S,intpos,intlen){ if(pos<1||pos>S.length||len<0||len>S.length-pos+1){ returnERROR; } Sub.length=len;C++数据结构实例代码全文共35页，当前为第25页。 Sub.ch=(char*)malloc(len*sizeof(char));C++数据结构实例代码全文共35页，当前为第25页。 for(inti=0;i<len;i++){ Sub.ch[i]=S.ch[pos+i]; } returnOK;}intPrint(HString&T){ for(inti=0;i<T.length;i++) { cout<<T.ch[i]<<""; } cout<<endl; returnOK;}intmain(){ HStringlx,hhc; StrAssign(lx,"huanhuncao"); StrAssign(hhc,"lixing"); Print(lx); Print(hhc); cout<<StrLength(lx)<<endl;C++数据结构实例代码全文共35页，当前为第26页。 cout<<StrLength(hhc)<<endl;C++数据结构实例代码全文共35页，当前为第26页。 HStringlx1; lx1.ch=(char*)malloc((lx.length+hhc.length)*sizeof(char)); Concat(lx1,lx,hhc); Print(lx1); HStringlx2; SubString(lx2,lx1,2,3); Print(lx2); system("pause"); return0;}huanhuncaolixing106huanhuncaolixinganh请按任意键继续...8链式字符串就是线性表的链式表示一样9数组的表示#include"iostream"C++数据结构实例代码全文共35页，当前为第27页。#include"stdarg.h"//提供宏va_startC++数据结构实例代码全文共35页，当前为第27页。#include"malloc.h"usingnamespacestd;#defineMAX_ARRAY_DIM8#defineOK1#defineERROR0typedefstruct{ int*base; intdim; int*bounds; int*constants; intelemtotal;}Array;intInitArray(Array&A,intdim,...){ if(dim<1||dim>MAX_ARRAY_DIM) returnERROR; A.dim=dim; cout<<"数组维数是："<<A.dim<<endl; A.bounds=(int*)malloc(dim*sizeof(int)); if(!A.bounds)C++数据结构实例代码全文共35页，当前为第28页。 exit(-2);C++数据结构实例代码全文共35页，当前为第28页。 intelemtotal=1; va_listap; va_start(ap,dim); cout<<"数组每维元素数目分别是："<<""; for(inti=0;i<dim;i++){ A.bounds[i]=va_arg(ap,int); cout<<A.bounds[i]<<""; if(A.bounds[i]<0){ return-2;} elemtotal*=A.bounds[i]; } cout<<endl; cout<<"数组元素数目是："<<elemtotal<<endl; A.elemtotal=elemtotal; va_end(ap); A.base=(int*)malloc(elemtotal*sizeof(int)); *(A.base)=0; if(!A.base) exit(-2); A.constants=(int*)malloc(dim*sizeof(int)); if(!A.constants)C++数据结构实例代码全文共35页，当前为第29页。 exit(-2);C++数据结构实例代码全文共35页，当前为第29页。 A.constants[dim-1]=1; for(inti=dim-2;i>=0;--i){ A.constants[i]=A.bounds[i+1]*A.constants[i+1]; } returnOK;}intDestroyArray(Array&A){ if(!A.base) returnERROR; free(A.base); A.base=NULL; if(!A.bounds) returnERROR; free(A.bounds); A.bounds=NULL; if(!A.constants) returnERROR; A.constants=NULL; returnOK;}intLocate(Array&A,va_listap,int&off)C++数据结构实例代码全文共35页，当前为第30页。{C++数据结构实例代码全文共35页，当前为第30页。 off=0; intind=0; for(inti=0;i<A.dim;i++){ ind=va_arg(ap,int); if(ind<0||ind>=A.bounds[i]) return-1; off+=A.constants[i]*ind; } returnOK;}intreturnLocate(Array&A,intany,...){ intoff=0; va_listap; va_start(ap,any); intind=0; for(inti=0;i<A.dim;i++){ ind=va_arg(ap,int); if(ind<0||ind>=A.bounds[i]) return-1; off+=A.constants[i]*ind;C++数据结构实例代码全文共35页，当前为第31页。 }C++数据结构实例代码全文共35页，当前为第31页。 va_end(ap); returnoff;}intValue(Array&A,intany,...){ i