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

}

#include <stdio.h>

#define LENGTH 20

void SequenceSearch(int *fp,int Length)

void Search(int *fp,int length)

void Sort(int *fp,int length)

void main()

{

 int count

 int arr[LENGTH]

 printf("请输入你的数据的个数:\n")

 scanf("%d",&count)

 printf("请输入%d个数据\n",count)

 for(int i=0i<counti++)

 {

  scanf("%d",&arr[i])

 }

 

 int choise=0

 do 

 { 

  printf("1.使用顺序查询.\n2.使用二分查找法查找.\n3.退出\n")

  scanf("%d",&choise)

  if(choise==1)

   SequenceSearch(arr,count)

  else if(choise==2)

   Search(arr,count)

  else if(choise==3)

   break 

 } while (choise==1||choise==2||choise==3)

}

void SequenceSearch(int *fp,int Length)

{

 int data

 printf("开始使用顺序查询.\n请输入你想要查找的数据.\n")

 scanf("%d",&data)

 for(int i=0i<Lengthi++)

  if(fp[i]==data)

  {

   printf("经过%d次查找，查找到数据%d.\n",i+1,data)

   return 

  }

 

 printf("经过%d次查找，未能查找到数据%d.\n",i,data)

}

void Search(int *fp,int length)

{

 int data

 printf("开始使用顺序查询.\n请输入你想要查找的数据.\n")

 scanf("%d",&data)

 printf("由于二分查找法要求数据是有序的，现在开始为数组排序.\n")

 Sort(fp,length)

 printf("数组现在已经是从小到大排列,下面将开始查找.\n")

 int bottom,top,middle

 bottom=0

 top=length

 

 int i=0

 while (bottom<=top)

 {

  middle=(bottom+top)/2

  i++

  if(fp[middle]<data)

  {

   bottom=middle+1

  }

  else if(fp[middle]>data)

  {

   top=middle-1

  }

  else

  {

   printf("经过%d次查找，查找到数据%d.\n",i,data)

   return

  }

 }

 printf("经过%d次查找，未能查找到数据%d.\n",i,data)

}

void Sort(int *fp,int length)

{

 printf("现在开始为数组排序，排列结果将是从小到大.\n")

 

 int temp

 for(int i=0i<lengthi++)

  for(int j=0j<length-i-1j++)

   if(fp[j]>fp[j+1])

   {

    temp=fp[j]

    fp[j]=fp[j+1]

    fp[j+1]=temp

   }

   

   printf("排序完成!\n下面输出排序后的数组:\n")

   for(int k=0k<lengthk++)

   {

    printf("%5d",fp[k])

   }

   printf("\n")

   

}

顺序查找法是程序设计中最常用到的算法之一，最原始的办法是从头到尾逐个查找。查找是在程序设计中最常用到的算法之一，假定要从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)。

---