第二章线性表

第二章线性表线性表的概念及抽象数据类型顺序表单链表循环链表双向链表应用与比较本章目标基于空间的考虑顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模。动态链表的存储空间是动态分配的，只要内存空间尚有空闲，就不会产生溢出。 当线性表的长度变化较大，难以估计存储规模时，采用动态链表作为存储结构较好顺序表和链表的比较基于时间的考虑顺序表可以随机存取，对表中任一结点都可以在O(1)时间内直接存取；链表中的结点需从头指针起开始顺着链找才能取得。 若线性表的操作主要是进行查找，很少做插入和删除时，宜采用顺序表存储结构顺序表进行插入、删除时，平均要移动表中近一半的元素；而链表只需要修改指针。 需要频繁进行插入、删除操作的线性表，宜采用链表存储结构。顺序表和链表的比较基于语言的考虑顺序表易于操作顺序表和链表的比较线性表链式存储方式的比较操作名链表名称找表头结点找表尾结点找P结点前驱结点带头结点单链表LL->nextO(1)一重循环O(n)顺P结点的next域无法找到P结点的前驱带头结点循环单链表LL->nextO(1)一重循环O(n)顺P结点的next域可以找到P结点的前驱：O(n)带尾指针的循环单链表RR->nextO(1)RO(1)顺P结点的next域可以找到P结点的前驱：O(n)带头结点双向循环链表LL->nextO(1)L->priorO(1)P->priorO(1)一元多项式可按升幂的形式写成：

Pn(x)=p0+p1xe1+p2xe2+…+pnxen，其中ei为第i项的指数(且1≤e1≤e2≤…≤en)pi是指数ei的项的系数一元多项式的表示及相加一元多项式的顺序存储表示(两种方法)一元多项式的链式存储表示一元多项式的存储一元多项式的顺序存储表示—方法1只存储该一元多项式各项的系数，每个系数所对应的指数项则隐含在存储系数的顺序表的下标中。如：B(x)=8x+22x7-9x8一元多项式的存储值080000022-9下标012345678一元多项式的顺序存储表示—方法1采用这种存储方法使得多项式的相加运算的算法定义十分简单，只需将下标相同的单元的内容相加即可。缺点：若多项式的非零项指数很高但非零项很少时，十分浪费存储空间，如：

R(x)=1+5x10000+7x20000一元多项式的存储一元多项式的顺序存储表示—方法2只存储非零项，此时每个非零项需要存储：非零项系数非零项指数如：B(x)=8x+22x7-9x8

一元多项式的存储

值系数822－9指数178下标012一元多项式的链式存储表示只存非零项，每一非零项由两部分构成（指数项和系数项）一元多项式的存储系数coef

指数exp指针next一元多项式的链式存储表示一元多项式的单链表表示示意图一元多项式的存储

A(x)=7+3x+9x8+5x17-17031517∧9881-1227-98∧

B(x)=8x+22x7-9x8

建立一元多项式链式存储的算法算法思想通过键盘输入一组多项式的系数和指数，用尾插法建立一元多项式的链表;以输入系数0为结束标志;并约定建立多项式链表时，总是按指数从小到大的顺序排列。一元多项式的存储两个一元多项式相加运算规则：两个多项式中所有指数相同的项的对应系数相加，若和不为零，则构成“和多项式”中的一项；所有指数不相同的项均复抄到“和多项式”中。一元多项式的存储-17031517∧9881-1227-98∧

polyapolyb-170111517∧227两个一元多项式相加一元多项式的存储-17031517∧9881-1227-98∧

polyapolybpqtail两个一元多项式相加若p->exp<q->exp，则结点p所指的结点应是“和多项式”中的一项，令指针p后移；若p->exp>q->exp，则结点q所指的结点应是“和多项式”中的一项，将结点q插入在结点p之前，且令指针q在原来的链表上后移；若p->exp==q->exp，则将两个结点中的系数相加，当和不为零时修改结点p的系数域，释放q结点；若和为零，则和多项式中无此项，从A中删去p结点，同时释放p和q结点。一元多项式的存储两个一元多项式相加一元多项式的存储-17031517∧9881-1227-98∧

polyapolybpqtail两个一元多项式相加一元多项式的存储-17031517∧98-1227-98∧

81polyapolybpqtail11temp两个一元多项式相加一元多项式的存储-170111517∧98-1227-98∧

polyapolybpqtailtail两个一元多项式相加一元多项式的存储-170111517∧98-1227-98∧

polyapolybpqtailtemptemp两个一元多项式相加一元多项式的存储-170111517∧-1227polyapolybpqtail多项式深度拷贝及应用比较两个多项式是否相等//比较两个多项式是否相等publicboolean

equals(Object

obj){ returnthis==obj||obj

instanceofPolynomia