顺序查找
算法描述
顺序比较即可。
平均查找长度
(n+1)/2, 其中n为表长。
时间复杂度
O(n)
#include "stdio.h"
typedef struct student{
int id; /*学生编号*/
char name[]; /*学生姓名*/
float score; /*成绩*/
}Student; int search(Student stu[],int n,int key){
int i;
for(i=; i<n; i++)
if( stu[i].id == key ) /*查找成功*/
return i;
return -; /*查找失败*/ }
void main()
{
Student stu[] = {{,"TOM",} ,
{,"LILY",},
{,"ANN",},
{,"LUCY",}
}; /*初始化结构体数组*/
int addr; /*要查找的记录的地址*/
addr = search(stu,,);
printf("Student ID: %d\n",stu[addr].id); /*输出查找到的记录的信息*/
printf("Student name: %s\n",stu[addr].name);
printf("Student score: %f\n",stu[addr].score);
}
折半查找
算法描述
限制：待查表必须是有序的向量(在内存中连续存储)
首先和数组中点比较，如果等于则返回，如果小于中点则在左边区间查找，如果大于中点则在右边区间查找。
平均查找长度
lg(n+1)
#include "stdio.h"
bin_search(int A[],int n,int key){
int low,high,mid;
low = ;
high = n-;//因为从0开始，所以减1
while(low<=high)
{
mid = (low + high)/;//从中间开始找，先找出中间的数为多少
if(A[mid]==key)return mid; /*查找成功，返回mid*/
if(A[mid]<key){
low = mid + ; /*在后半序列中查找*/
}
if(A[mid]>key){
high = mid - ; /*在前半序列中查找*/
}
}
return -; /*查找失败，返回-1*/
}
main()
{
int A[] = {,,,,,,,,,},i,n ,addr;
printf("The contents of the Array A[10] are\n");
for(i=;i<;i++)
printf("%d ",A[i]); /*显示数组A中的内容*/
printf("\nPlease input a interger for search\n");
scanf("%d",&n); /*输入待查找的元素*/
addr = bin_search(A,,n); /*折半查找，返回该元素在数组中的下标*/
if(- != addr) /*查找成功*/
printf("%d is at the %dth unit is array A\n ",n,addr);
else printf("There is no %d in array A\n",n); /*查找失败*/
}