、顺序表 在顺序表上的顺序查找(又称线性查找)的基本思想 从顺序表的一端开始,用给定数据元素的关键字逐个与顺序 表中各数据元素的关键字比较,若在顺序表中查找到要查找 的数据元素,则查找成功,函数返回该数据元素在顺序表中 的位置;否则查找失败,函数返回-1。 (1)顺序表的机内存储结构 typedef struct i DateType list[Max] nt size seqlist
6 一、顺序表 （1）顺序表的机内存储结构 在顺序表上的顺序查找（又称线性查找 ）的基本思想： 从顺序表的一端开始，用给定数据元素的关键字逐个与顺序 表中各数据元素的关键字比较，若在顺序表中查找到要查找 的数据元素，则查找成功，函数返回该数据元素在顺序表中 的位置；否则查找失败，函数返回-1。 typedef struct { DateType list[MaxSize]; int size; }SeqList;
(2)算法的实现 int SeqSearch(SeqList S, DataType x) i int i=0 while(i<s size &&S list[i]. key! =x key) 1++t if(S. listli] key == x. key) return i else return -1
7 （2）算法的实现 int SeqSearch(SeqList S, DataType x) { int i = 0; while(i<S.size && S.list[i].key!=x.key) i++; if(S.list[i].key == x.key) return i; else return -1; }
(3)顺序查找算法性能评价 分析: 查找第1个元素所需的比较次数为1; 查找第2个元素所需的比较次数为2; 查找第n个元素所需的比较次数为n; 总计全部比较次数为:1+2+.+n=(1+n)m/2 若求某一个元素的平均查找次数,还应当除以n(等概率), 即:ASL 成功 (1+n)12,时间效率为O( 这是查找成功的情况 同理:ASL失败=(1+n)/2 (4)顺序查找的特点 优点:算法简单,且对顺序结构或链表结构均适用 缺点:ASL太大,时间效率太低
8 （3）顺序查找算法性能评价 分析： 查找第1个元素所需的比较次数为1； 查找第2个元素所需的比较次数为2； …… 查找第n个元素所需的比较次数为n； 总计全部比较次数为：1＋2＋…＋n = (1+n)n/2 这是查找成功的情况 若求某一个元素的平均查找次数，还应当除以n（等概率）， 即： ASL成功＝（1＋n）/2 ，时间效率为O(n) 同理：ASL失败＝（1＋n）/2 （4）顺序查找的特点 优点：算法简单，且对顺序结构或链表结构均适用。 缺点：ASL 太大，时间效率太低
思考题: 1、问:对顺序结构如何线性查找? 答:利用顺序表 2、问:对单链表结构如何线性查找? 答:从头指针始“顺藤摸瓜” 3、问:对非线性(树结构)如何顺序查找? 答:借助各种二叉树遍历操作!
9 思考题： 1、问：对顺序结构如何线性查找？ 答：利用顺序表 2、问：对单链表结构如何线性查找？ 答：从头指针始 “顺藤摸瓜” 3、问：对非线性（树结构）如何顺序查找? 答：借助各种二叉树遍历操作！
有序顺序表 有序顺序表上的查找算法主要有顺序查找和折半查找两种方法 1、顺序查找 有序顺序表上顺序查找算法类同顺序表上的顺序查找算法 2、二分查找(又称折半查找) (1)算法的基本思想:先给数据排序(例如按升序排好),形成 有序表,然后再将key与正中元素相比,着key小,则缩小至 前半部内查找;再取其中值比较,每次缩小1/2的范围,直到 查找成功或失败为止。(详细见教材P263) 思考题: 问:能否使用单链表结构进行折半査查找? 无法实现!因全部元素的定位只能从头指针head开 始 问:对非线性(树)结构如何进行折半查找? 可借助二叉排序树来查找(属动态查找表形式)
10 (1)算法的基本思想：先给数据排序（例如按升序排好），形成 有序表，然后再将key与正中元素相比，若key小，则缩小至 前半部内查找；再取其中值比较，每次缩小1/2的范围，直到 查找成功或失败为止。（详细见教材P263) 思考题： 问：能否使用单链表结构进行折半查找？ ——无法实现！因全部元素的定位只能从头指针head开 始 问：对非线性(树)结构如何进行折半查找？ ——可借助二叉排序树来查找（属动态查找表形式）。 二、有序顺序表 有序顺序表上的查找算法主要有顺序查找和折半查找两种方法。 1、顺序查找 有序顺序表上顺序查找算法类同顺序表上的顺序查找算法。 2、二分查找（又称折半查找）