C++数据结构实例代码

1、1 线性表的顺序表示#include"iostream"#include"malloc.h"using namespacestd;typedefstruct int*elem;intlength;intlistsize;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, in

2、t e) if (i<1|i>L.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;in

3、t ListDelete(SqList &L, int i, int &e) if (i<1|i>L.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;-L.length; return e;int main()int a6=1,2,3,4,5;int *q=&a1;int *p=&a4; for (p;p>=q;-p) *(p+1)=*p;*q=3;for ( int i=0;i<6;i

4、+) cout<<ai<< " " ; cout<<endl; SqList lx;Init_Sq(lx);for ( int j=1;j<10;j+) ListInsert(lx,j,j);ListInsert(lx,3,55); int e_return;ListDelete(lx,4,e_return); for ( int m=0;m<10;m+) cout<<*(lx.elem+m)<< " " cout<<endl;cout<<e_return;

5、system( "pause" ); return 0;1 3 2 3 4 51 2 55 4 5 6 7 8 9 93 请按任意键继续 . . .2 线性表的链性表示 #include "iostream" #include "malloc.h" using namespacestd; typedef struct LNode int data;struct LNode *next;LNode,*LinkList;int InitList(LinkList &L)L=(LinkList)malloc( sizeof (LNo

6、de); L->next=NULL;return 1;int ListInsert(LinkList &L, int i, int e)LinkList p=L;int j=0;while (p&&j<i-1) p=p->next; +j;if (!p|j>i-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

7、, int i)LinkList p=L;int j=0;while (p->next&&j<i-1) p=p->next; +j;if (!(p->next)|j>i-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&&j<i)p=p->next;+j;if (!p|j<i)ret

8、urn 0;int e=p->data; return e;int main()LinkList lx;InitList(lx);for ( int i=1;i<6;i+)ListInsert(lx,i,i);ListDelete(lx,2);for ( int j=1;j<5;j+)cout<<GetElem(lx,j)<< " " cout<<endl;LinkList lx1,lx2;InitList(lx1);InitList(lx2);for ( int m=1;m<6;m+)ListInsert(lx1

9、,m,m);for ( int n=1;n<6;n+) ListInsert(lx2,n,2*n);for ( int j=1;j<6;j+)cout<<GetElem(lx1,j)<< " " system( "pause" ); return 0;1 3 4 51 2 3 4 5 请按任意键继续 . . .3 双向链表#include "iostream"#include "malloc.h" using namespacestd; typedef struct dlist

10、int data;struct dlist *prior; struct dlist *next; DList,*DLinkList;void InitList(DLinkList &L)L=(DLinkList)malloc( sizeof (DList);L->next=L;L->prior=L;int ListInsert(DLinkList &L, int i, int e)DLinkList p,s;p=L->next;int j=1;while (p&&j<i)p=p->next;+j;if (!p|j>i)ret

11、urn 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&&j<i) p=p->next;+j;if (!p|j>i) return 0;e=p->

12、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&&j<i)p=p->next;+j;if (!p|j>i)return 0;int e=p->data;return e;int main()DLinkList lx;InitList(lx);for ( int i=1

13、;i<6;i+)ListInsert(lx,i,2*i-1);for ( int j=1;j<6;j+) cout<<GetElem(lx,j)<< " " cout<<endl;int e;ListDelete(lx,2,e); cout<<e<<endl;for ( int j=1;j<5;j+) cout<<GetElem(lx,j)<< " "system( "pause" );return 0;1 3 5 7 931 5 7

14、 9 请按任意键继续 . . .4 顺序栈#include "iostream"#include "malloc.h"using namespacestd;#define STACK_INIT_SIZE 100 存？?储?e空?间？初？始0?分O?配？量 C?#define STACKINCREMENT 10存？储?e空?间？分O?配？增？量 C?typedef struct int *base;int *top;int stacksize;Stack;int InitStack(Stack &S)S.base=( int *)malloc(ST

15、ACK_INIT_SIZE* sizeof (int );if (!S.base)exit(-2);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return 1;int GetTop(Stack &S, int &e)if (S.top=S.base)return 0;e=*(S.top-1);return 1;int Push(Stack &S, int e)if (S.top-S.base>=S.stacksize)S.base=( int *)realloc(S.base,(S.stacksize+STACKINCREM

16、ENT)* 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;i<6;i+)Push(lx,i);int e;GetTop(lx,e); cout<<e<<endl;in

17、t e1;Pop(lx,e1); cout<<e1<<endl; GetTop(lx,e1); cout<<e1<<endl; system( "pause" ); return 0;554 请按任意键继续 . . .5 队列 #include "iostream" #include "malloc.h" using namespacestd; typedef struct QNode int data;struct QNode *next; QNode,*QueuePtr; typed

18、ef struct QueuePtr front;QueuePtr rear; LinkQueue;int InitQueue(LinkQueue &Q) Q.front=Q.rear=(QueuePtr)malloc( sizeof (QNode); if (!Q.front)exit(-2); Q.front->next=NULL; return 1;int DestroyQueue(LinkQueue &Q)while (Q.front) Q.rear=Q.front->next; free(Q.front); Q.front=Q.rear; return 1

19、;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 &

20、amp;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

21、); for ( int i=1;i<6;i+) Insert(lx,i);int front; GetFront(lx,front); cout<<front<<endl; int rear;GetRear(lx,rear); cout<<rear<<endl; int e;Delete(lx,e); cout<<e<<endl; GetFront(lx,front); cout<<front<<endl; system( "pause" ); return 0;1512

22、 请按任意键继续 . . .6 循环队列#include "iostream"#include "malloc.h" using namespacestd;#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 QueueLe

23、ngth(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;ret

24、urn 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;i<6;i+) EnQueue(lx,i); cout<<QueueLength(lx)<<endl; cout<<GetFront(lx)<<endl; cout<<Getrear(lx)<&l

25、t;endl;int m;DeQueue(lx,m); cout<<m<<endl; cout<<GetFront(lx)<<endl; system( "pause" );return 0;51512 请按任意键继续 . . .7 顺序表字符串#include "iostream"#include "malloc.h"using namespacestd;#define OK 1#define ERROR 0typedef struct char *ch;int length;HStr

26、ing;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;j<i;j+)T.chj=charsj;T

27、.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;i<S1.length;i+)T.chi=S1.chi;T.length=S1.length+S2.length;for ( int j=0;j<S2.length;j+)T.chS1.leng

28、th+j=S2.chj;return OK;int SubString(HString &Sub,HString &S,int pos, int len)if (pos<1|pos>S.length|len<0|len>S.length-pos+1)return ERROR;Sub.length=len;Sub.ch=( char *)malloc(len* sizeof (char );for ( int i=0;i<len;i+)Sub.chi=S.chpos+i;return OK;int Print(HString &T)for (

29、 int i=0;i<T.length;i+) cout<<T.chi<< " " ;cout<<endl;return OK;int main()HString lx,hhc;StrAssign(lx, "huanhuncao" );StrAssign(hhc, "lixing" );Print(lx);Print(hhc); cout<<StrLength(lx)<<endl; cout<<StrLength(hhc)<<endl;HStri

30、ng 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 g106 h u a n h u n c a o l i x i n g a n h请按任意键继续 . . .8 链式字符串就是线性表的链式表示一样9 数组的表示 #incl

31、ude "iostream"#include "stdarg.h"/ 提供宏 va_start #include "malloc.h" using 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(dim<1|dim

32、>MAX_ARRAY_DIM)return ERROR;A.dim=dim;cout<<" 数组维数是： "<<A.dim<<endl; 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;i<dim;i+)A.boundsi=

33、va_arg(ap,int); cout<<A.boundsi<<" " if(A.boundsi<0)return -2;elemtotal *=A.boundsi;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.

34、constants=(int *)malloc(dim*sizeof(int); if(!A.constants)exit(-2);A.constantsdim-1=1;for(int i=dim-2;i>=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

35、(!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;i<A.dim;i+) ind=va_arg(ap,int); if(ind<0|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;i<A.dim;i+) ind=va_arg(ap,int); if(ind<0|ind>=A.bo