数据结构之线性表——软件测试工程师面试秘籍
本章对大量企业的软件测试工程师岗位的笔试题和面试题进行分析，按照对软件测试工程师岗位要求的技术难度，对数据结构、操作系统、数据库、网络、设计模式、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），直到到达链表结尾。
页:
[1]
