/*基于线性表的查找法——顺序查找法      
顺序查找的缺点是n较大时，平均查找长度较大，效率低
优点对数据元素存储没有要求，顺序存储或链式存储均可；对表中记录的有序性也没有要求
*/
#include <stdlib.h>
#include<stdio.h>
#define LIST_SIZE 20

//链表结点类型
typedef struct {
    int key;
    int data;
}RecordType;

//链表数组结构
typedef struct {
    RecordType r[LIST_SIZE+1];      
    int length;
}RecordList;

//初始化链表数组
int Init_Seq(RecordList *RecordList){
    if (!RecordList->r) 
        return -1;
    else {
        RecordList->length = 0;
        return 1;
    }
}

//设置监视哨的顺序查找法 耿国华版本
int SeqSearch(RecordList l,int k){
    l.r[0].key = k;
    int i = l.length;
    while (l.r[i].key!=k)
        i--;
    return i;
}

/*不设置监视哨的顺序查找法 耿国华版本 
  虽然没有设置监视哨 但是还是空出来了第一个位置
  如果要实现从实际地址的第一个元素开始排序 那么i的条件则改为i>=0且如果查找失败的话 返回值要设置为-1 最后在输出下标的时候就需要index+1来调整
*/
int SeqSearch(RecordList l, int k) {
    int i = l.length;
    while (i>=1&&l.r[i].key != k)
        i--;
    if (i >= 1)
        return i;
    else
        return 0;
}

void main() {
    RecordList *S1 = (RecordList*)malloc(sizeof(RecordList));
    int a=Init_Seq(S1);
    //给链表数组赋值 如果在带有监视哨 要将数组的第一个位置空余出来不对其赋值
    for (int j = 0; j < 10; j++)
    {
        S1->r[j].key = j*2;
        S1->length++;
    }
    //数组成功赋值后的值
    printf("数组为：");
    for (int j = 0; j < 10; j++)
    {
        printf("%d ", S1->r[j].key);
    }
    //进行顺序查找 k代表关键字的值
    int k = 8;
    int index = SeqSearch(*S1, k);
    printf("\n关键字%d在%d个位置\n", k,index);

    system("pause");
}
 

 
线性表的顺序查找和折半查找
 
顺序查找
设置监视哨的顺序查找
非递归折半查找
递归折半查找
代码整合测试

 
顺序查找
 
//顺序查找
int Search_Seq01(SSTable ST,KeyType key)
{
	for(int i=ST.length;i>=1;i--)
		if(ST.R[i].key==key) return i;
	return 0;
}
 
设置监视哨的顺序查找
 
//设置监视哨的顺序查找
int Search_Seq02(SSTable ST,KeyType key)
{
	int i;
	ST.R[0].key = key;
	for(i=ST.length;ST.R[i].key!=key;i--);
	return i;
}
 
非递归折半查找
 
//非递归折半查找
int Search_Bin01(SSTable ST,KeyType key)
{
	int low=1,high=ST.length,mid;    //low和high分别为表的上下界 
	while(low<=high)
	{
		mid=(low+high)/2;     //取中间位置 
		if(ST.R[mid].key==key) return mid;    //找到给定值 
		else if(ST.R[mid].key>key) high = mid-1;   //前往前一个子表 
		else low = mid + 1;    //前往后一个子表 
	}
	return 0;
}
 
递归折半查找
 
//递归折半查找
int Search_Bin02(SSTable ST,KeyType key,int low,int high) 
{
	int mid = (low+high)/2;
	if(ST.R[mid].key==key) return mid;   //找到给定值 
	else if(ST.R[mid].key>key) Search_Bin02(ST,key,low,mid-1);   //前一个子表递归查找 
	else Search_Bin02(ST,key,mid+1,high);        //后一个子表递归查找 
}
 
代码整合测试
 
#include <stdio.h>
#include <stdlib.h>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20

typedef int Status;
typedef int KeyType;
typedef int InfoType;
typedef struct
{
	KeyType key;   //关键字域 
	InfoType otherInfo;   //其他域 
}ElemType;
typedef struct
{
	ElemType *R;   //储存空间基地址 
	int length;    //当前长度 
}SSTable;

//初始化一个自定义类型线性表
Status InitTable(SSTable *ST)
{
	ST->R = (ElemType *)malloc(MAXSIZE*sizeof(ElemType));    //开辟空间，别漏了sizeof(ElemType) 
	if(ST->R == NULL) return ERROR;
	ST->length =0;
	return OK;
}

//顺序查找
int Search_Seq01(SSTable ST,KeyType key)
{
	for(int i=ST.length;i>=1;i--)
		if(ST.R[i].key==key) return i;
	return 0;
}

//设置监视哨的顺序查找
int Search_Seq02(SSTable ST,KeyType key)
{
	int i;
	ST.R[0].key = key;
	for(i=ST.length;ST.R[i].key!=key;i--);
	return i;
}

//非递归折半查找
int Search_Bin01(SSTable ST,KeyType key)
{
	int low=1,high=ST.length,mid;    //low和high分别为表的上下界 
	while(low<=high)
	{
		mid=(low+high)/2;     //取中间位置 
		if(ST.R[mid].key==key) return mid;    //找到给定值 
		else if(ST.R[mid].key>key) high = mid-1;   //前往前一个子表 
		else low = mid + 1;    //前往后一个子表 
	}
	return 0;
}

//递归折半查找
int Search_Bin02(SSTable ST,KeyType key,int low,int high) 
{
	int mid = (low+high)/2;
	if(ST.R[mid].key==key) return mid;   //找到给定值 
	else if(ST.R[mid].key>key) Search_Bin02(ST,key,low,mid-1);   //前一个子表递归查找 
	else Search_Bin02(ST,key,mid+1,high);        //后一个子表递归查找 
}

int main()
{
	SSTable ST;
	InitTable(&ST);    //初始化顺序表 
	for(int i=1;i<=20;i++)   //循环赋值 
	{
		ST.R[i].key = i;
		ST.length+=1;
	}
	printf("%d\n",ST.R[Search_Seq02(ST,2)].key);    //由上往下对应查找 
	printf("%d\n",Search_Seq01(ST,3));
	printf("%d\n",Search_Bin01(ST,9));
	printf("%d",Search_Bin02(ST,14,1,20));
	return 0;
}

查找：
 
给定一个值k，在含有n个元素的表中找出关键字等于k的元素，若找到，则查找成功，否则，查找失败
 
 
 
查找前首先确定（1）存放数据的数据结构是什么（2）元素是否有序
 
动态查找表：查找的同时做修改操作（插入，删除）
 
静态查找表：查找中不涉及表的修改操作
 
内查找：整个查找过程都在内存中进行
 
外查找：查找过程需要访问外存
 
平均查找长度（ASL）：平均需要比较的次数
 
 
 ASL分为查找成功和查找失败两种情况
 
ASL越小，其时间性能越好
 
 
线性表的查找是一种最简单的查找表，分为顺序查找，折半查找（二分法） 
 
顺序查找：
 
思路：从表的一端向另一端逐个将关键字和定值k比较，若相等，则查找成功；否则查找失败
 
while(i<size&&key!=a[i])
{
i++;
}
if(i>=size)
{
//查找失败
}
else
{
//查找成功

}
 
性能分析：
 
查找成功的ASL:
 
 
 
 
 综上，线性表顺序查找的时间复杂度为O（n）
 
折半（二分）查找：
 
折半查找又叫二分查找，要求元素有序（递增或者递减），下面讨论递增的情况
 
思路：
 
nums[low,..,high]是当前查找区间，首先确定中点mid=(low+high)/2,然后将待查找的值k和
 
nums[mid]比较：
 
（1）nums[mid]=k,查找成功
 
（2）nums[mid]<k,说明k在右子表nums[mid+1,high]中
 
（3）nums[mid]>k.说明k在左子表nums[low,mid-1]中
 
重复这一过程
 
 
 
代码：
  
 
binsearch(int nums[],int k,int n)
{
int low=0;
int high=n-1;
while(low<=high)
{
mid=(low+high)/2;
  if(k==nums[mid])
 {
return mid;
}
else if(k<nums[mid])
{
high=mid-1;
}
else 
low=mid+1;
}
return -1;
}
 
 
二分查找的判定树（比较树）：
 
 
 内部节点：判定树中查找成功对应的节点
 
 外部节点：判定树中查找失败对应的节点
 
外部节点的构造方法：
 
对于内部节点的单分支点，添加一个孩子节点成为双分支节点；
 
对于内部节点的叶子节点，添加两个孩子节点成为双分支节点
 
 
 利用判定树求二分查找的ASL:
 
查找成功时，每个元素对应的概率为1/n,比较次数为根节点到该元素对应的节点的节点树（不是分支树）
 
查找失败是，每个外部节点的概率如果近似看出相等，每个外部节点的概率为1/N（N为外部节点的个数）,比较次数为根节点到外部节点的边的个数
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

为了方便描述过程，假定一个线性表结构体ArrayList
 
typedef struct ArrayList{
	int data[N];  
	int index;//初始值为-1，代表里面没有元素，使用时代表下标。
}*List;
 
 
第一种方法：顺序双指针法
 
 
 
 
指针i控制向后遍历，指针j记录需要交换的位置。、
 
 
1、进入循环，当遇到item元素时，不做任何处理，否则将指针i指向的值赋予指针j的位置，且指针j右移
 
 
2、循环终止，最终将线性表的index等于j-1的位置。（最后一步的index位置，看index的含义，代表下标就j-1，逻辑位置就直接等于j即可）
 
 
 
代码实现：
 
void deletes(List list,int item){
	int j=0;
	for(int i=0;i<=list->index;++i){
		if(list->data[i]!=item){
			list->data[j]=list->data[i];
			++j;
		}
	}
	list->index=j-1;
} 
 
 
第二种方法：前后双指针法
 
 
 
 
因为题目没有要求说非item元素是按照原来的顺序，所以可以采用该方法。
 
 
1、设置前后两个指针，i=0，j=index
 
 
2、i从前遍历，直到找到item元素的位置，j从后遍历，直到找到不是item元素的位置，将指针j指向的值放到指针i的位置，循环往复，直到i>j，结束循环。
 
 
3、设置index的位置。
 
 
 
代码实现：
 
void deletes(List list,int item){
	int i=0,j=list->index;
	while(i<=j){
		while(i<=j && list->data[i]!=item) i++;
		if(i<=j) while(i<=j && list->data[j]==item) j--;
		if(i<=j) list->data[i++]=list->data[j--];
	}
	list->index = j;
}
 
注意点：每次循环前都要先判断i，j的位置，防止出现越界，或不满足的情况。