mirror of
https://github.com/happyflyer/wangdao-data-structure.git
synced 2026-02-03 02:24:39 +08:00
206 lines
4.0 KiB
Markdown
206 lines
4.0 KiB
Markdown
# 顺序表
|
||
|
||
顺序表：用顺序存储方式实现的线性表。
|
||
|
||
顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。
|
||
|
||
- $LOC(L)$
|
||
- $LOC(L)+sizeof(ElemType)$
|
||
- $LOC(L)+2*sizeof(ElemType)$
|
||
- $...$
|
||
|
||
## 1. 静态分配
|
||
|
||
```cpp
|
||
#define MaxSize 10
|
||
typedef struct
|
||
{
|
||
ElemType data[MaxSize];
|
||
int length;
|
||
} SqList;
|
||
```
|
||
|
||
```cpp
|
||
void InitList(SqList &L)
|
||
{
|
||
// for (int i = 0; i < MaxSize; i++)
|
||
// {
|
||
// L.data[i] = 0;
|
||
// }
|
||
L.length = 0;
|
||
}
|
||
```
|
||
|
||
$MaxSize*sizeof(ElemType)$
|
||
|
||
- 使用“静态数组”实现
|
||
- 大小一旦确定就无法改变
|
||
|
||
## 2. 动态分配
|
||
|
||
```cpp
|
||
#define InitSize 10
|
||
typedef struct
|
||
{
|
||
ElemType *data;
|
||
int MaxSize;
|
||
int length;
|
||
} SeqList;
|
||
```
|
||
|
||
```cpp
|
||
void InitList(SeqList &L)
|
||
{
|
||
// 用 malloc 函数申请一篇连续的存储空间
|
||
L.data = (int *)malloc(InitSize * sizeof(int));
|
||
L.length = 0;
|
||
L.MaxSize = InitSize;
|
||
}
|
||
```
|
||
|
||
```cpp
|
||
void IncreaseSize(SeqList &L, int len)
|
||
{
|
||
int *p = L.data;
|
||
L.data = (int *)malloc((L.MaxSize + len) * sizeof(int));
|
||
for (int i = 0; i < L.length; i++)
|
||
{
|
||
L.data[i] = p[i]; // 时间复杂度高
|
||
}
|
||
L.MaxSize += len;
|
||
free(p);
|
||
}
|
||
```
|
||
|
||
- `malloc`：动态申请一整片连续的内存空间
|
||
- `free`：释放内存空间
|
||
|
||
```c
|
||
L.data = (ElemType *) malloc(sizeof(ElemType) * InitSize)
|
||
```
|
||
|
||
C++ 可以使用 `new`，`delete` 关键字。
|
||
|
||
- 使用“动态数组”实现
|
||
- `L.data = (ElemType *) malloc(sizeof(ElemType) * InitSize)`
|
||
- 顺序表存满时，可再用 `malloc` 动态扩展顺序表的最大容量
|
||
- 需要将数据元素复制到新的存储区域，并用 `free` 函数释放原区域
|
||
|
||
## 3. 顺序表的特点
|
||
|
||
- **随机访问**：即可以在 $O(1)$ 时间内找到第 $i$ 个元素。
|
||
- 存储密度高：每个结点只存储数据元素。
|
||
- 扩展容量不方便：静态分配不能扩展容量，动态分配可以扩展但时间复杂度高。
|
||
- 插入、删除元素操作不方便，需要移动大量元素。
|
||
|
||
## 4. 插入操作
|
||
|
||
$$
|
||
L=(\alpha_1,\alpha_2,\alpha_3,\alpha_4,\alpha_5)
|
||
$$
|
||
|
||
$$
|
||
[a_0,a_1,a_2,a_3,a_4]
|
||
$$
|
||
|
||
```cpp
|
||
bool ListInsert(SqList &L, int i, int e)
|
||
{
|
||
// i 的值必须是合法的位序
|
||
if (i < 1 || i > L.length + 1)
|
||
{
|
||
return false;
|
||
}
|
||
// 如果存储空间已满，则不能插入
|
||
if (L.length >= MaxSize)
|
||
{
|
||
return false;
|
||
}
|
||
// 插入操作
|
||
for (int j = L.length; j >= i; j--)
|
||
{
|
||
L.data[j] = L.data[j - 1];
|
||
}
|
||
L.data[i - 1] = e;
|
||
L.length++;
|
||
return true;
|
||
}
|
||
```
|
||
|
||
插入位置之后的元素都要后移。
|
||
|
||
- 最好时间复杂度：$O(1)$
|
||
- 最坏时间复杂度：$O(n)$
|
||
- 平均时间复杂度：$O(n)$
|
||
|
||
## 5. 删除操作
|
||
|
||
```cpp
|
||
bool ListDelete(SqList &L, int i, int &e)
|
||
{
|
||
// i 的值必须是合法的位序
|
||
if (i < 1 || i > L.length)
|
||
{
|
||
return false;
|
||
}
|
||
// 删除操作
|
||
e = L.data[i - 1];
|
||
for (int j = i; j < L.length; j++)
|
||
{
|
||
L.data[j - 1] = L.data[j];
|
||
}
|
||
L.length--;
|
||
return true;
|
||
}
|
||
```
|
||
|
||
删除位置之后的元素都要前移。
|
||
|
||
- 最好时间复杂度：$O(1)$
|
||
- 最坏时间复杂度：$O(n)$
|
||
- 平均时间复杂度：$O(n)$
|
||
|
||
代码要点：
|
||
|
||
- 代码中注意位序 $i$ 与数组下标的区别。
|
||
- 算法要有健壮性，注意判断 $i$ 的合法性。
|
||
- 移动元素时，从靠前的元素开始？还是从表尾元素开始？
|
||
- 分析代码，理解为什么有的参数需要加 `&`（C++ 语法中的引用）。
|
||
|
||
## 6. 按位查找
|
||
|
||
```cpp
|
||
int GetElem(SqList L, int i)
|
||
{
|
||
// i 的值必须是合法的位序
|
||
if (i < 1 || i > L.length)
|
||
{
|
||
return false;
|
||
}
|
||
return L.data[i - 1];
|
||
}
|
||
|
||
```
|
||
|
||
- 时间复杂度：$O(1)$
|
||
|
||
## 7. 按值查找
|
||
|
||
```cpp
|
||
int LocateElem(SqList L, int e)
|
||
{
|
||
for (int i = 0; i < L.length; i++)
|
||
{
|
||
if (L.data[i] == e)
|
||
{
|
||
return i + 1;
|
||
}
|
||
}
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
- 最好时间复杂度：$O(1)$
|
||
- 最坏时间复杂度：$O(n)$
|
||
- 平均时间复杂度：$O(n)$
|