数据结构上机答案(8)

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; }