查找算法1——顺序查找

查找也称为检索，是指从一批记录中找到指定记录的过程。查找算法是程序设计处理非数值问题非常重要的操作。查找算法包括：基于线性表的查找，基于树的查找，哈希表查找。

基于线性表的查找包括顺序查找、折半查找，和分块查找。

【顺序查找】
顺序查找是指从表的一端开始，逐个将待查找元素与表中的每个元素进行比较，如果某个元素与待查找元素相等，则查找成功，函数返回该元素所在顺序表的位置。否则查找失败，返回0。

【示例】

假设有一个元素序列为73，12，67，32，21，39，55，48，待查找的元素为32。顺序查找元素32的过程如图所示。

将待查找元素32与第1个元素即下标为0的元素进行比较，如果不等，继续比较下一个元素，直到遇到第4个元素，查找成功。

code:

#include<stdio.h>
#define MaxSize 100
#include<iostream>
using namespace std;
typedef struct
{
	int list[MaxSize];
	int length;
}Table;
int SeqSearch(Table S, int x)
/*在顺序表中查找元素x，如果找到返回该元素在表中的位置，否则返回0*/
{
	int i = 0;
	while (i<S.length&&S.list[i] != x)	/*从表的第1个元素开始查找x*/
		i++;
	if (S.list[i] == x)				/*如果找到x，返回元素的位置*/
		return i + 1;
	else							/*否则返回0*/
		return 0;
}
void main()
{
	Table T = { { 73,12,67,32,21,39,55,48 },8 };
	int i, position, x;
	printf("表中的元素:\n");
	for (i = 0; i<T.length; i++)
		printf("%4d", T.list[i]);
	printf("\n请输入要查找的元素:");
	scanf("%d", &x);
	position = SeqSearch(T, x);
	if (position)
		printf("%d是表的第%d个元素.\n", x, position);
	else
		printf("没有找到%d.", x);
	system("pause");
}

结果：

【特点】
#顺序查找时间简单，但是效率低，主要用于效率不高的情况。
#顺序查找可以利用顺序结构实现也可以利用链式结构实现。
【效率分析】

假设表中有n个元素，则查找第i个元素需要进行n-i+1次比较，如果元素在表中出现的概率都相等即1/n，则顺序表在查找时的平均查找长度为：

$ASL_{success} = \sum \limits_{i=1}^{n}P_i C_i =\sum \limits_{i=1}^{n} \frac{1}{n} * (n-i+1) = \frac{n+1}{2}$

即查找成功时平均比较次数约为表长的一半。