定州网站推广【定州办理400电话】定州SEO优化、定州微信公众号APP客户端小程序开发、定州网站托管、定州APP开发

定州网站推广【定州办理400电话】定州SEO优化、定州微信公众号APP客户端小程序开发、定州网站托管、定州APP开发

定州市，河北省辖县级市，由保定市代管， [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.3.4　习题

1. 设L 是表(3，1，4，1，5，9)，回答下列问题。

(a) delete (5，L )的值是多少？

(b) delete (1，L )的值是多少？

(c) 弹出L 的结果是什么？

(d) 将2压入表L 的结果是什么？

(e) 如果以元素6和表L 执行lookup，会返回什么？

(f) 如果M 是表(6，7，8)，那么LM（L 和M 的串接）的值是多少？ML 的值又是多少？

(g) first (L )是多少？last (L )又是多少？

(h) retrieve (3，L )的结果是多少？

(i) flengh (L )的值是多少？

(j) isEmpty (L )的值是多少？

2. ** 如果L 和M 是表，在什么条件下有LM=ML？

3. ** 设x 是元素而L 是表，那么在什么条件下以下等式为真？

(a) delete (x，insert (x，L ))=L

(b) insert (x，delete (x，L ))=L

(c) first (L )=retrieve (1，L )

(d) last (L )=retrieve (length (L )，L )

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)。

6.4.4　插入

向链表中插入元素x 的函数如图6-5所示。要插入x，需要确定x 没有出现在表中。如果它已经在表中，就什么都不用做。如果x 未出现，就必须将其添加到表中。将x 添加到表中的什么位置并不重要，不过图6-5中的函数是将x 添加到表的末尾。在第(1)行检测到末尾的NULL时，就确定x 不在表中。那么，第(2)到第(4)行就会将x 添加到表尾。

如果表非NULL，第(5)行就会检查x 是否在当前单元。如果x 不在这里，第(6)行就会对表的尾部进行递归调用。如果在第(5)行就找到x，那么函数insert就会终止，不进行任何递归调用，而且不会对表L 造成任何改变。调用insert(x,&D)会初始化将x 插入词典D 的操作。

     void insert(int x, LIST *pL)
     {(1)      if ((*pL) == NULL) {(2)          (*pL) = (LIST) malloc(sizeof(struct CELL));(3)          (*pL)->element = x;(4)          (*pL)->next = NULL;
         }(5)      else if (x != (*pL)->element)(6)          insert(x, &((*pL)->next));
     }复制代码

图 6-5　元素的插入

与查找和删除的情况一样，如果在表中没有找到x，就会到达表的末端，花费O(n)的时间。如果找到x，那么平均会走过表中一半1的位置，而且平均而言仍会花O(n)的时间。

1在后面的分析中，当说到长度为n的表的中点时，将会使用“一半”或“n/2”这样的说法。严格地说，(n+1)/2要更加精确。

定州网站推广【定州办理400电话】定州SEO优化、定州微信公众号APP客户端小程序开发、定州网站托管、定州APP开发