C语言数据结构顺序表的顺序查找和折半查找的功能

#C语言数据结构顺序表的顺序查找和折半查找的功能| 来源: 网络整理| 查看: 265

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

顺序查找算法：又称为线性查找，主要用在—线性表—中进行查找通常分为：1—无序线性表的一般查找； 2—对关键字有序的顺序表查找；优缺点分析：缺点：当线性表的表长过于长时，平均查找长度较大，效率低。优点：对顺序表中数据元素的存储没有要求，顺序存储链式存储均可。需注意：对于线性表的链式存储只能使用顺序查找. 折半查找，又称二分查找，它仅适用于有序的顺序表首先将给定值key与表中间位置元素的关键字比较，若相等，则查找成功，返回该元素的存储位置；(例如，在查找表升序排列时，若给定值key大于中间元素的关键字，则所查找的关键字只可能在后半部分)若不等，则所需查找的元素只能在中间元素以外的前半部分或后半部分中；然后在缩小范围内继续进行同样的查找，如此重复直到找到为止，若查找不成功，返回查找失败信息优缺点分析：折半查找方法的优点：折半查找的优点是比较次数少，查找速度快，平均性能好；折半查找方法的缺点：折半查找的缺点是：要求待查表为有序表，且插入删除困难。因此：折半查找方法适用于不经常变动而查找频繁的有序列表。

目的是：⑴ 输入一批整型数据，建立顺序表，然后用顺序查找； ⑵ 输入一批有序整型数据（如从小到大），然后用折半查找，查找一给定的整数。

#include #define maxsize 20//全局定义 #define OK 1 #define OVERFLOW -2 typedef 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 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 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语言数据结构第二版（严蔚敏、李冬梅）著

【本文地址】

公司简介

联系我们