张北网络公司哪家好【张北企业网站百度SEO推广公司】张北做网站开发价格、张北淘宝店铺开店装修设计运营、公司网站制作方案流程改版维护费用、张北高端企业网站页面制作设计专业公司需要多少钱

张北网络公司哪家好【张北企业网站百度SEO推广公司】张北做网站开发价格、张北淘宝店铺开店装修设计运营、公司网站制作方案流程改版维护费用、张北高端企业网站页面制作设计专业公司需要多少钱

河北省张家口市张北县地处河北省西北部，内蒙古高原南缘的坝上地区，境域东西109公里，南北67公里，东南部与崇礼区交界，桦皮岭为全县最高点，海拔2128米；北、中部地势平坦，向西北渐低，安固里淖为最低点，海拔1300米。全县总面积4185平方公里，辖18个乡镇、366个行政村、1167个自然村，总人口37.2万人。居民以汉族为主，占总人口的98%，还有蒙古族、回族、满族等。张北县是离京津地区最近的高原地区，夏天气候凉爽是避暑胜地。

张北县被列为第一批国家新型城镇化综合试点地区。 [1]  2019年11月，入选第二批节水型社会建设达标县（区）名单。 [2]  2020年2月29日，退出贫困县序列，正式脱贫“摘帽”。 [3]  2020年12月，入选河北省数字乡村试点地区名单。

删除操作稍有区别。在遇到含有元素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个元素。

插入

删除

查找

无重复

n/2→n

n/2→n

n/2→n

有重复

0

m

n/2→m

已排序

n/2

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 指向的那个单元就顺利地与表分离了，其前一个单元和后一个单元现在是互相指向的。

张北网络公司哪家好【张北企业网站百度SEO推广公司】张北做网站开发价格、张北淘宝店铺开店装修设计运营、公司网站制作方案流程改版维护费用、张北高端企业网站页面制作设计专业公司需要多少钱