导图社区 第二章 线性表
数据结构线性表部分知识总结，线性表是一种最基本的数据结构，它是具有相同数据类型的n（n≥0）个数据元素的有限序列。
这是一篇关于第七部分 新一代交换控制技术的思维导图，梳理了新一代交换控制技术中的NGN和SDN相关知识，有助于理解这两种技术的架构、原理和关键技术。
数据结构考研复习王道课本线性表总结，包含线性表的定义和基本操作、顺序存储、链式存储等，总结全面细致，适合做为复习资料。
社区模板帮助中心，点此进入>>
互联网9大思维
组织架构-单商户商城webAPP 思维导图。
域控上线
python思维导图
css
CSS
计算机操作系统思维导图
计算机组成原理
IMX6UL(A7)
考试学情分析系统
第二章 线性表
线性表是逻辑结构，顺序表和链表是存储结构
线性表的定义和基本操作
定义
相同数据类型的n个数据元素的有限序列
逻辑特性
直接前驱，直接后驱
特点（针对表中元素）
个数有限
逻辑上有顺序，元素有先后
元素数据类型都相同，占据存储空间一样
元素都是单个的数据元素
具有抽象性，不考虑元素表示的内容
顺序存储
顺序表
顺序表的定义
线性表的顺序存储
分配内存的方式
静态分配
动态分配
一旦数据空间占满，另外开辟一段更大的连续存储空间，将原表达元素全部拷贝到新空间
特点
元素的逻辑顺序和存储顺序相同
优点
可随机访问
存储密度高
缺点
插入删除移动大量元素
分配需要一段连续的存储空间
基本操作
初始化
插入
O(n)
删除
按值查找
按序号查找
O(1)
顺序存储的特点
数据元素按照顺序放在连续的存储单元中，适用于线性结构，也可用于非线性结构
链式存储
链表
单链表
线性表的链式存储，每个节点放元素自身信息和指向直接后继的指针
存储结构
非随机存取
头结点和头指针
头指针始终指向第一个结点，头结点可以作为链表的第一个结点，节点内无元素的数据，只有指向后继的指针信息
引入头结点的好处
头结点指向的链表的第一个节点无需特殊操作。
空表和非空表处理得到统一（头指针始终不为空）。
求表长
按序号查找结点
建立
头插法
读取数据顺序与链表元素顺序相反
尾插法
顺序相同
双链表
便于访问节点的前驱和后继，适用于插入删除等需要找前驱的操作
多了一个prior前驱域
循环链表
循环单链表
最后一个节点的指针指向头结点
判空条件
头结点的next域等于L
循环双链表
头结点的prior还要指向表尾节点
头结点的prior和next都等于L
静态链表
定义:数组来表述线性表的链式存储结构
节点包含
数据域
数组元素内容
指针域
数组下标，即节点在数组中的相对地址
顺序表和链表的比较
存取 读写方式
可随机存取
从表头开始，依次存取
逻辑结构和物理结构
逻辑物理上都相邻
逻辑相邻，物理不一定
操作
查找
顺序表可按序号随机存取
链式平均为n
删除，插入
n
1
空间分配
静态存储
动态存储
有空间就能分配
