一元多项式的表示
分析：多项式的关键数据:多项式项数n，各项系数ai 及指数 i
-
方法1:顺序存储结构直接表示
利用数组存储，数组下标表示指数i，然后数组数值表示系数ai
arr1.png
两个多项式相加: 两个数组对应分量相加
问题:如何表示多项式 x+3x^2000 ?
需要创建2001个空间 ，内部会包含很多0 造成很多的空间浪费不合理
-
方法2:顺序存储结构表示非零项
每个非零项 ai xi 涉及两个信息:系数 ai 和指数 i
可以将一个多项式看成是一个 (ai,i) 二元组的集合。
arr2.png
按指数大小有序存储!
相加过程:从头开始，比较两个多项式当前对应项的指数
P1: (9,12), (15,8), (3,2)
P2: (26,19), (-4,8), (-13,6), (82,0)
P3: (26,19) (9,12) (11,8) (-13,6)
实现了俩个多项式相加 空间也没有造成浪费 利用结构数组存储
-
方法3:链表结构存储非零项
list.png
“线性表(Linear List)”:由同类型数据元素构成有序序列的线性结构
广义表(Generalized List)
- 广义表是线性表的推广
- 对于线性表而言， n个元素都是基本的单元素;
- 广义表中，这些元素不仅可以是单元素也可以是另一个广义表。
多重链表:链表中的节点可能同时隶属于多个链
- 多重链表中结点的指针域会有多个，如前面例子包含了Next和 SubList两个指针域;
- 但包含两个指针域的链表并不一定是多重链表，比如在双向链表 不是多重链表。
什么是堆栈
具有一定操作约束的线性表 只在一端(栈顶，Top)做 插入、删除
后入先出:Last In First Out(LIFO)
