ch2-3一元多项式及习题(更新)试题.ppt

1.某线性表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用 存储方式最节省运算时间. A.单链表 B.单循环链表 C.双链表 D.双循环链表 例1：试用C或类C语言编写一高效算法，将一顺序存储的线性表（设元素均为整型量）中所有零元素向表尾集中，其他元素则顺序向表头方向集中。 * * 第2章 线性表 2.1 线性表的逻辑结构 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 一元多项式的表示和相加 * 2.4.1 一元多项式的定义 2.4.2 一元多项式的实现 2.4 一元多项式的表示和相加 * 但当多项式的次数很高且零系数项很多时，更适于用链表存储。 2.4.1 一元多项式的定义 机内存储方式？ 一般用顺序存储—— p0 p1 p2 … pn-1 pn 链式存储 0.0 -1 … pm em ^ p1 e1 通常设计两个数据域（系数项和指数项）和一个指针域 头结点 只存系数项（但零系数项也不能遗漏） P2000(x)= 1+ 3x1000 + 5x2000 * 用C语言具体描述它的定义 法一：用类C语言： 参见教材P42 法二：用标准C语言： typedef struct poly_node { int coef; int expn; struct poly_node *link; } poly_node, *poly_pointer; poly_pointer a, b, c; coef expn link 2.4.2. 一元多项式的实现 * 3 14 2 8 1 0 a ^ 8 14 －3 10 10 6 b ^ 例： 运算规则：两多项式中指数相同的项对应系数相加，若和不为0,则构成多项式c(=a+b)中的一项；a和b中所有指数不相同的项均应拷贝到c中。 链表a： 链表b： 多项式相加 * 实现思路： 依次比较Pa和Pb所指结点中的指数项，依 Pa-expn =、 、Pb-expn等情况，再决定是将两系数域的数值相加（并判其和是否为0），还是将较高指数项的结点插入到新表c中。 3 14 2 8 1 0 ^ a Pa 8 14 -3 10 10 6 ^ b Pb 11 14 -3 10 2 8 1 0 ^ c Pc 10 6 + 注：Pa＝Pa＋Pb，并销毁一元多项式Pb。 * 运算效率分析： (1) 系数相加 0 ? 加法次数? min(m, n) 其中 m和n分别表示表A和表B的结点数。 (2) 指数比较 极端情况是表A和表B 没有一项指数相同，比较次数最多为m+n-1 合计时间复杂度为 O(m+n) 算法略 * 本章小结 1.了解线性表的逻辑结构特性:数据元素之间存在着线性关系； 在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构； 用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。 2.熟练掌握这两类存储结构的描述方法，以及线性表的各种基本操作的实现。 3.能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。 选择 2.某线性表最常用的操作是在最后一个结点之后插入一 个结点或删除第一个结点，故采用 存储方式最节省运算时间. A.单链表 B.仅有头指针的单循环链表 C.双链表 D.仅有尾指针的单循环链表 D D 3.需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 A.单链表 B.静态链表 C.线性链表 D.顺序存储结构 4.如果最常用的操作是取第i个结点及其前驱，则采用 存储方式最节省时间 A.单链表 B.双链表 C.单循环链表 D.顺序表 B D 5.在一个长度为n（n1)的单链表上，设有头和尾两个指针，执行 操作与链表的长度有关。 A.删除单链表中的第一个元素。 B.删除单链表中的最后一个元素。 C.在单链表第一个元素前插入一个新元素。 D.在单链表最后一个元素后插入一个新元素 B 6.如果对线性表的运算只有4种，即删除第一个元素，删除最后一个元素，在第一个元素前插入，在最后一个元素后面插入新元素，则最好使