"数据结构-线性表-PPT"
数据结构是一门研究非数值计算的程序设计问题的学科，它研究的是计算机存储、表示、操作和保护非数值信息的方法和技术。线性表是数据结构的一种基本结构，它是一种线性结构，只有一个首结点和一个尾结点，除首尾结点外，其他结点只有一个直接前驱和一个直接后继。
线性表的定义：线性表是由n(n≥0)个数据特性相同的元素构成的有限序列。线性表中元素的个数n(n≥0)定义为线性表的表长。当n=0时，称之为空表。
线性表的特点：
* 只有一个首结点和一个尾结点
* 除首尾结点外，其他结点只有一个直接前驱和一个直接后继
* 线性表中元素的个数n(n≥0)定义为线性表的表长
* 当n=0时，称之为空表
选择题：线性表L=(a1, a2, …, an)，下列说法正确的是：
* 每个元素都有一个直接前驱和一个直接后继（错误）
* 线性表中至少有一个元素（正确）
* 表中诸元素的排列必须是由小到大或由大到小（错误）
* 除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继（正确）
案例引入：
案例1：一元多项式的线性表表示
在数学上，一个一元n次多项式 Pn(x) 可按升幂写成：Pn(x) = p0 + p1x + p2x2 + … + pn xn 可用一个线性表来表示：P = (p0, p1, p2, …, pn)。每一项的指数i 隐含在其系数pi 的索引中。
例如：P(x) = 10 + 5x - 4x2 + 3x3 + 2x4 可以用一个线性表来表示：P = (10, 5, -4, 3, 2)。
案例2：两个一元多项式相加的线性表表示
在数学上，一个一元n次多项式 Pn(x) 可按升幂写成：Pn(x) = p0 + p1x + p2x2 + … + pn xn 可用一个线性表来表示：P = (p0, p1, p2, …, pn)。不失一般性，一个一元m次 (m≤n) 多项式 Qm(x) 可用线性表表示为：Q = (q0, q1, q2, …, qm)。则 Rn(x) = Pn(x) + Qm(x) 可用线性表表示为：R = (p0+q0, p1+q1, p2+q2, …, pm+qm, pm+1, …, pn)。
例如：若A 17(x) = 7 + 3x + 9x8 + 5x17, B8(x) = 8x + 22x7 - 9x8, 则 A 17(x) + B8(x) = 7 + 11x + 27x7。
案例3：稀疏多项式的运算
一般情况下，一个一元n次多项式 Pn(x) 可按升幂写成：例如：稀疏矩阵A 17(x) = 7 + 3x + 9x8 + 5x17 可表示为 ((7,0),(3,1),(9,8),(5,17)) 可用一个长度为m且每个元素有两个数据项（系数项和指数项）线性表 ((p1,e1),(p2,e2),…,(pm,em)) 来表示。
编程题：给定稀疏多项式的若干组非负系数项和指数项，输出此稀疏多项式。
例如：
```cpp
#include <bits/stdc++.h>
using namespace std;
int u,v;
string s;
int main() {
int n;
cin>>n;
for(int i=1; i<=n; i++) {
cin>>u>>v;
if(i==n) s+=to_string(u)+"x^"+to_string(v);
else s+=to_string(u)+"x^"+to_string(v)+ "+";
}
cout<<"f(x)="<<s<<endl;
return 0;
}
```
