数据结构之线性表——软件测试工程师面试秘籍

lsekfe

　本章对大量企业的软件测试工程师岗位的笔试题和面试题进行分析，按照对软件测试工程师岗位要求的技术难度，对数据结构、操作系统、数据库、网络、设计模式、Java、C++、C#与.NET等基础知识进行总结。
　　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），直到到达链表结尾。