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

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

正定县，河北省石家庄市辖县，位于太行山东麓的山前倾斜平原、山前冲积扇的中上部，因“真正安定”之意得名 [1-2]  ；正定县位于东经114°23′~114°43′，北纬38°6′~38°22′，总面积486平方千米，气候型为温带季风气候，四季分明，多年平均气温13.1℃，多年平均降水量550毫米 [3]  ；截至2020年10月，正定县下辖2个街道、3个镇和5个乡，境内设有中国（河北）自由贸易试验区正定片区和正定新区；截至2019年末，正定县常住人口为51.7万人 [1]  。

正定县前身为真定县，有1600多年的建城史，最初为鲜虞国都城，后为中山国都城，建县始于秦始皇统一中国后设立的东垣县，“真定”一名始于汉高祖十一年（前196年）改东垣县为真定县，最终于清雍正元年（1723年）改为现名 [2]  。正定县是京津冀城市群、石家庄都市圈的重要城镇，境内建有石家庄正定国际机场，有京广高速铁路过境 [4]  。正定县有“九楼四塔八大寺，二十四座金牌坊”，有“古建艺术宝库”美称 [1]  。

2020年上半年，正定县财政收入为35.7亿元，同比增长5.8%；一般公共预算收入为26.9亿元，同比增长10.1%；固定资产投资为116.2亿元，同比增长11%；服务业增加值为100.3亿元，同比增长11%；规模以上高新技术产业增加值达5.9亿元，同比增长18%；社会消费品零售总额达40.8亿元，同比增长10%；外贸进出口总额达91亿元，同比增长366%；城乡居民人均可支配收入分别为18146元和10260元，同比增长8.2%和8.7% [5]  。

9.8.2　迪杰斯特拉算法的数据结构

现在要展示迪杰斯特拉算法的一种高效实现，它利用了5.9节的平衡偏序树结构。11这里要使用两个数组，一个是表示该图的graph数组，另一个是表示偏序树的potNodes。这样做的目的是，对图中的各节点u，都有一个与之对应的偏序树节点a，其优先级就等于dist (u)。不过，和5.9节不同的是，我们将按照最低优先级而不是最高优先级来组织该偏序树。或者，我们可以取-dist (u)为a 的优先级。图9-43展示了这种数据结构。

11其实，当弧的数量要比节点数的平方（也就是能达到的弧的最大数量）小一些时，这种实现是唯一的好方法。我们将在习题中讨论用于稠密图情况的一种简单实现。

我们用NODE作为图节点的类型。和往常一样，将用从0开始的整数为节点命名，还将使用POTNODE作为偏序树中节点的类型。就像在5.9节中那样，为了方便，我们会假设偏序树中的节点是用从1开始的整数编号的。因此，NODE和POTNODE类型就等同于int。

图 9-43　用来表示对应迪杰斯特拉算法的图的数据结构

GRAPH数据类型定义如下

typedef struct {
    float dist;
    LIST successors;
    POTNODE toPOT;} GRAPH[MAX];复制代码

这里，MAX是图中的节点数，而LIST则是由CELL类型的单元组成的邻接表的类型。因为需要加上为浮点数标号的标签，所以就应该像下面这样定义CELL类型

typedef struct CELL *LIST;struct CELL {
    NODE nodeName;
    float nodeLabel;
    LIST next;};复制代码

我们将数据类型POT声明为图中节点组成的数组

typedef NODE POT[MAX+1];复制代码

我们现在可以定义以下关键数据结构

GRAPH graph;POT potNodes;POTNODE last;复制代码

结构体数组graph含有图中的节点，而数组potNodes则包含了偏序树中的节点，而变量last则表示偏序树（存放在数组potNodes[1..last]中）当前的末端。

直觉上讲，偏序树的结构是用数组potNodes中的位置表示的，就像平常表示偏序树那样。该数组中的元素让我们通过引用回图本身来区分节点的优先级。特别要说的是，在potNodes[a]中放置的是所表示图节点的索引u。而dist字段graph[u].dist给出了节点a在偏序树中的优先级。

9.8.3　迪杰斯特拉算法的辅助函数

我们需要若干辅助函数来让实现运转起来。最基础的函数是swap，它会交换偏序树中的两个节点。这个问题并不像5.9节中的那么简单。在这里，graph的toPOT字段必须继续记录数组potNodes中的值，如图9-43所示。也就是说，如果graph[u].toPOT的值为a，那么还肯定有potNodes[a]的值为u。

swap函数的代码如图9-44所示。它接受的参数包括图G、偏序树P，以及偏序树中的两个节 点a和b。这里将检验该函数交换偏序树a 和b 两项中的值并交换对应图节点的toPOT字段的工作留给读者作为练习。

void swap(POTNODE a, POTNODE b, GRAPH G, POT P){
    NODE temp; /* 用来交换偏序树节点 */

    temp = P[b];
    P[b] = P[a];
    P[a] = temp;
    G[P[a]].toPOT = a;
    G[P[b]].toPOT = b;}复制代码

图 9-44　交换偏序树中两个节点的函数

我们将需要让节点在偏序树中上冒与下沉，就像在5.9节中所做的那样。其主要区别在于，这里的数组potNodes中元素的值不是优先级。这个值会把我们带到graph数组中的节点，而在表示该节点的结构体中可以找到字段dist，它会告诉我们优先级。因此我们还需要辅助函数priority返回合适节点对应的dist。我们还将在本节内容中作出如下假设，较小的优先级会上升到偏序树的顶端，而非5.9节中那样是较大优先级。

图9-45展示了priority、bubbleUp和bubbleDown函数，它们都是对5.9节中同名函数进行简单修改后得到的。这些函数都接受图G和偏序树P作为参数。而函数bubbleDown还需要整数参数last，用来表示数组P中当前偏序树的末端。

float priority(POTNODE a, GRAPH G, POT P){
    return G[P[a]].dist;}void bubbleUp(POTNODE a, GRAPH G, POT P){
    if ((a > 1) &&
            (priority(a, G, P) < priority(a/2, G, P))) {
        swap(a, a/2, G, P);
        bubbleUp(a/2, G, P);
    }}void bubbleDown(POTNODE a, GRAPH G, POT P, int last){
    POTNODE child;

    child = 2*a;
    if (child < last &&
            priority(child+1, G, P) < priority(child, G, P))
        ++child;
    if (child <= last &&
            priority(a, G, P) > priority(child, G, P)) {
        swap(a, child, G, P);
        bubbleDown(child, G, P, last);
    }}复制代码

图 9-45　偏序树中节点的上冒与下沉

9.8.4　初始化

我们将假设对应图中各节点的邻接表已经创建，而且指向图节点u 的邻接表的指针已经出现在graph[u].successors中。还要假设节点0是源节点。如果接受图节点i 与偏序树节点i+1对应，数组potNodes就恰如其分地被初始化为偏序树。也就是说，偏序树的根节点表示图的源节点，也就是我们给定优先级0的节点，而且我们要为所有其他节点给定优先级INFTY，这是定义为“无限”的常量。

带异常的初始化

请注意，在图9-46的第(2)行中，我们将dist[1]以及所有其他距离都置为INFTY。接着在第(5)行，再将该距离修正为0。与测试每个i 值以确定其是否为异常情况相比，这种方式要更具效率。诚然，如果我们将第(2)行替代为

if (i == 0)
   G[i].dist = 0;else
   G[i].dist = INFTY;复制代码

就可以消除第(5)行，不过这样一来不仅增加了代码，还会增加运行时间，因为这样修改就必须进行n 次测试和n 次赋值，而不是像图9-46中的第(2)行和第(5)行那样只用进行n+1次赋值而不用进行测试。

正如我们将要看到的，在迪杰斯特拉算法的第一轮处理中，我们选择“解决”源节点，这样就创造了可以作为非正式介绍中起始点的条件，其中源节点是已解决的，而且dist[u]只有在存在从源节点到u 的弧时才不是无限长。初始化函数如图9-46所示。正如本节中之前的函数那样，initialize接受图和偏序树作为参数，还要接受指向整数last的指针pLast，所以该函数可以将pLast初始化为MAX，也就是该图中节点的数量。回想一下，last表示的是与当前正使用的偏序树对应的数组中最后一个位置。

     void initialize(GRAPH G, POT P, int *pLast);
     {
         int i; /* i既作为图节点，也作为树节点， */(1)      for (i = 0; i < MAX; i++) {(2)          G[i].dist = INFTY;(3)          G[i].toPOT = i+1;(4)          P[i+1] = i;
         }(5)      G[0].dist = 0;(6)      (*pLast) = MAX;
     }复制代码

图 9-46　迪杰斯特拉算法的初始化

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