清华大学出版社 TSINGHUA UNIVERSITY PRESS 7.1顺序查找 1.2线性链表的顺序查找
7.1 顺序查找 7.1.2 线性链表的顺序查找
清华大学出版社 TSINGHUA UNIVERSITY PRESS 7.1顺序查找 线性表在链式存储结构下的顺序查找 输入:线性链表头指针HAD以及存储空间V、NEXT; 被查找的元素x。 输出:被查找元素x的结点在线性链表中的存储序号k 如果在线性链表中不存在元素值为x的结点, 则输出k=-1 PROCEDURE LSERCH(V, NEXT, HEAD,X,k K=HEAD WHIE(k≠0)and(V(k)≠x)DOk=NEXT(k) IF(K=0)Then k=-1 RETURN
7.1 顺序查找 线性表在链式存储结构下的顺序查找 输入：线性链表头指针HEAD以及存储空间V、NEXT； 被查找的元素x。 输出：被查找元素x的结点在线性链表中的存储序号k。 如果在线性链表中不存在元素值为x的结点， 则输出k＝－1。 PROCEDURE LSERCH(V，NEXT，HEAD，x，k) k＝HEAD WHILE (k≠0)and(V(k)≠x) DO k＝NEXT(k) IF (k＝0) THEN k＝－1 RETURN
清华大学出版社 TSINGHUA UNIVERSITY PRESS 7.1顺序查找 struct node iet d; struct node *next: j /*函数返回被査找元素x所在结点的存储地址, 如果在线性链表中不存在元素值为x的结点,则返回NLL*/ struct node *serch(head, x) struct node *head ETx;/*ET为线性链表中值域的数据类型* i struct node k k=head while((k≠NUL&&(k->d≠x)k=k一>next; return(k)
7.1 顺序查找 struct node { ET d； struct node *next； }； /*函数返回被查找元素x所在结点的存储地址， 如果在线性链表中不存在元素值为x的结点，则返回NULL*/ struct node *lserch(head，x) struct node *head； ET x； /*ET为线性链表中值域的数据类型*/ { struct node k； k＝head； while ((k≠NULL)&&(k－>d≠x)) k＝k－>next； return(k)； }
清华大学出版社 TSINGHUA UNIVERSITY PRESS 7.2有序表的对分查找 设有序线性表的长度为n,被查元素为x。 将x与线性表的中间项进行比较: 若中间项的值等于x,则说明查到,查找结束; 若x小于中间项的值,则在线性表的前半部分(即中间项 以前的部分)以相同的方法进行查找; 若x大于中间项的值,则在线性表的后半部分(即中间项 以后的部分)以相同的方法进行查找。 这个过程一直进行到查找成功或子表长度为0(说明线性 表中没有这个元素)为止 在最坏情况下,对分查找只需要比较log2n次, 而顺序查找需要比较n次
7.2 有序表的对分查找 设有序线性表的长度为n，被查元素为x。 将x与线性表的中间项进行比较： 若中间项的值等于x，则说明查到，查找结束； 若x小于中间项的值，则在线性表的前半部分（即中间项 以前的部分）以相同的方法进行查找； 若x大于中间项的值，则在线性表的后半部分（即中间项 以后的部分）以相同的方法进行查找。 这个过程一直进行到查找成功或子表长度为0(说明线性 表中没有这个元素)为止。 在最坏情况下，对分查找只需要比较log2n次， 而顺序查找需要比较n次
清华大学出版社 TSINGHUA UNIVERSITY PRESS 7.2有序表的对分查找 有序线性表在顺序存储结构下的对分查找 输入:有序线性表长度n以及线性表的存储空间V;被查找的元素x。 输出:被查找元素x在有序线性表中的序号k。如果在线性表中不存 在元素x,则输出k=-1 PROCEDURE BSERCH(V, n, x, k) n While (i<=j) DO k=(i+j/2 IF (V(k=x) THEN RETURN IF(V(k>X)then j=k-1; elsE i=k+1 IF (i>j)then k=-1 RETURN
7.2 有序表的对分查找 有序线性表在顺序存储结构下的对分查找 输入：有序线性表长度n以及线性表的存储空间V；被查找的元素x。 输出：被查找元素x在有序线性表中的序号k。如果在线性表中不存 在元素x，则输出k＝－1。 PROCEDURE BSERCH(V，n，x，k) i＝1； j＝n WHILE (i＜＝j) DO { k＝(i＋j)/2 IF (V(k)＝x) THEN RETURN IF (V(k)＞x) THEN j＝k－1； ELSE i＝k＋1； } IF (i＞j) THEN k＝－1 RETURN