数据结构上机答案

数据结构上机答案

1.1顺序线性表的基本操作 #include #include #define OK 1 #define ERROR 0

#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 #define ElemType int

typedef struct { int *elem,length,listsize; }SqList;

int InitList_Sq(SqList &L) { L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); L.length=0; L.listsize=LIST_INIT_SIZE; return OK; }

int Load_Sq(SqList &L) { int i; if(L.length==0) printf(\ else { printf(\ for(i=0;i

int ListInsert_Sq(SqList &L,int i,int e) { if(i<1||i>L.length+1) return ERROR; ElemType *newbase,*q,*p; if(L.length>=L.listsize)

{ newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType)); L.elem=newbase; L.listsize+=LISTINCREMENT; } q=&(L.elem[i-1]); for(p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p; *q=e; ++L.length; return OK; }

int ListDelete_Sq(SqList &L,int i,int &e) { ElemType *q,*p; if(i<1||i>L.length) return ERROR; p=&(L.elem[i-1]); e=*p; q=L.elem+L.length-1; for(++p;p<=q;p++) *(p-1)=*p; L.length--; return OK; }

int main() { SqList T; int a,i; ElemType e,x; if(InitList_Sq(T)) { printf(\ } while(1) { printf(\element\\n2:Delete element\\n3:Load all elements\\n0:Exit\\nPlease choose:\\n\ scanf(\ switch(a) { case 1: scanf(\

}

}

if(!ListInsert_Sq(T,i,x)) printf(\ else printf(\ break;

case 2: scanf(\ if(!ListDelete_Sq(T,i,e)) printf(\ else printf(\ break;

case 3: Load_Sq(T); break;

case 0: return 1; }

1.2合并顺序表 #include #include #define OK 1 #define ERROR 0

#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 #define ElemType int

typedef struct { int *elem,length,listsize; }SqList;

int InitList_Sq(SqList &L) { L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); L.length=0; L.listsize=LIST_INIT_SIZE; return OK; }

int Load_Sq(SqList &L) { int i; for(i=0;i

printf(\ return OK; }

int ListLength(SqList L) { return L.length; }

int GetElem(SqList L,int i,ElemType &e) { e=L.elem[i-1]; return OK; }

int ListInsert_Sq(SqList &L,int i,int e) { if(i<1||i>L.length+1) return ERROR; ElemType *p,*q,*newbase; if(L.listsize<=L.length) { newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType)); L.elem=newbase; L.listsize+=LISTINCREMENT; } q=&(L.elem[i-1]); for(p=&(L.elem[L.length-1]);p>=q;p--) *(p+1)=*p; *q=e; L.length++; return OK; }

void MergeList(SqList La,SqList Lb,SqList &Lc) { int i,j,k,La_len,Lb_len,ai,bj; i=j=1; k=0; InitList_Sq(Lc); La_len=ListLength(La); Lb_len=ListLength(Lb); while((i<=La_len)&&(j<=Lb_len)) {

GetElem(La,i,ai); GetElem(Lb,j,bj); if(ai<=bj) { ListInsert_Sq(Lc,++k,ai); i++; } else { ListInsert_Sq(Lc,++k,bj); j++; } } while(i<=La_len) { GetElem(La,i++,ai); ListInsert_Sq(Lc,++k,ai); } while(j<=Lb_len) { GetElem(Lb,j++,bj); ListInsert_Sq(Lc,++k,bj); } Load_Sq(Lc); }

int main() { int an,bn,i,e; SqList La,Lb,Lc; InitList_Sq(La); scanf(\ for(i=1;i<=an;i++) { scanf(\ ListInsert_Sq(La,i,e); } printf(\ Load_Sq(La); InitList_Sq(Lb); scanf(\ for(i=1;i<=an;i++) { scanf(\

}

ListInsert_Sq(Lb,i,e); }

printf(\Load_Sq(Lb); printf(\MergeList(La,Lb,Lc); return 0;

1.3顺序表逆置 #include #include #define OK 1 #define ERROR 0

#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 #define ElemType int

typedef struct { int *elem,length,listsize; }SqList;

int InitList_Sq(SqList &L) { L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L.elem) { printf(\ return ERROR; } L.length=0; L.listsize=LIST_INIT_SIZE; return OK; }

int Load_Sq(SqList &L) { int i; if(!L.length) { printf(\ return ERROR; }

else { for(i=0;i

int ListInsert_Sq(SqList &L,int i,int e) { ElemType *newbase,*p,*q; if(L.length>=L.listsize) { newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType)); if(!newbase) { printf(\ return ERROR; } L.elem=newbase; L.listsize+=LISTINCREMENT; } q=&(L.elem[i-1]); for(p=&(L.elem[L.length-1]);p>=q;p--) *(p+1)=*p; *q=e; L.length++; return OK; }

int swap(SqList &L,int n) { int i,j,temp; for(i=0,j=n-1;j>i;i++,j--) { temp=L.elem[i]; L.elem[i]=L.elem[j]; L.elem[j]=temp; } return OK; }

int main() {

SqList T; int n,i; ElemType x; scanf(\ InitList_Sq(T); for(i=1;i

1.4链式线性表的基本操作 #include #include #define ERROR 0 #define OK 1

#define ElemType int

typedef struct LNode { int data; struct LNode *next; }LNode,*LinkList;

int CreateLink_L(LinkList &L,int n) { LinkList p,q; int i; ElemType e; L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; q=(LinkList)malloc(sizeof(LNode)); q=L; for(i=0;i

p->data=e; p->next=q->next; q->next=p; q=q->next; } return OK; }

int LoadLink_L(LinkList &L) { LinkList p=L->next; if(!p) printf(\ else { printf(\ while(p) { printf(\ p=p->next; } } printf(\ return OK; }

int LinkInsert_L(LinkList &L,int i,ElemType e) { LNode *p=L,*s; int j=0; while(p&&jnext; j++; } if(!p||j>i-1) return ERROR; s=(LinkList)malloc(sizeof(LNode)); s->data=e; s->next=p->next; p->next=s; return OK; }

int LinkDelete_L(LinkList &L,int i,ElemType &e) { LNode *p=L,*q; int j=0; while(p->next&&jnext; j++; } if(!(p->next)||jnext; p->next=q->next; e=q->data; free(q); return OK; }

int main() { LinkList T; int a,n,i; ElemType x,e; printf(\ scanf(\ printf(\ if(CreateLink_L(T,n)) { printf(\ LoadLink_L(T); } while(1) { printf(\element\\n2:Delete element\\n3:Load all elements\\n0:Exit\\nPlease choose:\\n\ scanf(\ switch(a) { case 1:scanf(\ if(!LinkInsert_L(T,i,x)) printf(\ else printf(\ break;

}

}

case 2:scanf(\ if(!LinkDelete_L(T,i,e)) printf(\ else printf(\ break;

case 3:LoadLink_L(T); break; case 0:return 1; }

1.5合并链表 #include #include #define ERROR 0 #define OK 1

#define ElemType int

typedef struct LNode { int data; struct LNode *next; }LNode,*LinkList;

int CreateLink_L(LinkList &L,int n) { LinkList p,q; int i; ElemType e; L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; q=(LinkList)malloc(sizeof(LNode)); q=L; for(i=0;idata=e; p->next=q->next; q->next=p; q=q->next; }

return OK; }

int LoadLink_L(LinkList &L) { LinkList p=L->next; if(!p) printf(\ else { while(p) { printf(\ p=p->next; } } printf(\ return OK; }

void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc) { LinkList pa,pb,pc; pa=La->next; pb=Lb->next; Lc=pc=La; while(pa&&pb) { if(pa->data<=pb->data) { pc->next=pa; pc=pa; pa=pa->next; } else { pc->next=pb; pc=pb; pb=pb->next; } } pc->next=pa?pa:pb; free(Lb); }

int main() { LinkList La,Lb,Lc; int n; scanf(\ CreateLink_L(La,n); printf(\ LoadLink_L(La); scanf(\ CreateLink_L(Lb,n); printf(\ LoadLink_L(Lb); MergeList_L(La,Lb,Lc); printf(\ LoadLink_L(Lc); return 0; }

1.6线性链表逆置 #include #include #define OK 1 #define ERROR 0

#define ElemType int

typedef struct LNode { int data; struct LNode *next; }LNode,*LinkList;

int CreateLink_L(LinkList &L,int n) { LinkList p,q; int i; ElemType e; L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; q=(LinkList)malloc(sizeof(LNode)); q=L; for(i=0;i

p=(LinkList)malloc(sizeof(LNode)); p->data=e; p->next=q->next; q->next=p; q=q->next; } return OK; }

int LoadLink_L(LinkList &L) { LinkList p=L->next; if(!p) printf(\ else while(p) { printf(\ p=p->next; } printf(\ return OK; }

int inversion(LinkList &L) { LinkList p=L->next,q; L->next=NULL; while(p) { q=p->next; p->next=L->next; L->next=p; p=q; } return OK; }

int main() { LinkList T; int n; scanf(\ CreateLink_L(T,n);

printf(\ LoadLink_L(T); inversion(T); printf(\ LoadLink_L(T); return 0; }

2.1顺序栈的基本操作 #include #include #include #define OK 1 #define ERROR 0

#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10

typedef int SElemType; typedef int Status;

struct SqStack { SElemType *base; SElemType *top; int stacksize; };

Status InitStack(SqStack &S) { S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base) return ERROR; S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; }

Status Push(SqStack &S,SElemType e) { if(S.top-S.base>=S.stacksize) { S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));

if(S.base) return ERROR; S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *S.top++=e; return OK; }

Status Pop(SqStack &S,SElemType &e) { if(S.top==S.base) return ERROR; e=*--S.top; return OK; }

Status GetTop(SqStack S,SElemType &e) { if(S.top==S.base) return ERROR; e=*(S.top-1); return OK; }

int StackLength(SqStack S) { int i=0; while(S.top!=S.base) { i++; S.top--; } return i; }

Status StackTraverse(SqStack S) { SElemType *p=(SElemType*)malloc(sizeof(SElemType)); p=S.top; if(S.top==S.base) printf(\ else {

printf(\ p--; S.base--; while(p!=S.base) { printf(\ p--; } } printf(\ return OK; }

int main() { int a; SqStack S; SElemType x,e; if(InitStack(S)) printf(\ while(1) { printf(\the Top\\n4:Return the Length of the Stack\\n5:Load the Stack\\n0:Exit\\nPlease choose:\\n\ scanf(\ switch(a) { case 1:scanf(\ if(!Push(S,x)) printf(\ else printf(\ break; case 2:if(!Pop(S,e)) printf(\ else printf(\ break; case 3:if(!GetTop(S,e)) printf(\ else printf(\ break; case 4:printf(\

break; case 5:StackTraverse(S); break; case 0:return 1; } } }

2.2循环队列的基本操作 #include #include #define OK 1 #define ERROR 0 typedef int Status;

typedef int QElemType; #define MAXQSIZE 100

typedef struct { QElemType *base; int front; int rear; }SqQueue;

Status InitQueue(SqQueue &Q) { Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType)); if(!Q.base) return ERROR; Q.front=Q.rear=0; return OK; }

Status EnQueue(SqQueue &Q,QElemType e) { if((Q.rear+1)%MAXQSIZE==Q.front) return ERROR; Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MAXQSIZE; return OK; }

Status DeQueue(SqQueue &Q,QElemType &e) { if(Q.front==Q.rear)

return ERROR; e=Q.base[Q.front]; Q.front=(Q.front+1)%MAXQSIZE; return OK; }

Status GetHead(SqQueue Q,QElemType &e) { if(Q.front==Q.rear) return ERROR; e=Q.base[Q.front]; return OK; }

int QueueLength(SqQueue Q) { return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE; }

Status QueueTraverse(SqQueue Q) { int i; i=Q.front; if(Q.front==Q.rear) printf(\ else { printf(\ while(i!=Q.rear) { printf(\ i=i+1; } } printf(\ return OK; }

int main() { int a; SqQueue S; QElemType x,e; if(InitQueue(S))

printf(\ while(1) { printf(\\\n2:Delete \\n3:Get the Front \\n4:Return the Length of the Queue\\n5:Load the Queue\\n0:Exit\\nPlease choose:\\n\ scanf(\ switch(a) { case 1: scanf(\ if(!EnQueue(S,x)) printf(\ else printf(\ break; case 2: if(!DeQueue(S,e)) printf(\ else printf(\ break; case 3: if(!GetHead(S,e)) printf(\ else printf(\ break; case 4: printf(\ break; case 5: QueueTraverse(S); break; case 0: return 1; } } }

2.3栈的应用——进制转换 #include #include #define ERROR 0 #define OK 1

#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10

typedef int SElemType; typedef int Status;

struct SqStack { SElemType *base; SElemType *top; int stacksize; };

Status InitStack(SqStack &S) { S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base) return ERROR; S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; }

Status Push(SqStack &S,SElemType e) { if(S.top-S.base>=S.stacksize) { S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType)); if(S.base) return ERROR; S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *S.top++=e; return OK; }

Status Pop(SqStack &S,SElemType &e) { if(S.top==S.base) return ERROR; e=*--S.top; return OK; }

Status StackEmpty(SqStack &S) { if(S.top==S.base) return 0;

else return 1; }

int main() { int N,e; SqStack S; InitStack(S); scanf(\ while(N) { Push(S,N%8); N=N/8; } while(StackEmpty(S)) { Pop(S,e); printf(\ } return 0; }

2.4括号匹配检验

typedef char SElemType; #include #include #include #include #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 typedef int Status;

#define STACK_INIT_SIZE 10 #define STACKINCREMENT 2

struct SqStack { SElemType *base; SElemType *top; int stacksize; };

Status InitStack(SqStack &S) { S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base) return 0; S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; }

Status StackEmpty(SqStack S) { if(S.top==S.base) return TRUE; else return FALSE; }

Status Push(SqStack &S,SElemType e) { if(S.top-S.base>=S.stacksize) { S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!S.base) return 0; S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *S.top++=e; return OK; }

Status Pop(SqStack &S,SElemType &e) { if(S.top==S.base) return ERROR; e=*--S.top; return OK; }

void check() {

SqStack s;

SElemType ch[80],*p,e; if(InitStack(s)) {

gets(ch); p=ch; while(*p) switch(*p) {

case '(':

case '[':Push(s,*p++); break; case ')':

case ']':if(!StackEmpty(s)) {

Pop(s,e);

if(*p==')'&&e!='('||*p==']'&&e!='[') {

printf(\ return ; } else {

p++ ; break; } } else {

printf(\ return ; } default: p++; }

if(StackEmpty(s))

printf(\ else

printf(\ } }

int main() { check(); return 1;

}

2.5行编辑程序

typedef char SElemType; #include #include #include #include #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 typedef int Status;

#define STACK_INIT_SIZE 10 #define STACKINCREMENT 2

struct SqStack { SElemType *base; SElemType *top; int stacksize; };

FILE *fp;

Status InitStack(SqStack &S) { S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base) return 0; S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; }

Status StackEmpty(SqStack S) { if(S.top==S.base) return TRUE; else return FALSE; }

Status ClearStack(SqStack &S) { S.top=S.base;

return OK; }

Status DestroyStack(SqStack &S) { free(S.base); S.base=NULL; S.top=NULL; S.stacksize=0; return OK; }

Status Push(SqStack &S,SElemType e) { if(S.top-S.base>=S.stacksize) { S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!S.base) return 0; S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *S.top++=e; return OK; }

Status Pop(SqStack &S,SElemType &e) { if(S.top==S.base) return ERROR; e=*--S.top; return OK; }

Status StackTraverse(SqStack S,Status(*visit)(SElemType)) { while(S.top>S.base) visit(*S.base++); printf(\ return OK; }

Status visit(SElemType c)

{ printf(\ return OK; }

void LineEdit() { SqStack s; char ch,c; int n,i; InitStack(s); scanf(\ ch=getchar(); for(i=1;i<=n;i++) { ch=getchar(); while(ch!='\\n') { switch(ch) { case '#': Pop(s,c); break; case '@': ClearStack(s); break; default:Push(s,ch); } ch=getchar(); } StackTraverse(s,visit); ClearStack(s); } DestroyStack(s); }

int main() { LineEdit(); return 1; }

2.6表达式求值 #include #include #define OK 1 #define ERROR 0

#define STACK_INIT_SIZE 100

#define STACKINCREMENT 10

typedef int Status;

struct SqStack_T { char *base; char *top; int stacksize; };

struct SqStack_N { int *base; int *top; int stacksize; };

Status InitStack_T(SqStack_T &S) { S.base=(char*)malloc(STACK_INIT_SIZE*sizeof(char)); if(!S.base) return ERROR; S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; }

Status InitStack_N(SqStack_N &S) { S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int)); if(!S.base) return ERROR; S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; }

int Push_T(SqStack_T &S,char e) { if(S.top-S.base>=S.stacksize) { S.base=(char*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char)); if(!S.base)

return ERROR; S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *S.top++=e; return OK; }

int Push_N(SqStack_N &S,int e) { if(S.top-S.base>=S.stacksize) { S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int)); if(!S.base) return ERROR; S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *S.top++=e; return OK; }

int Pop_T(SqStack_T &S,char &e) { if(S.top==S.base) return ERROR; e=*--S.top; return OK; }

int Pop_N(SqStack_N &S,int &e) { if(S.top==S.base) return ERROR; e=*--S.top; return OK; }

char GetTop_T(SqStack_T S) { char e; if(S.top==S.base) return ERROR; e=*(S.top-1);

return e; }

int GetTop_N(SqStack_N S) { int e; if(S.top==S.base) return ERROR; e=*(S.top-1); return e; }

char Precede(char theta1,char theta2) { int a,b; switch(theta1) { case '+': a=2; break; case '-': a=2; break; case '*': a=4; break; case '/': a=4; break; case '(': a=0; break; case ')': a=6; break; case '=': a=-1; break; } switch(theta2) { case '+': b=1; break; case '-': b=1; break; case '*': b=3; break; case '/': b=3; break; case '(': b=6; break; case ')': b=0; break; case '=': b=-1; break; } if(a'; }

char precede(char e,char c) { if(c=='+'||c=='-') { if(e=='+'||e=='-'||e==')'||e=='=') return '>'; else return '<'; } if(c=='*'||'/') { if(e=='(') return '<'; else return '>'; } if(c=='(') { if(e==')') return '='; else return '<'; } if(c==')') return '>'; if(c=='=') { if(e=='=') return '='; else return '<'; } }

int In(char c) { if(c>='0'&&c<='9') return 1; else return 0; }

int Operate(int a,char theta,int b) {

int s; switch(theta) { case '+': s=a+b; break; case '-': s=a-b; break; case '*': s=a*b; break; case '/': if(b!=0) s=a/b; else printf(\ break; } return s; }

int main() { int k=0,m,y,a,b; SqStack_T OPTR; SqStack_N OPND; char c,theta; InitStack_T(OPTR); Push_T(OPTR,'='); InitStack_N(OPND); c=getchar(); while(c!='='||GetTop_T(OPTR)!='=') { if(In(c)) { m=c-'0'; if(k==1) { Pop_N(OPND,y); y=m+y*10; Push_N(OPND,y); k=1; c=getchar(); } else { y=m; Push_N(OPND,y); c=getchar(); k=1; }

} else { k=0; switch(Precede(GetTop_T(OPTR),c)) { case '<': Push_T(OPTR,c); c=getchar(); break; case '=': Pop_T(OPTR,c); c=getchar(); break; case '>': Pop_T(OPTR,theta); Pop_N(OPND,b); Pop_N(OPND,a); Push_N(OPND,Operate(a,theta,b)); break; } } } printf(\ return 0; }

2.7队列的应用——银行客户平均等待时间 #include #include #define OK 1 #define ERROR 0 typedef int Status;

typedef int QElemType; #define MAXQSIZE 100

typedef struct { QElemType *base; int front; int rear; }SqQueue;

Status InitQueue(SqQueue &Q) { Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType)); if(!Q.base) return ERROR; Q.front=Q.rear=0;

return OK; }

Status EnQueue(SqQueue &Q,QElemType e) { if((Q.rear+1)%MAXQSIZE==Q.front) return ERROR; Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MAXQSIZE; return OK; }

Status DeQueue(SqQueue &Q,QElemType &e) { if(Q.front==Q.rear) return ERROR; e=Q.base[Q.front]; Q.front=(Q.front+1)%MAXQSIZE; return OK; }

Status GetHead(SqQueue Q,QElemType &e) { if(Q.rear==Q.front) return ERROR; e=Q.base[Q.front]; return OK; }

int QueueLength(SqQueue Q) { return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE; }

Status QueueTraverse(SqQueue Q) { int i; i=Q.front; if(Q.rear==Q.front) printf(\ else { printf(\ while(i!=Q.rear)

{ printf(\ i=(i+1)%MAXQSIZE; } } printf(\ return OK; }

int main() { int i,a; SqQueue S; int p,q,e,r; float t,s=0; InitQueue(S); scanf(\ getchar(); for(i=1;i<=a*2;i++) { scanf(\ getchar(); EnQueue(S,e); } p=S.base[S.front]; while(S.rear>S.front) { q=p+S.base[S.front+1]; DeQueue(S,e); DeQueue(S,e); if(S.front==S.rear) break; r=q-S.base[S.front]; if(r<0) { r=0; p=S.base[S.front]; continue; } s=s+r; p=q; } t=s/a; printf(\

return OK; }

3.1计算next值 #include #include #include #define MAXSTRLEN 255

typedef unsigned char SString[MAXSTRLEN+1];

void get_next(SString T,int next[]) { int i=1,j=0; next[1]=0; while(i

int main() { int next[MAXSTRLEN],n,i,j; char ch; SString S; scanf(\ ch=getchar(); for(i=1;i<=n;i++) { ch=getchar(); for(j=1;j<=MAXSTRLEN&&(ch!='\\n');j++) { S[j]=ch; ch=getchar(); } S[0]=j-1;

}

get_next(S,next); printf(\ for(j=1;j<=S[0];j++) printf(\ printf(\}

return 0;

3.2KMP算法 #include #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0

#define INFEASLBLE -1 #define OVERFLOW -2 #define MAXSTRLEN 255

typedef unsigned char SString[MAXSTRLEN+1];

void get_next(SString T,int next[]) { int i=1,j=0; next[1]=0; while(i

int Index_KMP(SString S,SString T,int pos) { int next[MAXSTRLEN],i=pos,j=1; get_next(T,next); while(i<=S[0]&&j<=T[0])

{ if(j==0||S[i]==T[j]) { ++i; ++j; } else j=next[j]; } if(j>T[0]) return i-T[0]; else return 0; }

int main() { int n,i,j,pos; char ch; SString S,T; scanf(\ ch=getchar(); for(j=1;j<=n;j++) { ch=getchar(); for(i=1;i<=MAXSTRLEN&&(ch!='\\n');i++) { S[i]=ch; ch=getchar(); } S[0]=i-1; ch=getchar(); for(i=1;i<=MAXSTRLEN&&(ch!='\\n');i++) { T[i]=ch; ch=getchar(); } T[0]=i-1; pos=Index_KMP(S,T,0); printf(\ } return 0; }

4.1二叉树的构建及遍历操作 #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0

#define INFEASIBLE -1 #define OVERFLOW -2

typedef int Status;

typedef char ElemType; typedef struct BiTNode { ElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree;

BiTree CreateBiTree(BiTree &T) { char ch; scanf(\ if(ch=='#') T=NULL; else { if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) return ERROR; T->data=ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } return T; }

Status Visit(ElemType e) { if(e!='#') { printf(\ return OK; } else return FALSE;

}

Status PreOrderTraverse(BiTree T) { if(T) { if(Visit(T->data)) if(PreOrderTraverse(T->lchild)) if(PreOrderTraverse(T->rchild)) return OK; return ERROR; } else return OK; }

Status InOrderTraverse(BiTree T) { if(T) { if(InOrderTraverse(T->lchild)) if(Visit(T->data)) if(InOrderTraverse(T->rchild)) return OK; return ERROR; } else return OK; }

Status PostOrderTraverse(BiTree T) { if(T) { if(PostOrderTraverse(T->lchild)) if(PostOrderTraverse(T->rchild)) if(Visit(T->data)) return OK; return ERROR; } else return OK; }

int main() {

BiTree T; CreateBiTree(T); PreOrderTraverse(T); printf(\ InOrderTraverse(T); printf(\ PostOrderTraverse(T); printf(\ return 0; }

4.2实现二叉排序树的各种算法(1) #include #include #define TRUE 1 #define OK 1 #define ERROR 0

#define INFEASIBLE -1 #define OVERFLOW -2

#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10

typedef int Status; typedef int ElemType;

typedef struct BiTNode { ElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree;

typedef struct stack { BiTree *base; BiTree *top; int stacksize; }SqStack;

typedef struct queuenode { BiTree ch; struct queuenode *next; }queuenode,*queueptr;

typedef struct { queueptr front; queueptr rear;

}linkqueue;

Status InsertBiT(BiTree *T,int k) { BiTNode *q,*p=*T; while(p) { if(p->data==k) return ERROR; q=p; p=(kdata)?p->lchild:p->rchild; }

p=(BiTNode*)malloc(sizeof(BiTNode)); p->data=k; p->lchild=p->rchild=NULL; if(*T==NULL) *T=p; else if(kdata) q->lchild=p; else q->rchild=p; return OK; }

BiTree CreateBiT(int n) { BiTree T=NULL; int k,i;

for(i=1;i<=n;i++) { scanf(\ InsertBiT(&T,k); }

return T; }

Status Visit(ElemType e) {

printf(\ return OK; }

Status PreOrderTraverse(BiTree T) { if(T) { if(Visit(T->data)) if(PreOrderTraverse(T->lchild)) if(PreOrderTraverse(T->rchild)) return OK; return ERROR; } else return OK; }

Status InOrderTraverse(BiTree T) { if(T) { if(InOrderTraverse(T->lchild)) if(Visit(T->data)) if(InOrderTraverse(T->rchild)) return OK; return ERROR; } else return OK; }

Status PostOrderTraverse(BiTree T) { if(T) { if(PostOrderTraverse(T->lchild)) if(PostOrderTraverse(T->rchild)) if(Visit(T->data)) return OK; return ERROR; } else return OK;

}

Status Visits(ElemType e,int m,int &t) { if(e==m) t=1; return OK; }

Status Postsearch(BiTree T,int m,int &t) { if(T) { if(Postsearch(T->lchild,m,t)) if(Postsearch(T->rchild,m,t)) if(Visits(T->data,m,t)) return OK; return ERROR; } else return OK; }

Status InitStack(SqStack &S) { S.base=(BiTree*)malloc(STACK_INIT_SIZE*sizeof(BiTree)); if(!S.base) return ERROR; S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; }

Status Push(SqStack &S,BiTree e) { if(S.top-S.base>=S.stacksize) { S.base=(BiTree*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(BiTree)); if(S.base) return ERROR; S.stacksize+=STACKINCREMENT; } *S.top++=e; return OK;

}

Status Pop(SqStack &S,BiTree &e) { if(S.top==S.base) return ERROR; e=*--S.top; return OK; }

Status StackEmpty(SqStack &S) { if(S.top==S.base) return 1; else return 0; }

Status InOrderTraverses(BiTree T) {

SqStack s; InitStack(s); BiTree p; p=T;

while (p||!StackEmpty(s)) {

while(p) {

Push(s,p); p=p->lchild; }

Pop(s,p); Visit(p->data);

p=p->rchild; } return OK; }

void initqueue(linkqueue &q) { q.front=q.rear=(queueptr)malloc(sizeof(queuenode)); q.front->next=NULL; }

void enqueue(linkqueue &q,BiTree p) { queueptr s; s=(queueptr)malloc(sizeof(queuenode)); s->ch=p; s->next=NULL; q.rear->next=s; q.rear=s; }

void dequeue(linkqueue &q,BiTree &p) { int data; queueptr s; s=q.front->next; p=s->ch;

data=p->data;

q.front->next=s->next; if(q.rear==s) q.rear=q.front; free(s);

printf(\}

int queueempty(linkqueue q) { if(q.front->next==NULL) return 1; return 0; }

void traverse(BiTree bt) { linkqueue q; BiTree p; initqueue(q); p=bt; enqueue(q,p); while(queueempty(q)!=1) { dequeue(q,p); if(p->lchild!=NULL) enqueue(q,p->lchild); if(p->rchild!=NULL)

enqueue(q,p->rchild); } printf(\}

int main() { int m1,m2,n,i,t=0; BiTree T; scanf(\ T=CreateBiT(n); scanf(\ PreOrderTraverse(T); printf(\ InOrderTraverse(T); printf(\ PostOrderTraverse(T); printf(\ Postsearch(T,m1,t); if(t==1) printf(\ else printf(\ t=0; Postsearch(T,m2,t); if(t==1) printf(\ else printf(\ InsertBiT(&T,i); PreOrderTraverse(T); printf(\ InOrderTraverse(T); printf(\ PostOrderTraverse(T); printf(\ InOrderTraverses(T); printf(\ traverse(T); return 0; }

4.实现二叉排序树的各种算法(2) #include #include

#define TRUE 1 #define OK 1 #define ERROR 0

#define INFEASIBLE -1 #define OVERFLOW -2

#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10

typedef int Status; typedef int ElemType;

typedef struct BiTNode { ElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree;

typedef struct stack { BiTree *base; BiTree *top; int stacksize; }SqStack;

typedef struct queuenode { BiTree ch; struct queuenode *next; }queuenode,*queueptr; typedef struct { queueptr front; queueptr rear;

}linkqueue;

Status InsertBiT(BiTree *T,int k) { BiTNode *q,*p=*T; while(p) { if(p->data==k) return ERROR; q=p;

p=(kdata)?p->lchild:p->rchild; }

p=(BiTNode*)malloc(sizeof(BiTNode)); p->data=k; p->lchild=p->rchild=NULL; if(*T==NULL) *T=p; else if(kdata) q->lchild=p; else q->rchild=p; return OK; }

BiTree CreateBiT(int n) { BiTree T=NULL; int k,i;

for(i=1;i<=n;i++) { scanf(\ InsertBiT(&T,k); }

return T; }

Status Visit(ElemType e) { printf(\ return OK; }

Status PreOrderTraverse(BiTree T) { if(T) { if(Visit(T->data)) if(PreOrderTraverse(T->lchild)) if(PreOrderTraverse(T->rchild)) return OK; return ERROR; } else

return OK; }

Status InOrderTraverse(BiTree T) { if(T) { if(InOrderTraverse(T->lchild)) if(Visit(T->data)) if(InOrderTraverse(T->rchild)) return OK; return ERROR; } else return OK; }

Status PostOrderTraverse(BiTree T) { if(T) { if(PostOrderTraverse(T->lchild)) if(PostOrderTraverse(T->rchild)) if(Visit(T->data)) return OK; return ERROR; } else return OK; }

Status Visits(ElemType e,int m,int &t) { if(e==m) t=1; return OK; }

Status Postsearch(BiTree T,int m,int &t) { if(T) { if(Postsearch(T->lchild,m,t)) if(Postsearch(T->rchild,m,t))

本文来源：https://www.bwwdw.com/article/rl1o.html