顺序查找算法、二分（折半）查找算法详解【数据结构实验报告】

素颜马尾好姑娘i 2022-10-09 03:05 164阅读 0赞

### 文章目录 ###

*   *  一、顺序查找算法
     *  二、折半查找算法（二分查找）

## 一、顺序查找算法 ##

**1、算法核心**  
在顺序表ST中顺序查找其关键字等于key的元素，若找到，则函数值为该元素所在元素表中的位置。

**2、实现过程（详解在每一步的注释里）**

#include<iostream>
    using namespace std;
    
    typedef int KeyType;  //给int的别名KeyType
    typedef int InfoType;  //给int的别名InfoType 
    //数据元素类型定义 
    typedef struct
    { 
    	KeyType key;  //定义数据的关键字域
    	InfoType otherinfo;  //定义数据的其他域 
    } ElemType;  //数据元素类型名 
    //顺序表定义
    typedef struct
    { 	
    	ElemType R[10];  //存储空间的基地址（用R[]数据可以正常输出） 
    	int length;  //顺序表的长度
    }SStable;  //表类型名
    
    //表的初始化
    void Init_SStable(SStable &ST)
    { 
    	int i;
    	ST.length= 10;  //表长设为10 
    	//设置表的数据 
    	for(i=0; i<ST.length; i++)
    	{ 
    		ST.R[i].key= (i+10);  //初始化为从0开始的数字 
    		//正常输出，cout << ST.R[i].key << " "; 
    	}
    } 
    
    //设置监视哨的顺序查找函数
    int Search_Seq(SStable &ST, KeyType key) 
    { 
    	int i=0;  //遍历的下标 
    	ST.R[0].key= key;  //先定个初值 
    	for(i=ST.length; ST.R[i].key!=key; --i) ; //从后往前查找，若找到等值，则跳出循环 
    	return(i);  //并返回该遍历到的元素下标
    }
    
    int main()
    { 
    	SStable st;  //创建一个空表
    	Init_SStable(st);  //初始化顺序表 
    	
    	ElemType key;  //创建一个待查数据元素
    	key.key= 18;  //待查找元素值 
    	
    	int res= Search_Seq(st, key.key);  //在st中查找18的位置 
    	cout << "key在顺序表中的下标为：" << res << endl;
    	
    	//正常输出 
    // for(int i=0; i<st.length; i++)
    // { 
    // cout << st.R[i].key << " "; 
    // }
    }

**3、测试效果（在key.key的值那里做修改）**  
![1-1][]  
![1-2][]

## 二、折半查找算法（二分查找） ##

**1、算法核心**  
在有序表ST中折半查找其关键字等于key的数据元素，若找到，则函数值为该元素所在元素表中的位置，否则为0。

**2、实现过程（详解在每句注释中）**

#include <iostream>
    using namespace std;
    
    typedef int KeyType;  //给int的别名KeyType
    typedef int InfoType;  //给int的别名InfoType 
    //数据元素类型定义 
    typedef struct
    { 
    	KeyType key;  //定义数据的关键字域
    	InfoType otherinfo;  //定义数据的其他域 
    } ElemType;  //数据元素类型名 
    //顺序表定义
    typedef struct
    { 	
    	ElemType R[10];  //存储空间的基地址（用R[]数据可以正常输出） 
    	int length;  //顺序表的长度
    }SStable;  //表类型名
    
    //顺序表的初始化
    void Init_SStable(SStable &ST)
    { 
    	int i;
    	ST.length= 10;  //表长设为10 
    	//设置表的数据 
    	for(i=0; i<ST.length; i++)
    	{ 
    		ST.R[i].key= (i+10);  //初始化为从0开始的数字 
    	}
    } 
    
    //二分查找函数算法核心 
    int Search_Bin(SStable &ST, KeyType key)
    { 
    	int low=1;  //设置查找区间的初值，从1到最后一个 
    	int high= ST.length;
    	int mid;  //查找的中间下标 
    	
    	while(low<=high)  //不断遍历
    	{ 
    		mid= (low+high)/2;
    		if(key==ST.R[mid].key) return mid;  //找到待查找元素key 
    		else if(key<ST.R[mid].key) high=mid-1;  //继续在前一部分进行查找（因为前提ST是有序的表） 
    		else low=mid+1;  //继续在后一部分进行查找
    	}
    	return 0;  //表中不存在待查找元素 
    }
    
    int main()
    { 
    	SStable st;  //创建一个空表
    	Init_SStable(st);  //初始化顺序表 
    	
    	ElemType key;  //创建一个待查数据元素
    	key.key= 14;  //待查找元素值 
    	
    	int res= Search_Bin(st, key.key);  //在st中查找5的位置 
    	cout << "key在顺序表中的下标为：" << res << endl;	
    }

**3、测试效果（修改key.key）**  
![2-1][]  
![2-2][]

[1-1]: /images/20221005/73ccf465e6d34a0d876bac1cc5277041.png
[1-2]: /images/20221005/42f561590d2e4668bd3a08c6c129adbc.png
[2-1]: /images/20221005/86be15cb499140a4862890e0bc5d4b43.png
[2-2]: /images/20221005/27303ea75a224c3abb69487e9b54bfa5.png