欢迎关注我的微信公众号【万能的小江江】
2.1 线性表的定义和特点
线性结构的基本特点
第一个元素无前驱，最后一个元素无后继
定义
线性结构相邻元素之间存在序偶关系
2.2 案例引入
案例1：一元多项式的运算
什么是一元多项式
像这样，由n+1个系数唯一确定的式子，一元n次多项式
把一元多项式抽象为线性表
所以，我们把它抽象为有n+1个元素的有序序列，用线性表P表示
这里的i可以理解为线性表的系数，现在就是有n+1个元素的线性表了
设Q是一元m次多项式，我们就可以再定义一个有m+1个元素的线性表Q
两个线性表合成新的线性表
设m<=n，让P+Q生成一个新的线性表R
不难看出，我们可以很容易用类似数组这样的顺序存储结构实现上述的运算，这种也被称为稀疏多项式
但是实际的应用中，稀疏多项式采用上述表示方法会导致线性表出现很多零元素
案例2：稀疏多项式的运算
为什么会出现很多零元素
我们在处理这样的多项式时，要用长度20001的线性表来表示，但是表中只有3个非零元素，这样就会造成存储空间很大的浪费
如何避免因为稀疏多项式运算导致的存储空间浪费
线性表的元素可以包含多个数据项，可以通过改变元素设定，对多项式的每一项，用系数、指数等来唯一确定
把原来长这样的多项式
写成这样
注：pi是指数为ei项的非零系数，满足
原来的线性表
变成这样
这样，就可以确定出唯一的多项式了。最坏的情况下，哪怕都存满，也只比单独存系数多一倍的数据
所以像数组这样的顺序存储空间，有可能用不到这么多导致浪费，也可以用的太多了，空间不够用。改进方法就是用链式存储结构来表示多项式的有序序列，这样更灵活一些
案例3：图书信息管理系统
图书包含的信息
假设有关图书的数据都保存在一个文件中，每种图书只包含：ISBN（书号）、书名、价格
图书信息管理系统要实现的功能
- 查找：根据相关ISBN或者书名来查找，并返回图书在表中位置序号
- 插入：插入一种新的图书信息
- 删除：删除一种图书信息
- 修改：根据指定的ISBN（或者书名？），修改图书的价格
- 排序：将图书的价格升序或者降序排序
- 计数：统计表中图书的数量
我们可以把这个系统抽象成一个线性表，每本图书都是线性表中的一个元素，再根据适当的存储结构来表示这个线性表，在此基础上设计再完成相关的算法
2.3 线性表的类型定义
线性表的抽象数据类型定义
ADT list{
数据对象：D = {ai | ai属于 ElemSet,i = 1,2,...,n,n>=0}
数据关系：R = {<ai-1,ai>|ai-1,ai属于D,i=2,...,n}
基本操作：
InitList(&L)
操作结果：构造一个空的线性表L
DestoryList(&L)
初始条件：线性表L已存在
操作结果：销毁线性表L
ClearList(&L)
初始条件：线性表L已存在
操作结果：将L重置为空表
ListEmpty(L)
初始条件：线性表L已存在
操作结果：若L为空表，返回true，否则返回false
ListLength(L)
初始条件：线性表L已存在
操作结果：返回L中数据元素的个数
GetElem(L,i,&e)
初始条件：线性表L已存在，且1 <= i <= ListLength(L)
操作结果：用e返回L中第i个数据元素的值
LocateElem(L,e)
初始条件：线性表L已存在
操作结果：返回L中第1个值与e相同的元素在L中的位置，若这样的数据元素不存在，则返回值为0
PriorElem(L,cur_e,&pre_e)
初始条件：线性表L已存在
操作结果：若cur_e是L的数据元素，并且不是第一个，就用pre_e返回其前驱，否则操作失败，pre_e无定义
NextElem(L,cur_e,&next_e)
初始条件：线性表L已存在
操作结果：若cur_e是L的数据元素，并且不是最后一个，就用pre_e返回其后继，否则操作失败，next_e无定义
ListInsert(&L,i,e)
初始条件：线性表L已存在，且1 <= i <= ListLength(L)+1
操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
ListDelete(&L,i)
初始条件：线性表L已存在非空，且1 <= i <= Listlength(L)
操作结果：删除L的第i个数据元素，L的长度减1
TraverseList(L)
初始条件：线性表L已存在
操作结果：对线性表L进行遍历，在遍历过程中对L的每个节点访问一次
}ADT List
