线性表及其实现

多项式的表示（以一元多项式为例）
- 一元多项式： $f(x)=a_0+a_1x+...+a_{n-1}x^{n-1}+a_nx^n$
- 顺序存储结构直接表示
  - 含义：每个数组元素蕴含两个信息：该元素的值表示系数 $a_i$ ，该元素的下标表示指数 $i$ ，数组各元素对应于多项式的各项。
  - 例子： $f(x)=4x^5-3x^2+1$ 表示为数组 a = [1, 0, -3, 0, 0, 4]
  - 运算：两个多项式相加，即两个数组对应分量相加
  - 问题：需要利用大量连续空间，如果多项式的非零项较少，则造成大量空间浪费
  - 思考：剔除所有值为0的分量，只表示非零项
- 顺序存储结构表示非零项
  - 含义：将一个多项式看做一个 $(a_i, i)$ 二元组的集合。用结构数组（数组内每个元素都是一个由 $\{a_i, i\}$ 组成的结构）表示，每个分量对应一个非零项。
  - 例子：
    
    $P_1(x)=9x^{12}+15x^8+3x^2+82$
    
    a[0] a[1] a[2] a[3]
    
    9 15 3 82
    
    12 8 2 0
  - NOTE: 为了运算方便，必须按照 指数大小 进行有序存储
  - 运算：两个多项式相加时，应从头开始，比较当前对应项的指数，指数较大的项在前、较小的在后
- 链表存储结构表示非零项
  - 含义：每个结点存储多项式中一个非零项，结点包括系数、指数两个数据域及一个指针域
  - 结点的定义
```
typedef struct PolyNode *Polynomial;
struct PolyNode {
    int coef;
    int expon;
    Polynomial link;
}
```
抽象数据类型描述
- 数据对象： $D=\{a_i | a_i\in ElemSet, i=1,2,...,n, n>=0\}$
- 数据关系： $R1=\{\langle a_{i-1},a_i\rangle | a_{i-1}, a_i \in D, i=2,...,n\}$
- 操作集
  - InitList()：初始化一个空表
  - DestroyList(): 销毁线性表
  - ClearList(): 重置为空表
  - ListEmpty(): 检测是否为空表
  - ListLength(): 获取表中元素个数
  - GetElem(): 返回表中第 i 个元素的值
  - LocateElem(): 返回表中第一个与e值相等的元素的位序
  - PriorElem()：返回前驱元素
  - NextElem()：返回后继元素
  - ListInsert()：在第 i 个位置之前插入新的数据元素 e
  - ListDelete()：删除第 i 个元素，并返回其值
  - ListTraverse(): 遍历线性表中各元素

a[0]	a[1]	a[2]	a[3]
9	15	3	82
12	8	2	0

线性表的顺序存储实现

线性表的定义

typedef struct {
    ElemType *elem; //  存储空间基址(首地址)，相当于分量类型为ElemType的数组
    int length;     //  元素个数
    int list_size;  //  当前分配的存储量
} SqList;

主要操作集的实现

线性表的链式存储实现

线性表的定义

typedef struct {
    ElemType data;
    struct LNode *next;
} LNode,  *Link;    // Link为指针，指向类型为 LNode 的结点

typedef struct {
    Link head, tail;
    int length;
} LinkList;

主要操作集的实现