- 多项式的表示
多项式：
方法一：顺序存储结构直接表示
a[i]:项的系数
用下标表示次数，下标对应数组中的值表示系数。
| 下标i | 0 | 1 | 2 | 3 | 4 | 5 |
| a[i] | 1 | 0 | -3 | 0 | 0 | 4 |
存在的问题：造成空间的巨大浪费
方法二：顺序结构表示非零项
把多项式看成一个系数和指数组成的二元组，用结构数组来表示，排列时，按指数递减的顺序排列方便运算。
方法三：链表结构存储非零项
链表中每个节点存储多项式中的一个非零项，包括系数和指数两个数据域以及一个指针域，指针域把它给串起来，同样也可以按指数递减或者递增的顺序进行排列。
typedef struct PolyNode *Polynomial;
struct PolyNode{
int coef;
int expon;
Polynomial link;
}- 线性表
由 同类型 数据元素 构成的 有序序列 的 线性结构。
线性表的存储：
一.顺序存储：用数组的形式存储
typedef struct LNode *List;
struct LNode{
ElementType Data[MAXSIZE];
int Last;//用来指示最后一个元素的位置
}；
struct LNode L;//struct LNode是L的类型
List PtrL;//定义struct LNode *型（可直接用List表示）变量PtrL访问下标为i的元素：L.Data[i]或PerL->Data[i]
线性表的长度：L.Last+1或PerL->List+1
操作实现：
1.初始化（建立空的顺序表）
List MakeEmpty(){
List PtrL;
PtrL=(List)malloc(sizeof(struct LNode));
//分配一个LNode大小的空间
PtrL->Last=-1;
//尾部初始化为-1
return PtrL;
}2.查找
int Find(ElementType X,List PtrL){
int i=0;
while(i<=Ptrl->Last&&PtrL->Data[i]!=X)
i++;
if(i>Ptrl->Last)
return -1;//没有找到元素X返回-1
else
return i;//找到，则返回元素所在的位置
}查找成功的平均比较次数为（n+1）/2,平均时间性能为O（n）.
3.插入
在线性表的第i（1<=i<=n+1）个位置插入一个值为X的新元素,也就是在下标为i-1的位置插入元素。
方法：先移动再插入，先挪动后面的。
void Insert(ElementType X,int i,List Ptrl){
int j;
if(PtrL->Last==MAXSIZE-1){//表满时不能插入元素
printf("表满")；
return;
}
if(i<1||i>PtrL->Last+2){//插入位置不合适时不允许插入
print("位置不合法")；
return;
}
for(j=Ptrl->Last;j>=i-1;j--){//向后移动元素
PtrL->Data[j+1]=PtrL->Data[j];
}
PtrL->Data[i-1]=X;//插入元素
PtrL->Last++;//Last指向最后的元素
return;
}平均移动次数为n/2，平均时间性能为O（n）
4.删除
删除表的第i（1<=i<=n）个位置上的元素,对应的下标为i-1
方法：将下标为i-1之后的元素依次往前挪，先挪动前面的，按从左往右的顺序挪动。
void Delete(int i, List PrtL){//i指的是第i个位置，对应的下标是i-1
int j;
if(i<1||i>PtrL->Last+1){
printf("不存在第%d个元素",i);
return;
}
for(j=i;j<=PtrL->Last;j++){
PtrL->Data[j-1]=PtrL->Data[j];/从下标为i-1的位置开始覆盖元素
}
PtrL->Last--;//Last指向最后的元素
return;
}平均移动次数为（n-1）/2，时间复杂度为O（n）
二.链式存储
逻辑上相邻的元素在物理上不一定相邻。
typedef struct LNode *List;//List是struct LNode *类型
struct LNode{
ElementType Data;
List Next;
};
struct Lnode L;//L是struct Lnode类型
List PtrL;1.求表长
用链表遍历的方式求
int Length (List PtrL){
List p=PtrL;//p指向表的第一个结点
int j=0;
while(p){
p=p->next;
j++;
}
return j;
}时间性能为O(n)
2.查找
（1）按序号查找
List FindKth(int K,List PrtL){
List p=PtrL;
int i;
while(p!=NULL&&i<K){
p=p->Next;
i++；
}
if(i==K)
return p;//找到第K个元素
else
return NULL;
}（2）按值查找
List Find(ElementType X,List PtrL){
List p=PtrL;
while(p!=NULL&&P->Data!=X){
p=p->next;
}
return p;
}3.插入
在第i-1（1<=i<=n+1）个节点后插入一个节点
List Insert(ElementType X,int i,List PrtL){
List p,s;
if(i==1){//插入的新节点在第0个位置时，要改变头节点的位置
s=(List)malloc(sizeof(struct LNode));
s->Data=X;
s->next=p;
return s;
}
p=FindKth(i-1,Ptrl);//查找第i-1个节点
if(p==NULL){
printf("参数错误")；
return NULL;
}
else{
s=(List)malloc(sizeof(struct LNode));
s->Data=X;
s->next=p;//先改变新插入节点的next指针
p->next=s;再改变第i-1个节点的next指针
return PtrL;
}
}4.删除操作
删除链表第i（1<=i<=n）个位置上的节点
List Delete(int i,List PtrL){
List p,s;
if(i==1){
s=PtrL;
if(PtrL!=NULL)//表非空时
PtrL=PtrL->next;
else//特别注意要考虑为空表的情况
return NULL;
free(s);
return PtrL;
}
p=FindKth(i-1,PtrL);
if(p==NULL){
printf("第%d个节点不存在",i-1);
return NULL;
}
else if(p->Next==NULL){
printf("第%d个节点不存在",i);
return NULL;
}
else{
s=p->next;//s指向当前被删除的节点
p=s->next;//删除节点
free(s);//释放节点空间
return PtrL;
}
}
