chapter02_线性表

1、第二章第二章 线性表线性表线性表是最简单和最常用的线性表是最简单和最常用的一种数据结构。一种数据结构。本章讨论线性表的定义、顺本章讨论线性表的定义、顺序存储结构和链式存储结构。序存储结构和链式存储结构。重点是线性表两种不同存储重点是线性表两种不同存储结构下的操作及其相应的算结构下的操作及其相应的算法。法。第二章第二章 线性表线性表2.1 线性表的概念及其抽象数据类型线性表的概念及其抽象数据类型2.2 线性表的顺序存储线性表的顺序存储2.3 线性表的链式存储线性表的链式存储2.4 线性表的应用线性表的应用一元多项式的表示及相加一元多项式的表示及相加2.5 顺序表与链表的综合比较（自学）顺序表与链

2、表的综合比较（自学）2.6 总结与提高（复习作业）总结与提高（复习作业）2.1 线性表的概念及其抽象数据类型线性表的概念及其抽象数据类型v线性表的逻辑结构线性表的逻辑结构线性表的定义线性表的定义线性表的特点线性表的特点v线性表的抽象数据类型定义线性表的抽象数据类型定义线性表的逻辑结构线性表的逻辑结构v线性表的定义线性表的定义线性表是由线性表是由n（n=0）个）个类型相同的数据元素类型相同的数据元素组组成的成的有限序列有限序列，记做，记做(a1,a2,ai-1,ai,ai+1,an)v第一个元素第一个元素a1无直接前驱无直接前驱v最后一个元素最后一个元素an无直接后继无直接后继v每个数据元素每个

3、数据元素ai只有一个直接前驱和一个直接后继只有一个直接前驱和一个直接后继v数据元素之间具有数据元素之间具有一对一一对一的关系的关系v线性表的特点线性表的特点线性表的逻辑结构线性表的逻辑结构v线性表的定义线性表的定义v线性表的特点线性表的特点同一性同一性：线性表由同类数据元素组成：线性表由同类数据元素组成有穷性有穷性：线性表由有限个数据元素组成：线性表由有限个数据元素组成v表长度：表中数据元素的个数表长度：表中数据元素的个数有序性有序性：线性表中相邻数据元素之间存在序偶关：线性表中相邻数据元素之间存在序偶关系系线性表的抽象数据类型定义线性表的抽象数据类型定义ADT List数据元素：数据元素：D

4、=ai|aiD0,i=1,2,n,n=0,D0为某一数据对象为某一数据对象结构关系：结构关系：R=|ai,ai+1D0,i=1,2,n-1基本操作：基本操作：(1) InitList(L)操作前提：操作前提：L为未初始化的线性表为未初始化的线性表操作结果：将操作结果：将L初始化为空表初始化为空表(2) DestroyList(L)操作前提：线性表操作前提：线性表L已经存在已经存在操作结果：将操作结果：将L销毁销毁(3) ClearList(L)操作前提：线性表操作前提：线性表L已经存在已经存在操作结果：将操作结果：将L置为空表置为空表线性表的抽象数据类型定义线性表的抽象数据类型定义数据元素：数

5、据元素：D=ai|aiD0,i=1,2,n,n=0,D0为某一数据对象为某一数据对象结构关系：结构关系：R=|ai,ai+1D0,i=1,2,n-1基本操作：基本操作：(4)EmptyList(L)操作前提：线性表操作前提：线性表L已经存在已经存在操作结果：如果操作结果：如果L为空表则返回为空表则返回TRUE，否则返回，否则返回FALSE(5)ListLength(L)操作前提：线性表操作前提：线性表L已经存在已经存在操作结果：如果操作结果：如果L为空表则返回为空表则返回0，否则返回表中数据元素的个，否则返回表中数据元素的个数数(6)Locate(L,e)操作前提：线性表操作前提：线性表L已经

6、存在，已经存在，e为合法数据元素值为合法数据元素值操作结果：如果操作结果：如果L中存在数据元素中存在数据元素e，则将，则将“当前指针当前指针”指向数指向数据元素据元素e所在位置并返回所在位置并返回TRUE，否则返回，否则返回FALSE线性表的抽象数据类型定义线性表的抽象数据类型定义数据元素：数据元素：D=ai|aiD0,i=1,2,n,n=0,D0为某一数据对象为某一数据对象结构关系：结构关系：R=|ai,ai+1D0,i=1,2,n-1基本操作：基本操作：(7)GetData(L,i)操作前提：线性表操作前提：线性表L已经存在，且已经存在，且i值合法值合法操作结果：返回线性表操作结果：返回线

7、性表L中第中第i个数据元素的值个数据元素的值(8)InsList(L,i,e)操作前提：线性表操作前提：线性表L已经存在，已经存在，e为合法元素值且为合法元素值且i值合法值合法操作结果：在表中第操作结果：在表中第i个位置之前插入新的数据元素个位置之前插入新的数据元素e，L的长度的长度加加1(9)DelList(L,i,e)操作前提：线性表操作前提：线性表L已经存在，已经存在，e为合法元素值且为合法元素值且i值合法值合法操作结果：删除操作结果：删除L的第的第i个数据元素，并用个数据元素，并用e返回其值，返回其值，L的长度的长度减减12.2 线性表的顺序存储线性表的顺序存储v线性表的顺序存储结构线

8、性表的顺序存储结构顺序表的定义顺序表的定义地址映像的计算公式地址映像的计算公式线性表顺序存储的表示线性表顺序存储的表示v线性表顺序存储结构上的基本操作线性表顺序存储结构上的基本操作查找操作查找操作插入操作插入操作删除操作删除操作线性表的顺序存储结构线性表的顺序存储结构v顺序表的定义顺序表的定义演示演示线性表的顺序存储是指用线性表的顺序存储是指用一组地址连续的存储单一组地址连续的存储单元元依次存储线性表中的各个数据元素，采用顺序依次存储线性表中的各个数据元素，采用顺序存储结构存放的线性表通常称为顺序表。存储结构存放的线性表通常称为顺序表。顺序表归纳为：顺序表归纳为：关系线性化关系线性化、结点顺序

9、存结点顺序存v地址映像的计算公式地址映像的计算公式v线性表顺序存储的表示线性表顺序存储的表示一组连续的存储一组连续的存储单元存放线性表单元存放线性表的数据元素的数据元素线性表的顺序存储结构线性表的顺序存储结构v顺序表的定义顺序表的定义演示演示v地址映像的计算公式地址映像的计算公式假设线性表中有假设线性表中有n个元素个元素，每个元素占每个元素占k个单元个单元，第一个元素的地址为第一个元素的地址为loc(a1)，则第，则第i个元素地址个元素地址loc(ai)的计算公式：的计算公式：loc(ai)=loc(a1)+(i-1)*kv线性表顺序存储的表示线性表顺序存储的表示线性表的顺序存储结构线性表的顺

10、序存储结构v顺序表的定义顺序表的定义演示演示v地址映像的计算公式地址映像的计算公式v线性表顺序存储的表示线性表顺序存储的表示说明说明#define MaxSize 100 / /* *此处的宏定义变量表示线性表的最大长度此处的宏定义变量表示线性表的最大长度* */ /typedef struct list DataType dataMaxSize; / /* *存放线性表的数组存放线性表的数组* */ / int last; / /* *线性表最后一个元素的下标，空表为线性表最后一个元素的下标，空表为-1-1* */ /SeqList;思考：思考：last和和len有怎样的关系？有怎样的关系？

11、线性表的顺序存储结构线性表的顺序存储结构#define MaxSize 100typedef struct DataType dataMaxSize; int last; SeqList;#define MaxSize 100typedef struct DataType dataMaxSize; int len; SeqList;(1)结点类型结点类型DataType由线性由线性表中的元素类型确定。表中的元素类型确定。(2)数组下标从数组下标从0开始计数，即开始计数，即data0存放线性表的第一存放线性表的第一个元素个元素a1。(3)len=last+1对顺序表的另一种定义对顺序表的另一种定

12、义线性表顺序存储结构上的基本操作线性表顺序存储结构上的基本操作v建立一个顺序存储的线性表建立一个顺序存储的线性表算法描述算法描述算法实现：将线性表的每个元素依次存储到数组算法实现：将线性表的每个元素依次存储到数组中中(*L).MaxSizea1a2aian01i-1n-1a1a2aian线性表顺序存储结构上的基本操作线性表顺序存储结构上的基本操作void create(SeqList *L) int i; scanf(%d,&(*L).last+1); / /* *输入线性表的长度输入线性表的长度* */ / for(i=0;i=(*L).last;i+) / /* *将线性表的每个元

13、素依次存入数组将线性表的每个元素依次存入数组* */ / scanf(%d,&(*L).datai);main() static SeqList *L; int i; clrscr(); create(L); for(i=0;i=0)&(i=(*L).last) e=(*L).datai; return e;算法的时间复杂度：算法的时间复杂度：O(1)线性表顺序存储结构上的基本操作线性表顺序存储结构上的基本操作int locate(SeqList *L,DataType e) int loc=-1,i; for(i=0;i=(*L).last;i+) if(e=(*L).dat

14、ai) loc=i; break; return loc;算法的时间复杂度：算法的时间复杂度：O(n)线性表顺序存储结构上的基本操作线性表顺序存储结构上的基本操作v插入操作插入操作在表的第在表的第i个位置之前插入一个新元素个位置之前插入一个新元素e，使长，使长度为度为n的线性表变成长度为的线性表变成长度为n+1的线性表。的线性表。算法思想算法思想n 原表插入位置之后的所有元素依次后移一位原表插入位置之后的所有元素依次后移一位n 空出插入位置，在该位置插入新结点空出插入位置，在该位置插入新结点n 线性表表长加线性表表长加1动画演示动画演示算法描述算法描述算法分析算法分析线性表顺序存储结构上的基本

15、操作线性表顺序存储结构上的基本操作a1a2aian-1anea1a2aian-1ane线性表顺序存储结构上的基本操作线性表顺序存储结构上的基本操作#define OK 1#define ERROR 0int inslist(SeqList *L, int i, DataType e) int j; if(i(*L).last) printf(insert position is illegal.n); return ERROR; if(*L).last=MaxSize-1) printf(array is full.n); return ERROR; / /* *插入位置之后的所有元素依插入位

16、置之后的所有元素依次后移一位次后移一位* */ / for(j=(*L).last;j=i;j-) (*L).dataj+1=(*L).dataj; / /* *将元素将元素e e插入位置插入位置i i之前之前* */ / (*L).datai=e; / /* *线性表表长加线性表表长加1 1* */ / (*L).last+; return OK;线性表顺序存储结构上的基本操作线性表顺序存储结构上的基本操作v算法分析算法分析p在表尾插入元素，原有元素不需要移动，直接插入即在表尾插入元素，原有元素不需要移动，直接插入即可可p在表头插入元素，所有元素（在表头插入元素，所有元素（n个）依次后移一位

17、，个）依次后移一位，然后插入新元素然后插入新元素结论：元素的移动次数和插入位置有关结论：元素的移动次数和插入位置有关设设Eins为平均移动次数，为平均移动次数，Pi为在第为在第i个位置之前插入元个位置之前插入元素的概率，等概率素的概率，等概率(Pi=1/(n+1)情况下：情况下：2nk1n1)1in(1n1)1in(PEn1in1k1n1iiins-=+=+=+=+=线性表顺序存储结构上的基本操作线性表顺序存储结构上的基本操作v删除操作删除操作将表的第将表的第i个元素删除，使长度为个元素删除，使长度为n的线性表变的线性表变成长度为成长度为n-1的线性表。的线性表。算法思想算法思想n 将第将第i

18、个位置的元素赋值给指定变量个位置的元素赋值给指定变量n 原表删除位置之后的所有元素依次前移一位原表删除位置之后的所有元素依次前移一位n 线性表表长减线性表表长减1动画演示动画演示算法描述算法描述算法分析算法分析线性表顺序存储结构上的基本操作线性表顺序存储结构上的基本操作a1a2aiai+1an-1an*ea1a2ai+1an-1an线性表顺序存储结构上的基本操作线性表顺序存储结构上的基本操作#define OK 1#define ERROR 0int dellist(SeqList *L, int i, DataType *e) int j; if(i(*L).last) printf(del

19、ete position is illegal.n); return ERROR; if(*L).last=-1) printf(array is empty.n); return ERROR; / /* *将删除位置上的元素传递将删除位置上的元素传递给指针变量给指针变量e e* */ / *e=(*L).datai-1; / /* *删除位置之后的所有元素删除位置之后的所有元素依次前移一位依次前移一位* */ / for(j=i;jdata表示表示p所指结点的所指结点的数据域数据域p-next表示表示p所指结点中的所指结点中的指针域指针域请注意区分请注意区分结点变量结点变量和和指向结点的指针

20、变量指向结点的指针变量有关指针的几个基本操作的含义有关指针的几个基本操作的含义q=p;q=p-next;p=p-next;ppqpqpp单链表上的基本运算单链表上的基本运算v初始化单链表初始化单链表void initlist(LinkList *L) / /* *L L是指向单链表的头指针是指向单链表的头指针* */ / / /* *mallocmalloc是动态分配函数，为头结点分配存储空间是动态分配函数，为头结点分配存储空间* */ / *L=(LinkList)malloc(sizeof(Node); (*L)-next=NULL;单链表上的基本运算单链表上的基本运算v建立单链表：头插法

21、建表建立单链表：头插法建表算法思想：算法思想：从一个空表开始，每次读入数据，生从一个空表开始，每次读入数据，生成新结点，将读入数据存放到新结点的数据域中，成新结点，将读入数据存放到新结点的数据域中，然后将然后将新结点插入到当前链表的表头结点之后新结点插入到当前链表的表头结点之后，直至读入结束标志为止。直至读入结束标志为止。动画演示动画演示算法描述算法描述H初始化初始化的空表的空表a1ss指向新申请的结点指向新申请的结点s-data=a1插入第一个结点插入第一个结点Ha1a2sa3sHa2a1Ha3a2a1Hanan-1a2a1s-next=H-next;H-next=s;单链表上的基本运算单链

22、表上的基本运算LinkList CreateFromHead(LinkList H) Node *s; DataType e; int flag=1; H=(LinkList)malloc(sizeof(Node);/ /* *初始化空表初始化空表* */ / H-next=NULL; while(flag)/ /* *用用flagflag标志建表是否结束标志建表是否结束* */ / scanf(%d,&e); if(e!=0) s=(Node *)malloc(sizeof(Node);/ /* *为新插入结点分配存储空间为新插入结点分配存储空间* */ / s-data=e;/ /

23、* *指针指针s s指向新插入的结点指向新插入的结点* */ / s-next=H-next; H-next=s; else flag=0; return H;单链表上的基本运算单链表上的基本运算v建立单链表：尾插法建表建立单链表：尾插法建表算法思想：算法思想：从一个空表开始，每次读入数据，生从一个空表开始，每次读入数据，生成新结点，将读入数据存放到新结点的数据域中，成新结点，将读入数据存放到新结点的数据域中，然后然后将新结点插入到当前单链表的表尾将新结点插入到当前单链表的表尾。动画演示动画演示算法描述算法描述H初始化初始化的空表的空表a1ss指向新申请的结点指向新申请的结点s-data=a1

24、插入第一个结点插入第一个结点Ha1a2s在当前单链表表尾在当前单链表表尾插入第二个结点插入第二个结点Ha1a2a3s在当前单链表表尾在当前单链表表尾插入第三个结点插入第三个结点Ha1a2an-1anr始终指向单链表的表尾始终指向单链表的表尾r-next=s;r=s;单链表上的基本运算单链表上的基本运算LinkList CreateFromTail(LinkList H) Node *s,*r;DataType e;int flag=1; H=(LinkList)malloc(sizeof(Node); H-next=NULL; r=H; while(flag) scanf(%d,&e)

25、; if(e!=0) s=(Node *)malloc(sizeof(Node); s-data=e; r-next=s; r=s; else flag=0; r-next=NULL; return H;单链表上的基本运算单链表上的基本运算v查找：按序号查找查找：按序号查找算法思想：算法思想：从单链表的头指针指向的头结点出发从单链表的头指针指向的头结点出发，逐个结点向下搜索，直至所说到第逐个结点向下搜索，直至所说到第i个结点为止个结点为止顺序访问顺序访问。动画演示动画演示算法描述算法描述&a1a1&a2a2&a3a3&a4anHpp单链表上的基本运算单链表上的基

26、本运算Node *Get(LinkList H, int i) int j=0; Node *p=H; while(p-next!=NULL)&(jnext; j+; if(i=j) return p; else return NULL;单链表上的基本运算单链表上的基本运算v查找：按值查找查找：按值查找算法思想：算法思想：从单链表的头指针指向的头结点出发从单链表的头指针指向的头结点出发，逐个将结点值和给定值逐个将结点值和给定值e作比较，返回查找结果。作比较，返回查找结果。动画演示动画演示算法描述算法描述&a1a1&a2a2&a3a3&a4anHppp-d

27、ata=e单链表上的基本运算单链表上的基本运算Node *Locate(LinkList H, DataType key) Node *p; p=H-next; while(p!=NULL) if(p-data!=key) p=p-next; else break; return p;单链表上的基本运算单链表上的基本运算v求单链表长度操作求单链表长度操作算法思想：算法思想：从结点从结点“头头”开始开始“数数(p=L-next)”，用用指针指针p依次指向各个结点依次指向各个结点，并，并附设计数器附设计数器j计数计数，一直一直“数数”到最后一个结点到最后一个结点(p-next=NULL)，从而得到

28、单链表的长度。从而得到单链表的长度。动画演示动画演示算法描述算法描述La1a2an-1anpp=L-next;j=0;p=p-next;j+;p单链表上的基本运算单链表上的基本运算int ListLength(LinkList L) Node *p=L-next; int j=0; while(p!=NULL)p=p-next;j+; return j;单链表上的基本运算单链表上的基本运算v单链表插入操作单链表插入操作算法思想：算法思想：n 查找：在单链表中找到第查找：在单链表中找到第i-1个结点并由指针个结点并由指针pre指示指示n 申请：申请新结点申请：申请新结点s，将其数据域的值置为，将

29、其数据域的值置为en 插入链表：通过修改指针域将新结点插入链表：通过修改指针域将新结点s插入单链表插入单链表L动画演示动画演示算法描述算法描述寻找第寻找第i-1个结点并由指针个结点并由指针pre指示指示La1ai-1aianpre申请新的结点申请新的结点Sse插入插入s结点结点La1ai-1aianprees与与ai连接连接s-next=pre-next;ai-1与与ai断开连接，插入断开连接，插入spre-next=s;单链表上的基本运算单链表上的基本运算int InsList(LinkList L, int i, DataType e) Node *pre,*s; int k; pre=L

30、;k=0; / /* *从头开始，查找第从头开始，查找第i-1i-1个结点个结点* */ / while(pre!=NULL&knext;k=k+1; / /* *第第1 1步完成，找到第步完成，找到第i-1i-1个结点个结点* */ / if(!pre)printf(insert position is illegal!n);return ERROR; s=(Node *)malloc(sizeof(Node); s-data=e; / /* *第第2 2步完成，为指针步完成，为指针s s分配空间并且指向插入元素分配空间并且指向插入元素e e* */ / s-next=pre-nex

31、t; pre-next=s; / /* *第第3 3步完成，结点步完成，结点s s插入链表中插入链表中* */ / return OK;单链表上的基本运算单链表上的基本运算v单链表删除操作单链表删除操作算法思想：算法思想：n 查找：通过计数方式找到第查找：通过计数方式找到第i-1个结点并由指针个结点并由指针pre指指示示n 删除第删除第i个结点并释放结点空间个结点并释放结点空间动画演示动画演示算法描述算法描述寻找第寻找第i-1个结点并由指针个结点并由指针pre指示指示La1ai-1aianai+1pre删除第删除第i个结点并释放结点空间个结点并释放结点空间r=pre-next;pre-next

32、=pre-next-next;free(r);删除结点删除结点i并释放结点空间并释放结点空间La1ai-1aianai+1prer单链表上的基本运算单链表上的基本运算int DelList(LinkList L, int i, DataType *e) Node *pre,*r; int k; pre=L;k=0; while(pre-next!=NULL&knext;k=k+1; / /* *第第1 1步完成，找到第步完成，找到第i-1i-1个结点并由指针个结点并由指针prepre指示指示* */ / if(!(pre-next)printf(delete position is i

33、llegal!n);return ERROR; r=pre-next; pre-next=pre-next-next; *e=r-data; / /* *删除结点并把删除元素保存在变量删除结点并把删除元素保存在变量* *e e中中* */ / free(r); / /* *释放结点空间释放结点空间* */ / return OK;循环链表循环链表v循环链表的定义循环链表的定义循环链表（循环链表（Circular Linked List）是一个首尾）是一个首尾相接的链表。将单链表相接的链表。将单链表最后一个结点的指针域由最后一个结点的指针域由NULL改为指向头结点改为指向头结点，就得到了单链形式

34、的循，就得到了单链形式的循环链表，称为循环单链表。环链表，称为循环单链表。v循环链表的结构循环链表的结构循环链表循环链表v循环链表的定义循环链表的定义v循环链表的结构循环链表的结构La1ai-1aianai+1rear-next=NULL;rear-next=L;rearL双向链表双向链表v双向链表的定义双向链表的定义单链表的每个结点里再增加一个单链表的每个结点里再增加一个指向其前驱的指指向其前驱的指针域针域prior，这样形成的链表中就有两条方向不同，这样形成的链表中就有两条方向不同的链，称为的链，称为双向链表双向链表（Double Linked List）。）。v双向链表的结点结构双向链表

35、的结点结构v双向链表的结点定义双向链表的结点定义v双向链表的结构双向链表的结构v双向链表上的基本运算双向链表上的基本运算双向链表双向链表v双向链表的定义双向链表的定义v双向链表的结点结构双向链表的结点结构v双向链表的结点定义双向链表的结点定义v双向链表的结构双向链表的结构v双向链表上的基本运算双向链表上的基本运算datanextprior双向链表双向链表v双向链表的定义双向链表的定义v双向链表的结点结构双向链表的结点结构v双向链表的结点定义双向链表的结点定义typedef struct node DataType data; struct node *prior; struct node *n

36、ext;DoubleNode,*DoubleList; v双向链表的结构双向链表的结构v双向链表上的基本运算双向链表上的基本运算双向链表双向链表v双向链表的定义双向链表的定义v双向链表的结点结构双向链表的结点结构v双向链表的结点定义双向链表的结点定义v双向链表的结构双向链表的结构v双向链表上的基本运算双向链表上的基本运算nextpriorL双向链表上的基本运算双向链表上的基本运算v双向链表的插入操作双向链表的插入操作算法思想算法思想：在双向链表的第：在双向链表的第i个结点之前插入一个结点之前插入一个结点，需要修改相关结点的前驱指针域和后继个结点，需要修改相关结点的前驱指针域和后继指针域。指针域

37、。动画演示动画演示算法描述算法描述ai-1nextpriorainextpriorenextpriors-next=p;p-prior=s;ps指针指针p指向第指向第i个结点个结点指针指针s指向需要插入的结点指向需要插入的结点s-prior=p-prior;p-prior-next=s;双向链表上的基本运算双向链表上的基本运算int InsDoubleList(DoubleList L, int i, DataType e) DoubleNode *s,*p; int k=0; p=L; while(p!=NULL&knext; k=k+1; if(!p)printf(insert p

38、osition is illegal!n);return FALSE; s=(DoubleNode *)malloc(sizeof(DoubleNode); if(s)s-data=e; s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s; return TRUE; return FALSE;双向链表上的基本运算双向链表上的基本运算v双向链表的删除操作双向链表的删除操作算法思想算法思想：删除双向链表的第：删除双向链表的第i个结点，同样需个结点，同样需要修改相关结点的前驱指针域和后继指针域。要修改相关结点的前驱指针域和后继指针域。动画演示动画

39、演示算法描述算法描述指针指针p指向第指向第i个结点（删除结点）个结点（删除结点）分析：分析：结点结点ai-1如何用指针如何用指针p表示？表示？结点结点ai+1如何用指针如何用指针p表示？表示？ai-1aiai+1p结点结点ai-1：p-prior结点结点ai+1：p-nextp-prior-next=p-next;p-next-prior=p-prior;双向链表上的基本运算双向链表上的基本运算int DelDoubleList(DoubleList L, int i, DataType *e) DoubleNode *s,*p; int k=0; p=L; while(p!=NULL&

40、;knext; k=k+1; if(!p)printf(delete position is illegal!n);return FALSE; *e=p-data; p-prior-next=p-next; p-next-prior=p-prior; free(p); return TRUE; 2.4 线性表的应用线性表的应用一元多项式的表示及相加一元多项式的表示及相加v一元多项式的表示一元多项式的表示v一元多项式的存储一元多项式的存储v一元多项式的相加运算一元多项式的相加运算一元多项式的表示一元多项式的表示v一元多项式可按升幂的方式写成：一元多项式可按升幂的方式写成：ei为第为第i项的指数项的指数pi是指数是指数ei的项的系数的项的系数1=e1=e2=enn21ene2e10nxp.xpxpp)x(P+=问题问题1：假设：假设Qm(x)是一个一是一个一元多项式，如何用一个线性表元多项式，如何用一个线性表Q表示？表示？问题问题2：若假设：若假设mcoef=c; s-exp=e; rear-next=s; rear=s; scanf