数据结构教程 第三十五课 实验七 查找

核心提示：教学目的： 练习顺序查找、折半查找及二叉排序树的实现教学重点：教学难点：授课内容：顺序查找折半查找 顺序查找及折半查找示例 #include <stdio.h>typedef int KeyType;typedef struct{ KeyType key; int maths; int english

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

教学重点：

教学难点：

授课内容：

顺序查找

折半查找

顺序查找及折半查找示例

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