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

1 线性表的顺序表示#include iostream#include malloc.h using namespace std;typedef struct int*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;1 5 1 2 请按任意键继续.6 循环队列#include iostream#include malloc.h using namespace std;#define MAXSIZE 100 typedef struct int*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;5 1 5 1 2 请按任意键继续.7 顺序表字符串#include iostream#include malloc.h using namespace std;#define OK 1#define ERROR 0 typedef struct char*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!=0 if(!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;0 int 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 o l i x i n g 10 6 h u a n h u n c a o l i x i n g a n h 请按任意键继续.8 链式字符串就是线性表的链式表示一样 9 数组的表示#include iostream#include stdarg.h/提供宏 va_start#include malloc.h using namespace std;#define MAX_ARRAY_DIM 8#define OK 1#define ERROR 0 typedef struct int*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,int);if(ind=A.boundsi)return-1;off+=A.constantsi*ind;va_end(ap);e=*(A.base+off);return e;int Assign(Array&A,int e,.)int off=0;va_list ap;va_start(ap,e);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);*(A.base+off)=e;return OK;int main()Array lx;InitArray(lx,2,3,4);/构造一个二维数组，前面 2 是维数，后面两个数字是每维的长度 /上图是 3 行 4 列的二维数组，行的下标是 0,1,2，列的下标是 0,1,2,3 /InitArray(lx1,3,2,3,4);/三维数组的写法 coutlx23的相对地址为：returnLocate(lx,-1,2,3)endl;/这里的2和3都是下标，相当于是 a23,所以地址为 11，也就是最后一个元素的地址，地址是从 0 开始的 coutlx00的相对地址为：returnLocate(lx,-1,0,0)endl;Assign(lx,108,0,0);coutlx00的值为：Value(lx,-1,0,0)endl;Assign(lx,257,1,1);coutlx11的值为：Value(lx,-1,1,1)endl;system(pause);return 0;数组维数是：2 数组每维元素数目分别是：3 4 数组元素数目是：12 lx23的相对地址为：11 lx00的相对地址为：0 lx00的值为：108 lx11的值为：257 请按任意键继续.