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