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

教学重点：

教学难点：

授课内容：

顺序查找

折半查找

顺序查找及折半查找示例

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