Download presentation
Presentation is loading. Please wait.
1
顺序查找
2
顺序查找是最为朴素的一种查找方式。它的查找过程为：从表的一端开始，依次将记录的关键字和给定值进行比较，若某个记录的关键字和给定值相等，则查找成功； 反之，若扫描整个表后，仍未找到关键字和给定值相等的记录，则查找失败。 顺序查找 顺序查找方法既适用于线性表的顺序存储结构，又适用于线性表的链式存储结构。
3
typedef struct{ KeyType key; InfoType otherinfo; }ElemType;
数据元素类型定义 顺序表定义 typedef struct{ ElemType *R; int length; }SSTable;
4
int LocateELem(SqList L,ElemType e) { for (i=0;i< L
int LocateELem(SqList L,ElemType e) { for (i=0;i< L.length;i++) if (L.elem[i]==e) return i+1; return 0; } 算 法 这个算法有个不好的地方在于，查找过程中每步都要检测整个表是否查找完毕。
5
改进方法就是顺序表的0号单元不存放查找表的元素，查找之前先对0号单元赋值key，这样0号单元就起着一个监视哨的作用。
算 法 改 进 int Search_Seq( SSTable ST , KeyType key ){ //若成功返回其位置信息，否则返回0 ST.R[0].key =key; for( i=ST.length; ST.R[ i ].key!=key; - - i ); return i; }
6
这样就省去了每一步都要检测整个表是否查找完毕。虽说这是一个很小的改进，但是这个改进却能将顺序查找的效率提高几乎两倍。 对于顺序查找，我们在之前已经进行了分析，平均查找长度ASL为(n+1)/2。查找不成功时，需要比较n+1次。 算 法 改 进
7
优点：算法简单，对表结构无任何要求，既可适用于顺序结构，也可适用于链式结构。 缺点：查找效率较低，当n很大时，不宜采用顺序查找。
顺序查找的优缺点
Similar presentations
