数据结构上机答案
更新时间:2024-03-30 18:46:01 阅读量: 综合文库 文档下载
数据结构上机答案
1.1顺序线性表的基本操作 #include
#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 #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 #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 #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&&j int LinkDelete_L(LinkList &L,int i,ElemType &e) { LNode *p=L,*q; int j=0; while(p->next&&j 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 #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 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 #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 #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 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 #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 #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 #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 #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 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 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 #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 #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 #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=(k p=(BiTNode*)malloc(sizeof(BiTNode)); p->data=k; p->lchild=p->rchild=NULL; if(*T==NULL) *T=p; else if(k 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 #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=(k p=(BiTNode*)malloc(sizeof(BiTNode)); p->data=k; p->lchild=p->rchild=NULL; if(*T==NULL) *T=p; else if(k 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))
正在阅读:
数据结构上机答案03-30
各省军区独立师历史沿革04-25
当一次家作文400字3篇02-05
超声波测距毕业论文06-02
幼儿园托班教案(精选多篇)09-26
含参数导数常见的讨论05-15
解放思想与实事求是 毛概06-07
天音通信2011届大学生校园招聘执行手册(正式版)08-19
震撼全球66亿人的健康大发现06-07
- 冀教版版五年级科学下册复习资料
- 微生物学复习提纲
- 2013—2014学年小学第二学期教研组工作总结
- 国有土地转让委托服务合同协议范本模板
- 我的固废说明书
- 企业管理诊断报告格式
- 东鼎雅苑施工组织设计
- 谈谈如何做好基层党支部书记工作
- 浮梁县环保局市级文明单位创建工作汇报
- 管理学基础知识
- 大学物理实验报告23 - PN结温度传感器特性1
- 计算机网络实践
- 酒桌上这四种情况下要坐牢,千万别不当回事……
- 国家康居示范工程建设技术要点
- 中国贴布行业市场调查研究报告(目录) - 图文
- 新课标下如何在高中物理教学中培养学生的创新能力初探
- 营养师冬季养生食谱每日一练(7月4日)
- 关注江西2017年第3期药品质量公告
- 建设海绵城市专题习题汇总
- 10万吨年环保净水剂建设项目报告书(2).pdf - 图文
- 数据结构
- 上机
- 答案
- 安全知识题库(1)(1)
- 大学生闲置物回收再利用公益事业创业项目
- 长期静脉输液者血管的选择和保护方法的探讨
- 中国大学分专业排名-管理学
- 正一开光科仪
- 有效咳嗽咳痰
- 世界银行集团中国业务介绍
- 重庆高院党风廉政电视讲话
- 超星尔雅军事理论-数学的思维方式与创新
- 嘉兴市教育研究院(通知)
- 深圳市政府投资信息化工程建设项目项目建议书编制指南
- 机械工业绿色制造技术 - 现代制造技术试卷94分
- 中西部地区两型农业的发展着力点
- 三年级《千克的初步认识》教学设计
- 中考专题 数学(部分1) - 图文
- 数据中心基础设施需求
- 新课标人教版3-1选修三1.5《电势差》WORD教案4
- 用打点计时器测速度(匀变速直线运动的实验探究)
- 《诗经》两首优秀教案 - 图文
- 吴迪3+1选股法(内含通达信公式) - 图文