Skip to content

Commit f04ac37

Browse files
ruyuejunruyuejun
committed
修正顺序表相关介绍
1 parent ee72e8a commit f04ac37

File tree

12 files changed

+94
-98
lines changed

12 files changed

+94
-98
lines changed

‎02-数据结构/00-数组简介.md‎

Lines changed: 10 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1,20 +1,24 @@
11
## 一 数组概念
22

3-
数组是最简单的数据结构之一，基本所有的语言都提供了数组，这里只是对数组做出简单的介绍。
3+
数组是最简单的数据结构之一，基本所有的语言都提供了数组，这里就不再对数组进行详细介绍了。
44

5-
## 二 数组的增删改查
5+
数组本质上是在物理上一组连续的内存上存储的数据，属于顺序存储结构。
66

7-
## 三 稀疏数组
7+
但是我们必须要知道，在早期的语言中，数组并不支持在运行期间改变大小，必须预定义数组的容量，比如C语言，一些近代语言如Java,JS是支持数组的动态定义的，即长度可变，所以数组可以分为：
8+
- 静态数组：编译时确定数组的长度，为了防止空间不足，所以尽量将数组的长度定义的大点，但是容易造成内存浪费
9+
- 动态数组：不需要在编译时确定长度，而是在运行过程中确定。
810

9-
#### 3.1 问题的引入
11+
## 二 稀疏数组
12+
13+
#### 2.1 问题的引入
1014

1115
如下所示的五子棋程序，有存盘退出和续上盘的功能：
1216
![](../images/Algorithm/sparsearry-1.png)
1317

1418

1519
如果使用二维数组来存储，就会如右侧所示存储很多为0的浪费空间。
1620

17-
#### 3.2 稀疏数组存储数据
21+
#### 2.2 稀疏数组存储数据
1822

1923
当一个数组中大部分元素为0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组，其处理方式为：
2024
- 记录数组一共有几行几列，有多少个不同的值
@@ -25,6 +29,6 @@
2529

2630
图中的row/，col，val分别代表有多少行，多少列，对应值，其中第一条数据6，7，10存储了左侧数据总计有6行，7列，10个不同值。
2731

28-
#### 3.3 原始数组转换为稀疏数组
32+
#### 2.3 原始数组转换为稀疏数组
2933

3034

‎02-数据结构/01-线性表1-概述.md‎

Lines changed: 18 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -3,11 +3,11 @@
33
线性表：零到多个数据元素组成的有限序列，即线一样性质的表。
44

55
概念的解释：
6-
- 序列：元素之间是有顺序的，若元素存在多个，则第一个元素无前驱，最后一个元素无后继，其他每个元素都有且只有一个前驱和后继。
7-
- 有限：元素的数量是有限的，不过计算机中的对象都是有限的，无限数列只存在于数学概念中。
6+
- 序列：元素之间是有序的，若元素存在多个，则第一个元素无前驱，最后一个元素无后继，其他每个元素都有且只有一个前驱和后继，即相邻元素间是一对一关系
7+
- 有限：元素的数量是有限的，不过计算机中的对象都是有限的，无限数列只存在于数学概念中
88

99
线性表图示：
10-
![](../images/Algorithm/list-0.png)
10+
![](../images/Algorithm/list-1.png)
1111

1212
线性表的元素的个数为n，n即是线性表的长度，n=0时，即为空表。
1313

@@ -16,5 +16,18 @@
1616
线性表在日常生活中的案例：幼儿园小朋友手拉手排队过马路：每个人记着自己的前一位和后一位。
1717

1818
## 二 线性表的划分
19-
20-
![](../images/Algorithm/list-1.png)
19+
20+
按照物理存储结构划分，线性表分为:
21+
- 顺序表：顺序结构存储
22+
- 链式表：链式结构存储
23+
24+
链式表按照逻辑存储结构划分，线性表分为：
25+
- 静态链表：有些语言没有指针，或者在不使用指针时，为了描述链表的插入删除操作，使用数组来存储链表数据，这样的链表是静态链表
26+
- 动态链表：包括常见的单链表，双向链表，循环链表等
27+
28+
## 三 线性表与数组的区别
29+
30+
- 在物理上：数组是顺序存储结构，线性表可以使用顺序存储，也可以使用链式存储
31+
- 在逻辑上：数组并不一定是线性的，因为其元素可以是结构，枚举，类等，而线性表在逻辑上必定是线性的（后续各种数据结构大多是基于逻辑而命令）。
32+
- 容量上：数组的长度一般是固定的，而链表的长度支持动态改变，可以随时删减添加，并且能够知道元素个数。
33+
- 维度上：数组是有维度的，二维数组等明显和线性表不同

02-数据结构/01-线性表2-顺序存储.md renamed to 02-数据结构/01-线性表2-顺序表.md

Lines changed: 40 additions & 59 deletions
Original file line numberDiff line numberDiff line change
@@ -1,59 +1,12 @@
1-
## 一 Go语言原生线性表
1+
## 一 顺序表
22

3-
go语言中已经提供了list：
4-
```go
5-
package main
6-
7-
import (
8-
"fmt"
9-
"container/list"
10-
)
11-
12-
func main() {
13-
14-
l := list.New()
15-
l.PushBack("first")
16-
l.PushFront("67")
17-
fmt.Printf("%v", l) // &{{0xc00009e060 0xc00009e030 <nil> <nil>} 2}
18-
19-
}
20-
```
21-
22-
当然在学习场合，我们需要自己定义一个list对象，并提供list的常用操作方法。
23-
24-
## 二 顺序结构存储线性表
25-
26-
#### 2.1 顺序结构存储方式简介
27-
28-
线性表只是一种逻辑结构，在物理上它的存储可以是顺序的也可以是链式的。
29-
30-
线性表的顺序存储结构：用一段地址连续的存储单元依次存储线性表的数据元素。如图所示：
31-
32-
![](../images/Algorithm/list-2.png)
33-
34-
注意：C系语言中数组索引位置从0开始。
35-
36-
37-
#### 2.2 顺序结构存储方式定义
38-
39-
```
40-
线性表对象 SequenList
41-
线性表数据 Data = {a1, a2, a3, ... , an}
42-
线性表方法
43-
NewSequenList() # 初始化一个线性表
44-
IsEmpty() # 判断线性表是否为空
45-
Append() # 从线性表末尾添加元素
46-
Insert() # 从某个位置添加元素
47-
```
3+
#### 1.1 存储方式
484

49-
#### 2.2 顺序结构存储方式实现
5+
线性表只是一种逻辑结构，在物理上它的存储可以是顺序的也可以是链式的，顺序表就是用一段地址连续的存储单元依次存储线性表的数据元素。如图所示：
506

7+
![](../images/Algorithm/sequenlist-1.png)
518

52-
53-
54-
## 三 理解顺序结构存储的线性表
55-
56-
#### 3.1 随机存取结构
9+
#### 1.2 随机存取结构
5710

5811
假设一个线性表占据了c个存储单元，那么线性表中第`i+1`个数据元素的存储位置，第`i`个数据元素存储位置三者之间的关系(LOC是获取存储位置的函数)：
5912

@@ -64,23 +17,51 @@ LOC(a<sub>i+1</sub>) = LOC(a<sub>i</sub>) + c
6417
LOC(a<sub>i</sub>) = LOC(a<sub>1</sub>) + (i - 1) * c
6518

6619
如图所示：
67-
![](../images/Algorithm/line-3.png)
20+
![](../images/Algorithm/sequenlist-2.png)
6821

6922
通过上述公式，可以随时计算线性表中任意位置的地址，不管是最后一个还是第一个，都是相同的时间，那么我们队线性表位置的存入和取出数据，对于计算机来说都是相等的时间，是一个常数，用时间复杂度来表示的话，其存取时间性能为O(1)，通常将具备这一特点的存储结构称为随机存取结构。
7023

71-
72-
#### 3.2 插入与删除的理解
24+
#### 1.3 顺序表的修改 存取
7325

7426
插入：
75-
![](../images/Algorithm/line-4.png)
27+
![](../images/Algorithm/sequenlist-3.png)
7628

7729
删除：
78-
![](../images/Algorithm/line-5.png)
30+
![](../images/Algorithm/sequenlist-4.png)
7931

8032
如果元素插入到最后一个位置，或者删除最后一个位置，那么之前的数据元素无需排序，此时是最好的情况，时间复杂度为O(1)，因为不需要移动元素。
8133

8234
如果是其他情况，则所有的数据元素都要进行移动，这个时间复杂度为O(n)。
8335

8436
总结：
85-
- 顺序结构存储的线性表，在存、读数据时，时间复杂度是O(1)
86-
- 顺序结构存储的线性表，插入和删除时，时间复杂度都是O(n)
37+
- 顺序结构存储的线性表，在存、读数据时，时间复杂度是O(1)，因为是一段连续的内存，直接可以通过索引获得
38+
- 顺序结构存储的线性表，插入和删除时，时间复杂度都是O(n)，因为需要重新移动位置
39+
40+
## 二 顺序表实现
41+
42+
#### 1.2 顺序表定义
43+
44+
```
45+
顺序表对象
46+
SequenList { # 伪代码，模拟一个对象
47+
size # 顺序表的长度
48+
length # 顺序表元素的个数
49+
data # 顺序表的数据
50+
}
51+
52+
顺序表方法
53+
NewSequenList() # 初始化一个顺序表
54+
IsEmpty() # 判断顺序表是否为空
55+
Append() # 从顺序表末尾添加元素
56+
Insert(index) # 从顺序表某个位置添加元素
57+
...
58+
```
59+
60+
#### 1.3 顺序表实现
61+
62+
```go
63+
64+
```
65+
66+
67+

02-数据结构/01-线性表3-链式存储.md renamed to 02-数据结构/01-线性表3-链表.md

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -19,7 +19,7 @@
1919

2020
线性表的链式存储可以用一组任意的存储的单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这意味着，这些数据元素可以存在内存未被占用的任意位置。当然，这样也会随之而来一些问题：除了要存储数据元素信息外，还要存储它的后继元素的存储地址。
2121

22-
![](../images/Algorithm/linkedline-1.png)
22+
![](../images/Algorithm/linkedlist-1.png)
2323

2424
#### 1.2 链表的结点
2525

@@ -30,19 +30,19 @@
3030

3131
n个Node链接成了一个链表，即使线性表的链式存储结构。
3232

33-
![](../images/Algorithm/linkedline-2.png)
33+
![](../images/Algorithm/linkedlist-2.png)
3434

3535
#### 1.3 头指针与头结点
3636

3737
线性表都有头有尾，链表中的第一个Node的存储位置称为头指针，之后的每一个Node，其实都是上一个后继指针指向的位置。
3838

3939
链表的最后一个Node，不存在后继，这个结点指针为空。
4040

41-
![](../images/Algorithm/linkedline-3.png)
41+
![](../images/Algorithm/linkedlist-3.png)
4242

4343
为了方便对链表进行操作，有时候会在单链表的第一个结点前附设一个一个结点，称为头结点。头结点的数据域可以不存储任何信息，但可以存储如线性表的长度等附加信息。头结点的指针域存储指向第一个结点的指针，如图所示：
4444

45-
![](../images/Algorithm/linkedline-4.png)
45+
![](../images/Algorithm/linkedlist-4.png)
4646

4747
头指针与头结点区别：
4848

@@ -59,7 +59,7 @@ n个Node链接成了一个链表，即使线性表的链式存储结构。
5959
#### 1.4 链表图示
6060

6161
空链表：
62-
![](../images/Algorithm/linkedline-5.png)
62+
![](../images/Algorithm/linkedlist-5.png)
6363

6464
普通链表：
65-
![](../images/Algorithm/linkedline-6.png)
65+
![](../images/Algorithm/linkedlist-6.png)

‎02-数据结构/01-线性表8-总结与应用.md‎

Lines changed: 20 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -1,40 +1,38 @@
11
## 一 线性表分类总结
22

3+
按照物理存储结构划分，线性表分为:
4+
- 顺序表：顺序结构存储
5+
- 链式表：链式结构存储
6+
7+
链式表按照逻辑存储结构划分，线性表分为：
8+
- 静态链表：有些语言没有指针，或者在不使用指针时，为了描述链表的插入删除操作，使用数组来存储链表数据，这样的链表是静态链表
9+
- 动态链表：包括常见的单链表，双向链表，循环链表等
10+
311
## 二 线性表使用总结
412

5-
#### 2.1 顺序存储线性表
13+
#### 2.1 顺序表优缺点
14+
615
整体而言，线性表适合元素个数不太变化，经常存取数据的场景。
716

8-
线性表优点：
17+
顺序表优点：
918
- 无需为表示数据结构的逻辑关系增加额外空间
1019
- 可以快速存取表中任一位置元素
1120

12-
线性表缺点：
21+
顺序表缺点：
1322
- 插入和删除操作需要移动大量元素
1423
- 线性表长度变化较大时，难以确定容量(MaxSize)
1524
- 容易造成存储空间碎片
1625

17-
#### 2.2 链表与顺序线性表对比
18-
19-
存储分配方式：
20-
- 顺序结构：用一段连续的存储单元依次存储
21-
- 单链表：使用链式结构，用一组任意的存储单元存储
26+
#### 2.2 顺序表与链表对比
2227

23-
时间性能：
24-
- 顺序结构：查询性能为O(1)，插入删除性能为O(n)
25-
- 单链表：：查询性能为O(n)，插入删除性能为O(1)
26-
27-
空间性能：
28-
- 顺序结构：需要预分配空间，分大了浪费，分小了容易溢出
29-
- 单链表：：无需分配空间，即个数也不受限制
30-
31-
总结：需要频繁查找，使用顺序存储，需要频繁更新，使用链式存储
28+
| 表类型 | 存储结构 | 时间性能 | 空间性能 |
29+
| :------| ------: | ------: | ------: |
30+
| 顺序表 | 顺序存储 | 查询性能O(1),修改性能O(n) | 需要预分配空间，容易浪费 |
31+
| 链表 | 链式存储 | 查询性能O(n),修改性能O(1) | 无需分配空间，元素个数任意 |
3232

3333
#### 2.3 静态链表
3434

35-
- 优点：插入阐述只用改游标，不用移动元素，破除了顺序存储的缺点
36-
- 缺点：没有解决连续存储分配带来的表长无法确定问题，失去了顺序结构随机存取特性
37-
38-
贴士：静态链表只是给一些没有指针的高级语言提供了一种实现方案。
35+
- 优点：插入删除只用改游标，不用移动元素，不再有顺序表的缺点
36+
- 缺点：没有解决连续存储分配带来的表长无法确定问题，失去了顺序表存取特性
3937

40-
![](../images/Algorithm/line-6.png)
38+
贴士：静态链表只是给一些没有指针的高级语言提供了一种实现方案。

‎images/Algorithm/list-0.png‎

-108 KB
Binary file not shown.

‎images/Algorithm/list-1.png‎

5.29 KB
Loading

‎images/Algorithm/list-6.png‎

-168 KB
Binary file not shown.

images/Algorithm/list-2.png renamed to images/Algorithm/sequenlist-1.png

File renamed without changes.

images/Algorithm/list-3.png renamed to images/Algorithm/sequenlist-2.png

File renamed without changes.

0 commit comments

Comments
 (0)