【数据结构】-顺序查找

旧城等待， 2023-03-06 05:21 4阅读 0赞

### 顺序查找 ###

*  1.头文件及类型定义
 *  2.顺序表类型定义
 *  3.函数声明
 *  4.基本操作
 *   *  4.1 初始化顺序表
     *  4.2 赋值
     *  4.3 顺序查找★★★
     *  4.4 main函数
 *  5.小结

# 1.头文件及类型定义 #

#include<stdio.h>
    #include<stdlib.h>
    #define InitSize 10		//初始化数组长度
    #define ElemType int

# 2.顺序表类型定义 #

//顺序查找表类型定义-顺序表(动态分配)
    typedef struct {
        
    	ElemType* elem;		//用动态数组存放数据元素
    	int length;			//顺序表的当前长度
    }SSTable;

# 3.函数声明 #

/*函数声明*/
    void InitTable(SSTable& ST);					//1.初始化顺序表
    bool AssignTable(SSTable& ST);					//2.赋值
    int Search_Seq(SSTable ST, ElemType key);		//3.顺序查找

# 4.基本操作 #

## 4.1 初始化顺序表 ##

//1.初始化顺序表
    void InitTable(SSTable& ST) {
        
    	ST.elem = (ElemType*)malloc(sizeof(ElemType) * InitSize);		//初始化动态数组基址
    	ST.length = 0;
    }

## 4.2 赋值 ##

//2.赋值(仅做测试)
    bool AssignTable(SSTable& ST) {
        
    	int i = 1;
    	ElemType x;
    	scanf("%d", &x);
    	while (x != -1) {
        		//输入-1结束顺序表赋值
    		if (ST.length >= InitSize-1)		//判断当前存储空间是否已满，若已满，不能插入
    			return false;
    		ST.elem[i] = x;
    		ST.length++;
    		i++;
    		scanf("%d", &x);
    	}
    	return true;
    }

## 4.3 顺序查找★★★ ##

//3.顺序查找
    int Search_Seq(SSTable ST, ElemType key) {
        
    	int i;		//循环变量&数组下标
    	ST.elem[0] = key;	//"哨兵"
    	for (i = ST.length; ST.elem[i] != key; --i);	//从后往前
    	return i;		//若表中不存在关键字为key的元素，将查找到i为0时退出for循环
    }

## 4.4 main函数 ##

int main() {
        
    	SSTable ST;			//声明顺序表
    	InitTable(ST);		//初始化顺序表
    
    	printf("顺序表赋值开始，请依次输入元素：");
    	if (!AssignTable(ST))	
    		printf("输入元素个数大于顺序表长度，赋值失败！");
    	else {
        
    		printf("当前顺序表的长度为:%d\n", ST.length);
    		int key;		
    		printf("请输入您要查找的值：");
    		scanf("%d", &key);
    		if (!Search_Seq(ST, key))
    			printf("当前顺序表中无此元素！");
    		else
    			printf("您要查找的元素所在位序为：%d", Search_Seq(ST, key));
    	}	
    	return 0;
    }

# 5.小结 #

*  说明  
    顺序查找也称**线性查找**，主要用于在**线性表**中进行查找。通常分为关键字**无序**的顺序查找和关键字**有序**的顺序查找。本文实现的是无序的顺序查找，当关键字有序时，查找失败可以不用再比较到表的另一端就能返回查找失败的信息，从而降低顺序查找失败的平均查找长度。
    
    需要注意的是，顺序查找不是就必须要用顺序表，顺序查找的线性表既可以是**顺序存储结构**\->顺序表；又可以是**链式存储结构**\->链表，本文实现的方式是动态分配的顺序表，其他存储结构也类似。