定州网站优化【定州开通400电话】定州网站搭建、定州微信公众号推文外包、定州开通京东拼多多设计、定州淘宝装修

定州网站优化【定州开通400电话】定州网站搭建、定州微信公众号推文外包、定州开通京东拼多多设计、定州淘宝装修

定州市，河北省辖县级市，由保定市代管， [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月，入选河北省数字乡村试点地区名单。

1. 为(a)图6-4中delete函数，(b)图6-5中insert函数的运行时间建立递推关系。它们的解各是多少？

2. 为使用带重复链表的词典操作插入、查找和删除编写C语言函数。

3. 为如图6-6那样使用已排序表的插入和删除操作编写C语言函数。

4. 编写C语言函数，使其能在双向链表中由p 指向的单元之后的新单元中插入元素x。图6-9是用于删除的相似函数，不过对插入操作来说，我们不需要知道表头L。

5. 如果使用双向链表数据结构，一种选择是不通过指向单元的指针表示表，而通过具有未使用element字段的单元来表示。请注意，这一“表头”单元本身并非表的一部分。该“表头”的next字段指向该表真正的第一个单元，而这第一个单元的previous字段则指向该“表头”单元。然后可以在不知道表头L（正是我们在图6-9中需要知道的）的情况下删除由指针p指向的单元，而不是那个未使用element字段的“表头”。编写C语言函数，使其利用这里描述的格式从双向链表中删除元素。

6. 编写递归函数，实现使用链表数据结构的(a)retrieve (i ,L )；(b)length (L )；(c)last (L )。

7. 扩展下列函数，使其单元可以接受任意类型ETYPE的元素，使用函数eq (x,y )测试x 和y 是否相等，并用lt (x,y )分辨x 是否在ETYPE类型元素的次序下先于y。

(a) 图6-3中的lookup 。

(b) 图6-4中的delete 。

(c) 图6-5中的insert 。

(d) 使用带重复表的insert、delete 和lookup 。

(e) 使用已排序表的insert、delete 和lookup 。

6.5　表基于数组的实现

实现表的另一种常见方式是创建由下列两部分组成的结构体。

1. 存放元素的数组；

2. 记录表中当前元素数量的变量length。

图6-10展示了如何使用数组A[0..MAX-1]表示表(a0,a1,…,an-1)。元素a0、a1、…、an-1存储在A[0..n-1]中，而且length=n。

图 6-10　存放表(a0,a1,…,an-1)的数组A

就像在6.4节中那样，我们假设表中元素都是整数，并邀请读者将这些函数一般化为支持任意类型。表基于数组的实现所使用结构体的声明如下

typedef struct {
    int A[MAX];
    int length;} LIST;复制代码

这里的LIST是包含两个字段的结构体，第一个字段是存储元素的数组A，而第二个则是含有表中当前元素数目的整数变量length。MAX是个用户定义的常量，用于为存储在表中的元素的数目确定边界。

与表的链表表示相比，基于数组的表示从多个方面讲都更方便。不过，它会受到表不能长过数组的限制，这可能导致插入操作失败。在链表表示中，只要有可用的计算机内存，就可以让表增长到尽可能长。

对基于数组的表执行词典操作，所花的时间与对链表表示的表执行这些操作所花的时间基本相同。要插入x，先查找x。如果没找到x，就要检查是否有length< MAX。如果length 不小于MAX，就有出错的情况，因为没法将新元素装入数组中。否则，我们将x 存储在A[length]中，并将length 增加1。要删除x，还是先查找x，如果找到，就将数组A中x 之后的元素都下移一个位置，然后将length 减1。插入和删除的具体函数实现留作本节习题。接下来要介绍查找操作的细节。

6.5.1　线性查找

图6-11是实现查找操作的函数。因为数组A可能很大，所以选择传递指向LIST类型结构体的指针pL作为lookup 的形式参数。在该函数中，结构体的两个字段可以称为pL->A[i]和pL->length。

从i=0开始，第(1)至第(3)行的for循环会依次检查数组的每个位置，直到它到达最后出现的位置，或是找到x。如果找到x，就返回TRUE。如果它检查了表中的每个元素而没有找到x，就会在第(4)行返回FALSE。这种查找方法叫作线性查找或顺序查找。

     BOOLEAN lookup(int x, LIST *pL)
     {
         int i;(1)      for (i = 0; i < pL->length; i++)(2)          if (x == pL->A[i])(3)              return TRUE;(4)      return FALSE;
     }复制代码

图 6-11　通过线性查找进行查找操作函数

不难理解，如果x 在表中，那么在找到x 之前，平均要查找数组A[0..length-1]的一半。因此，设n 为length的值，那么执行一次查找要花O(n)的时间。如果x 未出现，就要查找完整个数组A[0..length-1]，再次需要O(n)的时间。这样的表现，与对用链表表示的表执行查找操作的表现是一样的。

常数因子在实际应用中的重要性

纵观第3章，我们一直在强调运行时间的大O度量的重要性，而且可能给大家留下了这样的印象：大O是唯一的影响因素，或是说任何O(n)算法在执行某项任务时都和其他O(n)算法有着同样的表现。不过在这里，在对哨兵的讨论中，以及其他几节中，我们都会细究隐藏在O(n)之中的常数因子。原因很简单。尽管运行时间的大O度量主导了常数因子，但研究该主题的人都能很快地了解这一点。例如，我们了解到只要n 大到足以产生影响，就要使用具有O(n logn)运行时间的排序。软件性能上的竞争优势，往往源于对具有正确“大O”运行时间的算法中的常数因子的改进，而这种优势通常能决定软件产品的成败。

6.5.2　带哨兵的查找

通过将x 临时插入表的末尾，可以简化图6-11中for循环的代码，并为该程序提速。在表末端的这个x 就叫作哨兵（sentinel）。这项技术最先是在3.6节附注栏内容“更具防御性的程序设计”中提到的，而它在这里有着重要的应用。假设在表的末端始终有一个额外的槽，就可以使用图6-12中的程序查找x。该程序的运行时间仍为O(n)，但比例常数更小，因为图6-12所示程序的循环体和循环测试所需的机器指令数，通常小于图6-11所示程序所需的。

     BOOLEAN lookup(int x, LIST *pL)
     {
         int i;(1)      pL->A[pL->length] = x;(2)      i = 0;(3)      while (x != pL->A[i])(4)          i++;(5)      return (i < pL->length);
     }

定州网站优化【定州开通400电话】定州网站搭建、定州微信公众号推文外包、定州开通京东拼多多设计、定州淘宝装修