线性表及顺序存储

多项式的表示
一元多项式及其运算
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