C++数据结构实例代码.doc

1 线性表的顺序表示#include iostream#include malloc.husing namespace std;typedef structint *elem;int length;int listsize;SqList;int Init_Sq(SqList &L)L.elem=(int *)malloc(100*sizeof(int);if(!L.elem)exit(-2);L.length=0;L.listsize=100;return 1;int ListInsert(SqList &L,int i,int e)if(iL.length+1)return 0;if(L.length=L.listsize)int *newbase=(int *)realloc(L.elem,(L.listsize+10)*sizeof(int);if(!newbase)exit(-2);L.elem=newbase;L.listsize+=10;int *q=&(L.elemi-1);int *p=&(L.elemL.length-1);for(p;p=q;-p)*(p+1)=*p;*q=e;+L.length;return 1;int ListDelete(SqList &L,int i,int &e)if(iL.length)return 0;int *p=&(L.elemi-1);e=*p;int *q=L.elem+L.length-1;for(+p;p=q;-p)*(p+1)=*p;*q=3;for(int i=0;i6;i+)coutai ;coutendl;SqList lx;Init_Sq(lx);for(int j=1;j10;j+)ListInsert(lx,j,j);ListInsert(lx,3,55);int e_return;ListDelete(lx,4,e_return);for(int m=0;m10;m+)cout*(lx.elem+m) ;coutendl;coutnext=NULL;return 1;int ListInsert(LinkList &L,int i,int e)LinkList p=L;int j=0;while(p&jnext;+j;if(!p|ji-1)return 0;LinkList s=(LinkList)malloc(sizeof(LNode);s-data=e;s-next=p-next;p-next=s;return 1;int ListDelete(LinkList &L,int i)LinkList p=L;int j=0;while(p-next&jnext;+j;if(!(p-next)|ji-1)return 0;LinkList q=p-next;p-next=q-next;free(q);return 1;int GetElem(LinkList L,int i)LinkList p=L-next;int j=1;while(p&jnext;+j;if(!p|jdata;return e;int main()LinkList lx;InitList(lx);for(int i=1;i6;i+)ListInsert(lx,i,i);ListDelete(lx,2);for(int j=1;j5;j+)coutGetElem(lx,j) ;coutendl;LinkList lx1,lx2;InitList(lx1);InitList(lx2);for(int m=1;m6;m+)ListInsert(lx1,m,m);for(int n=1;n6;n+)ListInsert(lx2,n,2*n);for(int j=1;j6;j+)coutGetElem(lx1,j)next=L;L-prior=L;int ListInsert(DLinkList &L,int i,int e)DLinkList p,s;p=L-next;int j=1;while(p&jnext;+j;if(!p|ji)return 0;s=(DLinkList)malloc(sizeof(DList);s-data=e;s-prior=p-prior;p-prior-next=s;s-next=p;p-prior=s;return 1;int ListDelete(DLinkList &L,int i,int &e)DLinkList p;p=L-next;int j=1;while(p&jnext;+j;if(!p|ji)return 0;e=p-data;p-prior-next=p-next;p-next-prior=p-prior;free(p);return 1;int GetElem(DLinkList &L,int i)DLinkList p,s;p=L-next;int j=1;while(p&jnext;+j;if(!p|ji)return 0;int e=p-data;return e;int main()DLinkList lx;InitList(lx);for(int i=1;i6;i+)ListInsert(lx,i,2*i-1);for(int j=1;j6;j+)coutGetElem(lx,j) ;coutendl;int e;ListDelete(lx,2,e);couteendl;for(int j=1;j5;j+)coutGetElem(lx,j)=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;int Pop(Stack &S,int &e)if(S.top=S.base)return 0;e=*-S.top;return 1;int main()Stack lx;InitStack(lx);for(int i=1;i6;i+)Push(lx,i);int e;GetTop(lx,e);couteendl;int e1;Pop(lx,e1);coute1endl;GetTop(lx,e1);coute1next=NULL;return 1;int DestroyQueue(LinkQueue &Q)while(Q.front)Q.rear=Q.front-next;free(Q.front);Q.front=Q.rear;return 1;int Insert(LinkQueue &Q,int e)QueuePtr p=(QueuePtr)malloc(sizeof(QNode);if(!p)exit(-2);p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return 1;int GetFront(LinkQueue &Q,int &e)if(Q.front=Q.rear)return 0;e=Q.front-next-data;return 1;int GetRear(LinkQueue &Q,int &e)if(Q.front=Q.rear)return 0;e=Q.rear-data;return 1;int Delete(LinkQueue &Q,int &e)if(Q.front=Q.rear)return 0;QueuePtr p;p=Q.front-next; e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);return 1;int main()LinkQueue lx;InitQueue(lx);for(int i=1;i6;i+)Insert(lx,i);int front;GetFront(lx,front);coutfrontendl;int rear;GetRear(lx,rear);coutrearendl;int e;Delete(lx,e);couteendl;GetFront(lx,front);coutfrontendl;system(pause);return 0;1512请按任意键继续. . .6 循环队列 #include iostream#include malloc.husing namespace std;#define MAXSIZE 100typedef structint *base;int front;int rear;SqQueue;int Init(SqQueue &Q)Q.base=(int *)malloc(MAXSIZE*sizeof(int);if(!Q.base)exit(-2);Q.front=Q.rear=0;return 1;int QueueLength(SqQueue &Q)return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;int EnQueue(SqQueue &Q,int e)if(Q.rear+1)%MAXSIZE=Q.front)return 0;Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAXSIZE;return 1;int DeQueue(SqQueue &Q,int &e)if(Q.front=Q.rear)return 0;e=Q.baseQ.front;Q.front=(Q.front+1)%MAXSIZE;return 1;int GetFront(SqQueue &Q)int e=Q.baseQ.front;return e;int Getrear(SqQueue &Q)int e=Q.baseQ.rear-1;return e;int main()SqQueue lx;Init(lx);for(int i=1;i6;i+)EnQueue(lx,i);coutQueueLength(lx)endl;coutGetFront(lx)endl;coutGetrear(lx)endl;int m;DeQueue(lx,m);coutmendl;coutGetFront(lx)endl;system(pause);return 0;51512请按任意键继续. . .7 顺序表字符串#include iostream#include malloc.husing namespace std;#define OK 1#define ERROR 0typedef structchar *ch;int length;HString;int StrAssign(HString &T,char *chars)T.ch=(char *)malloc(sizeof(char);if(T.ch)free(T.ch);/int i=strlen(chars);int i=0;char *c;for(c=chars;*c;+i,+c);/判D断?条?件t为a*c!=0if(!i)T.ch=NULL;T.length=0;T.ch=(char*)malloc(i*sizeof(char);for(int j=0;ji;j+)T.chj=charsj;T.length=i;return OK;0int StrLength(HString &S)return S.length;int Concat(HString &T,HString &S1,HString &S2)T.ch=(char *)malloc(S1.length+S2.length)*sizeof(char);for(int i=0;iS1.length;i+)T.chi=S1.chi;T.length=S1.length+S2.length;for(int j=0;jS2.length;j+)T.chS1.length+j=S2.chj;return OK;int SubString(HString &Sub,HString &S,int pos,int len)if(posS.length|lenS.length-pos+1)return ERROR;Sub.length=len;Sub.ch=(char *)malloc(len*sizeof(char);for(int i=0;ilen;i+)Sub.chi=S.chpos+i;return OK;int Print(HString &T)for(int i=0;iT.length;i+)coutT.chi ;coutendl;return OK;int main()HString lx,hhc;StrAssign(lx,huanhuncao);StrAssign(hhc,lixing);Print(lx);Print(hhc);coutStrLength(lx)endl;coutStrLength(hhc)endl;HString lx1;lx1.ch=(char *)malloc(lx.length+hhc.length)*sizeof(char);Concat(lx1,lx,hhc);Print(lx1);HString lx2;SubString(lx2,lx1,2,3);Print(lx2);system(pause);return 0;h u a n h u n c a ol i x i n g106h u a n h u n c a o l i x i n ga n h请按任意键继续. . .8 链式字符串就是线性表的链式表示一样9 数组的表示 #include iostream#include stdarg.h/提供宏va_start#include malloc.husing namespace std;#define MAX_ARRAY_DIM 8#define OK 1#define ERROR 0typedef structint *base;int dim;int *bounds;int *constants;int elemtotal;Array;int InitArray(Array &A,int dim,.)if(dimMAX_ARRAY_DIM)return ERROR;A.dim=dim;cout数组维数是：A.dimendl;A.bounds=(int *)malloc(dim*sizeof(int);if(!A.bounds)exit(-2);int elemtotal=1;va_list ap;va_start(ap,dim);cout数组每维元素数目分别是： ;for(int i=0;idim;i+)A.boundsi=va_arg(ap,int);coutA.boundsi ;if(A.boundsi0)return -2;elemtotal *=A.boundsi;coutendl;cout数组元素数目是：elemtotal=0;-i)A.constantsi=A.boundsi+1*A.constantsi+1;return OK;int DestroyArray(Array &A)if(!A.base)return ERROR;free(A.base);A.base=NULL;if(!A.bounds)return ERROR;free(A.bounds);A.bounds=NULL;if(!A.constants)return ERROR;A.constants=NULL;return OK;int Locate(Array &A,va_list ap,int &off)off=0;int ind=0;for(int i=0;iA.dim;i+)ind=va_arg(ap,int);if(ind=A.boundsi)return -1;off+=A.constantsi*ind;return OK;int returnLocate(Array &A,int any,.)int off=0;va_list ap;va_start(ap,any);int ind=0;for(int i=0;iA.dim;i+)ind=va_arg(ap,int);if(ind=A.boundsi)return -1;off+=A.constantsi*ind;va_end(ap);return off;int Value(Array &A,int any,.)int e;int off=0;va_list ap;va_start(ap,any);int ind=0;for(int i=0;iA.dim;i+)ind=va_arg(ap,i