张北企业微信公众号小程序开发公司、张北企业网页设计方案、张北做网站开发价格、张北微信公众号制作运营报价明细表、张北网站设计公司费用、张北网站推广大概需要多少钱

张北企业微信公众号小程序开发公司、张北企业网页设计方案、张北做网站开发价格、张北微信公众号制作运营报价明细表、张北网站设计公司费用、张北网站推广大概需要多少钱

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

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

6.4　链表数据结构

实现表的最简单方式就是使用链表。每个链表单元都由两个字段构成，一个字段包含着表中的元素，另一个字段则含有指向链表下一单元的指针。简单起见，假设元素都是整数。我们不仅能使用具体的int类型来表示元素的类型，而且能用==、<等标准比较运算符来比较元素。本节习题将会启发读者编写这些函数的变体，使其能处理任意类型的元素，而元素的比较则是由用户定义的函数进行的，比如测试相等性的eq，及测试x 在次序上是否先于y 的lt (x,y )，等等。

接下来，要使用来自1.6节中的宏：

DefCell(int, CELL, LIST);复制代码

它可展开为表示单元和表的标准结构体

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

请注意，LIST是指向单元的指针类型。实际上，每个单元的next字段既指向下一个单元，也指向表中剩余的所有部分。

图6-2展示了表示抽象表L=(a1,a2,…,an)的链表。每个单元都对应一个元素，元素ai 出现在第i 个单元的element字段。对i=1,2,…,n-1而言，第i 个单元中的指针是指向第i+1个单元的，而最后一个单元中的指针为NULL，表示这是表的末尾。在表之外是个名为L的指针，它指向该表的第一个单元，L是LIST类型的。如果表L 为空，L的值就为NULL。

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

表和链表

请记住，表是一种抽象模型，或者说是数学模型。而链表则是种简单的数据结构，这在第1章中提到过。虽然链表是实现表数据模型的一种方式，但正如我们所见，它并非实现表数据模型的唯一方式。无论如何，这是再次记住模型与实现模型的数据结构之间区别的良好时机。

6.4.1　词典操作的链表实现

如果用链表表示词典，那么该如何实现操作？以下对词典的操作是在5.7节中定义的。

1. insert (x，D )，将元素x 插入词典D 中；

2. delete (x，D )，从词典D 中删除元素x；

3. lookup (x，D )，确定元素x 是否在词典D 中。

我们将看到，与之前章节中讨论过的二叉查找树相比，链表是一种更为简单的实现词典的数据结构。不过，在使用链表表示时，词典操作的运行时间不像使用二叉查找树时那么少。在第7章中还将看到一种更佳的表示词典的方式——散列表，它利用对表的词典操作作为子例程。

这里假设我们的词典包含的是整数，而且单元是按照本节开头那样定义的。那么词典的类型就是LIST，也是像本节开头那样定义的。含有元素集合{a1,a2,…,an}的词典可以用图6-2中的链表表示。还有很多其他的表可以表示这一集合，因为元素的次序在集合中是无关紧要的。

6.4.2　查找

要执行lookup(x，D )，就要对表示D 的表中的每个单元加以检验，看看它是否存放了所需的元素x。如果是，就返回TRUE。如果到达表末仍未发现x，就返回FALSE。一如之前那样，定义的常量TRUE和FALSE表示常数1和0，BOOLEAN则表示定义的类型int。递归函数lookup(x,D)如图6-3所示。

如果表的长度为n，就说图6-3中的函数所花的时间为O(n)。除了结尾的递归调用外，lookup花的时间是O(1)。当调用执行之后，剩余的表的长度要比表L 的长度小1。因此对长度为n 的表执行lookup要花上O(n)的时间应该不会让人感到意外。更加正式地讲，以下递推关系给出了当第二个参数指向的表L 长度为n 时lookup的运行时间。

BOOLEAN lookup(int x, LIST L){
    if (L == NULL)
        return FALSE;
    else if (x == L->element)
        return TRUE;
    else
        return lookup(x, L->next);}复制代码

图 6-3　在链表中查找

依据。T0.=O(1)，因为当L 为NULL时，没有进行递归调用。

归纳。T(n)=T(n-1)+O(1)。

正如我们在第3章中见过很多次，这一递推关系的解是T(n)=O(n)。因为含n 个元素的词典是用长度为n 的表表示的，所以对大小为n 的词典执行查找操作所花的时间也是O(n)。

不幸的是，进行一次成功查找的平均时间也与n 成比例。如果要查找的元素x 确定在D 中，那么x 在表中位置的期望值为(n+1)/2。也就是说，x 会等可能地出现在从第一个元素到第n 个元素中的任一位置。因此，递归调用lookup的次数的期望值是(n+1)/2。因为每次调用所花的时间是O(1)，所以平均成功查找所花的时间为O (n )。当然，如果查找不成功，那么在到达表末并返回FALSE之前，已经进行了全部n 次调用。

6.4.3　删除

从链表中删除元素x 的函数如图6-4所示。第二个参数pL是指向表L 的指针，而不是表L 本身。这里使用了“按引用调用”的风格，因为我们希望delete可以从表中删除含有x 的单元。随着我们沿着表向下移动，pL中存放着一个指针，它指向的是指向“当前”单元的指针。如果在第(2)行发现x 在当前单元C 中，就接着在第(3)行改变指向单元C 的指针，使得它指向该表中紧跟在C 之后的那个单元。如果C 正好在表的末尾，之前指向C 的指针就成了NULL。如果x 不是当前的元素，那么在第(4)行就递归地从表尾删除x。

请注意，如果表为空表，那么第(1)行的测试会使该函数在没有任何动作的情况下返回。这是因为x 不会出现在空表中，而我们不需要采取任何措施来从词典中删除x。如果D 是表示词典的链表，那么调用delete(x,&D)就会初始化从词典D 中删除x 的操作。

     void delete(int x, LIST *pL)
     {(1)      if ((*pL) != NULL)(2)          if (x == (*pL)->element)(3)              (*pL) = (*pL)->next;
             else(4)              delete(x, &((*pL)->next));
     }复制代码

图 6-4　删除元素

如果元素x 没有出现在表示词典D 的链表中，那么就会继续向下运行直到表的末端，为每个元素花上O(1)的时间。分析过程类似对图6-3中lookup函数的分析，这里就将细节留给读者自己来分析吧。因此，如果D 有n 个元素，那么删除不在D 中的元素所花的时间是O(n)。如果x 在词典D 中，那么平均下来，将会在表中接近中点的位置遇到x。因此，平均要查找(n+1)/2个单元，而成功删除操作的运行时间也是O(n)。

张北企业微信公众号小程序开发公司、张北企业网页设计方案、张北做网站开发价格、张北微信公众号制作运营报价明细表、张北网站设计公司费用、张北网站推广大概需要多少钱