定州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月，入选河北省数字乡村试点地区名单。

6.4.5　带重复的插入、查找和删除

如果在执行插入操作之前不检查x是否出现在表中，可以让插入操作运行得更快。不过，这样做的后果就是，在表示词典的表中可能有某一元素的多个副本。

要执行词典操作insert (x，D )，只要创建一个新单元，将x放进去，并将该单元压入表示D 的表的开头即可。这一操作花费O(1)的时间。

查找操作就和图6-3中所示的一模一样。唯一的不便就是可能要查找更长的表，因为表示词典D 的表的长度可能会大于D 中的成员数。

重提抽象和实现

大家可能会感到惊讶，我们在表示词典的表中使用了重复，因为抽象数据类型DICTIONARY被定义为集合，而集合是不含重复的。不过，有重复的并不是词典，而实现词典的数据结构可以有重复。但是，即便当x在链表中多次现身，它在链表表示的词典中也只会出现一次。

删除操作稍有区别。在遇到含有元素x 的单元时，我们不能停止对x 的查找，因为表中可能还有x 的其他副本。因此，就算表L 的表头包含x，也必须将x 从L 的尾部删除。这样一来，我们不只要处理更长的表，而且要实现成功的删除操作，就必须查找每个单元，而不像表中不允许出现重复的情况时那样是平均查找表的一半。这些带重复的词典操作的细节就留作本节习题了。

总之，通过允许重复，可以让插入操作变得更快，时间是O(1)而不是O(n)。不过，成功的删除操作需要对整个表进行查找，而不是平均查找一半列表。而且对于查找和删除，必须要处理比不允许重复时更长的表，虽然长多少取决于插入词典中已存在元素的频率有多高。

要选择哪种方法是有点技巧的。显然，如果插入操作占主导地位，就应该允许重复。在极端情况下，如果只插入而从不查找或删除，就能让每次操作具有O(1)（而不是O(n)）的性能。2如果有理由确定从不会插入词典中已存在的元素，就可以使用快速插入和快速删除，那样只要找到待删除元素的一次出现就可以停下了。另一方面，如果有可能插入重复的元素，而且查找或删除又占主导地位，那么在插入x 之前最好还是先检查一下它是否已经存在于表中，就如图6-5所示的insert函数那样。

2如果从来都不管词典中有什么，还干嘛费事往里面插东西呢？

6.4.6　表示词典的已排序表

另一种方案是让表示词典D 的表中的元素一直按照递增次序排好序。然后，如果希望查找元素x，只要行进到x 可能出现的位置就行了，平均而言，也就是表的中间位置。如果遇到大于x 的元素，就说明在后面的部分没希望找到x 了。因此就不用沿着表行进以继续进行失败的查找了。这样做可以节省为2的因数（开销变为一半），不过确切的因数是有些模糊的，因为在表中每遇到一个元素就必须询问按照排序次序x 是否在其之后。不过，在进行插入和删除操作时，在不成功的查找上也能节约同样的开销。

用于已排序表的查找函数如图6-6所示。把图6-4和图6-5所示函数修改为处理已排序表的版本的工作就留作本节习题了。

BOOLEAN lookup(int x, LIST L){
    if (L == NULL)
        return FALSE;
    else if (x > L->element)
        return lookup(x, L->next);
    else if (x == L->element)
        return TRUE;
    else /* 这里有 x < L->element，
            因此x 不可能在已排序表 L 中 */
        return FALSE;}复制代码

图 6-6　在已排序表中查找

6.4.7　各种方法的比较

图6-7中的表格表明了对我们讨论过的3种基于表的词典表示，执行3种词典操作各自必须查找的单元数。设词典中有n 个元素，如果不允许重复，这也就是表示词典的表的长度。在允许重复出现时，我们用m 来表示该表的长度。我们知道m≥n，但不知道m 比n 大多少。在用到n/2→n 这样的表示方式时，意思是当查找成功时，平均查找了n/2个单元，而在不成功时，平均查找了n 个单元。而n/2→m 这样的项则表示，在一次成功的查找中，我们在看到要查找的元素之前，平均会看到词典中n/2个元素3，但在失败的查找中，就必须走完整个长度为m 的表，直到到达其末端。

3事实上，因为可能存在重复，所以在看到n/2个不同元素前，可能已经检查了多于n/2个元素。

图 6-7　3种用链表表示词典的方法所查找的单元数

请注意，除了有重复情况下的插入操作外，这些运行时间都要比数据结构为二叉查找树时词典操作的平均运行时间长。正如我们在5.8节中所见，在使用二叉查找树时，词典操作平均所花时间为O(logn)。

明智的测试次序

请注意图6-6的程序中3项测试的次序。首先要测试L 不为NULL。我们没有其他的选择，因为如果L 为NULL，则其余两项测试会导致错误。设y 是L->element的值。那么除了最后一个单元外，在每个访问过的单元都有x>y。因为如果有x=y，就是成功完成了查找，而如果x< y，就是没能找到x 而终止。因为首先要测试x>y，而且当且仅当它失败时，我们才需要区分另两种情况。测试的这种次序遵循这样一个基本原则：要首先测试最平常的情况，并因此节约平均要执行的总测试数。

如果访问了k 个单元，就要测试k 次L 是否为NULL，而且要测试k 次x 是否大于y。并且还要测试一次是否有x=y，这样总共要进行2k+1次测试。也就是说，只比图6-3中利用未排序表的lookup函数成功找到元素x 的情况多一次测试。如果未找到该元素，可以预期在图6-6中使用的测试要比在图6-3中使用的测试少得多，因为图6-6中平均只要检查一半单元后就会停止。因此，虽然不管使用已排序表还是使用非排序表，词典操作的大O运行时间都是O(n)，但是如果使用已排序表的话，通常会有常数因子上的轻微优势。

6.4.8　双向链表

在链表中，要从某个单元向表的开头移动不是那么容易的。而双向链表是这样一种数据结构，它让表中向前和向后的移动都非常方便。整数双向链表中的单元包含3个字段：

typdef struct CELL *LIST;struct CELL {
    LIST previous;
    int element;
    LIST next;};复制代码

多出来的这个字段含有指向表中前一个单元的指针。图6-8展示了表示表L=(a1,a2,…,an)的双向链表数据结构。

图 6-8　表示表L=(a1,a2,…,an)的双向链表

双向列表结构上的词典操作基本与单向链表上的那些操作相同。要了解双向链表的优势，可以考虑只给定指向元素ai 所在单元的指针时删除该元素的操作。在单向链表中，我们要通过从头开始查找该表来找出前一个单元。而有了双向链表，就可以通过如图6-9所示的一系列指针操作，在O(1)时间里完成这一操作。

     void delete(LIST p, LIST *pL)
     {
         /* p 是指向待删除单元的指针，
           而pL 是指向链表的指针 */(1)      if (p->next != NULL)(2)          p->next->previous = p->previous;(3)      if (p->previous == NULL) /* p 指向第一个单元 */(4)          (*pL) = p->next;
         else(5)          p->previous->next = p->next;
     }复制代码

图 6-9　从双向链表中删除元素

图6-9中所示的delete(p,pL)函数接受指向待删除单元的指针p，以及指向表L 本身的指针pL 作为参数。也就是说，pL 是指向表中第一个单元的指针的地址。在图6-9的第(1)行中，我们要检查p 有没有指向最后一个单元。如果没有的话，那么在第(2)行，我们会让接下来那个单元的反向指针指向在p 之前的那个单元。如果p 正好指向第一个单元的话，就让它等于NULL。

第(3)行会测试p 是否为第一个单元。如果是，那么在第(4)行我们会让pL 指向第二个单元。请注意，在这种情况下，第(2)行会让第二个单元的previous字段变为NULL。如果p 不是指向第一个单元，那么在第(5)行我们会让前一个单元的正向指针指向p 之后的那个单元。这样一来，由p 指向的那个单元就顺利地与表分离了，其前一个单元和后一个单元现在是互相指向的。

6.4.9　习题

定州400电话办理【定州网站公司】定州百度优化、定州域名注册、定州网店美工、定州微信公众号托管