C++数据结构实例代码

线性表的顺序表示#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){int*newbase=(int1/35下载文档可编辑*)realloc(L.elem,(L.listsize+10)*sizeof(int));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;for(++p;p<=q;++p){2/35下载文档可编辑*(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);}3/35下载文档可编辑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请按任意键继续...线性表的链性表示#include"iostream"#include"malloc.h"usingnamespacestd;typedefstructLNode{intdata;structLNode*next;4/35下载文档可编辑}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;return1;5/35下载文档可编辑}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){6/35下载文档可编辑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;LinkListlx1,lx2;7/35下载文档可编辑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 请按任意键继续...双向链表#include"iostream"#include"malloc.h"usingnamespacestd;typedefstructdlist8/35下载文档可编辑{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)return0;9/35下载文档可编辑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;p->next->prior=p->prior;/35下载文档可编辑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);for(inti=1;i<6;i++)/35下载文档可编辑{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 请按任意键继续...顺序栈#include"iostream"#include"malloc.h"/35下载文档可编辑usingnamespacestd;#defineSTACK_INIT_SIZE100// 存??储??é空?间?初?始o?分¤?配?量￠?#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)return0;/35下载文档可编辑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;}/35下载文档可编辑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;}554/35下载文档可编辑请按任意键继续...队列#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;}intDestroyQueue(LinkQueue&Q)/35下载文档可编辑{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){if(Q.front==Q.rear)/35下载文档可编辑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;free(p);/35下载文档可编辑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");return0;/35下载文档可编辑}1512请按任意键继续...循环队列#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);Q.front=Q.rear=0;/35下载文档可编辑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;}/35下载文档可编辑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;DeQueue(lx,m);/35下载文档可编辑cout<<m<<endl;cout<<GetFront(lx)<<endl;system("pause");return0;}51512请按任意键继续...顺序表字符串#include"iostream"#include"malloc.h"usingnamespacestd;#defineOK1#defineERROR0typedefstruct{char*ch;intlength;}HString;intStrAssign(HString&T,char*chars)/35下载文档可编辑{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){/35下载文档可编辑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;Sub.ch=(char*)malloc(len*sizeof(char));/35下载文档可编辑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;cout<<StrLength(hhc)<<endl;/35下载文档可编辑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请按任意键继续...链式字符串就是线性表的链式表示一样数组的表示#include"iostream"#include"stdarg.h"// 提供宏va_start/35下载文档可编辑#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)exit(-2);/35下载文档可编辑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)exit(-2);/35下载文档可编辑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){/35下载文档可编辑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;}/35下载文档可编辑va_end(ap);returnoff;}intValue(Array&A,intany,...){inte;intoff=0;va_listap;va_start(ap,any);