【数据结构与算法_01_线性表】线性表

素颜马尾好姑娘i 2024-03-17 13:46 51阅读 0赞

## 数据结构与算法 ##

### 线性表 ###

#### 定义 ####

● 线性表  
具有相同数据类型\*\*（同类型）\*\*的n个数据元素有限序列  
● 三方面  
● 定义  
`逻辑结构`  
● **相同数据类型  
● 每个数据元素所占的空间相同  
● 有限  
● 有限个元素  
● 序列  
● 是有次序的  
● 基本操作**

#### 操作—`基本操作` ####

运算  
● 创建线性表【initList(&L)】  
● 初始化线性表。构建一个空的线性表，分配内存空间  
● 销毁线性表【destroyList(&L)】  
● 释放所占内存空间  
● 插入操作【listLnsert(&L,i,e)】  
● 在L中的第i个位置插入e元素  
● 删除操作【listDelete(&L,i,&e)】  
● 删除L表中第i个位置的元素并用e返回删除的元素值  
● 查找操作  
● 按值查找【LocalElem(L,e)】  
● 在L表中查找具有给定关键字值元素  
● 按位查找【GetElem(L,i)】  
● 获取L表中第i个位置元素值  
● 其他常用操作  
● 表长【Length(L)】  
● 返回L表长度，即数据元素个数  
● 输出操作【printList(L)】  
● 前后顺序，输出L表中所有元素值  
● 判空操作【empty(L)】  
● 若L为空表，则返回true；反之，则为false  
● 物理结构  
存储结构  
● 顺序表  
方式–顺序存储  
● 定义  
代码层面如何实现？  
● 代码：typedef struct\{ElemType name; int length;\} structName;  
逻辑结构上是相邻的，在物理结构上也是位置相邻的存储单元  
● 基本操作实现  
运算实现  
● 静态分配  
是通过使用“静态数组”实现的，数据固定长度  
● 代码实现

● 缺点  
静态分配，大小固定，无法改变。  
● 动态分配  
“动态分配数组指针”，  
● Key  
动态申请和释放内存空间  
● malloc()&&free()  
stdlib.h标准库中的函数  
● malloc()  
申请内存空间  
● 返回指针类型，需强制转换成该类型下的指针  
● 其参数需要指明申请多大的连续内存空间  
● 代码实现

● 缺点  
虽可动态增加数组长度，但系统/时间开销较大，需要复制原有的再增加最后，再删除原有的。  
● 数据元素大小  
如何得知数据元素的大小？  
● sizeof(ElemType)  
通过该函数可得到数据元素大小。  
● 特点

①随机访问，即O(1)时间内找到第i个元素； ② 存储密度高，每个节点进存储数据元素； ③ 扩容不便。（即使采用动态分配方式，其时间复杂度也较高）； ④插入、删除不便，需要移动大量元素。

#### 线性表—注意 ####

● 五注意

*  ● 对数据的操作 记忆思路。创销、增删改查
 *  ● C语言函数定义
 *  ● 实际需求—具体操作 实际开发中，依据实际需求定义其他操作
 *  ● 命名可读性
 *  ● 引用型参数“&”使用 何时要用？需要将修改的参数结果回传（“带回来”）时