教学目的： 练习顺序查找、折半查找及二叉排序树的实现

教学重点：

教学难点：

授课内容：

顺序查找

逆@风@者

折半查找

顺序查找及折半查找示例

#include <stdio.h>



typedef int KeyType;

typedef struct{

  KeyType key;

  int maths;

  int english;

}ElemType;

#define EQ(a,b)  ((a)==(b))

#define LT(a,b)  ((a)< (b))

#define LQ(a,b)  ((a)<=(b))



typedef struct {

  ElemType *elem;

  int length;

}SSTable;



int Search_Seq(SSTable ST,KeyType key)

{

  int i;

  ST.elem[0].key=key;

  for(i=ST.length; !EQ(ST.elem[i].key,key); --i);

  return i;

}



int Search_Bin(SSTable ST,KeyType key)

{

  int low,mid,high;

  low=1;high=ST.length;

  while(low<=high){

    mid=(low high)/2;

    if EQ(key,ST.elem[mid].key) return mid;

    else if LT(key,ST.elem[mid].key) high=mid -1;

    else  low=mid  1;

  }

}



getdata(SSTable * t)

{

  FILE *fp;

  int i=1;

  fp=fopen("stu.txt","r");

  fscanf(fp,"%d",&(t->length));

  while(i<=t->length)

    {

      fscanf(fp,"%d %d %d",&(t->elem[i].key),

		 &(t->elem[i].maths),&(t->elem[i].english)  );

      i  ;

    }

  fclose(fp);

}



main()

{

  ElemType stu[50];

  SSTable  class;

  int i,j,k;

  long time;

  class.elem=stu;





  getdata(&class);



  printf("This class has %d students.\n",class.length);

  printf("Input stuno you want search:\n");

  scanf("%d",&k);



  i=Search_Seq(class,k);

  j=Search_Bin(class,k);

  printf("Maths   English\n");

  printf("%d       %d\n",class.elem[i].maths,class.elem[i].english);

  printf("%d       %d\n",class.elem[j].maths,class.elem[j].english);



  for(i=1;i<=4;i  )

    {j=stu[i].maths stu[i].english;

      printf("%d\n",j);

    }



}

二叉排序树

示例

#include <alloc.h>



#define ERROR 0;

#define FALSE 0;

#define TRUE 1;

#define OK 1;





typedef int ElemType;

typedef int Status;

typedef int KeyType;



#define EQ(a,b)  ((a)==(b))

#define LT(a,b)  ((a)< (b))

#define LQ(a,b)  ((a)<=(b))



typedef struct BinaryTree



{

  ElemType data;

  struct BinaryTree *l;

  struct BinaryTree *r;

}*BiTree,BiNode;



BiNode * new()

{

  return( (BiNode *)malloc(sizeof(BiNode)) );

}



CreateSubTree(BiTree *T,ElemType *all,int i)

{

  if ((all[i]==0)||i>16)

    {

      *T=NULL;

      return OK;

    }

  *T=new();

  if(*T==NULL) return ERROR;

  (*T)->data=all[i];

  CreateSubTree(&((*T)->l),all,2*i);

  CreateSubTree(&((*T)->r),all,2*i 1);

}



CreateBiTree(BiTree *T)

{

  ElemType all[16]={0,1,2,3,0,0,4,5,0,0,0,0,6,0,0,0,};

  CreateSubTree(T,all,1);

}



printelem(ElemType d)

{

  printf("%d\n",d);

}



PreOrderTraverse(BiTree T,int (*Visit)(ElemType d))

{

  if(T){

    if(Visit(T->data))

      if(PreOrderTraverse(T->l,Visit))

	if(PreOrderTraverse(T->r,Visit)) return OK;

    return ERROR;

  } else  return OK;

}



InOrderTraverse(BiTree T,int (*Visit)(ElemType d))

{

  if(T){

    if(InOrderTraverse(T->l,Visit))

      if(Visit(T->data))

        if(InOrderTraverse(T->r,Visit)) return OK;

    return ERROR;

  }else return OK;

}



Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree *p){



  if(!T) {*p=f;return FALSE;}

  else if EQ(key,T->data){ *p=T;return TRUE;}

  else if LT(key,T->data) SearchBST(T->l,key,T,p);

  else SearchBST(T->r,key,T,p);

}



Status InsertBST(BiTree *T,ElemType e){

  BiTree p;

  BiTree s;

  if(!SearchBST(*T,e,NULL,&p)){

    s=(BiTree)malloc(sizeof(BiNode));

    s->data=e;s->l=s->r=NULL;

    if(!p) *T=s;

    else if (LT(e,p->data)) p->l=s;

    else p->r=s;

    return TRUE;

  }

  else return FALSE;

}



void Delete(BiTree *p){

 BiTree q,s;

  if(!(*p)->r){

    q=(*p);

    (*p)=(*p)->l;

    free(q);

  }

  else if(!(*p)->l){

    q=(*p);

    (*p)=(*p)->r;

    free(q);

  }

  else {



/*    q=(*p);

    s=(*p)->l;

    while(s->r) {q=s; s=s->r;}

    (*p)->data=s->data;

    if(q!=(*p) ) q->r=s->l;

    else q->l=s->l;

    free(s);

    */



    q=s=(*p)->l;

    while(s->r) s=s->r;

    s->r=(*p)->r;

    free(*p);

    (*p)=q;



  }

}



Status DeleteBST(BiTree *T,KeyType key){

  if (!(*T) )

    {return FALSE;}

  else{

    if ( EQ(key,(*T)->data)) Delete(T);

    else if ( LT(key,(*T)->data)) DeleteBST( &((*T)->l), key);

    else DeleteBST( &((*T)->r),key);

    return TRUE;

  }

}





main()

{

  BiTree root;

  BiTree sroot=NULL;

  int i;

  int a[10]={45,23,12,3,33, 27,56,90,120,62};

  system("cls");

  CreateBiTree(&root);

  printf("PreOrderTraverse:\n");

  PreOrderTraverse(root,printelem);

  printf("InOrderTraverse:\n");

  InOrderTraverse(root,printelem);

  for(i=0;i<10;i  )

    InsertBST(&sroot,a[i]);

  printf("InOrderTraverse:\n");

  InOrderTraverse(sroot,printelem);

  for(i=0;i<3;i  )

  DeleteBST(&sroot,a[i]);

  printf("Now sroot has nodes:\n");

  InOrderTraverse(sroot,printelem);

}