多项式的表示
一元多项式及其运算
f(x)=a_0 + a_1x + a_{n-1}x^{n-1} + a_nx^n
主要运算：多项式相加、相减、相乘等
如何表示多项式？
多项式的关键数据
- 多项式项数n
- 各项系数a_i 和指数 i
方法1：顺序存储结构直接表示
数组各分量对应多项式各项
比如
f(x)=4x^5 - 3x^2 +1
用两个数组表示
image.png
第一个数组表示的是次幂
第二个数组表示的是系数
不足之处在于当遇到x + 3x^{2000}
表示次幂的数组前面0-1999空置，很多空间被浪费
方法2：顺序存储结构表示非零项
每个非零项涉及两个信息：指数和系数
image.png
按照指数大小有序存储！
方法3：链表结构存储非零项
链表中的每个结点存储多项式中的一个非零项，包括系数和指数两个数据域以及一个指针域
链表存储表示为
image.png
多项式表示问题的启示
- 同一个问题可以有不同的表示存储方法
- 有同一类共性问题：有序线性序列的组织和管理
线性表：由同类型数据元素构成有序序列的线性结构
- 表中元素个数称为线性表的长度
- 线性表没有元素时，称为空表
- 表起始位置称表头，表结束位置称表尾
线性表的抽象数据类型描述
类型名称：线性表（List）
数据对象集：线性表是n(>=0)个元素构成的有序序列(a_1,a_2 ...a_n)
操作集：线性表L属于List，整数i表示位置，元素X属于ElemenType
线性表基本操作主要有：
- 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 Lenght(List L):返回线性表L的长度n
线性表的顺序存储实现
利用数组的连续存储空间顺序存放线性表的各元素
image.png
主要操作的实现
1. 初始化（建立空的顺序表）
image.png
通过malloc申请结构
image.png
把结构的Last声明为-1，因为Last代表的是最后一个，对应下标需要-1
image.png
返回结构的指针
image.png
2. 查找
image.png
平均查找次数为(n+1)/2
平均时间性能为O(n)
3. 插入
插入到第i个位置，对应下标为i-1
其次，先把最后一个往后挪，依次腾出直到腾出第i个位置
image.png
image.png
p->[num]表示p指向的结构体变量中的num成员。
4. 删除
和插入不一样的是
插入，是从前往后挪
删除，从前往后挪
image.png
image.png
