《数据结构》(C语言版)严蔚敏著_数据结构实验指导(5)

}

int main(){ int n; do {

printf(\ printf(\ printf(\ printf(\ printf(\ scanf(\ getchar();

switch(n){

case 1:show_strCompare();break; case 2:show_subString();break; default:n=0;break; }

}while(n); return 0; }

?

运行程序

输入： 1

student students

2

Computer Data Stuctures 10 4

运行结果：

2、实现串的模式匹配算法。补充下面程序，实现串的BF和KMP算法。 #include #include #define MAXSIZE 100 typedef struct{

char data[MAXSIZE]; int length;

}SqString;

int index_bf(SqString *s,SqString *t,int start);

21

void getNext(SqString *t,int next[]);

int index_kmp(SqString *s,SqString *t,int start,int next[]); void show_index();

int index_bf(SqString *s,SqString *t,int start){

补充代码..... }

void getNext(SqString *t,int next[]){ int i=0,j=-1; next[0]=-1;

while(ilength){

if((j==-1)||(t->data[i]==t->data[j])){

i++;j++;next[i]=j; }else

j=next[j]; } }

int index_kmp(SqString *s,SqString *t,int start,int next[]){ 补充代码..... }

void show_index(){ SqString s,t;

int k,next[MAXSIZE]={0},i;

printf(\ printf(\

22

gets(s.data);

s.length=strlen(s.data); printf(\ gets(t.data);

t.length=strlen(t.data);

printf(\ scanf(\

printf(\ getNext(&t,next); printf(\ printf(\ for(i=0;i

printf(\ printf(\}

int main(){

show_index(); return 0;

}

输入：

abcaabbabcabaacbacba abcabaa 1

运行结果：

四、实验小结

五、教师评语

23

实验四 二叉树

一、实验目的

1、掌握二叉树的基本特性

2、掌握二叉树的先序、中序、后序的递归遍历算法 3、理解二叉树的先序、中序、后序的非递归遍历算法

4、通过求二叉树的深度、叶子结点数和层序遍历等算法，理解二叉树的基本特性

二、实验预习

说明以下概念 1、二叉树：

2、递归遍历：

3、 非递归遍历：

4、层序遍历：

三、实验内容和要求

1、阅读并运行下面程序，根据输入写出运行结果，并画出二叉树的形态。 #include #include #define MAX 20

typedef struct BTNode{ /*节点结构声明*/ char data ; /*节点数据*/

struct BTNode *lchild;

struct BTNode *rchild ; /*指针*/

}*BiTree;

void createBiTree(BiTree *t){ /* 先序遍历创建二叉树*/ char s;

BiTree q;

printf(\s=getche();

if(s=='#'){*t=NULL; return;}

q=(BiTree)malloc(sizeof(struct BTNode));

if(q==NULL){printf(\q->data=s;

*t=q;

createBiTree(&q->lchild); /*递归建立左子树*/ createBiTree(&q->rchild); /*递归建立右子树*/

24

}

void PreOrder(BiTree p){ /* 先序遍历二叉树*/ if ( p!= NULL ) {

printf(\ PreOrder( p->lchild ) ; PreOrder( p->rchild) ; } }

void InOrder(BiTree p){ /* 中序遍历二叉树*/ if( p!= NULL ) {

InOrder( p->lchild ) ; printf(\ InOrder( p->rchild) ; } }

void PostOrder(BiTree p){ /* 后序遍历二叉树*/ if ( p!= NULL ) {

PostOrder( p->lchild ) ; PostOrder( p->rchild) ; printf(\

} }

void Preorder_n(BiTree p){ /*先序遍历的非递归算法*/ BiTree stack[MAX],q; int top=0,i;

for(i=0;i

while(q!=NULL){

printf(\

if(q->rchild!=NULL) stack[top++]=q->rchild; if(q->lchild!=NULL) q=q->lchild; else

if(top>0) q=stack[--top]; else q=NULL; } }

void release(BiTree t){ /*释放二叉树空间*/ if(t!=NULL){

release(t->lchild); release(t->rchild); free(t);

25