JAVA与数据结构-线性表

目录

一.线性表的概念

二.线性表的关系及分类

三.数组与顺序表

四.链表

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),插入愈多其优势越明显

故选用结构时需据实际情况。