C语言顺序查找程序

//顺序查找

//思路:从仔饥表中最后一个记录开始，逐个进行记录的关键字和

//给定值的比较，若某个记录的关键字和给定值比较相等，则

//返回返回记录所在的位置，或查找完所有记录后还没有发现

//符合的记录，则查找失败。

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

#include <time.h>

#define N 10

typedef int DataType//定义比较的元素类型

//静态查找表的顺序存储结构

typedef struct{

DataType * data//数据元素存储空间基址，按实际长度分配，0号单元留空

//建表时按实际长度分配，0 号单元留空

int length//表长度

}SSTable

//创建一个静态表，内容为20以内的随机数

void createST(SSTable* ST,int n){

int i

time_t t

if(ST!=NULL){

ST->data=(DataType*)calloc(n+1,sizeof(DataType))

if(ST->data!=NULL){

srand((unsigned) time(&t))

for(i=1i<=ni++){

ST->data[i]=rand() //产生20以内的随机数

}

ST->length=n

}

}

}

//创建一个静态表，内容按从小到大排列，以便折半查找

void createST_binary(SSTable* ST,int n){

int i,j=0

time_t t

if(ST!=NULL){

ST->data=(DataType*)calloc(n+1,sizeof(DataType))

if(ST->data!=NULL){

for(i=1i<=ni++){

ST->data[i]=j

j+=4

}

ST->length=n

}

}

}

//打印出静态表的内容

void print_SSTable(SSTable* ST){

int i,n=ST->length

if(ST!=NULL){

for(i=1i<=ni++){

printf("%d ",ST->data[i])

}

printf("\n")

}

}

//顺序查找(Sequential Search)

//思路:从表中最后一个记录开始，逐个进行记录的关键字和

//给定值的比较，若某个记录的关键字和给定值比较相等，则

//返回返回记录所在的位置，或查找完所有记录后还没有发现

//符合的记录，则查找失败。

//查找成功：返回记录所在位置

//查找失败：返回0

int search_seq(SSTable ST,DataType key){

int i

if(ST.data==NULL)return 0

ST.data[0]=key//设置监视哨。目的在于免去查找过程中每一步都要检测整

//个表是否查找完毕，是一个很有效的程序设计技巧 。监视

//哨也可以设在高下标处。

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

return i

}

//折半查找(Binary Search)

//当记录的key按关系有序时可以使用折半查找

//思路：对于给定key值，逐步确定待查记录所在区间，每次将搜索空间减少一半念咐返（折半），

//直到查找成功或失败为止。

int search_binary(SSTable ST,DataType key){

int low,high,mid

low=1

high=ST.length

while(low<=high){//当表简凯空间存在时

mid=(low+high)/2

if(ST.data[mid]==key){

return mid//查找成功，返回mid

}

if(key<ST.data[mid]){

high=mid-1//继续在前半区间查找

}else{

low=mid+1//继续在后半区间查找

}

}

return 0//查找失败

}

//分块查找（只记录思想）

//分块查找中，设记录表长为n，将表的n个记录分成b=n/s个块，每个s个记录

//最后一个记录数可以少于s个，且表分块有序，即后一个块的所有key值大于

//前一个块的所有key值

//每块对应一个索引项，索引项记录了该块记录的最大key值和该块第一记录的指针（或序号）

//算法：

//（1）由索引表确定待查找记录所在的块；

//（2）在块内顺序查找。

int main(){

int n=20//在20个数中查找,方便看结果，不要设置得太大

SSTable ST,ST_binary//分别用于顺序查找和折半查找的静态表

index indtb[n+1]//索引表，用于分块查找

createST(&ST,n)//创建一个随机静态表

createST_binary(&ST_binary,n)//创建一个从小到大顺序排列的静态表

//采用顺序查找

printf("原始数据:")

print_SSTable(&ST)

printf("顺序查找5的结果:%d\n",search_seq(ST,5))

printf("顺序查找10的结果:%d\n",search_seq(ST,10))

printf("顺序查找12的结果:%d\n",search_seq(ST,12))

printf("顺序查找15的结果:%d\n",search_seq(ST,15))

printf("顺序查找20的结果:%d\n",search_seq(ST,20))

printf("--------------------------------------------\n")

//采用折半查找

printf("原始数据:")

print_SSTable(&ST_binary)

printf("折半查找5的结果:%d\n",search_binary(ST_binary,5))

printf("折半查找10的结果:%d\n",search_binary(ST_binary,10))

printf("折半查找12的结果:%d\n",search_binary(ST_binary,12))

printf("折半查找15的结果:%d\n",search_binary(ST_binary,15))

printf("折半查找20的结果:%d\n",search_binary(ST_binary,20))

system("pause")//暂停一下，看看结果

free(ST.data)//不要忘了释放堆空间

return 0

}

你可以这样想，如果燃颤没有这句话呢》？

int Search_Seq(SSTable ST,KeyType key){

//在顺序表中顺序查找其关键字等于key的数据元素。

//ST.elem[0].key = key

for(i=ST.length!EQ(ST.elem[i].key,key)--i)

return i

}//Search_Seq

看程序怎么执行的：

for

i 指向数组最后一个元素，

判断是否相等，若相等，跳滑明出循环；不等，继续执行；

i = i - 1；

当程序执行至i = 0时，此时数组元素已经被判断结束，若继续执行，就会内存泄漏，就是数组下标信段告越界。编译也许没问题，运行就会出错。

查找表：

是由同一类型的数据元素（或记录）构成的集合。

查找表的 *** 作：

1、查询某个“特定的”数据元素是否在查找表中。

2、检索某个“特定的”数据元素的各种属性。

3、在查找表中插入一个数据元素；

4、从查找表中删去某个数据元素。

静态查找表

对查找表只作前两种 *** 嫌唤作

动态查找表

在查找过程中查找表元素集合动态改变

关键字

是数据元素（或记录）中某个数据项的值

主关键字

可以唯一的地标识一个记录

次关键字

用以识别若干记录

查找

根据给定的某个值，在查找表中确定一个其关键字等于给定的记录或数据元素。若表中存在这样的一个记录，则称查找是成功的，此时查找的结果为给出整个记录的信息，或指示该记录在查找表中的位键者虚置；若表中不存在关键字等于给定值的记录，则称查找不成功。

一些约定：

典型的关键字类型说明：

typedef float KeyType//实型

typedef int KeyType//整型

typedef char *KeyType//字符串型

数据元素类型定义为：

typedef struct{

KeyType key// 关键字域

...

}ElemType

对两个关键字的比较约定为如下的宏定义：

对数值型关键字

#define EQ(a,b) ((a)==(b))

#define LT(a,b) ((a)<(b))

#define LQ(a,b) ((a)<=(b))

对字符串型关键字

#define EQ(a,b) (!strcmp((a),(b)))

#define LT(a,b) (strcmp((a),(b))<0)

#define LQ(a,b) (strcmp((a),(b))<=0)

二、静态查找表

静态查找表的类型定义：

ADT StaticSearchTable{

数据对象D：D是具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标识数据元素的关键字。

数据关系R：数据元素同属一个集合。

基本 *** 作P：

Create(&ST,n)

*** 作结果：构造一个含n个数据元素的静态查找表ST。

Destroy(&ST)

初始条件：静态查找表ST存在。

*** 作结果：销毁表ST。

Search(ST,key)

初始条件：静态查找表ST存在，key为和关键字类型相同的给定值。

*** 作结果：若ST中在在其关键字等于key的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。

Traverse(ST,Visit())

初始条件：静态查找表ST存在，Visit是对元素 *** 作的应用函数。

*** 作结果：按某种次序对ST的每个元素调用函数visit()一次且仅一次。一旦visit()失败，则 *** 作失败。

}ADT StaticSearchTable

三、顺序表的查找

静态查找表的顺序存储结构

typedef struct {

ElemType *elem

int length

}SSTable

顺序查找：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之，查找不成功。

int Search_Seq(SSTable ST,KeyType key){

ST.elme[0].key=key

for(i=ST.length!EQ(ST.elem[i].key,key)--i)

return i

}

查找 *** 作的性能分析：

查找算法中的基本 *** 作是将记录的关键字和给定值进行比较，，通常以“其关键字和给定值进行过比较的记录个数的平均值”作为衡量依据。

平均查找长度：

为确定记录在查找表中稿燃的位置，需用和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度。

其中：Pi为查找表中第i个记录的概率，且；

Ci为找到表中其关键字与给定值相等的第i个记录时，和给定值已进行过比较的关键字个数。

等概率条件下有：

假设查找成功与不成功的概率相同：

---