信息学竞赛宝典 数据结构基础

版权信息

书名：信息学竞赛宝典　数据结构基础

ISBN：978-7-115-63502-0

本书由人民邮电出版社发行数字版。版权所有，侵权必究。

您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。

我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。

如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。

版　　权

编  著 张新华　梁靖韵　刘树明

责任编辑 赵祥妮

人民邮电出版社出版发行　　北京市丰台区成寿寺路11号

邮编　100164 　电子邮件　315@ptpress.com.cn

网址　http://www.ptpress.com.cn

读者服务热线：(010)81055410

反盗版热线：(010)81055315

内 容 提 要

数据结构是计算机存储、组织数据的方式，往往同高效的检索算法和索引技术有关。学习和掌握数据结构的相关知识，使我们能够更好地运用计算机来解决实际问题。

为了提高读者的学习效率，本书直接从各类竞赛真题入手，以精练而准确的语言、全面细致地介绍了信息学竞赛中经常用到的数据结构类型，包括链表、堆栈、队列、树、图等。本书精挑细选、由浅入深地安排了相关习题。考虑读者接受水平的差异，一般在引入新知识点的题目时，本书会提供该题目的完整参考代码，但随着读者对此知识点的理解逐步加深，后续的同类型题目将逐步向仅提供算法思路、提供伪代码和无任何提示的方式转变。此外，对于一些思维跨度较大的题目，本书会酌情给予读者一定的提示。

本书可以与《信息学竞赛宝典　基础算法》同步学习，也可以作为有一定编程基础的读者学习数据结构算法的独立用书。

前  言

编程竞赛介绍

随着计算机逐步深入人们生活的各个方面，利用计算机及其程序设计来分析、解决问题的算法在计算机科学乃至整个科学界的作用日益明显。相应地，各类以算法为主的编程竞赛也层出不穷：在国内，有全国青少年信息学奥林匹克联赛（National Olympiad in Informatics in Provinces，NOIP），该联赛与全国中学生生物学联赛、全国中学生物理竞赛、全国高中数学联赛、全国高中学生化学竞赛对高中生而言是含金量最高的竞赛；在国际上，有面向中学生的国际信息学奥林匹克竞赛（International Olympiad in Informatics，IOI）、面向亚太地区在校中学生的信息学科竞赛即亚洲与太平洋地区信息学奥林匹克（Asia-Pacific Informatics Olympiad，APIO），以及由国际计算机学会（Association for Computing Machinery，ACM）主办的面向大学生的国际大学生程序设计竞赛（International Collegiate Programming Contest，ICPC）等。

因为各类编程竞赛要求参赛选手不仅要有深厚的计算机算法功底、快速并准确编程的能力和创造性的思维，而且要有团队合作精神和抗压能力，所以编程竞赛逐渐得到高校、IT公司和其他社会团体的认同和重视。编程竞赛的优胜者更是Microsoft、Google、百度、Facebook（已更名为Meta）等全球知名IT公司争相高薪招募的对象。因此，除了各类参加编程竞赛的选手，很多不参加此类竞赛的研究人员和从事IT行业的人士，也都希望能得到这方面的专业训练并从中取得一定的收获。

为什么要学习数据结构

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。数据结构是带有结构特性的数据元素的集合，它研究的是数据的逻辑结构、物理结构和它们之间的关系，数据结构会对这些结构定义相适应的运算，设计出相应的算法，确保经过运算以后得到的新结构仍保持原来的结构类型。数据结构往往与高效的检索算法和索引技术有关。

据统计，当今处理非数值计算性问题占用了85%以上的机器时间，这类问题涉及的数据结构更为复杂，数据元素之间的相互关系一般无法用数学方程加以描述。因此，解决这类问题的关键不再是优化数学分析和计算方法，而是要设计出合适的数据结构。通常情况下，精心设计的数据结构可以带来更高的运行效率或者存储效率。

数据结构是计算机科学与技术、计算机信息管理等专业的基础课程，是十分重要的核心课程。所有的计算机系统软件和应用软件都要用到各种类型的数据结构，学习和掌握数据结构的相关知识，使我们能够更好地运用计算机来解决实际问题。可以说，数据结构是计算机学科知识结构的核心和技术体系的基石。

本书的特色及用法

本书包含了NOIP中常用的数据结构类型，如堆栈、队列、树、图等，适用于NOIP级别的竞赛选手学习。

为了提高读者的学习效率，本书直接以各类竞赛真题入手，以精练而准确的语言，全面、细致地介绍编程竞赛中常用的数据结构类型。考虑读者接受水平的差异，一般在引入包含新知识点的题目时，本书会提供该题目的完整参考代码以供读者参考，但随着读者对知识点的理解逐步加深，后续的同类型题目将逐步向仅提供思路、提供伪代码和无任何提示的方式转变。此外，对于一些思维跨度较大的题目，本书会酌情给予读者一定的提示。

本书的内容是按照难易程度划分的，但是并不建议读者严格按照本书既有的顺序逐步学习，因为这很容易导致学到后面的内容时，就忘了前面学习过的内容。一个比较好的学习建议是，读者在掌握某个章、节的大部分内容后，可以先学习后面章、节的内容，剩下的部分和没有做过的较难的题目，可以在后面的复习巩固中完成。

本书的配套资源

本书精心安排了由浅入深的相关例题与习题，让读者能进一步掌握数据结构相关知识。对于例题，本书给出了详细的算法分析和参考代码，题目对应的数字（如402001）为配套题库网站中的题目编号，网址为www.magicoj.com，读者可在该网站通过题目编号查找对应题目并进行在线评测。因篇幅所限，对于习题，本书仅提供配套题库网站的题目编号，请读者到配套题库网站上完成习题。

本书有配套的源代码、课件，读者可登录“异步社区”网站搜索本书，在本书的页面中进行相关资源的下载。

适合阅读本书的读者

本书可以作为本系列书的读者后续的学习教材，也可以作为有一定编程基础的读者学习数据结构的参考用书。

本书可作为NOIP的复赛教材和ICPC的参考与学习用书，还可作为计算机专业的学生、IT工程师、科研人员、算法爱好者的参考和学习用书。

致谢

感谢全国各中学、大学的信息学奥赛指导教师们，他们对本书的编写提出了许多真诚而有益的建议，并对笔者在写书过程中遇到的一些困惑和问题给予了热心的解答。

本书使用了NOIP的部分原题、在线评测网站的部分题目，并参考和收集了其他创作者发表在互联网、杂志等媒体上的相关资料，无法一一列举，在此对相关人员一并表示衷心的感谢。

感谢卷积文化传媒（北京）有限公司的CEO高博先生和他的同事。

最后要说的话

由于笔者水平所限，书中难免存在不妥之处，欢迎读者赐正。读者如果在阅读过程中发现任何问题，请发送电子邮件到hiapollo@sohu.com，希望读者能对本书提出建设性意见，以便重印时改进。

希望本书的出版，能够给学有余力的中学生、计算机专业的大学生、程序算法爱好者和IT从业者提供一些新思路。

广州市第六中学强基计划基地教材编委会

2024年1月

第1章　链表

1.1　何谓链表

我们知道，数组一般需要先定义长度（事先预估数组元素个数），但这在解决某些问题时并不是特别适用。例如，记录不同学校的学生时，由于各校人数不同，开辟过大的数组会导致存储空间浪费，开辟过小的数组会导致数组元素不够用。

链表可以根据需要动态开辟内存单元，是一种常见的重要数据结构。图1.1所示为最简单的一种链表。

图1.1

链表如同铁链，一环扣一环，中间是不能断开的。例如，幼儿园教师带领小朋友出来散步，教师牵着第一个小朋友的手，第一个小朋友牵着第二个小朋友的手……最后一个小朋友的一只手是空的，这就是一个“链”。

教师即“头指针”变量，即图1.1中的“Head”，它用于存放一个地址。链表中的每一个元素被称为一个“节点”，每个节点都包含两部分：一部分是存储数据元素的数据域，另一部分是存储下一个节点地址的指针域。

最后一个元素的指针域不指向其他节点，它被称为“表尾”，以“NULL”表示。“NULL”在C++里指向“空地址”。

显然，链表使用结构体和指针变量实现是十分合适的。

由于NOIP已允许使用C++的STL（Standard Template Library，标准模板库），因此本书中许多数据结构的实现都可以使用STL轻松实现，例如队列可以使用STL的queue实现，堆栈可以使用STL的stack实现……此外，使用效率更高的数组仿真也是不错的选择。对学习时间不充裕的读者来说，本章的链表内容可以略过不看，但如果想要对数据结构有更深刻的理解以应对更高层次的挑战，建议读者还是认认真真把基础夯实。

1.2　简单静态链表

下面的代码实现的是一个简单静态链表，它由3个存储学生数据（学号、成绩）的节点组成。请考虑：（1）head的作用；（2）p的作用。

 1    // 简单静态链表
 2    #include <bits/stdc++.h>
 3    using namespace std;
 4    
 5    struct  student
 6    {
 7      long num;                      //学号
 8      float score;                    //成绩
 9      struct student *next;          //该指针指向student类型的结构体
10    };                               //注意必须有分号
11    
12    int main()
13    {
14      struct student a,b,c;
15      a.num=34341;                   //a学生赋值
16      a.score=81.5;
17      b.num=34343;                   //b学生赋值
18      b.score=97;
19      c.num=34344; //c学生赋值
20      c.score=82;
21      struct student *head=&a;       //head指向a的地址
22      a.next=&b;                     //将b的地址赋给a.next，即连接下一结构体元素
23      b.next=&c;
24      c.next=NULL;                   //最后一个元素指向空地址
25      struct student *p=head;        //定义指针变量p指向head
26      do                             //输出记录
27      {
28        cout<<p->num<<" "<<p->score<<endl;
29        p=p->next;                   //p指向下一节点
30      } while(p!=NULL);
31      return 0;
32    }

head是“头指针”变量，指向链表中的第一个节点地址，这相当于“幼儿园教师”拉着第一个“小朋友”的手。输出链表中每个节点的值相当于登记小朋友的名字，但是这件事教师是不适合亲自做的，因为她必须时刻拉着小朋友的手，否则小朋友就有可能会跑得找不到人影（链表地址丢失）。p是教师的“助手”，所以由p从教师的位置开始向后一步步移动以登记小朋友的名字。

1.3　动态链表

完善的动态链表程序通常具有以下基本功能：建立链表、插入节点、删除节点、输出链表、释放链表等。随后的代码将依次实现这些功能。

为了程序的易读性和可扩展性，可以在程序开头先进行预定义处理。请务必领会下面的代码含义，否则将影响对后续代码的理解。

 1    #include <bits/stdc++.h>
 2    using namespace std;
 3    
 4    //typedef用于为复杂的声明定义简单的别名
 5    typedef struct List *Link;                     //Link代表链表指针
 6    typedef struct List Lnode;                     //Lnode代表链表节点
 7    
 8    struct List
 9    {
10      int data;                                   //此处仅以一个整型变量为例
11      struct List *next;
12    };

1.3.1　链表的建立

建立链表之前，Head指向NULL。链表建好后，每次新建一个节点连接到链表时，首先使NewPoint（新建节点）的指针域指向Head指向的地址，再将Head指向NewPoint的地址，如图1.2所示。

图1.2

链表建立函数应该返回节点指针，其输入参数也应该是节点指针，参考代码如下。其中第6行的关键字new表示要在内存中开辟一个新的空间，该空间用于保存NewPoint。

 1    Link Create(Link Head)                         //建立链表
 2    {
 3      int newData;
 4      while(1)
 5      {
 6        Link NewPoint=new Lnode;//开辟空间保存NewPoint，如果失败，NewPoint=NULL
 7        printf("输入链表元素: 结束输入'-1'\n");
 8        scanf("%d",&newData);
 9        if (newData==-1)                           //如果输入-1，则创建完毕
10          return Head;                             //返回Head
11        NewPoint->data=newData;                    //赋值给节点
12        NewPoint->next=Head;                       //NewPoint连接到链表头
13        Head=NewPoint;                             //更新Head，即指向NewPoint
14      }
15    }

1.3.2　链表的显示

链表显示函数Display()无返回值，其输入参数为链表的头指针，参考代码如下。

 1    void Display(Link Head)                 //显示链表节点元素
 2    {
 3      Link p=Head;                          //由指针p代替Head来完成扫描任务
 4      if(p==NULL)
 5        printf("\n链表为空\n");
 6      else
 7        while(p!=NULL)
 8        {
 9          printf("%d ",p->data);            //输出指针指向地址的值
10          p=p->next;                        //指针移到下一个节点
11        }
12      printf("\n");
13    }

1.3.3　查找节点元素x的位置

函数Locate()用于查找节点元素x在链表中的位置，参考代码如下。

 1    int Locate(Link Head,int x)                //查找节点元素x在链表中的位置
 2    {
 3      int n=0;
 4      Link p=Head;                             //由指针p代替Head来完成扫描任务
 5      while(p!=NULL && p->data !=x)
 6      {
 7        p=p->next;
 8        n++;
 9      }
10      return p==NULL? -1: n+1;
11    }

1.3.4　返回链表的长度

函数Lenth()用于返回链表的长度，参考代码如下。

 1    int Lenth(Link Head)                    //返回链表长度
 2    {
 3      int len=0;
 4      Link p=Head; //由指针p代替Head来完成扫描任务
 5      while(p!=NULL)
 6      {
 7        len++;
 8        p=p->next;
 9      }
10      return len;
11    }

1.3.5　获得节点元素值

函数Get()用于获得链表中第i个位置的节点元素值，参考代码如下。

 1    int Get(Link Head,int i)                     //获得第i个位置的节点元素值
 2    {
 3      int j=1;                                   //定义j为计数器
 4      Link p=Head;
 5      while(j<i && p!=NULL)                      //直到找到第i个位置的节点元素值
 6      {
 7        p=p->next;
 8        j++;
 9      }
10      if(p!=NULL)
11        return(p->data);
12      else
13        printf("输入数据错误!");
14      return -1;
15    }

1.3.6　节点的插入

函数Insert()用于将节点x插入链表的第i个位置，参考代码如下。

 1    Link Insert(Link Head,int x,int i)      //插入节点x到第i个位置 
 2    {
 3      Link NewPoint=new Lnode;              //新建节点，new用于动态开辟内存空间
 4      NewPoint->data=x;                     //为节点赋值
 5      if(i==1)                              //如果插入位置为第一个节点位置
 6      {
 7        NewPoint->next=Head;
 8        Head=NewPoint;
 9      }
10      else
11      {
12        int j=1;
13        Link p=Head;
14        while(j<i-1 && p->next!=NULL)       //找到i-1处
15        {
16          p=p->next;
17          j++;
18        }
19        if(j==i-1)
20        {
21          NewPoint->next=p->next;
22          p->next=NewPoint;
23        }
24        else  printf("插入节点失败，输入的值错误!");
25      }
26      return Head;
27    }

1.3.7　节点的删除

因为链表中唯一能够找到节点的办法是使用上一个节点的指针，所以如果我们将某个节点直接删去，这个节点所指向的节点和它之后的所有节点都没有办法再找到了。为了解决这个问题，一般采取这样的方法：记录下要删除的节点之前的那个节点，在删除节点之前，把这个节点的指针指向要删除的那个节点的指针指向的节点。比如现在要删除图1.3所示链表中的节点t，先找到它之前的节点p，在删除t之前将p的指针指向节点c，然后删除t，这样在删除t之前，就已经把t从链表中剔除出来了，不会影响之后的节点。

图1.3

参考代码如下，其中第7行，表示将括号内指针指向的内存空间释放。记住，用new动态开辟的内存空间，一定要用delete()释放；否则，即便程序运行结束，这部分内存空间仍然不会被操作系统回收，从而成为被白白浪费掉的“内存垃圾”，这种现象称为“内存泄漏”。

 1    Link Del(Link Head,int i)                        //删除i位置上的节点
 2    {
 3      Link p=Head,t;
 4      if(i==1)                                       //如果是第一个节点
 5      {
 6        Head=Head->next;
 7        delete(p);                                   //删除Head指向的节点
 8      }
 9      else
10      {
11        int j=1;                                     //j为计数器
12        while(j<i-1 && p->next !=NULL)               //找到删除的前一个位置
13        {
14          p=p->next;
15          j++;
16        }
17        if(p->next!=NULL && j==i-1)
18        {
19          t=p->next;
20          p->next=t->next;
21        }
22        if(t!=NULL)
23          delete(t);                                 //释放节点内存空间
24      }
25      return Head;
26    }

1.3.8　释放链表

函数SetNull()用于将Head指向的链表中的全部节点从内存中释放，参考代码如下。

 1    Link SetNull(Link Head)                                   //释放链表
 2    {
 3      Link p=Head;
 4      while(p!=NULL)                                          //逐个节点释放
 5      {
 6        p=p->next;
 7        delete(Head);
 8        Head=p;
 9      }
10      return Head;
11    }

完整的链表演示程序读者可在下载资源的代码中查看，文件保存在“第1章　链表”文件夹中，文件名为“完整链表”。

1.4　数组与链表的比较

一个常见的编程问题：遍历同样大小的数组和链表，哪个比较快？如果按照某些教科书上的分析方法，两者一样快，因为时间复杂度都是 O(n)，但其实遍历数组比遍历链表要快很多。

首先介绍一个概念：存储器层次（memory hierarchy）。计算机中存在多种不同的存储器，各存储器的平均存取速度相差很大，如表1.1所示。

表1.1

各存储器的平均存取速度差异非常大，CPU寄存器的平均存取速度是内存的平均存取速度的大约100倍！这就是为什么CPU生产厂家发明了CPU缓存，而CPU缓存就是数组和链表的关键区别所在。

CPU缓存会把一个连续的内存空间读入，因为数组结构是连续的内存地址，所以数组的全部或者部分元素被连续保存在CPU缓存中，平均读取每个元素只要3个CPU时钟周期。而链表的节点是分散在堆空间里面的，读取的时候CPU缓存帮不上忙，只能去读取内存，平均读取时间为100个CPU时钟周期。这样算下来，遍历数组的速度比遍历链表的速度快大约33倍！（以上皆为理论数字，具体的数字因CPU型号及环境不同而略有差异）。

因此，程序中尽量使用连续的数据结构，这样可以充分发挥CPU缓存的优势。对缓存友好的算法称为 Cache- oblivious algorithm，有兴趣的读者可以参考相关资料。再举一个简单的例子，程序如下。

//程序1
for(int i=0;i<N;i++)
 for(int j=0;j<N;j++)
   for(int k=0;k<100;k++)
     //b[k][j]为非逐行连续读取
     c[i]+=a[k]*b[k][j]; 

//程序2
for(int i=0;i<N;i++)
  for(int k=0;k<100;k++)
    for(int j=0;j<N;j++)
       //b[k][j]为逐行连续读取
       c[i]+=a[k]*b[k][j]; 

两个程序的执行结果一样，算法复杂度也一样，但是程序2的执行速度要快很多，因为C++的数组是按行存储的。

1.5　课后练习

1．猴子选大王（网站题目编号：401001）

2．试用单链表编写学生成绩管理系统

该系统具有添加学生记录、显示全部学生记录、按座位号删除学生记录、按座位号修改学生成绩等功能。数据格式大致如表1.2所示。

表1.2