定州小程序制作【定州企业邮箱】定州网站外包、定州微信商城开发、定州网店美工、定州淘宝设计

定州小程序制作【定州企业邮箱】定州网站外包、定州微信商城开发、定州网店美工、定州淘宝设计

定州市，河北省辖县级市，由保定市代管， [1]  是河北省省直管县（市）体制改革试点县（省直管县行政区划隶属关系不变 [2]  ）， [3-4]  是全省重点培育的新兴区域中心城市。连续4年获评全国中小城市投资潜力百强、新型城镇化质量百强，晋级全国科技创新百强，入围全国县域经济强县。面积1283平方公里，截至2019年，定州市常住总人口123.09万人，辖25个乡镇（办），542个村（社区）。 [5-6] 

定州市位于京津冀经济区，是京津冀经济区重要节点城市 [7]  ，国家新型城镇化综合试点地区 [8]  ，河北省十二五规划重点培育的现代化中等城市 [9]  ，河北省十大历史文化名城之一。

2019年，定州市户籍总户数37.3万户，户籍总人口124.1万人，比上年增加0.3万人。常住总人口123.09万人，比上年末增加0.4万人。 [6]  2019年，定州市生产总值实现3330429万元，比上年增长7.1%。按常住人口计算，定州市人均地区生产总值为27101元。 [6]  2020年9月，入选河北省食品产业强县（市、区）（培育型）名单。 [10]  2020年12月，入选河北省数字乡村试点地区名单。

图 6-12　进行带哨兵查找的函数

第(1)行将哨兵放置在刚好越过该表的位置。请注意，因为length不会发生改变，所以这个x 并非真正是表的一部分。第(3)和第(4)行的循环会增加 i，直到我们找到x。请注意，因为设置了哨兵，所以即便表是空表，还是保证能找到x。在找到x 之后，第(5)行会测试是找到了表中真正出现的x（也就是，i < length），还是找到了哨兵（也就是，i < length）。请注意，如果使用哨兵，就一定要严格保证length 小于MAX，否则就没有位置放置哨兵了。

6.5.3　利用二叉查找对已排序表进行查找

假设表L中的元素a0、a1、…、an-1已经按照非递减次序排好序。如果该已排序表存储在数组A[0..n-1]中，就可以利用二叉查找技术，从而带来可观的速度提升。我们首先必须找到中间元素的下标m，也就是说m=[(n-1)/2]。4然后将元素x与A[m ]相比较。如果它们相等，就已经找到x 了。如果x< A[m ]，就递归地重复对子表A[0..m-1]的查找。如果x>A[m ]，就递归地重复对子表A[m+1..n-1]的查找。无论何时尝试查找空表，都会报错。图6-13展示了分区过程。

4⌊a⌋表示a 向下取整，就是a 的整数部分。因此⌊6.5⌋=6，而且⌊6⌋=6。而⌈a⌉表示a 向上取整，是大于等于a 的最小整数。例如⌈6.5⌉=7，而⌈6⌉=6。

函数binsearch的代码要将x 放置在如图6-14所示的已排序数组A 中。该函数使用变量low和high表示x 可能出现的区域的下界和上界。如果较低的区域超过了较上的区域，那么就没找到x，此时函数就会终止并返回FALSE。

否则，binsearch会通过mid=⌊(low+high)/2⌋计算该区域的中点。然后该函数会检查区域正中的元素A[mid ]，以确定x 是否在该位置。如果x 不在该位置，而且小于A[mid ]，就继续在中点下方的区域查找，要是x 大于A[mid ]，就继续在中点上方的区域查找。这一思路概括了图6-13所示的划分，其中low 是0，而high 是n-1。

图 6-13　二叉查找将区域一分为二

利用归纳断言“如果x 在数组中，那么它一定出现在A[low..high]这个区域内”，就可以证明函数binsearch的正确性。证明过程要对high-low 的差进行归纳，这留作本节的习题。在每次迭代中，binsearch 要么

1. 在到达第(8)行时找到元素x，要么

2. 在第(5)行或第(7)行，对长度至多为待查找数组A[low..high]长度一半的子表递归调用自身。

     BOOLEAN binsearch(int x, int A[], int low, int high)
     {
         int mid;(1)      if (low > high)(2)          return FALSE;
         else {(3)          mid = (low + high)/2;(4)          if (x < A[mid])(5)              return binsearch(x, A, low, mid-1);(6)          else if (x > A[mid])(7)              return binsearch(x, A, mid+1, high);
             else /* x == A[mid] */(8)              return TRUE;
         }
     }复制代码

图 6-14　使用二叉查找进行查找操作的函数

由长度为n 的数组开始，在其长度变为1之前，我们最多对有待查找的数组进行log2n 次分割。于是我们要么在A[mid]找到x，要么在对空表调用该函数后仍未找到x。

想要在具有n 个元素的数组A中寻找x，可以调用binsearch(x,A,0,n-1)。我们知道binsearch最多会调用自身O(logn)次。在每次调用中，都要花费O(1)的时间，再加上递归调用的时间，因此二叉查找的运行时间是O(logn)。这是可与平均花费O(n)时间的线性查找相媲美的查找方式。

6.5.4　习题

1. 编写函数，利用对数组的线性查找进行下列操作：(a)向表L中插入x；(b)从表L中删除x。

2. 使用带哨兵的数组，重复习题(1)的练习。

3. 使用已排序数组，重复习题(1)的练习。

4. 假设表中元素具有任意类型ETYPE，对ETYPE类型来说有函数eq (x,y )区分x 和y 是否相等，还有ly (x, y ) 函数可以区分x 就ETYPE类型元素的次序而言是否先于y，编写以下函数：

(a) 图6-11中的lookup函数；

(b) 图6-12中的lookup函数；

(c) 图6-14中的binsearch函数。

5. ** 设图6-14中的二叉查找算法最多进行k 次探测（也就是在第(3)行求mid的值）时最长数组的长度(high-low+1)为P (k )。例如，P(1)=1，且P(2)=3。写出P (k )的递推关系，再求出自己所写的递推关系的解。它是否说明二叉查找进行的探测次数为O(logn)？

6. * 对low 和high 之差进行归纳，证明：如果x 在区域A[low..high]中，那么图6-14中的二叉查找算法会找到x。

7. 假设数组中可以出现重复的元素，使得插入操作可以在O(1)时间内完成。为这种数据结构编写插入、删除和查找函数。

8. 使用迭代，重新编写二叉查找程序。

9. ** 为对n 个元素的数组进行二叉查找的运行时间建立递推关系，并求解。提示：为了简化问题，可以取T(n)作为对具有n 个或更少元素（而不是像我们常用的方法那样刚好有n 个元素）的数组进行二叉查找的运行时间上界。

10. 在三分查找中，给定从low 到high 的区域，先计算该区域中大约1/3处的位置

first=⌊(2×low+high)/3⌋

并将其与A[second ]相比较。如果x>A[first ]，就计算近似2/3处的位置

second=⌈(low+2×high)/3⌉

并将x与A[second ]进行比较。因此我们将x 隔离在这3个区域的其中一个里，每个区域都不大于low 到high 形成区域的三分之一。编写函数执行三分查找。

11. ** 用三分查找重复习题5。也就是说，要找出三分查找时最多需要k 次探测的最大数组的递推关系并为其求解。二叉查找和三分查找哪种所需的探测次数多？也就是说，对于给定的k，二叉查找和三分查找哪种能处理更大的数组？

6.6　栈

栈是基于表数据模型的抽象数据类型，栈中的所有操作都是在表的一端执行的，而这一端就叫作栈的栈顶。术语“LIFO表”（后入先出表）指的就是栈。

栈的抽象模型与表的抽象模型如出一辙，也就是一列某一类型的元素a1、a2、…、an 。将栈与一般表区分开来的就是栈可以接受的一些特殊操作。我们将在后面的内容中介绍更加齐全的操作，不过现在，我们注意到最精髓的栈操作就是push（压入）和pop（弹出），其中push (x )是将元素x 放在栈顶，pop 则是从栈中移除最顶端的元素。如果将栈顶写在右端，那么对表（a1,a2,…,an）应用push (x )操作，就得到表（a1,a2,…,an ,x）。而弹出表（a1,a2,…,an）得到的是表（a1,a2,…,an-1）。弹出空表ε 是不可能的，而且会出错。

示例 6.9

很多编译器首先会把出现在程序中的中缀表达式转换成等价的后缀表达式。例如，表达式(3+4)×2的后缀形式就是34+2×。栈可以用来为后缀表达式求值。由空栈开始，我们从左至右扫描需要求值的后缀表达式。每当遇到一个参数，就将其压入栈中。而在遇到运算符时，就弹出栈两次，并记下弹出的操作数。然后对弹出的两个值（其中第二个值是运算符左边的操作数）应用该运算符，然后将结果压入该栈。图6-15展示了处理后缀表达式34+2×每一步操作之后栈的情况。在完成处理后，求值的结果14留在该栈中。

图 6-15　用栈求后缀表达式的值

6.6.1　对栈的操作

之前讨论过的两种抽象数据类型——词典和优先级队列，都拥有一组明确与之关联的操作。栈其实是一些相似的ADT，它们有着相同的底层模型，但各自有着所允许操作集不同的变种。在本节中，我们要讨论栈的通用操作，并展示两种可用来实现栈的数据结构，一种是基于链表的，另一种是基于数组的。

正如之前提到的，在任意一组栈操作中都可以看到push 和pop。为栈ADT选择的操作还有个共性：它们都可以在O(1)时间内实现，而与栈中的元素数量无关。大家可以自行验证一下，对于我们提到的两种数据结构，所有操作都只需要常数时间。

除了push 和pop 外，通常还需要clear 操作将栈初始化为空栈。在示例6.9中，默认假设栈一开始为空，而没有解释它为什么是这样。还有一种操作，就是确定栈当前是否为空的测试。

最后要考虑的操作是确定栈是否“已满”的测试。现在在栈的抽象模型中，没有关于满栈的概念，因为原则上讲，栈是可以随意变长的表。不过，在栈的任何一种实现中，都会有某个无法超越的长度。最常见的例子就是在用数组表示表或栈时。正如在6.5节中看到的，必须假设表的长度不会超过常量MAX，否则insert 函数的实现就没法正常工作了。

定州小程序制作【定州企业邮箱】定州网站外包、定州微信商城开发、定州网店美工、定州淘宝设计