计算机软件技术基础-第2章 数据结构与算法.ppt

第 * 页 通常称用于查找的数据集合为查找结构，它是由同一数据类型的数据(或记录)组成。 每个对象有若干属性，其中有一个属性，其值可唯一地标识这个对象，称为关键字。使用基于关键字的搜索，查找结果应是唯一的。但在实际应用时，查找条件是多方面的，可以使用基于属性的查找方法，但查找结果可能不唯一。 第 * 页 实施查找时有两种不同的环境 静态环境 查找结构不需进行插入和删除操作。 ? 静态查找表 动态环境 查找过程中可能要对查找结构执行数据插入、删除或修改等操作，并对查找结构进行调整，结构可能发生变化。 ? 动态查找表 动态查找表的表结构是在查找过程中动态生成的。 第 * 页 以线性结构表示静态查找表。 基本原理：将待查找记录依次逐个与表中记录进行比较。 1. 顺序查找 （Sequential Search) 第 * 页 SL.elem 顺序查找过程（从前向后查找） 假设给定查找值 e=64, 要求 SL.elem[k] = e, 问: k = ? k k 第 * 页 SL.elem i SL.elem i 60 i key=64 key=60 i 64 顺序查找过程（从后向前查找） 0单元用于存放待查找关键字，作为“哨兵”(guard) 返回0 返回7 第 * 页 int Search_Seq( TB SL, TYPE key ) { SL.elem[0].key = key; // “哨兵” for (i=SL.length; SL.elem[i].key!=key; --i); // 从后往前找 return i; // 查找成功时i为有效下标,否则i为0 } 顺序查找算法实现（从后向前查找） 第 * 页 查找成功:最少比较次数 最多比较次数 平均比较次数 查找失败:最少比较次数 最多比较次数 平均比较次数 查找算法的评价指标 第 * 页 查找算法的平均查找长度ASL (Average Search Length) 指为了确定记录在查找表中的位置，需要和给定值进行关键字比较的次数的期望值: 其中，n为表长，Pi为查找表中第i个记录的概率，且 ；Ci为查找到该记录时，曾和给定值进行关键字比较的次数。 第 * 页 在等概率情形，查找任一记录的概率相等：pi = 1/n, i = 1, 2, ?, n 查找不成功时， 查找成功时， 以从前向后顺序查找算法为例， 查找算法时间复杂度？ O(n) 第 * 页 顺序查找算法总结 查找长度： 查找成功:最少比较次数　 1 最多比较次数　 n　 平均比较次数 (n+1)/2 查找失败:最少比较次数 n 最多比较次数 n 平均比较次数 n 优点：查找结构无特殊要求（线性结构均适用）；算法简单； 缺点：查找效率较低，不适于大表查找。 第 * 页 上述按顺序查找表的查找算法简单，但平均查找长度较大，不适用于表长较大的查找结构。 2. 折半查找（二分查找） （Binary Search) 若静态查找表为有序表，则查找过程可以基于“折半”进行。 第 * 页 基于有序顺序表的折半查找 设n个数据对象存放在一个有序顺序表中，并按其关键字值从小到大（或从大到小）排好序。 原理：折半查找时, 每次都先求出位于查找区间正中的对象的下标mid，用其关键字与给定值x比较，然后根据比较结果将查找区间缩小一半，直至找到被查找对象。 第 * 页 1.Element[mid].key==x 查找成功； 2.Element[mid].keyx 把查找区间缩小为表的前半部分，继续折半查找； 3.Element[mid].keyx 把查找区间缩小为表的后半部分，继续折半查找； 如果查找区间缩小到一个对象，且仍未找到想要查找的对象，则查找失败。 折半查找算法（设数据按关键字从小到大有序排列） 第 * 页 右单支树 由于一般二叉树必须仿照完全二叉树那样存储，可能会浪费很多存储空间，右单支树就是一个极端情况。 数组大小为31，实际使用5个数组单元！ 第 * 页 数组中每个元素都是一个结构体类型，包含data、parent、leftChild、rightChild四个分量（域），分别存放数据以及该结点的双亲结点、左孩子结点、右孩子结点所在的数组单元下标。 二叉树的另一数组表示（结构数