算法导论——Data Structures and Dynamic Arrays 笔记
Interface(API/ADT) vs Data structure
| Interface | Data structure |
|---|---|
| 规范 | 表示 |
| 可以存储哪些数据 | 如何存储 |
| 操作的作用，支持哪些操作，在某种意义上的含义 | 算法——如何支持这些操作 |
| 问题 | 解决方案 |
同一个问题可以用不同的数据结构来解决
两个主要接口
两个主要接口：集合、序列
不同级别的序列
静态序列接口
有 x 1 , x 2 , x 3 , , , x n x_1,x_2,x_3,,,x_n x1,x2,x3,,,xn 序列，问以下的解决方案
| 问题 | 描述 |
|---|---|
| Build(x) | 在此接口中构建数据结构 |
| Len() | 返回长度 |
| Inter_Seq() | 按照指定的顺序排列或者输出 |
| Get_at(i) | 获取第i个位置的元素 |
| Set_at(i,x) | 将第i个位置的元素替换为x |
| Get_First/Last() | 获取第一个或最后一个元素 |
| Set_First/Last(x) | 将第一个或最后一个元素替换为x |
自然的解决方案：静态数组
使用静态数组的原因：
- 数组在内存中是连续的
- Array[i] 等价于 memery[address(arrray) + i]
- 即可以用恒定的时间来访问其中的元素
使用静态数组的时间复杂度：
| 函数 | 时间复杂度 |
|---|---|
| Get_at(i)、Set_at(i)、Len() | O(1) |
| Build(x)、Inter_Seq | O(n) |
内存分配模型：可以在O(n)的时间内分配一个大小为n的数组 => 空间复杂度等同于时间复杂度
动态序列接口
对静态的序列添加如下的操作：
| 问题 | 描述 |
|---|---|
| Insert_at(i,x) | 在第i个位置添加值为x的元素 |
| Delete_at(i) | 删除第i个位置的元素 |
| Insert/Delete_First/Last(i,x)/(i) | 在第一个或者最后一个位置进行插入或者删除 |
解决方案：链表
什么是链表？
- 将项目存储在一堆节点中
- 每一个节点都有一个项目和下一个指针
- 使用下一个指针来链接这些节点
- 在RAM是无序的
| 静态数组 | 链表 |
|---|---|
| insert/delete_at() 花费O(n)时间 | insert/delete_first()花费O(1)时间，get/set_at()在最坏的情况下花费O(n)时间 |
| 原因：如果靠近开头，则之后的所有元素后移 | |
| 必须分配一个新数组 |
动态数组：List可以解决以上的问题
两个主要数据结构工具/方法
两个主要数据结构工具：数组、基于指针或链接的数据结构