Skip to content

Commit bdbbd27

Browse files
ruyuejunruyuejun
committed
修正文字描述
2 parents cce691a + 2e980a3 commit bdbbd27

37 files changed

+604
-617
lines changed

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

Lines changed: 91 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,91 @@
1+
## 一 数组概念
2+
3+
数组是最简单的数据结构之一，基本所有的语言都提供了数组，这里就不再对数组进行详细介绍了。
4+
5+
但是我们必须要知道，在早期的语言中，数组并不支持在运行期间改变大小，必须预定义数组的容量，比如C语言，一些近代语言如Java,JS是支持数组的动态定义的，即长度可变，所以数组可以分为：
6+
- 静态数组：编译时确定数组的长度，为了防止空间不足，所以尽量将数组的长度定义的大点，但是容易造成内存浪费
7+
- 动态数组：不需要在编译时确定长度，而是在运行过程中确定。
8+
9+
数组本质上是在物理上一组连续的内存上存储的数据，属于顺序存储结构。
10+
11+
## 二 稀疏数组
12+
13+
#### 2.1 问题的引入
14+
15+
如下所示的五子棋程序，有存盘退出和续上盘的功能：
16+
![](../images/Algorithm/sparsearry-1.png)
17+
18+
如果使用二维数组来存储，就会如右侧所示存储很多为0的浪费空间。
19+
20+
#### 2.2 稀疏数组存储数据
21+
22+
当一个数组中大部分元素为0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组，其处理方式为：
23+
- 记录数组一共有几行几列，有多少个不同的值
24+
- 把具有不同值的元素的行列/值记录在一个小规模数组中
25+
26+
如图所示：
27+
![](../images/Algorithm/sparsearry-2.png)
28+
29+
图中的row/，col，val分别代表有多少行，多少列，对应值，其中第一条数据6，7，10存储了左侧数据总计有6行，7列，10个不同值。
30+
31+
#### 2.3 原始数组转换为稀疏数组
32+
33+
```go
34+
type Node struct {
35+
row int
36+
col int
37+
val int
38+
}
39+
40+
func NewSparseArray(arr [11][11]int) []Node{
41+
42+
var sa []Node
43+
n := Node{
44+
row: len(arr),
45+
col: len(arr[0]),
46+
val: 0,
47+
}
48+
sa = append(sa, n)
49+
50+
for i1, v1 := range arr {
51+
for i2, v2 := range v1 {
52+
if v2 != 0 {
53+
n := Node{
54+
row : i1,
55+
col : i2,
56+
val : v2,
57+
}
58+
sa = append(sa ,n)
59+
}
60+
}
61+
}
62+
63+
return sa
64+
}
65+
66+
// 打印原始数组
67+
func ShowOrigin(arr [11][11]int) {
68+
for i1, v1 := range arr {
69+
for i2, v2 := range v1 {
70+
fmt.Printf("%d|%d=%d\t", i1, i2, v2)
71+
}
72+
fmt.Println()
73+
}
74+
}
75+
76+
// 打印稀疏数组
77+
func ShowSparse(n []Node) {
78+
fmt.Println(n)
79+
}
80+
81+
// 稀疏数组转普通数组
82+
func TransToArray(n []Node) (arr [11][11]int){
83+
for i, v := range n {
84+
if i == 0 {
85+
continue
86+
}
87+
arr[v.row][v.col] = v.val
88+
}
89+
return
90+
}
91+
```

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

Lines changed: 0 additions & 30 deletions
This file was deleted.

‎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‎

Lines changed: 0 additions & 95 deletions
This file was deleted.

0 commit comments

Comments
 (0)