C语言——查找算法的设计与应用（静态表折半查找，无序表中采用顺序查找）

﹏ヽ暗。殇╰゛Y 2023-06-21 07:28 14阅读 0赞

## 二叉排序树设计 ##

设计一个读入一串整数，然后构造二叉排序树，进行查找。  
二叉排序树又称二叉查找树，它可以是一棵空树，若非空时具有下述性质：  
1.若根结点的左子树非空，则左子树上所有结点的关键字值均小于等于根结点的关键字值。  
2.若根结点的右子树非空，则右子树上所有结点的关键字值均大于等于根结点的关键字值。  
3.根结点的左、右子树也分别为二叉排序树。  
二叉排序树建立说明：  
当需要插入一个节点到二叉排序树时，需要先找到它的父节点。

## 程序需求 ##

1.从空的二叉树开始，每输入一个结点数据，就建立一个新结点插入到当前已生成的二叉排序树中。  
2.在二叉排序树中查找某一结点。  
3.用其它查找算法进行排序。

## 算法的基本思想 ##

二叉排序树，又叫二叉查找树，它或者是一棵空树；  
或者是具有以下性质的二叉树：  
1.若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；  
2.若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；  
3.它的左右子树也分别为二叉排序树。  
与次优二叉树相对，二叉排序树是一种动态树表。其特点是：树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。

二叉排序树的删除操作相对复杂，因为不能因为删除了结点，让这颗二叉排序树变得不满足二叉排序树的性质，所以对于二叉排序树的删除存在三种情况：  
1.叶子结点；（直接删除结点）  
2.仅有左或者右子树的结点；（删除结点后，将它的左子树或者右子树整个移动到删除结点的位置）  
3.左右子树都有的结点。  
核心思想：将它的直接前驱或者直接后继作为删除结点的数据

**程序的流程**  
程序由三个模块组成：  
1.输入模块：一个一个输入二叉排序树的结点（char）  
2.计算模块：设计二叉排序树的插入，删除，先序遍历，中序遍历，后序遍历函数  
3.输出模块：完成插入和删除，显示二叉排序树的遍历结果  
**算法的时空分析**  
二叉排序树的插入和查找算法的基本过程都是查找操作，所以其时间复杂度是O（log2n）

## 二叉排序树 ##

#include <stdio.h>
    #include <stdlib.h>
    #include <conio.h>
    #include <math.h>
    enum BOOL
    {
        False,True};
    typedef struct  BiTNode       //定义二叉树节点结构
    {
        char  data;                  //为了方便，数据域只有关键字一项
     struct BiTNode *lchild,*rchild; //左右孩子指针域
    }BiTNode,*BiTree;
    
    BOOL SearchBST(BiTree,char,BiTree,BiTree&); //在二叉排序树中查找元素
    BOOL InsertBST(BiTree &,char);    //在二叉排序树中插入元素  
    BOOL DeleteBST(BiTree &,char);    //在二叉排序树中删除元素
    void Delete(BiTree &);            //删除二叉排序树的根结点
    void InorderBST(BiTree);          //中序遍历二叉排序树，即从小到大显示各元素
    void preorderBST(BiTree);
    void postorderBST(BiTree);
    
    void main()
    {
        BiTree T,p;
     char ch,keyword,j='y';
     BOOL temp;
     T=NULL;
     while(j!='n')
    {
        
    printf("1.元素插入\n");
         printf("2.元素查找\n");
         printf("3.中序遍历\n");
    	 printf("4.先序遍历\n");
    	 printf("5.后序遍历\n");
         printf("6.元素删除\n");
         printf("7.退出\n");
         scanf(" %c",&ch); //输入操作选项
         switch(ch)
          {
        
    	    case '1':printf("请输入要插入的结点关键字(char):");
    		scanf(" %c",&keyword); //输入要插入元素的关键字
    		temp=InsertBST(T,keyword);
    		if(!temp) printf("%c 已经存在!\n",keyword); //该元素已经存在
    		else printf("成功插入%c!\n",keyword); //成功插入
    		break;
            case '2':printf("请输入要搜索的结点关键字(char):");
    		scanf(" %c",&keyword); //输入要查找元素的关键字
    		temp=SearchBST(T,keyword,NULL,p);
    		if(!temp) printf("%c 没有找到!\n",keyword); //没有找到
    		else printf("成功找到%c!\n",keyword); //成功找到
    		break;
            case '3':if(!T) printf("二叉树没有根节点!\n");
    		else {
        InorderBST(T);printf("\n");}
    		break;
    		case '4':if(!T) printf("二叉树没有根节点!\n");
    		else {
        preorderBST(T);printf("\n");}
    		break;
    		case '5':if(!T) printf("二叉树没有根节点!\n");
    		else {
        postorderBST(T);printf("\n");}
    		break;
            case '6':printf("请输入要删除的结点关键字(char):");
    		scanf(" %c",&keyword); //输入要删除元素的关键字
    		temp=DeleteBST(T,keyword);
    		if(!temp) printf("%c 不存在!\n",keyword); //该元素不存在
    		else printf("成功删除%c\n",keyword); //成功删除
    		break;
            default: j='n';
        }
     }
     printf("程序结束!\n请按任意键关闭窗口!\n");
     getchar();
    }
    void InorderBST(BiTree T)
    {
        //以中序方式遍历二叉排序树T，即从小到大显示二叉排序树的所有元素
     if(T->lchild) InorderBST(T->lchild);
     printf("%2c",T->data);
     if(T->rchild) InorderBST(T->rchild);
    }
    
    void preorderBST(BiTree T)
    {
        //以先序方式遍历二叉排序树T，即从小到大显示二叉排序树的所有元素
     printf("%2c",T->data);
     if (T->lchild) InorderBST(T->lchild);
     if(T->rchild) InorderBST(T->rchild);
    }
    
    void postorderBST(BiTree T)
    {
        //以后序方式遍历二叉排序树T，即从小到大显示二叉排序树的所有元素
     if(T->lchild) InorderBST(T->lchild);
     if(T->rchild) InorderBST(T->rchild);
     printf("%2c",T->data);
    }
    
    BOOL SearchBST(BiTree T,char key,BiTree f,BiTree &p)
    {
        //在根指针T所指二叉排序树中递归的查找其关键字等于key的元素，若查找成功
     //则指针p指向该数据元素，并返回True,否则指针指向查找路径上访问的最后一
     BOOL tmp1,tmp2;
     tmp1=tmp2=False;
     if(!T) {
        p=f;return False;}  //查找不成功
     else if(key==T->data) {
        p=T;return True;} //查找成功
     else if(key<T->data) tmp1=SearchBST(T->lchild,key,T,p); //在左子树中继续查找
     else tmp2=SearchBST(T->rchild,key,T,p); //在右子树中继续查找
     if(tmp1||tmp2) return True; //若在子树中查找成功，向上级返回True
     else return False;          //否则返回False
    }
    
    BOOL InsertBST(BiTree &T,char e)
    {
        //当二叉排序树T中不存在元素e时，插入e并返回True,否则返回False
     BiTree p,s;
     if(!SearchBST(T,e,NULL,p)) //查找不成功
       {
        s=(BiTree)malloc(sizeof(BiTNode));
        s->data=e;
        s->lchild=s->rchild=NULL;
        if(!p) T=s;         //被插结点*s为新的根结点
        else if(e<p->data) p->lchild=s; //被插结点*s为左孩子
        else p->rchild=s;   //被插结点*s为右孩子
        return True;  //成功插入
       }
     else return False; //树中已存在关键字为e的数据元素
    }
    
    BOOL DeleteBST(BiTree &T,char key)
    {
        //若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素结点
     BOOL tmp1,tmp2;
     tmp1=tmp2=False;
     if(!T) return False;  //不存在关键字等于key的数据元素
     else
       {
        if(key==T->data) {
        Delete(T); return True;} 
           //找到关键字等于key的数据元素并删除它
        else if(key<T->data) tmp1=DeleteBST(T->lchild,key); //继续在左子树中删除
        else tmp2=DeleteBST(T->rchild,key);   //继续在右子树中删除
        if(tmp1||tmp2) return True;    //在子树中删除成功，返回True
        else return False;      //不存在该元素
       }
    }
    
    void Delete(BiTree &p)
    {
        //在二叉排序树中删除结点p,并重接它的左或右子树
     BiTree s,q;
     if(!p->rchild)  //右子树空，只需重接它的左子树
      {
        q=p;
       p=p->lchild;
       free(q);
      }
     else if(!p->lchild) //左子树空，只需重接它的右子树
      {
        q=p;
       p=p->rchild;
       free(q);
      }
     else  //左右子树均不空
      {
        q=p;
       s=p->lchild;
       while(s->rchild)
         {
        q=s;s=s->rchild;} //转左，然后向右走到尽头
       p->data=s->data;     //s指向被删结点的前驱
       if(q!=p) q->rchild=s->rchild; //重接*q的右子树
       else q->lchild=s->lchild;     //重接*q的左子树
       free(s);
      }
    }

**输入和输出的格式**  
输入：菜单选择功能插入，一个一个进行二叉排序树结点的输入  
输出：选择插入元素，删除元素功能，然后进行中序，先序，后序遍历并输出  
（注意：必须先建立树才能进行插入，删除，遍历功能）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70 3]  
**静态表折半查找**

#include <conio.h>
    #include <stdio.h>[文件包含]
    #define MAX 30    //定义有序查找表的最大长度
    typedef struct{
        
       char elem[MAX];       //有序查找表
       int length;             //length指示当前有序查找表的长度
    }SSTable;
    void initial(SSTable &);    //初始化有序查找表
    int search(SSTable,int);        //在有序查找表中查找元素
    void print(SSTable);             //显示有序查找表中所有元素
    void main()
    {
        SSTable ST;      //ST为一有序查找表
     int ch,loc,flag=1;
     char j;
     initial(ST);         //初始化有序查找表[初始化一个有序查找表ST]
     while(flag)
        {
         printf("请选择：\n");
          printf("1.显示所有元素\n");
          printf("2.查找一个元素\n");
          printf("3.退出\n");
          scanf(" %c",&j);
          switch(j)
    	{
        case '1':print(ST); break; //显示所有元素
    	 case '2':{
        printf("请输入要查找的元素：");
    		   scanf("%d",&ch);      //输入要查找的元素的关键字
    		   loc=search(ST,ch);    //查找
    		   if(loc!=0) printf("该元素所在位置是：%d\n",loc); //显示该元素位置
    		   else    printf("%d 不存在!\n",ch);//当前元素不存在
    		   break;
    		  }
    	 default:flag=0;
    	}
        }
     printf("程序运行结束!按任意键退出!\n");
    }
    void initial(SSTable &v)
    {
        //初始化有序查找表
     int i;
     printf("请输入静态表的元素个数："); //输入有序查找表初始化时的长度
     scanf("%d",&v.length);
     printf("请从小到大输入%d个元素（整形数）：\n",v.length);
     getchar();
     for(i=1;i<=v.length;i++) scanf("%d",&v.elem[i]);
    }
    
    int search(SSTable v,int ch)
    {
        //在有序查找表中查找ch的位置，成功返回其位置，失败返回0
     int low,high,mid;
     low=1;high=v.length; //置区间初值
     while(low<=high)
       {
        mid=(low+high)/2;
        if(v.elem[mid]==ch) return mid; //找到待查元素
        else if(v.elem[mid]>ch) high=mid-1; //继续在前半区间进行查找
        else low=mid+1;                     //继续在后半区间进行查找
     
       }
     return 0;     //找不到时，i为0
    }
    void print(SSTable v)          //显示当前有序查找表所有元素
    {
        int i;
     for(i=1;i<=v.length;i++) printf("%d ",v.elem[i]);
     printf("\n");
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70 4]  
**无序表中采用顺序查找算法**

#include<stdio.h>
    #define MAX_LENGTH 100
    typedef struct	
    {
        
    	int key[MAX_LENGTH];
    	int length;
    }stable;
    	int SeqSearch(stable ST,int key,int count)
    {
        int i;
    for(i=ST.length;i>0;i--)
    	{
        
    	count++;
    	if(ST.key[i]==key)
    	return i;
    	}
    return 0;
    }
    int Binsearch(stable ST,int key,int count)
    {
        
    	int low=1,high=ST.length,mid;
    	while(low<=high)
    	{
        
    		count++;
    		mid=(low+high)/2;
    		if(ST.key[mid]==key)
    			return mid;
    		else
    			if(key<ST.key[mid])
    				high=mid-1;
    			else
    				low=mid+1;
    	}
    return 0;
    }
    main()
    {
        
    	stable ST1;
    	int a,b,k,x,count1=0,count2=0,temp=0;
    	ST1.length=0;
    	printf("请按从小到大的顺序输入查找表数据:(-1代表结束!)\n");
    	for(a=0;a<MAX_LENGTH;a++)
    	{
        
    		scanf("%d",&temp);
    		if(temp!=-1)
    		{
        
    			ST1.key[a]=temp;
    			ST1.length++;
    		}
    		else
    			break;
    	}
    	printf("输入数据为: \n");
    	for(b=0;b<ST1.length;b++)
    	{
        
    		printf("%d",ST1.key[b]);
    	}
    	printf("\n请输入要查找的数据: ");
    	scanf("%d",&k);
    	a=SeqSearch(ST1,k,count1)+1;
    	printf("\n顺序查找:该数据的位置在第:%d个\n",a);
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70 5]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191211190145233.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191211190157359.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191211190207482.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/2019121119022248.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20191211190355964.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20191211190443252.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw==,size_16,color_FFFFFF,t_70