C++数据结构实例代码

1、1线性表的顺序表示 #include "iostream" #include "malloc.h" using namespacestd; 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 &

2、;L, int i, int 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.le

3、ngth; return 1;int 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;

4、for (int i=0;i<6;i+) 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 (LNode);L-&g

6、t;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, int i)LinkL

7、ist 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) return 0;int e=p

8、->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,m,m);for (int n=1;n<6;n+)

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

10、kList;voidInitList(DLinkList &L)L=(DLinkList)malloc(L->next=L;L->prior=L;sizeof (DList);intListInsert(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)return 0;s=(DLinkList)malloc( s->data=e;s->prior=p->prior

11、; p->prior->next=s; s->next=p;sizeof (DList);p->prior=s;return 1;intListDelete(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->data;p->prior->next=p->next;p->next->prior=p->prio

12、r; 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;i<6;i+)ListInsert(lx,i,2*i-1);for (int j=1;j<6;j+) cout<&

13、lt;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 9请按任意键继续.4顺序栈#include "iostream"#include "malloc.h" using namespacestd;#defin

14、e STACK_INIT_SIZE 100/ 存？储？ 6空？间？初？始o?分。？配？量 0?#define STACKINCREMENT /0存？?储？心？间?分。？配？增？量 0?typedef struct int *base; int *top; int stacksize;Stack;int InitStack(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; return 1

15、; 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+STACKINCREMENT)* sizeof (int ); if (!S.base) exit(-2);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMEN

16、T;*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; int e1;Pop(lx,e1); cout<<e1<<endl;GetTop(lx,e1); cout<<e1<<endl; sy

17、stem( "pause");return 0;554请按任意键继续.5队列#include "iostream"#include "malloc.h" using namespacestd; typedef struct QNode int data;struct QNode *next;QNode,*QueuePtr; typedef struct QueuePtr front; QueuePtr rear;LinkQueue;int InitQueue(LinkQueue &Q) Q.front=Q.rear=(Queu

18、ePtr)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;int Insert(LinkQueue &Q, int e)QueuePtr p=(QueuePtr)malloc( sizeof (QNode);if (!p)exit(-2);p->data=e;

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

20、.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;i<6;i+) Insert(lx,i);int front;GetFront(lx,front); cout<<front<<endl; int rear;GetRear(lx,

21、rear); cout<<rear<<endl; int e;Delete(lx,e); cout<<e<<endl; GetFront(lx,front); cout<<front<<endl; system( "pause"); return 0;1512请按任意键继续.6循环队列#include "iostream"#include "malloc.h"using namespacestd;#define MAXSIZE 100 typedef struct

22、 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) re

23、turn 0;Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAXSIZE; return 1; int DeQueue(SqQueue &Qjnt &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

24、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)<<endl;int m;DeQueue(lx,m);cout<<m<<endl;cout<<GetFront(lx)<<endl;system( "pause"); return 0;515

25、12请按任意键继续一.7顺序表字符串#include "iostream"#include "malloc.h" using namespacestd;#define OK 1#define ERROR 0typedef 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

26、*c;for (c=chars;*c;+i,+c);/ 判 D断?条？?件t 为a*c!='0'if (!i)ch=NULL;T.length=0;T.ch=( char*)malloc(i* sizeof (char);for (int j=0;j<i;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 *)mall

27、oc(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.length+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

28、+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 (int i=0;i<T.length;i+) cout<<T.chi<< "" cout<<endl; return OK; int main()HString lx,hhc;StrAssign(lx, "huan

29、huncao");StrAssign(hhc, "lixing");Print(lx);Print(hhc);sizeof (char);cout<<StrLength(lx)<<endl; cout<<StrLength(hhc)<<endl; HString lx1;lx1.ch=( char *)malloc(lx.length+hhc.length)* Concat(lx1,lx,hhc);Print(lx1);HString lx2;SubString(lx2,lx1,2,3);Print(lx2);sys

30、tem( "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.h" using namespace std;#define MAX_ARRAY_DIM 8#define OK 1#define E

31、RROR 0typedef structint *base;int dim;int *bounds;int "constants;int elemtotal;Array;int InitArray(Array &A,int dim,.)if(dim<1|dim>MAX_ARRAY_DIM) return ERROR;A.dim=dim;cout<<"数组维数是："<<A.dim<<endl; A.bounds=(int *)malloc(dim*sizeof(int);if(!A.bounds)exit(-2

32、);int elemtotal=1;va_list ap;va_start(ap,dim);cout<”数组每维元素数目分别是："<<""for(int i=0;i<dim;i+) A.boundsi=va_arg(ap,int); cout<<A.boundsi<<""if(A.boundsi<0) return -2;elemtotal *=A.boundsi;cout<<endl;cout<<"数组元素数目是："<<elemtot

33、al<<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);A.constantsdim -1=1;for(int i=dim -2;i>=0;-i)A.constantsi=A.boundsi+1*A.constantsi+1;return OK;int DestroyA

34、rray(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;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.b