定义被查找的顺序表中每个记录的类型如下: struct RecType ∥记录类型 public int key;/存放关键字,假设关鍵字为int类型 public string data;/存放其他数据,假设为 Istring类型 定义一个顺序表查找类 SqlistSearch class如下 class salistsearchClass const int MaxSize=100; 顺序表中最多元素个数 public ectype r; 顺序表 public int length; 存放顺序表的长度 public ldxTypell I; /索引表 BTNode ra /拆半查找判定树根结点 string sstr /用于返回结果 public sqlistsearchClasso/构造函数,用于查找顺序表的初始化 i rnew BTNodeo; R=new RecType MaxSize]; I=new IdxType MaxSize]; length=0 /顺序表的基本运算算法和查找算法
定义被查找的顺序表中每个记录的类型如下： struct RecType //记录类型 { public int key; //存放关键字，假设关键字为int类型 public string data; //存放其他数据，假设为string类型 }; 定义一个顺序表查找类SqListSearchClass如下 ： class SqListSearchClass { const int MaxSize=100; //顺序表中最多元素个数 public RecType[] R; //顺序表 public int length; //存放顺序表的长度 public IdxType[] I; //索引表 BTNode r; //拆半查找判定树根结点 string sstr; //用于返回结果 public SqListSearchClass() //构造函数，用于查找顺序表的初始化 { r=new BTNode(); R=new RecType[MaxSize]; I=new IdxType[MaxSize]; length=0; } //顺序表的基本运算算法和查找算法 }
82.1顺序查找 顺序查找是一种最简单的查找方法。 它的基本思路是:从表的一端开始顺序扫描顺序表 依次将扫描到的元素关键字和给定值相比较,若当前扫描 到的元素关键字与k相等,则查找成功;着扫描结束后,仍 未找到关键字等于k的元素,则查找失败
8.2.1 顺序查找 顺序查找是一种最简单的查找方法。 它的基本思路是：从表的一端开始顺序扫描顺序表， 依次将扫描到的元素关键字和给定值k相比较，若当前扫描 到的元素关键字与k相等，则查找成功；若扫描结束后，仍 未找到关键字等于k的元素，则查找失败
顺序查找的算法如下 public int SeqSearch(int k) /顺序查找算法 int i=0 while(i< length&&R[ i- key!=k)/从表头往后找 i++; if (i>=length) 未找到返回0 return 0; else return i+l /找到后返回其逻辑序号计+1
顺序查找的算法如下 ： public int SeqSearch(int k) //顺序查找算法 { int i=0; while (i<length && R[i].key!=k) //从表头往后找 i++; if (i>=length) //未找到返回0 return 0; else return i+1; //找到后返回其逻辑序号i+1 }
从顺序查找过程可以看到(不考虑越界比较n),c取 决于所查记录在表中的位置。如查找表中第1个记录R[0时, 仅需比较一次;而查找表中最后一个记录Rm-1时,需比较n 次,即c-。因此成功时的顺序查找的平均查找长度为: ASL=∑PC=-∑i=-x2(n+ n+ L n n 2 查找成功时的平均比较次数约为表长的一半。 思考题:不成功时的平均查找长度是多少?
从顺序查找过程可以看到（不考虑越界比较i<n），ci取 决于所查记录在表中的位置。如查找表中第1个记录R[0]时, 仅需比较一次；而查找表中最后一个记录R[n-1]时，需比较n 次，即ci=i。因此,成功时的顺序查找的平均查找长度为： 2 1 2 1 1 ( 1) 1 1 + = + = = = = = n n n n i i n c i p sq ASL n i n i 查找成功时的平均比较次数约为表长的一半 。 思考题：不成功时的平均查找长度是多少？
8.2,2折半查找 折半查找也称为二分查找,要求线性表中的节点必须己按 关键字值的递增或递减顺序排列。 思路:首先用要查找的关键字与中间位置的节点的关键 字相比较,这个中间节点把线性表分成了两个子表,若比较结 果相等则查找完成;若不相等,再根据k与该中间节点关键字的 比较大小确定下一步查找哪个子表,这样递归进行下去,直到 找到满足条件的节点或者该线性表中没有这样的节点
8.2.2 折半查找 折半查找也称为二分查找，要求线性表中的节点必须己按 关键字值的递增或递减顺序排列。 思路：首先用要查找的关键字k与中间位置的节点的关键 字相比较，这个中间节点把线性表分成了两个子表，若比较结 果相等则查找完成;若不相等，再根据k与该中间节点关键字的 比较大小确定下一步查找哪个子表，这样递归进行下去，直到 找到满足条件的节点或者该线性表中没有这样的节点