C语言顺序表顺序查找和折半查找的基本思想和应用

顺序查找算法：又称为线性查找，主要用在—线性表—中进行查找

通常分为：1—无序线性表的一般查找；

2—对关键字有序的顺序表查找；

优缺点分析：

缺点：当线性表的表长过于长时，平均查找长度较大，效率低。

优点：对顺序表中数据元素的存储没有要求，顺序存储链式存储均可。

需注意：对于线性表的链式存储只能使用顺序查找.

折半查找，又称二分查找，它仅适用于有序的顺序表

首先将给定值key与表中间位置元素的关键字比较，若相等，则查找成功，返回该元素的存储位置；(例如，在查找表升序排列时，若给定值key大于中间元素的关键字，则所查找的关键字只可能在后半部分)若不等，则所需查找的元素只能在中间元素以外的前半部分或后半部分中；然后在缩小范围内继续进行同样的查找，如此重复直到找到为止，若查找不成功，返回查找失败信息

优缺点分析：

折半查找方法的优点：折半查找的优点是比较次数少，查找速度快，平均性能好；

折半查找方法的缺点：折半查找的缺点是：要求待查表为有序表，且插入删除困难。

因此：折半查找方法适用于不经常变动而查找频繁的有序列表。

目的是：⑴ 输入一批整型数据，建立顺序表，然后用顺序查找；

⑵ 输入一批有序整型数据（如从小到大），然后用折半查找，查找一给定的整数。

#include <stdlib.h>#define maxsize 20//全局定义#define OK 1#define OVERFLOW -2typedef struct{int key;//关键字}ElemType;typedef struct{ElemType *elem;int length;}sqlist;int initList(sqlist &L){L.elem=new ElemType[maxsize];//分配数组存储空间if(!L.elem) exit (OVERFLOW);L.length=0;return OK;}void display(sqlist &L)//自定义输出函数，将顺序表的key值输出。{int i;for(i=0;i<L.length;i++)printf("%d ",L.elem[i].key);printf("\n");}void get(sqlist &L,int size)//3.自定义取值函数利用循环依次为elem[i].key取值，{for(int i=0;i<size;i++){scanf("%d",&L.elem[i].key);L.length++;}}int search(sqlist L,int key)//自定义顺序查找函数，在顺序表L中顺序查找其关键字等于key的数据元素，若找到，则函数值为该元素在表中的位置，否则为0.{for(int i=L.length;i>=1;--i)if(L.elem[i].key==key) return i;return 0;}int search_Bin(sqlist L,int key)//6.自定义折半查找函数，置查找区间初值，low为1，high为表长；当low小于等于high时，mid取low和high的中间值，将给定值key与中间位置记录的关键字进行比较，若查找成功返回mid，若不相等则利用中间位置记录将表对分成前后两个子表。如果key比中间位置记录的关键字小，则high取为mid-1,否则low取为mid+1；循环结束，说明查找区间为空，则查找失败，返回0.{int low=1,high=L.length,mid;while(low<=high){mid=(low+high)/2;if(key==L.elem[mid].key) return mid;else if(key<L.elem[mid].key) high=mid-1;else low=mid+1;}return 0;}int main(){int m,x,y;int m1,x1,y1;sqlist L,M;initList(L);initList(M);printf("请输入顺序表的长度(顺序查找)\n");scanf("%d",&m);printf("请输入一批数据\n");get(L,m);printf("以下为输入的顺序表(顺序查找)\n");display(L);printf("请输入你想查找的元素(顺序查找)\n");scanf("%d",&x);y=search(L,x);printf("经过顺序查找发现查找的元素在第%d位\n",y+1);printf("请输入顺序表的长度(折半查找)\n");scanf("%d",&m1);printf("请按由大到小输入一批数据(折半查找)\n");get(M,m1);printf("以下为输入的顺序表(折半查找)\n");display(M);printf("请输入你想查找的元素(折半查找)\n");scanf("%d",&x1);y1=search_Bin(M,x1);printf("经过折半查找发现查找的元素在第%d位\n",y1+1);return 0;}`

C语言数据结构第二版（严蔚敏、李冬梅）著