数据结构-第4次课第二章线性表(双向链表多项式).ppt

2 3 3双向链表双向链表 Doublelinkedlist 在单链表的每个结点里再增加一个指向其直接前趋的指针域prior 这样就形成的链表中有两个方向不同的链 故称为双向链表 形式描述为 structDuLNode datatypedata DuLNode prior next 结点 存储前趋结点的地址 存储数据元素 存储后继结点的地址 双链表一般由头指针唯一确定的 将头结点和尾结点链接起来构成循环链表 并称之为双向链表 设指针p指向某一结点 则双向链表结构的对称性可用下式描述 p prior next p p next prior 双向链表结点p前的插入数据x的操作 p x q newDuLNode q data x q prior p prior q next p p prior next q p prior q 双向链表结点p前的插如数据x的操作 p x q newDuLNode q data x q prior p prior q next p p prior next q p prior q 双向链表结点p前的插如数据x的操作 p x q newDuLNode q data x q prior p prior q next p p prior next q p prior q p prior next p next p next prior p prior deletep p 删除p指针所指的结点 p prior next p next p next prior p prior deletep p 删除p指针所指的结点 p prior next p next p next prior p prior deletep p 删除p指针所指的结点 双向链表的插入 删除灵活 链表维护的工作量大 所需的存储空间较大 2 4一元多项式的表示及相加 一 一元多项式的表示多项式的操作是表处理的典型用例 数学上 一元多项式可按升幂写成 在计算机中 可以用一个线性表来表示 P p0 p1 pn 但是对于形如 S x 1 3x10000 2x20000 的多项式 上述表示方法是否合适 一般情况下的一元稀疏多项式可写成Pn x p1xe1 p2xe2 pmxem其中 pi是指数为ei的项的非零系数 0 e1 e2 em n 可以下列线性表表示 p1 e1 p2 e2 pm em P999 x 7x3 2x12 8x999 例如 可用线性表 7 3 2 12 8 999 表示 ADTPolynomial 数据对象 数据关系 抽象数据类型一元多项式的定义如下 D ai ai TermSet i 1 2 m m 0TermSet中的每个元素包含一个表示系数的实数和表示指数的整数 R1 ai 1 ai D i 2 n且ai 1中的指数值 ai中的指数值 CreatPolyn P m DestroyPolyn P PrintPolyn P 基本操作 操作结果 输入m项的系数和指数 建立一元多项式P 初始条件 一元多项式P已存在 操作结果 销毁一元多项式P 初始条件 一元多项式P已存在 操作结果 打印输出一元多项式P PolynLength P AddPolyn Pa Pb SubtractPolyn Pa Pb 相减操作 ADTPolynomial 初始条件 一元多项式P已存在 操作结果 返回一元多项式P中的项数 初始条件 一元多项式Pa和Pb已存在 操作结果 完成多项式相加运算 即 Pa Pa Pb 并销毁一元多项式Pb 二 一元多项式的实现 typedefstruct 表达式中项的表示floatcoef 系数intexpn 指数 term ElemType typedefOrderedLinkListpolynomial 用带表头结点的有序链表表示多项式 结点的数据元素类型定义为 存储结构 用线性链表表示 有头结点 每个结点有coef 系数exp指数next 指针 其中 头结点的exp为 1 多项式A x 7 3x 9x8 5x17 例 求两多项式的和多项式A x 7 3x 9x8 5x17B x 8x 22x7 9x8 二 一元多项式的相加算法 一元多项式相加运算规则 指数相同的项系数相加 A x B x 相加的和多项式为C x A x B x 7 11x 22x7 5x17 设多项式A x B x 分别用带表头结点的线性链表pa pb表示 完成 ha ha hb 一元多项式加法算法主要步骤 分别对两个链表ha hb进行扫描 ha和hb分别指向两个表的头结点 设工作指针pa pb分别指向两个多项式当前进行比较的结点 qa指针指向pa的前驱 qb指针指向pb的前驱 初始 qa ha pa ha next pb hb next 若pa pb都不为空 则比较两者指数 pa expexp qa pa后移 pa exp pb exp 将pb所指结点的系数 加 到pa所指结点的系数上 若和为0 则pa所指结点删除 pb所指结点删除 qa pa qb pb调整 否则pb所指结点删除 qa pa qb pb调整 pa exp pb exp 将表hb中pb所指结点插入到ha表pa所指结点之前 qb pb后移 若pb不空 hb表中从pb开始的结点插入到ha表尾上 intcomp inta intb if anext pb hb next while pa NULL pb qb pb pb next break 1 qb next pb next qa next pb pb next pa pb qb next qa qa next break if pb NULL qa next pb delet