企业官网建设流程全解析

2.1 线性表的基本概念

2.1.1 线性表的定义

• 线性表是具有相同数据类型的 (n) 个数据元素组成的有限序列。

记作：

L=(a_1,a_2,。。。。,a_n)

其中：

• (a_1) 是第一个元素。
• (a_n) 是最后一个元素。
• 当 (n=0) 时，线性表为空表。

2.1.2 线性表的逻辑特征

1. 存在唯一的第一个元素。
2. 存在唯一的最后一个元素。
3. 除第一个元素外，每个元素有且仅有一个直接前驱。
4. 除最后一个元素外，每个元素有且仅有一个直接后继。

2.1.3 线性表的基本操作

本节总结：线性表是一种线性逻辑结构。其核心特征是元素之间存在唯一的前后关系，常见实现方式为顺序存储和链式存储。

2.2 顺序表

2.2.1 顺序表的定义

• 顺序表是使用一组地址连续的存储单元依次存储线性表元素的存储结构。

2.2.2 顺序表的特点

1. 逻辑相邻的元素在物理存储位置上也相邻。
2. 支持通过下标随机访问元素。
3. 插入和删除可能需要移动大量元素。
4. 静态数组的容量通常固定；动态数组可以根据需要扩容。

2.2.3 顺序表的结构示例

//数组通过下标访问元素，通常可以在常数时间内完成。 int[] arr = new int[10]; arr[0] = 10; arr[1] = 20; arr[2] = 30; System.out.println(arr[1]);

2.2.4 顺序表的插入

在长度为 (n) 的顺序表中，于第 (i) 个位置插入元素，需要将原来第 (i) 个及其之后的元素向后移动。

基本步骤：

1. 判断插入位置是否合法。
2. 判断顺序表是否有剩余容量。
3. 将第 (n) 个元素至第 (i) 个元素依次向后移动。
4. 将新元素放入第 (i) 个位置。
5. 更新表长。

• 示例：

int[] arr = {10, 20, 30, 40, 0}; int length = 4; int position = 2; int value = 15; for (int i = length; i > = position; i--) { arr[i] = arr[i - 1]; } arr[position - 1] = value; length++;

插入后有效元素为：

10, 15, 20, 30, 40

2.2.5 顺序表的删除

删除第 (i) 个元素时，需要将该元素之后的所有元素依次向前移动。

基本步骤：

1. 判断删除位置是否合法。
2. 删除目标位置的元素。
3. 将后续元素依次向前移动。
4. 更新表长。

• 示例：

int[] arr = {10, 20, 30, 40, 50}; int length = 5; int position = 3; for (int i = position - 1; i < length - 1; i++) { arr[i] = arr[i + 1]; } length--;

• 删除后有效元素为：

10, 20, 40, 50

2.2.6 顺序表的时间复杂度

本节总结：顺序表最大的优势是随机访问效率高；主要缺点是插入、删除可能引起元素移动，且需要管理存储容量。

2.3 单链表

2.3.1 单链表的定义

单链表通过结点之间的指针连接数据元素，每个结点包含数据域和指针域。

class Node { int data; Node next; Node(int data) { this.data = data; } }

其中：

• data：保存结点数据。
• next：指向下一个结点。
• 最后一个结点的next通常为null。

2.3.2 单链表的特点

1. 结点在内存中不要求连续存储。
2. 通过指针建立逻辑上的前后关系。
3. 插入、删除操作通常不需要移动其他结点。
4. 不支持像数组那样直接通过下标随机访问。
5. 查找某个位置的结点通常需要从头遍历。

2.3.3 单链表的遍历

Node current = head; while (current ! = null) { System.out.println(current.data); current = current.next; }

• 从头结点开始，依次访问结点，直到指针为null。
  时间复杂度：

O(n)

2.3.4 单链表的插入

在结点p后面插入新结点s：

s.next = p.next; p.next = s;

• 必须先让新结点指向原来的后继，再修改前驱结点的指针。
• 若顺序写反，可能丢失后续链表的访问路径。

2.3.5 单链表的删除

• 删除结点p后面的结点：

if (p ! = null && p.next ! = null) { p.next = p.next.next; }

• 通过修改指针，跳过需要删除的结点。

2.3.6 头指针、头结点和首元结点

• 设置头结点可以统一空表与非空表的操作，减少特殊情况的处理。

2.3.7 单链表的时间复杂度

本节总结：单链表通过指针连接结点。它的插入、删除在已知前驱结点时效率较高，但访问指定位置需要遍历。

2.4 双链表

2.4.1 双链表的定义

• 双链表的每个结点包含数据域、前驱指针和后继指针。

class DoubleNode { int data; DoubleNode prev; DoubleNode next; DoubleNode(int data) { this.data = data; } }

2.4.2 双链表的特点

1. 可以沿next方向向后遍历。
2. 可以沿prev方向向前遍历。
3. 插入和删除操作可以直接修改前驱和后继关系。
4. 每个结点需要额外存储一个指针。

2.4.3 双链表插入

• 在结点p后插入结点s，基本指针关系如下：

s.prev = p; s.next = p.next; if (p.next != null) { p.next.prev = s; } p.next = s;

• 需要同时维护前驱和后继指针。

2.4.4 双链表删除

• 删除结点p时：

if (p.prev ! = null) { p.prev.next = p.next; } if (p.next ! = null) { p.next.prev = p.prev; }

实际应用中还需要根据是否存在头结点、尾结点等情况维护链表的首尾引用。

本节总结：双链表支持双向遍历，删除已定位的结点较方便，但需要额外的指针空间，且插入、删除时必须维护前驱和后继关系。

2.5 循环链表

2.5.1 循环单链表

1.循环单链表的最后一个结点不指向null，而是指向链表中的指定结点，通常指向头结点或第一个数据结点。

2.若采用头结点形式，则空循环单链表可以让头结点的next指向自身。

2.5.2 循环双链表

循环双链表同时具有前驱和后继指针，并且首尾结点相互连接。

常见形式：

• 尾结点的next指向头结点。
• 头结点的prev指向尾结点。

2.5.3 循环链表的特点

1. 可以从指定结点继续遍历。
2. 遍历时需要判断是否回到起始位置，避免无限循环。
3. 适合循环调度、轮流访问等场景。

本节总结：循环链表通过首尾连接形成循环结构，适合循环访问问题，但遍历终止条件必须设计正确。

2.6 顺序表与链表的比较

本节总结：顺序表适合随机访问，链表适合在已定位结点后进行灵活的插入和删除。具体选择应根据实际操作频率决定。