9.2静态查找表 ◆静态查找表结构 ◆顺序查找 ◆有序表的折半查找 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 11 9.2 静态查找表 静态查找表结构 顺序查找 有序表的折半查找
92.1静态查找表结构 静态查找表是数据元素的线性表,可以是基于数组 的顺序存储或以线性链表存储。 *顺序存储结构 typedef struct t ElemType * elem; /数组基址* int length /表长度* IS TBL 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 12 静态查找表是数据元素的线性表，可以是基于数组 的顺序存储或以线性链表存储。 /* 顺序存储结构 */ typedef struct{ ElemType *elem； /* 数组基址 */ int length； /* 表长度 */ }S_TBL； 9.2.1 静态查找表结构
/*链式存储结构结点类型 typedef struct NODE ElemType elem 结点的值域* truct NODE*next;/下一个结点指针域 Node Type 2021年1月21日 数据结构讲义 13
2021年1月21日 数据结构讲义 13 /* 链式存储结构结点类型 */ typedef struct NODE{ ElemType elem； /* 结点的值域 */ truct NODE *next； /* 下一个结点指针域 */ }NodeType；
922顺序查找 顺序査找又称线性查找,是最基本的查找方法之一。其 查找方法为:从表的一端开始,向另一端逐个按给定 值kx与关键码进行比较,若找到,查找成功,并给出 数据元素在表中的位置;若整个表检测完,仍未找到 与kx相同的关键码,则查找失败,给出失败信息 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 14 9.2.2 顺序查找 顺序查找又称线性查找，是最基本的查找方法之一。其 查找方法为：从表的一端开始，向另一端逐个按给定 值kx与关键码进行比较，若找到，查找成功，并给出 数据元素在表中的位置；若整个表检测完，仍未找到 与kx相同的关键码，则查找失败，给出失败信息
【算法9.1】以顺序存储为例,数据元素从下标为1的数组 单元开始存放,0号单元留空。 int s search(S TBL tbl, Key Type kx) (A在表山中查找关键码为的数据元素,若找到返回该元素在数组中的下 标,否则返回0*/ tbl.elem[O].key=kx;/*存放监测,这样在从后向前查找失败 时,不必判表是否检测完,从而达到算法统一*/ for (i= tbl length; tbl elem[i]. key<>kx; i-- /*从标尾端向前找* return1 2021年1月21日 数据结构讲义 15
2021年1月21日 数据结构讲义 15 【算法9.1】以顺序存储为例，数据元素从下标为1的数组 单元开始存放，0号单元留空。 int s_search(S_TBL tbl，KeyType kx) { /*在表tbl中查找关键码为kx的数据元素，若找到返回该元素在数组中的下 标，否则返回0 */ tbl.elem[0].key = kx；/* 存放监测，这样在从后向前查找失败 时，不必判表是否检测完，从而达到算法统一*/ for (i = tbl.length;tbl.elem[i].key<>kx;i--)； /* 从标尾端向前找 */ return i； }