一、数据结构基本概念

1. 定义

数据结构：

数据元素之间的组织关系，以及数据元素在计算机中的存储方式。

数据结构 =

逻辑结构 + 存储结构 + 数据运算

二、逻辑结构

逻辑结构：

数据元素之间的关系。

主要分四类。

1. 集合结构

特点：

元素之间只有“属于同一集合”的关系。

例如：

{A,B,C,D}

没有前后关系。

2. 线性结构 ⭐

特点：

数据元素之间是一对一关系。

形式：

A → B → C → D

特点：

每个元素：

• 除第一个外都有唯一前驱

• 除最后一个外都有唯一后继

常见：

• 数组

• 链表

• 栈

• 队列

3. 树形结构 ⭐

特点：

一对多关系。

例如：

文件目录：

        C盘
       /   \
    图片   文档

特点：

• 有根节点

• 父子关系

4. 图结构 ⭐

特点：

多对多关系。

例如：

地图：

A —— B
|\   |
| \  |
C —— D

特点：

• 顶点

• 边

三、存储结构

存储结构：

数据在计算机中的表示方式。

主要两种：

1. 顺序存储 ⭐⭐⭐

特点：

数据元素连续存储。

例如数组：

地址:

1000 1004 1008 1012

 A    B    C    D

优点

随机访问快

例如：

访问：

a[5]

直接计算：

时间：

缺点

插入删除慢

例如：

数组：

A B C D

中间插入X：

A B X C D

需要移动：

C D

复杂度：

2. 链式存储 ⭐⭐⭐

特点：

数据元素不连续，通过指针连接。

例如：

A → B → C → D

节点：

数据域 + 指针域

优点

插入删除方便。

例如：

原：

A → B → C

插入X：

A → X → B → C

只修改指针。

复杂度：

（已知节点位置）

缺点

访问慢。

例如：

找第100个节点：

必须：

1→2→3→……→100

复杂度：

四、时间复杂度 ⭐⭐⭐⭐⭐

1. 定义

时间复杂度：

算法执行时间随输入规模增长的变化趋势。

关注：

增长速度。

不是实际运行时间。

2. 常见复杂度排序

从快到慢：

↓

↓

↓

↓

↓

考试记忆：

常数最快，对数其次，平方很慢。

五、常见复杂度对应

O(1)

固定操作。

例如：

数组随机访问：

a[i]

O(log n)

每次减少一半。

典型：

二分查找。

例如：

1000个数据：

1000
500
250
125
...

O(n)

遍历一次。

例如：

链表查找。

for(i=0;i<n;i++)

O(n²)

双重循环。

例如：

for(i=0;i<n;i++)
{
    for(j=0;j<n;j++)
    {

    }
}

典型：

• 冒泡排序

• 插入排序平均情况

六、软考高频对比 ⭐⭐⭐⭐⭐

顺序表 vs 链表

口诀：

数组擅长找，链表擅长改。

七、常见错误

错误1：

“已知位置，链表插入一定O(1)”

错误。

分情况：

已知节点指针：

例如：

p指向B

插入：

O(1)

只知道第几个位置：

例如：

“第100个位置插入”

需要先找：

O(n)

错误2：

随机访问 ≠ 查找

随机访问：

已知位置直接取。

例如：

数组第5个元素

查找：

不知道位置寻找目标。

例如：

找值50。

八、考前必须记忆

数据结构关系：

线性结构：
一对一

树：
一对多

图：
多对多

复杂度：

随机访问：
顺序表 O(1)

链表访问：
O(n)

二分查找：
O(log n)

双重循环：
O(n²)