数据结构 线性结构

线性结构

多项式表示

1. 数组表示
   • 直接表示
   • 表示非零项
2. 链表存储非零项

多项式问题的启示：

• 同一个问题可以有不同的表示(存储)方法
• 引出的一系列问题的共性 管理一个有序的线性序列的问题 —— 这里归结为 线性表的问题

线性表（Linear List)

def: 由同类型数据元素构成有序序列的线性结构

• 表中元素个数 为线性表的长度
• 线性表没有元素时，称为空表
• 表起始位置称表头，表结束位置称表尾

对应抽象数据类型描述

类型名称：线性表（List）
数据对象集：线性表是 n($\geq$)个元素构成的有序序列($a_1, a_2, …, a_n$)
操作集：线性表$L\in List$，整数 i 表示位置，元素$X\in ElementType$, 线性表的主要操作有：

1. List MakeEmpty(): 初始化一个空线性表；
2. ElementType FindKth( int K, List L ): 根据位序K，返回相应元素；
3. int Find( ElementType X, List L ): 在线性表 L 中查找 X 的第一次出现的位置；
4. void Insert( ElementType X, int i, List L ): 在位序 i 前插入一个新元素 X；
5. void Delete( int i, List L ): 删除指定位序 i 的元素；
6. int Length( List L ): 返回线性表 L 的长度n。

得到平均时间复杂度步骤：

• 考虑所有情况S
• 计算总次数N
• 平均复杂度 = N / S