数据结构电子教案搜索结构.ppt
《数据结构电子教案搜索结构.ppt》由会员分享,可在线阅读,更多相关《数据结构电子教案搜索结构.ppt(37页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、1 1第七章 搜索结构数据结构电子教案数据结构电子教案2 2第七章第七章 搜索结构搜索结构3 3搜索搜索(Search)(Search)的概念的概念静态搜索表静态搜索表n所谓所谓搜索搜索,就是在数据集合中寻找满足某种,就是在数据集合中寻找满足某种条件的数据对象。条件的数据对象。n搜索的结果通常有两种可能:搜索的结果通常有两种可能:搜索成功搜索成功,即找到满足条件的数据对象。,即找到满足条件的数据对象。这时,作为结果,可报告该对象在这时,作为结果,可报告该对象在结构中结构中的的位置位置, 还可给出该对象中的具体信息。还可给出该对象中的具体信息。搜索不成功搜索不成功,或搜索失败。作为结果,应,或搜
2、索失败。作为结果,应报告一些信息报告一些信息, 如失败标志、位置如失败标志、位置等。等。4 4n通常称用于搜索的数据集合为通常称用于搜索的数据集合为搜索结构搜索结构,它,它是由同一数据类型的对象是由同一数据类型的对象(或记录或记录)组成。组成。n在每个对象中有若干属性,其中有一个属性,在每个对象中有若干属性,其中有一个属性,其值可唯一地标识这个对象。称为其值可唯一地标识这个对象。称为关键码关键码。使用基于关键码的搜索,搜索结果应是唯一使用基于关键码的搜索,搜索结果应是唯一的的。但在实际应用时,搜索条件是多方面的,。但在实际应用时,搜索条件是多方面的,可以使用基于属性的搜索方法,但搜索结果可以使
3、用基于属性的搜索方法,但搜索结果可能不唯一。可能不唯一。n实施搜索时有两种不同的环境。实施搜索时有两种不同的环境。u静态环境静态环境,搜索结构在插入和删除等操作,搜索结构在插入和删除等操作的前后不发生改变。的前后不发生改变。 静态搜索表静态搜索表 5 5u动态环境动态环境,为保持较高的搜索效率,为保持较高的搜索效率, , 搜索搜索结构在执行插入和删除等操作的前后将自结构在执行插入和删除等操作的前后将自动进行调整,结构可能发生变化。动进行调整,结构可能发生变化。 动态搜索表动态搜索表n在静态搜索表中,数据元素存放于数组中,在静态搜索表中,数据元素存放于数组中,利用数组元素的下标作为数据元素的存放
4、地利用数组元素的下标作为数据元素的存放地址。搜索算法根据给定值址。搜索算法根据给定值 k,在数组中进行,在数组中进行搜索。直到找到搜索。直到找到 k 在数组中的存放位置或可在数组中的存放位置或可确定在数组中找不到确定在数组中找不到 k 为止。为止。 静态搜索表静态搜索表6 6数据表与搜索表的类定义数据表与搜索表的类定义 #include #include using namespace std;template class dataList; / 前视定义template class dataNode / 数据表中结点类的定义 friend class dataList; / 声明友元类pri
5、vate:7 7 K key;/ 关键码域 E other; / 其他域,视问题而定public: dataNode ( ) / 构造函数 K getKey( ) const return key; / 读取关键码 void setKey (const K x) key = x; / 修改关键码; template class dataList / 数据表类定义protected:8 8 dataNode *Element;/ 数据表存储数组 int ArraySize, CurrentSize;/ 数组长度和元素个数public: dataList (int sz) : ArraySize(
6、sz), CurrentSize(0) Element = new dataNodesz; assert (Element != NULL); dataList (dataList& R); / 复制构造函数 virtual dataList( ) delete Element; / 析构函数 9 9 virtual int Length( ) const return CurrentSize; virtual K getKey (const int i) const / 提取第 i(0 开始)元素值 assert (i = 0 & i = 0 & i CurrentSize); Elemen
7、ti.key = x; 1010 virtual bool Insert (const dataNode& e1); / 插入 virtual bool Remove (const K x, E& e1); / 删除 void output( ) const;/ 输出void input( );/ 输入 ;template bool dataList:Insert (const dataNode& e1) / 在dataList的尾部插入新元素, 若插入失败函数返/ 回false, 否则返回true.11 11 if (CurrentSize = ArraySize) return false
8、; ElementCurrentSize = e1;/ 插入在尾端 CurrentSize+; return true;template bool dataList:Remove (const K x, E& e1) / 在dataList中删除关键码为x的元素, 通过e1返回。/ 用尾元素填补被删除元素。 if (CurrentSize = 0) return false; int i; for (i = 0; i CurrentSize & Elementi.key != x; i+); / 在表中顺序寻找1212 if (i = CurrentSize) return false; /
9、未找到 e1 = Elementi.other; / 找到,保存被删元素的值 Elementi = ElementCurrentSize-1; / 填补 CurrentSize-; return true;template void dataList:output( ) const cout 数组中的元素为: endl; for (int i = 0; i CurrentSize; i+) cout Elementi.key ; cout endl;1313 cout 元素个数 : CurrentSize endl;template void dataList:input( ) cout Cu
10、rrentSize;cout 输入数组元素的关键码: n; for (int i = 0; i CurrentSize; i+) cout 元素 i + 1 Elementi.key; 1414n顺序搜索主要用于在顺序搜索主要用于在线性表线性表中搜索。中搜索。n设若表中有设若表中有 CurrentSize 个元素,则顺序搜个元素,则顺序搜索从表的先端开始,顺序用各元素的关键码索从表的先端开始,顺序用各元素的关键码与给定值与给定值 x 进行比较进行比较n若找到与其值相等的元素,则搜索成功,给若找到与其值相等的元素,则搜索成功,给出该元素在表中的位置。出该元素在表中的位置。n若整个表都已检测完仍未
11、找到关键码与若整个表都已检测完仍未找到关键码与 x 相相等的元素,则搜索失败。给出等的元素,则搜索失败。给出失败信息失败信息 ( 这这里用里用 -1 表示表示 )。顺序搜索(顺序搜索(Sequential SearchSequential Search) 1515n一般的顺序搜索算法在第二章已经讨论过,本一般的顺序搜索算法在第二章已经讨论过,本章介绍一种使用章介绍一种使用“监视哨监视哨”的顺序搜索方法。的顺序搜索方法。n设在设在数据表数据表 dataList 中顺序搜索关键码与给中顺序搜索关键码与给定值定值 x 相等的数据元素,要求数据元素在表中相等的数据元素,要求数据元素在表中从下标从下标
12、0 开始存放开始存放, 下标为下标为 CurrentSize 的元的元素作为控制搜索过程自动结束的素作为控制搜索过程自动结束的“监视哨监视哨”使使用。用。n若搜索成功,则函数返回该元素在表中序号若搜索成功,则函数返回该元素在表中序号 Location(下标)(下标), 若搜索失败,则函数返回若搜索失败,则函数返回 -1。1616顺序搜索表类顺序搜索表类 const int defaultSize = 100;template class SearchList : public dataList public:SearchList(int sz = defaultSize) : dataList
13、(sz) int SeqSearch (const K x) const; / 顺序搜索int SeqSearch (const K x, int loc)const; / 递归搜索;1717使用监视哨的顺序搜索算法使用监视哨的顺序搜索算法 template int SearchList:SeqSearch (const K x) const ElementCurrentSize.setKey(x); / 监视哨 int i = 0; while (Elementi+.getKey( ) != x) ; /从前向后顺序搜索 return (i = CurrentSize ? -1 : i);c
14、onst int Size = 10;void main (void) 1818 dataList L1 (Size);/ 定义搜索表L1 int Target; int Loc; L1.input( ); L1.output( );/ (修改教材) cout Target;/ 输入要搜索的数据 if ( (Loc = L1.SeqSearch(Target) = 0 ) cout 找到待查元素位置在: Loc + 1 endl;/ 搜索成功 else cout 没有找到待查元素! endl; / 搜索不成功1919n设数据表中有设数据表中有 n 个元素,搜索第个元素,搜索第 i 个元素的个元
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 电子 教案 搜索 结构
限制150内