上往建站提供服务器空间服务商，百度快照排名，网站托管，百度推广运营,致力于设计外包服务与源代码定制开发，360推广，搜狗推广,增加网站的能见度及访问量提升网络营销的效果,主营：网站公司,百度推广公司电话,官网搭建服务,网站服务企业排名,服务器空间,英文域名等业务，专业团队服务，效果好。

秦皇岛申请400电话费用【秦皇岛企业全国热线电话办理】秦皇岛开通400电话电信价格、秦皇岛微信公众号代运营外包托管、秦皇岛网店编辑装修美工、秦皇岛网站推广优化大概需要多少钱

秦皇岛，简称“秦”，别称港城、临榆，是河北省地级市，国务院批复确定的中国环渤海地区重要的港口城市，著名的滨海旅游、休闲、度假胜地 [1]  。截至2019年，全市下辖4个区、3个县，总面积7813平方千米，常住人口314.63万人，城镇人口191.04万人，城镇化率60.72%。 [2] 

秦皇岛地处中国华北地区、河北东北部、南临渤海，是中国首批沿海开放城市、首都经济圈的重要功能区、京津冀辐射东北的重要门户和节点城市 [3]  ，华北、东北和西北地区重要的出海口、全国性综合交通枢纽、京津冀协同发展与振兴东北老工业基地两大国家战略的交汇点，是中国最早的自主通商口岸、中国最大铝制品生产加工基地、北方最大粮油加工基地，被誉为“车轮制造之都”。 [4-5] 

秦皇岛因秦始皇东巡至此派人入海求仙而得名，是中国唯一一个因皇帝帝号而得名的城市，因《浪淘沙·北戴河》而闻名遐迩，汇集了丰富的旅游资源，是驰名中外的旅游休闲胜地，山海关区是国家历史文化名城 [6]  。秦皇岛作为国家创新型城市试点，拥有13所高等院校，八十余名享受国务院特殊津贴专家，15万名在校大学生，人才密度居全省首位 [7]  。

秦皇岛曾获中国最美海滨城市、全国十佳生态文明城市、中国北方最宜居城市、中国最佳休闲城市、中国最具爱心城市、中国最具幸福感城市等荣誉。秦皇岛曾协办北京亚运会和北京奥运会，是中国唯一协办过奥运会和亚运会的地级市。2017年获全国文明城市称号。2018年获得国家森林城市称号。

2.8.4　完整的程序

图2-31包含了完整的归并排序程序。它类似于图2-3中所示的选择排序程序。第(1)行中MakeList函数读取输入的每个整数，并通过一个简单的递归算法将其放入链表中（我们将在下一节中详细描述该递归算法）。主程序的第(2)行含有对MergeSort的调用，会将一个已排序表返回给PrintList。而PrintList函数会向下遍历整个已排序表，打印出每个元素。

      #include <stdio.h>
      #include <stdlib.h>

      typedef struct CELL *LIST;
      struct CELL {
          int element;
          LIST next;
      };

      LIST merge(LIST list1, LIST list2);
      LIST split(LIST list);
      LIST MergeSort(LIST list);
      LIST MakeList();
      void PrintList(LIST list);

      main()
      {
          LIST list;

          list = MakeList();
 (1)      PrintList(MergeSort(list));
 (2)  }

      LIST MakeList()
      {
          int x;
          LIST pNewCell;

 (3)      if (scanf("%d", &x) == EOF) return NULL;
          else {
 (4)          pNewCell = (LIST) malloc(sizeof(struct CELL));
 (5)          pNewCell->next = MakeList();
 (6)          pNewCell->element = x;
 (7)          return pNewCell;
          }
      }

      void PrintList(LIST list)
      {
 (8)      while (list != NULL) {
 (9)          printf("%d
", list->element);(10)          list = list->next;
          }
      }复制代码

图 2-31(a)　使用归并排序的排序程序（开头）

LIST MergeSort(LIST list){
    LIST SecondList;

    if (list == NULL) return NULL;
    else if (list->next == NULL) return list;
    else {
        SecondList = split(list);
        return merge(MergeSort(list), MergeSort(SecondList));
    }}LIST merge(LIST list1, LIST list2){
    if (list1 == NULL) return list2;
    else if (list2 == NULL) return list1;
    else if (list1->element <= list2->element) {
        list1->next = merge(list1->next, list2);
        return list1;
    }
    else {
        list2->next = merge(list1, list2->next);
        return list2;
    }}LIST split(LIST list){
    LIST pSecondCell;

    if (list == NULL) return NULL;
    else if (list->next == NULL) return NULL;
    else {
        pSecondCell = list->next;
        list->next = pSecondCell->next;
        pSecondCell->next = split(pSecondCell->next);
        return pSecondCell;
    }}复制代码

图 2-31(b)　使用归并排序的排序程序（结尾）

2.8.5　习题

1. 给出对表(1,2,3,4,5)和(2,4,6,8,10)应用merge函数的结果。

2. 假设一开始有表(8,7,6,5,4,3,2,1)，给出产生的merge、split和Mergesort的调用序列。

3. * 多路归并排序会将一个表均分为k 个部分（或分为接近均等的k 个部分），并分别为这些表排序，然后，通过比较这k 个表中第一个元素的大小并选出最小的那个，将这些表合并起来。本节中描述的归并算法就是k=2时的情况。修改图2-31中的程序，使其成为k=3情况下的多路归并排序程序。

4. * 重写归并排序程序，使用2.2节习题7中的lt和key函数，以比较任意类型的元素。

5. 将函数merge、split和MakeList分别与图2-21联系起来。这些函数合适的大小各为多少？

2.9　证明递归程序的属性

如果想证明某个递归函数的某个特定属性，通常需要证明关于调用一次该函数的效果的命题。例如，这种效果可能是参数和返回值之间的关系，比如“调用函数，参数为i，返回i !”。我们经常要为函数的参数定义“大小”的概念，并通过对这个大小的归纳进行证明。可以用很多方式定义参数大小，其中包括如下内容。

1. 某个参数的值。比如，在图2-19的阶乘递归程序中，合适的参数大小就是参数n 的值。

2. 某个参数指向的表的长度。图2-27所示的split递归函数就是个例子，合适的参数大小是表的长度。

3. 参数构成的某些函数。例如，前面提到过，图2-22中递归的选择排序会对数组中有待排序的元素数目进行归纳。对参数n 和i 来说，该函数就是n-i+1。再比如，图2-24中merge函数合适的参数大小就是两个参数指向的表的长度之和。

不管选择了什么样的参数大小，关键是，在函数被调用时，如果参数的大小为s，那么只能以大小为s-1或更小的参数执行函数调用。这样我们可以对参数大小进行归纳，从而证明程序的属性。此外，当这个大小下降到某个固定的值（例如0）时，该函数一定不会再进行递归调用了，因而我们可以由依据情况开始进行归纳证明了。

示例 2.26

考虑2.7节图2-19中的阶乘程序。通过对i的归纳，证明对i≥1，有如下命题为真。

命题 S(i )。在调用fact时如果参数n的值为i，那么fact会返回i !。

依据。对i=1，图2-19中第(1)行的测试会使作为依据的第(2)行被执行，结果返回值为1，也就是1!。

归纳。假设S(i)为真，也就是说，在调用fact时，如果参数为某个值不小于1的i，那么它会返回i!。现在，考虑在调用fact时，变量n的值为i+1的情况。如果i≥1，那么i+1至少等于2，所以第(3)行的归纳情况是适用的，因此返回值就是n×fact(n-1)。或者有，因为变量n的值为i+1，返回的结果是(i+1)×fact(i )。由归纳假设，fact(i)返回了i !。因为有（i+1）×i !=(i+1)!，所以证明了归纳步骤，也就是参数为i+1的fact函数会返回(i+1)!。

示例 2.27

现在，我们来看看2.8节图2-31a中的辅助例程——MakeList函数。该函数会创建一个用来存放输入元素的链表，并返回指向该链表的指针。我们要对输入序列中元素的数目n进行归纳，证明对n≥0，有以下命题为真。

命题 S(n)。若输入序列为x1、x2、…、xn则MakeList会创建一个含有x1、x2、…、xn的链表，并返回指向该链表的指针。

依据。依据为n=0，也就是，当输入序列为空时的情况。第(3)行中MakeList函数对EOF的测试会导致返回值被置为NULL。因此，MakeList正确地返回了空链表。

归纳。假设对n≥0，有S(n)为真，并考虑对有n+1个元素的序列调用MakeList时会发生的情况。假设我们刚读取了第一个元素x1。

MakeList的第(4)行会创建指向新单元c的指针。由归纳假设，第(5)行会递归调用Makelist创建一个指针，指向存放其余n个元素x2、x3、…、xn+1的链表。该指针在第(5)行会被装入c 的next字段。第(6)行则会将x1装入c 的element字段。第(7)行会返回第(4)行所创建的指针。该指针指向存放x1、x2、…、xn+1这n+1个输入元素的链表。

这样就证明了归纳步骤，并得出MakeList能正确处理所有输入的结论。

示例 2.28

在最后一个示例中，要证明图2-29中归并排序程序的正确性，其中假设split和merge函数分别能正确执行它们的任务。我们要对作为MergeSort函数的参数的表的长度进行归纳。要通过对不小于0的n进行完全归纳来证明的命题如下。

命题 S(n)。如果list是MergeSort被调用时长度为n 的表，那么MergeSort将返回具有相同元素的已排序表。

依据。要使用S(0)和S(1)作为依据。当list的长度为0时，它的值为NULL，因此图2-29中第(1)行的测试会成功，而整个函数会直接返回NULL。同样，如果list的长度是1，第(2)行的测试会成功，函数就会直接返回list。因此，MergeSort函数在n 等于0或1时会返回list。这一结果证明了S(0)和S(1)，因为长度为0或1的表本来就是已排序的。

归纳。假设n≥1，而且对所有的i=0、1、…n，都有S(i )为真。我们必须要证明S(n+1)为真。因此，要考虑长度为n+1的表。因为n≥1，所以表的长度至少为2，这样就到达了图2-29中的第(3)行。在那里，如果表的长度n+1为偶数，split就会把该表分为两个长度都为(n+1)/2的表，否则如果n+1为奇数，就分为长度分别为(n/2)+1和n/2的两个表。因为n≥1，所以这些表的长度不可能达到n+1。这样的话，归纳假设适用于它们，我们就可以由此得出结论，通过对第(4)行的递归调用，正确地对长度减半的表进行了排序。我们已假设merge是能正确工作的，所以返回的表也是已排序的。

秦皇岛申请400电话费用【秦皇岛企业全国热线电话办理】秦皇岛开通400电话电信价格、秦皇岛微信公众号代运营外包托管、秦皇岛网店编辑装修美工、秦皇岛网站推广优化大概需要多少钱

上往建站提供搭建网站，域名注册，官网备案服务，网店详情页设计，企业网店，专业网络店铺管理运营全托管公司咨询电话，服务器空间，微信公众号托管，网页美工排版,致力于域名申请，竞价托管，软文推广，全网营销,提供标准级专业技术保障，了却后顾之忧,主营：虚拟主机，网站推广，百度竞价托管，网站建设，上网建站推广服务，网络公司有哪些等业务，专业团队服务，效果好。

服务热线：400-111-6878 手机微信同号:18118153152（各城市商务人员可上门服务）