數(shù)據(jù)結構教程第三十五課實驗七查找

字號： 小 中 大

教學目的： 練習順序查找、折半查找及二叉排序樹的實現(xiàn)
    教學重點：
    教學難點：
    授課內(nèi)容：
    順序查找
    折半查找
    順序查找及折半查找示例
    #include
    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
    #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);
    }