建行个人网站济南网站制作 泉诺
目录
一.线性表的概念
二.线性表的关系及分类
三.数组与顺序表
四.链表
1.静态链表(链表的的数组底层实现）
2.循环链表
3.双向链表
五.栈
1.栈的概念
2.栈的底层实现
3.共享空间栈
4.逆波兰表达式（后缀表达式）
5.栈与递归
六.队列
1.队列概念
2.队列的底层实现
3.循环队列
七.链式储存与顺序储存
一.线性表的概念
线性表是0个或n个相同数据类型的有限序列
构成线性表的条件：除了头尾外每个结点有且仅有一个前驱和后继。
二.线性表的关系及分类
线性表按物理存储结构可分为顺序存储结构和链式存储结构。
基本顺序存储结构为数组，基本链式存储结构为链表。
以数组为底层可实现顺序表和栈及队列。
以链表为底层可实现栈和队列。
其关系图大致如下：
三.数组与顺序表
封装顺序表的使用：
定义
List<类型参数> 顺序表名 = new ArrayList<>();
ArrayList<类型参数> 顺序表名 = new ArrayList<>();
【ArrayList实现了List接口】
顺序表的底层实现：
底层是对数组的处理较简单
顺序表底层需要实现的一般方法:
(其余可自行到库中查看）
四.链表
链表的一般底层实现：
通过内部类定义结点与C语言中结构体类似
要实现的一般方法有：
1.静态链表(链表的的数组底层实现）
静态链表的实现的每一个结点需要值域和游标（游标用来存储下一节点的下标） 
2.循环链表
链表的尾部指针域指向头结点
3.双向链表
在单向链表的属性中多了一个指向前一个结点的“指针”.
五.栈
1.栈的概念
只在表首进行删除和插入操作的线性表
2.栈的底层实现
数组实现：
需要一top变量指示栈顶下标（栈空为-1，栈满为n)
大致框架如下，方法（push,pop,peek,empty等可参考库函数尝试实现)
链表实现：
以“头指针”指示栈顶，对头指针及其前一个结点进行操作即可实现栈的基本方法
基本结构如下：
3.共享空间栈
用于底层为数组实现的栈节省空间，两栈合并。
结构大致如下：
可定义top1,top2分别表示两栈顶当两栈顶相遇（top1+1=top2)时栈满。
当top1 = -1且top2 = n时栈空（n为栈大小）。
4.逆波兰表达式（后缀表达式）
中缀转后缀：
一种较容易推导方法为加括号，通过栈推导可自行查资料
5.栈与递归
递归的底层可以理解为一个栈，每次递归时所得数据存储在栈中直到递归出口再将数据依次弹出
六.队列
1.队列概念
只在头部进行删除尾部进行插入的线性表 （先进先出）
2.队列的底层实现
数组实现：
与栈相似多出一个属性指示队尾，对队首队尾进行操作
链表实现：
单向链表实现时与栈相似都是对头指针进行操作，只是加入删除元素的方式有所不同
双向链表实现队列较为快捷可同时对头尾指针进行操作。
3.循环队列
以数组为底层实现循环队列时防止假满状态（队尾元素删除后其空间无法利用，头指针一直向前走无法回头）实现空间重复利用。定义front rear指示队列首尾部
循环队列大小计算公式：
ret = (front - rear + maxSize) % maxSize
循环队列循环的实现：
添加删除元素时分别对尾头指针进行操作；
添加移动尾的下标：
(rear + 1) % maxSize
删除移动头的下标：
（front + 1) % maxSize
循环队列满空的判断：
空时front = rear
满时判断：
1.标记法
flag=false 时为空
flag=true时为满
2.留空法
留下一个位置不放元素
当(rear + 1) % maxSize = front 时为满
通过以上操作我们可以发现下标只在（0 ~ maxSize - 1)范围内变化，从而实现循环
4.双向队列
可在两边同时进出的队列
七.链式储存与顺序储存
顺序存储结构如数组及以其为底层实现的结构：
1.空间大小确定
2.如需查找，时间复杂度仅为O(1)较易进行
3.插入操作需移动插入位置后所有元素，时间复杂度为O(n),不便
链式存储结构如链表及以其为底层实现的结构：
1.大小不固定
2.只可按一定顺序进行查找O(n)不便
3.插入时找指定元素时O(n)插入时O(1),插入愈多其优势越明显
故选用结构时需据实际情况。