第2章 磨刀霍霍，有备无患
2.1 数据结构
数据结构是历年来笔试和面试的重点之一，针对它至少会有两三道大题。
数据结构包括线性结构和非线性结构两种。线性结构中的线性表、栈、队列、串和非线性结构中的二叉树是高频考点。本节总结需要熟练掌握的考点，并提供数据结构方面的大量面试题、解题思路。
2.1.1 线性表
考点：
线性表的两种存储结构及其特点
链表基本操作：新增节点、删除节点
链表逆序等算法
线性表分两种存储结构，即顺序存储结构（主要代表为顺序表）和链式存储结构（主要代表为链表），分别如图2.1和图2.2所示。
图2.1 线性表的顺序存储结构
在图2.1中，n表示线性表的长度，ai表示数据元素，i表示数据元素ai在线性表中的位序。
顺序存储结构的特点如下。
（1）前后两个节点的存储空间是紧邻的。
（2）空间利用率高，但实现时要预估容量。
（3）查找操作的时间复杂度为O(n)，读取操作的时间复杂度为O(1)。
（4）新增节点需要移动n-i+1个节点，删除节点需要移动n-i个节点。
链式存储结构的特点如下。
（1）存储空间可以连续，也可以不连续。
（2）为了存放后续节点的地址，需要动态申请空间。
（3）查找操作的时间复杂度为O(n)，读取操作的时间复杂度为O(n)。
（4）新增和删除操作简单，仅需变化两次指针。
图2.2 线性表的链式存储结构
链表中新增节点的过程如下。
（1）新增节点指向下一节点。
（2）上一节点指向新增节点。
新增节点的过程如图2.3所示。
链表中删除节点的过程就是从上一节点指向下一节点。此过程较简单，故不画示意图。
顺序表的逆序过程如图2.4所示。
图2.3 新增节点的过程
图2.4 顺序表的逆序过程
链表的逆序过程如下。
（1）设置3个辅助指针，分别指向前3个节点。
（2）反转前2个指针指向的节点。
（3）3个辅助指针后移两个位置，循环执行步骤（2），直到到达链表结尾。
查看《软件测试工程师面试秘籍》全部连载章节
版权声明：51Testing软件测试网获得人民邮电出版社和作者授权连载本书部分章节。
任何个人或单位未获得明确的书面许可，不得对本文内容复制、转载或进行镜像，否则将追究法律责任。
