线性表及其实现
# 线性表及其实现
# 多项式的表示
# 顺序存储结构直接表示
- 系数较大时,难以表示
# 顺序存储结构表示非零项
存储系数和指数
只用表示非零项
多项式相加
# 链表结构储存非零项
# 什么是线性表
线性表(Linear List):由同类型数据元素构成有序序列的线性结构
- 表中元素个数称为线性表的长度
- 线性表没有元素时,称为空表
- 表起始位置称表头,表结束位置称表尾
# 线性表的抽象数据类型描述
- 类型名称:线性表(List)
- 数据对象集:线性表是 n (≥0)个元素构成的有序序列( a 1 , a 2 , ,a n )
- 操作集:线性表L List,整数i表示位置,元素X ElementType,
线性表基本操作主要有:
List MakeEmpty()
:初始化一个空线性表L
;- ElementType FindKth( int K, List L ):根据位序K,返回相应元素 ;
- int Find( ElementType X, List L ):在线性表L中查找X的第一次出现位置;
- void Insert( ElementType X, int i, List L):在位序i前插入一个新元素X;
- void Delete( int i, List L ):删除指定位序i的元素;
- int Length( List L ):返回线性表L的长度n。
# 线性表的实现
# 顺序储存实现
# 链式储存实现
- 插入,删除,先找到前一个结点
- 注意操作的节点是头结点的情况
# 广义表
# 二元多项式
- "复杂" 链表
# 多重链表
- 十字链表表示稀疏矩阵
- 行和列均是循环链表
- 起始的 Term 是入口节点
- 有矩阵的信息,多少行,多少列,多少个非零元素
编辑 (opens new window)