数据结构查找A.ppt

《数据结构查找A.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课前思考题：猜价格游戏：已知主持人手中的物品价格为1至31元之间的整数，猜中者可得该奖品。1.如果你猜错时主持人只告诉你所猜价格错了让你重新猜，平均要几次才能猜对?2.如果你猜错时主持人告诉你所猜价格是高了还是低了再让你重新猜，最少要几次才可保证对任意一个价格都能猜对？1如何应用数据结构知识求解实际问题？根据实际问题数据之间的关系确定其数据结构。例如图的n各城市架设最经济通信线路问题，数据之间存在多对多的关系，因此对应数据结构为带权图。根据问题需求基于该数据结构基本操作定义相应算法。实际问题是求最经济通信线路，实际上就是求带权图的极小连通子图，也就是求图的最小生成树。因

2、此应该采用图的最小生成树算法进行求解。根据数据特征选择存储结构，并选择该数据存储结构的对应算法进行求解。如果是稀疏图，采用邻接表存储，调用kruskal算法如果是稠密图，采用邻接矩阵存储，调用Prim算法一个乡镇有6个村且各村之间是连通的，要在其中一个村建立急救中心，希望到各村去急救的平均时间最短，应该把急救中心建在哪个村？－最短路径和最小问题！如果考虑各村人数呢？2数据结构课程的内容38.1基本概念8.2静态查找8.3动态查找8.4哈希查找第8章查找48.1基本概念定义查找－查询特定元素是否在查找列表中。(3)目的提高查找效率(2)实质关键字的比较或匹配。猜价格游戏：

3、已知物品价格为1至9之间的整数，请按两种不同方式来猜物品价格。65(4)评估查找方法优劣的标准一般用查找次数的平均值来评估算法的优劣。称为平均查找长度（ASL：averagesearchlength）。静态查找——只查找，不改变查找表的数据元素。动态查找——既查找，又改变查找表内的数据元素。(5)分类6静态查找算法主要有：8.2静态查找1、顺序查找（线性查找）2、二分查找（折半或对分查找）3、分块查找（索引顺序查找）4、静态树表的查找71.顺序查找（又称线性查找）定义：用逐一比较的办法顺序查找关键字。i例123456789101156359211756644580389

4、2找64iiii81、顺序查找（Linearsearch，又称线性查找）（1）顺序表的机内存储结构：typedefstruct{ElemTypeelem[N];//0号单元留空。表容量为全部元素intlength;//表长，即表中数据元素个数}SSTable;顺序查找：即用逐一比较的办法顺序查找关键字，这显然是最直接的办法。对顺序结构如何线性查找？见下页之例;对单链表结构如何线性查找？函数虽未给出，但也很容易编写；只要知道头指针head就可以“顺藤摸瓜”；对非线性树结构如何顺序查找?可借助各种遍历操作！9已知顺序表元素存储在a[1-n]中，要在其中查找关键字为k的某元素

5、的位置，该如何编程？(找到返回位置，找不到返回0）intseqsrch(inta[],intn,intk){for(inti=1;i<=n;i++)if(k==a[i])returni;return0;}//每次循环比较两次10（2）算法的改进：技巧：把待查关键字key存入表头或表尾（俗称“哨兵”），这样可以加快执行速度。i例01234567891011513192137566475808892找6464监视哨iiii比较次数=5比较次数：查找第n个元素：1查找第n-1个元素：2……….查找第1个元素：n查找第i个元素：n+1-i查找失败：n+111将待查找的特定值ke

6、y存入顺序表的首部（如0号单元），则顺序查找的实现方案为：从后向前逐个比较！intSearch_Seq(SSTableST,KeyTypekey){//在顺序表ST中，查找关键字与key相同的元素；若成功，返回其位置信息，否则返回0ST.elem[0].key=key;//设立哨兵，可免去查找过程中每一步都要检测是否查找完毕。当n很大时，查找时间将减少一半。for(i=ST.length;ST.elem[i].key!=key;--i);//不要用for(i=n;i>0;--i)或for(i=1;i<=n;i++)returni;//若到达0号单元才结束循环，说明不成功

7、，返回0值(i=0)。成功时则返回找到的那个元素的位置i。}//Search_Seq（2）改进算法：12——返回特殊标志，例如返回空记录或空指针。前例中设立了“哨兵”，就是将关键字送入末地址ST.elem[0].key使之结束并返回i=0。讨论②查找效率怎样计算？——用平均查找长度ASL衡量。讨论①查不到怎么办？讨论③如何计算ASL？分析：查找第1个元素所需的比较次数为1；查找第2个元素所需的比较次数为2；……查找第n个元素所需的比较次数为n；总计全部比较次数为：1＋2＋…＋n=(1+n)n/2未考虑查找不成功的情况：查找哨兵所需的比较次