线性表的论述（Java版）
- 1. 基础知识摘要
-
- 1.1 线性表的定义：
- 1.2 前驱和后继：
- 1.3 开始结点和终端结点：
- 1.4 特点：
- 1.5 顺序存储的线性表：
- 1.6 顺序表的插入、删除和按值查找操作的实现方法及性能 :
- 单链表的图形结构：
-
-
- 顺序表上的插入操作 insert ( i , x )
- 插入的图形操作：
- 插入Java代码如下：
- 顺序表上的删除操作 remove( i )
- 顺序表上的按值查找操作 indexOf ( x )
-
- 1.7 循环链表
-
- 循环单链表：
-
- 循环单列表存在优点：
-
-
- 列如，现将两个带尾指针循环列表this和 list 合并为 this。
-
- 1.8 双向链表
-
- 双向链表的图形结构：
- 双向链表的插入的图形结构：
1. 基础知识摘要
1.1 线性表的定义：
线性表是由n ( n >= 0 )个数据元素构成的有序数列。
下标 i 标识数据元素在线性表中的位序号，n为线性表的表长，当 n=0 时，此线性表时空表 。
1.2 前驱和后继：
a< i -1 >就是a < i > 的前驱，反之则为后继。
1.3 开始结点和终端结点：
线性表中没有前驱的数据元素称为开始结点，没有后继的数据元素称为终端结点。
1.4 特点：
- 数据元素具有相同的数据类型。
- 有且只有一个开始结点和终端结点。
- 除开始结点和终端结点外，其余结点有且只有一个前驱和一个后继。
1.5 顺序存储的线性表：
顺序存储的线性表称为顺序表。它是用一组地址连续的存储单元依次存放线性表中的各个数据元素，从而使线性表在逻辑上相邻的数据元素，在物理存储位置上也是相邻的。
顺序表的主要优点使存储密度高，节省存储空间，且读取顺序表中的数据元素非常便利。
【补充】：
存储密度：（结点数据本身所占的存储量）/ （结点结构所占的存储总量）
1.6 顺序表的插入、删除和按值查找操作的实现方法及性能 :
单链表的图形结构：
顺序表上的插入操作 insert ( i , x )
做法：
- 检查 i 的合法性。
- 将插入位置及其之后的所有元素后移一个存储位置
- 将 x 插入到第 i 个位置
- 将表长值加 1
插入的图形操作：
插入Java代码如下：
public void Insert(Node n) {
Node p = head;
if (p.next == null) { //只存在头结点
n.next = p.next;
p.next = n; //插入结点
} else {
//假设为data为int类型
while ((int) p.next.data <= (int) n.data) {
if (p.next.next != null) {
p = p.next;
} else {
n.next = p.next.next;
p.next.next = n; //插入结点n
break;
}
}
}
}
最好情况： 在表尾插入，不会引起数据元素的移动，时间复杂度为 O(1)
最坏情况： 在表头插入, 会引起n个数据元素的移动，时间复杂度为 O(n)
平均情况： 在等概率条件下，数据元素的平均移动次数为 n/2,时间复杂度为 O(n)
顺序表上的删除操作 remove( i )
做法：
- 检查 i 的合法性
- 将第 i 个位置之后的所有数据元素均向前移动一个存储位置
- 将表长减 1
最好情况: 删除表尾元素，不会引起数据元素的移动，时间复杂度为 O(1)
最坏情况：删除表头元素， 会引起 n - 1 个数据元素向前移动，时间复杂度为 O(n)
平均情况：在等概率条件下， 数据元素的平均移动次数为 (n - 1) / 2 , 时间复杂度为 O(n)
顺序表上的按值查找操作 indexOf ( x )
查找的主要操作就是比较。从表头到表尾或从表尾到表头对各个数据元素进行依次比较。
比较的次数与 x 在表中的位置和表长有关。
例如，若查询表中第 i 个位置上的数据元素值为 x ，则需要比较 x + 1 次。
最好情况： 查找的元素在表头，时间复杂度为 O(1)
最坏情况： 查找的元素在表尾， 时间复杂度为 O(n)
平均情况： 在等概率条件下，数据元素的平均比较次数为 （n+1）/2,时间复杂度为 O(n)
【例 1.1】要将一个顺序表{a0,a1…,an-1}中的第i个数据元素ai(0<=i<=n-1)删除，需要移动( n-i-1 )个数据元素。
【例 1.2】要在一个顺序表{a0,a1…,an-1}中的第i(0<=i<=n-1)个位置之前插入一个新的数据元素，需要移动( n-i )个数据元素。
【例 1.3】将长度为n的单链表链接在长度为m的单链表后面，其算法的时间复杂度为（ O（m））
1.7 循环链表
循环单链表：
通俗来说，循环单列表就是将尾结点指向头结点，我们一般还会使用一个尾指针。
循环单列表存在优点：
列如，现将两个带尾指针循环列表this和 list 合并为 this。
答：
我们可以直接根据表尾指针就可找到每个需要修改的指针域的地址，算法时间复杂度和两个链表的长度都无关，因此时间复杂度为O（1）。
循环单链表除此之外，其他操作几乎与单链表的操作相同。
1.8 双向链表
双向链表存在前驱指针域、数据域和后继指针域。
双向链表的图形结构：
双向链表的插入的图形结构：
双向链表的删除可以结合图理解。
