§82线性结构的检索 ·属于静态检索 算法简单,但速度不高 主要用在对小型数据集的检索 般的线性表有两种存贮结构:连续式与链式 对它们的检索,一般采用顺序搜索的方式——称为顺 序查找 ·若元素已按关键字排序,则可采用更高效的检索法 折半查找 16
16 §8.2 线性结构的检索 • 属于静态检索 • 算法简单，但速度不高 • 主要用在对小型数据集的检索 • 一般的线性表有两种存贮结构：连续式与链式 • 对它们的检索，一般采用顺序搜索的方式──称为顺 序查找 • 若元素已按关键字排序，则可采用更高效的检索法 ──折半查找
§8.21无序表的检索 (一)算法 long Seq Search(int a[, long n, int key /*连续存储结构的线性表的顺序查找 a[]输入量.一维数组,充当线性表,n为元素个数 序号为0的位置不使用 key待查关键字 返回—成功时返回key在表中的序号,否则返回0*/ long 1, a[O]=key;∥设置监视哨 En while(alj]!=key)i-- return 1 17
17 §8.2.1 无序表的检索 (一)算法 long SeqSearch(int a[], long n, int key) { /*连续存储结构的线性表的顺序查找 a[ ]——输入量.一维数组，充当线性表，n为元素个数。 序号为0的位置不使用 key——待查关键字 返回——成功时返回key在表中的序号，否则返回0*/ long i; a[0]=key; //设置监视哨 i=n;; while(a[i]!=key) i--; return i; }
§8.21无序表的检索 二)平均检索长度 ·检索成功时的平均检索长度 ASL=∑l/n(n-i+1)=1n(n-i+1)=(n+1)/2=O(n) ASL总=q(n+1)q1(n+l)2 若它们是等概率的 ASL总=1/2(n+1)+1/2(n+1)/2=3/4(n+1) 18
18 §8.2.1 无序表的检索 (二)平均检索长度 • 检索成功时的平均检索长度 ASL=∑1/n(n-i+1)=1/n (n-i+1)=(n+1)/2=O(n) ASL总=q0(n+1)+q1(n+1)/2 • 若它们是等概率的 ASL总=1/2(n+1)+1/2·(n+1)/2=3/4(n+1)
§8.21无序表的检索 (三)线性链表的顺序检索 在链表中检索关键字值为key的结点的过程为: =pLead while(p!=nULL & pkey=key)p=p-next return p;i为NULL时失败,否则p指向所查到的结点
19 §8.2.1 无序表的检索 (三)线性链表的顺序检索 • 在链表中检索关键字值为key的结点的过程为： p=pHead; while (p!=NULL && p→key!=key) p=p→next; return p; //p为NULL时失败，否则p指向所查到的结点
§822有序表的折半检索 (一)折半检索算法 基本思想 先找出有序表中点位置上的元素(表空时无中点,表示检索 不成功),用待查关键字与它比较 若相等,则已查到,结束 否则,若它小于待查关键字,则下步在有序表的前半部(值 小于中点元素的部分)中按类似方法检索,若它的值大于待 查关键字,则在表的后半部按类似方法检索 20
20 §8.2.2 有序表的折半检索 (一)折半检索算法 • 基本思想 –先找出有序表中点位置上的元素（表空时无中点，表示检索 不成功），用待查关键字与它比较 –若相等，则已查到，结束 –否则，若它小于待查关键字，则下步在有序表的前半部（值 小于中点元素的部分）中按类似方法检索，若它的值大于待 查关键字，则在表的后半部按类似方法检索