实现折半查找(数据结构与算法 - 查找)

梦里梦外; 2023-05-21 08:47 29阅读 0赞

#### 相关知识 ####

折半查找通常是针对顺序存储的线性表，线性表的结点按关键码从小到大排序，后面称之为折半查找的顺序表。为了简化讨论，假设折半查找的顺序表中每个结点只含一个关键码，关键码为整数。图 1 给出了一个存储了 4 个关键码的折半查找的顺序表的存储结构图。  
下面描述了线性表顺序存储的一种实现方案。该实现方案的示意图为：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YW5nemlndWFuZw_size_16_color_FFFFFF_t_70]  
指针pkey是存储关键码的连续空间的起始地址，顺序表中当前的关键码的个数由len给出，该顺序表中最多可存储max个关键码。  
将pkey、len、max组织成一个结构，该结构定义为：

struct BSeqList
    { 
        int* pkey;  // 指向关键码数组的指针
        int len;  // 当前元素个数
        int max;  // 线性表的最大元素数
    };

只要给定指向该结构的一指针blist，就可对线性表进行操作。  
对折半查找的顺序表定义如下操作，各个操作函数的功能详见下面给出的代码文件 BSlist.cpp 的代码框架：

BSeqList* BSL_Create(int size);
    void BSL_Free(BSeqList* blist);
    int BSL_InsKey(BSeqList* blist, int key);
    int BSL_FindKey(BSeqList* blist, int key);
    int BSL_DelKey(BSeqList* blist, int key);
    void BSL_Print(BSeqList* blist);

输入输出格式说明  
输入格式：  
首先输入一个正整数max，创建一个最多可存储max个元素的表。  
然后输入多个操作：如果输入 “insert” ，则后面跟一个数x，表示将x插入；如果输入 “delete” ，则后面跟一个数x，表示将x删除；如果输入 “end” ，表示输入结束。  
输出格式：  
输出表的长度，然后从表头到表尾依次输出各元素。  
以下是平台对 step1/Main.cpp 的样例测试集：  
样例输入：

9
    insert 9
    insert 8
    insert 89
    insert 11
    insert 22
    insert 13
    delete 11
    delete 5
    end

样例输出：

list length: 5
    The list contains: 8  9  13  22  89

//折半查找的顺序表 实现文件
    //每个结点的数据是关键码
    //
    #include <stdio.h>
    #include <stdlib.h>
    #include "BSlist.h"
    BSeqList* BSL_Create(int size)
    //创建一个顺序表
    //与BSL_Free()配对
    { 
        BSeqList* blist=(BSeqList*)malloc(sizeof(BSeqList));
        blist->pkey = (int*)malloc(sizeof(int)*size);
        blist->max=size;
        blist->len=0;
        return blist;
    }
    void BSL_Free(BSeqList* blist)
    //释放/删除顺序表
    //与BSL_Create()配对
    { 
        free(blist->pkey);
        free(blist);
    }
    int BSL_FindKey(BSeqList* blist, int key)
    //在排序的顺序表中查找关键码值为key的结点，返回结点的编号
    //返回值大于等于0时表示找到值为key的结点的编号，-1表示没有找到
    { 
        int k, r, m;
        k=0; r=blist->len-1;
        while (k<=r) 
        { 
            m=(k+r)>>1; //m=(k+r)/2
            if (key==blist->pkey[m]) 
      	{ 
       	    return m; 
      	}
            else
            { 
                if (key<blist->pkey[m])  
       	    { 
        		r=m-1; 
       	    }
                else 
       	    { 
        		k=m+1; 
       	    }
      	}    
        }
        return -1;
    }
    int BSL_InsKey(BSeqList* blist, int key)
    //在排序的顺序表中插入一个值为key的结点
    //返回值大于等于0时表示插入的位置, -1表示表满（无法插入）
    { 
        if (blist->len>=blist->max) 
        { 
      	return -1; 
        }
        int k, r, m;
        k=0; r=blist->len-1;
        //寻找插入位置
        while (k<=r) 
        { 
            m=(k+r)>>1; //m=(k+r)/2
            if (key == blist->pkey[m]) 
            { 
                return -2;若不允许插入已存在的值，则需要此行
            }
            if (key<blist->pkey[m])  
            { 
                r=m-1;
            }
            else 
            { 
                k=m+1;
            }
        }
        //插入位置为k, 腾出k号位置
        for (r=blist->len; r>k; r--) 
        { 
         blist->pkey[r]=blist->pkey[r-1];
     }
        //key放入k号位置
        blist->pkey[k]=key;
        blist->len++;
        return k;
    }
    int BSL_DelKey(BSeqList* blist, int key)
    //在排序的顺序表中删除值为key的结点, 
    //存在值为x的结点则返回结点编号, 未找到返回－1
    { 
        int k=BSL_FindKey(blist, key);
        if (k<0) 
        { 
      	return -1; 
        }
        int i=k;
        while(i < blist->len-1) 
        { 
            blist->pkey[i] = blist->pkey[i+1];
            i++;
        }
        blist->len --;
        return k;
    }
    void BSL_Print(BSeqList* blist)
    //打印整个顺序表
    { 
        if (blist->len==0) 
        { 
            printf("The list is empty.\n");
            return;
        }
        printf("The list contains: ");
        for (int i=0; i<blist->len; i++) 
        { 
            printf("%d ", blist->pkey[i]);
        }
        printf("\n");
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YW5nemlndWFuZw_size_16_color_FFFFFF_t_70]: /images/20230521/953b69e822fd4c6895b18a04dda553be.png