顺序查找法

顺序查找法是程序设计中最常用到的算法之一，最原始的办法是从头到尾逐个查找。查找是在程序设计中最常用到的算法之一，假定要从n个整数中查找x的值是否存在，最原始的办法是从头到尾逐个查找，这种查找的方法称为顺序查找。

1、顺序查找：

（1）最好情况：要查找的第一个就是。时间复杂度为：O(1)。

（2）最坏情况：最后一个是要查找的元素。时间复杂度未：O(n)。

（3）平均情况下就是：（n+1）/2。

所以总的来说时间复杂度为：O(n)。

2、二分查找：O(log2n)->log以2为底n的对数。

解释：2^t = nt = log(2)n。

3、插值查找：O(log(2)(log(2)n))->log以2为底的（log以2为底的n的对数）的对数。

4、斐波那契查找：O(log2n)->log以2为底n的对数。

5、树表查找：

（1）二叉树：O(log2n)~O(n)之间。

（2）红黑树：O(lgn)。

（3）B和B+树：O(log2n)。

6、分块查找：O(log2n)~O(n)之间。

7、哈希查找：O(1)。

查找算法集：顺序查找、二分查找、插值查找、动态查找(数组实现、链表实现)

// search.cpp : Defines the entry point for the console application.

//

#include "stdafx.h"

#include "LinkTable.h"

#defineMAX_KEY 500

//------------------------------数组实现部分----------------------------------

/**//*

无序数组顺序查找算法函数nsq_Order_Search<用数组实现>

参数描述：

int array[]:被查找数组

int n:被查找数组元素个数

int key:被查找的关键值

返回值:

如果没有找到:nsq_Order_Search = -1

否则:nsq_Order_Search = key数组下标

*/

int nsq_Order_Search(int array[],int n,int key)

...{

int i

array[n] = key

/**//*for循环后面的分号必不可少*/

for(i=0key!=array[i]i++)

return(i<n?i:-1)

}

/**//*

有序数组顺序查找算法函数sq_Order_Search<用数组实现>

参数描述：

int array[]:被查找数组

int n:被查找数组元素个数

int key:被查找的关键值

返回值:

如果没有找到:sq_Order_Search = -1

否则:sq_Order_Search = key数组下标

*/

int sq_Order_Search(int array[],int n,int key)

...{

int i

array[n] = MAX_KEY

/**//*for循环后面的分号必不可少*/

for(i=0key>array[i]i++)

if(i<n &&array[i] == key)

return(i)

else

return(-1)

}

/**//*

有序数组二分查找算法函数sq_Dichotomy_Search0<用数组实现>

参数描述：

int array[]:被查找数组

int n:被查找数组元素个数

int key:被查找的关键值

返回值:

如果没有找到:sq_Dichotomy_Search0 = -1

否则:sq_Dichotomy_Search0 = key数组下标

*/

int sq_Dichotomy_Search0(int array[],int n,int key)

...{

int low,high,mid

low = 0

high = n - 1

while(low<=high)

...{

mid = (high+low)/2

if(array[mid] == key)

return(mid)

/**//*key>array[mid] 表明要求查找的值在[mid+1,high]*/

/**//*否则,在[low,mid-1]*/

if(key >array[mid])

low = mid + 1

else

high = mid - 1

}

return(-1)

}

/**//*

有序数组插值查找算法函数sq_Dichotomy_Search1<用数组实现>

(插值查找算法是二分查找算法的改进)

参数描述：

int array[]:被查找数组

int n:被查找数组元素个数

int key:被查找的关键值

返回值:

如果没有找到:sq_Dichotomy_Search1 = -1

否则:sq_Dichotomy_Search1 = key数组下标

*/

int sq_Dichotomy_Search1(int array[],int n,int key)

...{

int low,high,//二分数组的上,下标

pos //查找码的大致(估算)位置

low = 0

high = n-1

while(low <= high)

...{

pos = (key-array[low])/(array[high]-array[low])*(high-low)+low

/**//*找到关键值,中途退出*/

if(key == array[pos])

return(pos)

if(key >array[pos])

low = pos + 1

else

high = pos - 1

}

/**//*没有找到,返回-1*/

return(-1)

}

//------------------------------数组实现部分----------------------------------

//------------------------------链表实现部分----------------------------------

/**//*

无序链表顺序查找算法函数nlk_Order_Serach<用链表实现>

[查找思想:遍历链表的所有节点]

参数描述：

Node *head:被查找链表的首指针

int key:被查找的关键值

返回值:

如果没有找到:nlk_Order_Serach = NULL

否则:nlk_Order_Serach = 键值为key的节点的指针

*/

Node *nlk_Order_Serach(Node *head,int key)

...{

for(head!=NULL &&head->data != keyhead = head->link)

return(head)

}

/**//*

有序链表顺序查找算法函数lk_Order_Serach<用链表实现>

[查找思想:依次遍历链表的节点,发现节点不在key的范围时提前结束查找]

参数描述：

Node *head:被查找链表的首指针

int key:被查找的关键值

返回值:

如果没有找到:lk_Order_Serach = NULL

否则:lk_Order_Serach = 键值为key的节点的指针

*/

Node *lk_Order_Search(Node *head,int key)

...{

for(head!=NULL &&head->data <keyhead=head->link)

/**//*当遍历指针为NULL或没有找到键值为key的节点,返回NULL(表明没有找到)*/

/**//*否则,返回head(表明已经找到)*/

return(head==NULL || head->data != key ? NULL : head)

}

/**//*

有序链表动态查找算法函数lk_Dynamic_Search<用链表实现>

[查找思想:依次遍历链表的节点,发现节点不在key的范围时提前结束查找]

参数描述：

Node *head:被查找链表的首指针

Node **p 键值为key的节点的前驱指针(回传参数)

Node **q:键值为key的节点指针(回传参数)

int key:被查找的关键值

注意:

当 *p == NULL 且 *q != NULL,链表的首节点键值为key

当 *p != NULL 且 *q != NULL,链表的中间(非首,尾)节点键值为key

当 *p != NULL 且 *q == NULL,链表的尾节点键值为key

当 *p == NULL 且 *q == NULL,链表是空链表

*/

void lk_Dynamic_Search(Node *head,Node **p,Node **q,int key)

...{

Node *pre,*cur

pre = NULL

cur = head

for(cur != NULL &&cur->data <keypre = cur,cur = cur->link)

*p = pre

*q = cur

}

/**//*

有序链表动态插入算法函数lk_Dynamic_Insert<用链表实现>

参数描述：

Node *head:被插入链表的首指针

int key:被插入的关键值

返回值:

lk_Dynamic_Search = 插入键值为key的节点后的链表首指针

*/

Node *lk_Dynamic_Insert(Node *head,int key)

...{

Node

*x,//插入节点的前驱节点

*y,//插入节点的后续节点

*p //插入的节点

p = (Node *)malloc(sizeof(Node))

p->data = key

p->link = NULL

lk_Dynamic_Search(head,&x,&y,key)

if(x==NULL)

...{

p->link = x

head = p

}

else

...{

p->link = x->link

x->link = p

}

ListLinkTable(head,"插入节点")

return(head)

}

/**//*

有序链表动态删除算法函数lk_Dynamic_Delete<用链表实现>

参数描述：

Node *head:被删除链表的首指针

int key:被删除的关键值

返回值:

lk_Dynamic_Delete = 删除键值为key的节点后的链表首指针

*/

Node *lk_Dynamic_Delete(Node *head,int key)

...{

Node*x,//删除节点的前驱节点

*y //删除的节点

lk_Dynamic_Search(head,&x,&y,key)

if(x==NULL)

/**//*因为x=NLLL时,y指向首指针*/

head = y->link

else

x->link = y->link

free(y)

ListLinkTable(head,"删除节点")

return(head)

}

//------------------------------链表实现部分----------------------------------

int main(int argc, char* argv[])

...{

Node *head

//Node *p,*x,*y

int KEY

int count,i

//int result

KEY = 11

//PrintArrayValue(TestArray2,DEFAULT_ARRAY_SIZE,"原始")

//result = sq_Dichotomy_Search1(TestArray2,DEFAULT_ARRAY_SIZE,KEY)

//printf("查找结果是：数组[%d] = %d ",result,TestArray2[result])

head = CreateLinkTable(DEFAULT_ARRAY_SIZE,TestArray2)

ListLinkTable(head,"原始")

/**//*

p = lk_Order_Search(head,KEY)

if(p==NULL)

printf(" 查找结果是：指定链表中没有[数据域 = %d]的节点! ",KEY)

else

printf(" 查找结果是：节点.Data = %d 节点.Link = %d 节点.Addr = %d ",p->data,p->link,p)

*/

printf("输入插入节点的个数： ")

scanf("%d",&count)

for(i=0i<counti++)

...{

printf("输入插入节点的数据域： ")

scanf("%d",&KEY)

lk_Dynamic_Insert(head,KEY)

}

do

...{

printf("输入删除节点的数据域： ")

scanf("%d",&KEY)

lk_Dynamic_Delete(head,KEY)

}while(head!=NULL)

printf(" 应用程序正在运行...... ")

return 0

}

#include <stdio.h>

#include <stdlib.h>

#define MAX_LENGTH 100

typedef int KeyType

typedef struct {

KeyType *elem

int length

}SSTable//顺序表的存储结构

/*

此算法比第二个算法多了一个判定i是否出界的流程，对于查找数目较少的情况，

二者查找时间相差不大，对于存在大量数据时，该算法的主要查找时间消耗再判

定是否出界上，所以第二个算法明显比第一个算法好，唯一增加的就是一个“哨兵”

数据。

int Search_Seq(SSTable ST, KeyType key){

int i

for(i=1i<=ST.length &&ST.elem[i] != keyi++ )

if(i<=ST.length)

return i

else

return 0

}

*/

int Search_Seq(SSTable ST, KeyType key){

int i

ST.elem[0] = key//“哨兵”，如果顺序表中不存在要查找的数据的话，则查找指针必定指向该哨兵

for(i = ST.lengthST.elem[i] != keyi--)

return i //找到的话，则i != 0,否则i = 0

}

void main()

{

int i, key

SSTable T

T.elem = (KeyType *)malloc(sizeof(KeyType))

printf("How Many Entries Do You Want input\n")

scanf("%d", &T.length)

for(i=1i<=T.lengthi++){

printf("Please input the %dth entries \n", i)

scanf("%d", &T.elem[i])

}

for (i=1i<=T.lengthi++)

printf("%5d",T.elem[i])//显示已经输入的所有数据

printf("\nPlease input the data you want to search\n")

scanf("%d", &key)

i = Search_Seq(T,key)

printf("the search data is locate the %dth(0 indicate can not find)\n",i)

}

---