数据结构线性表(数据结构).ppt

1. 第一种表示方法 Pn=(a0,a1, … , an) 适用于指数连续排列、 “0”系数较少的情况。但对于指数不全的多项式，如P20000(x) = 3 + 5x50 + 14x20000, 会造成系统空间的巨大浪费。 2. 第二种表示方法 一般情况下，一元多项式可写成： 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)) ADT Polynomial {数据对象: D={ai|ai ∈ TermSet, i=1,2,…,m, m≥0 TermSet中的每个 元素包含一个表示系数的实数和表示 指数的整数} 数据关系：R1={ai-1,ai|ai-1,ai ∈ D,且ai-1 中的指数值ai中的指数值, i=2,…n} }ADT Polynomial 3. 一元多项式的抽象数据类型定义 typedef struct { float coef; int expn; }term, ElemType; 4. 抽象数据类型(Polynomial)的实现 多项式链表的相加 AH = 1 - 10x6 + 2x8 +7x14 BH = - x4 + 10x6 - 3x10 + 8x14 +4x18 两个多项式的相加 结果多项式另存 扫描两个相加多项式，若都未检测完： 若当前被检测项指数相等，系数相加。若未变成 0，则将结果加到结果多项式。 若当前被检测项指数不等，将指数小者加到结果多项式。 若有一个多项式已检测完，将另一个多项式剩余部分复制到结果多项式。 思考题： 2.1线性表的两种存储结构各有哪些优缺点？ 2.2 实现顺序线性表的插入等 算法。 2.3已知线性表的元素按递增顺序排列，并以带头结点的单链表作存储结构。试编写一个删除表中所有值大于min且小于max的元素（若表中存在这样的元素）的算法。 2.3 线性表的链式表示和实现1. 线性链表 特点：在内存中用一组任意的存储单元来存储线性表的数据元素，用每个数据元素所带的指针来确定其后继元素的存储位置。这两部分信息组成数据元素的存储映像，称作结点。 结点：数据域 + 指针域（链域） 链式存储结构：n个结点链接成一个链表 线性链表（单链表）：链表的每个结点只包含一个指针域。 data next 单链表 (Singly Linked List) first 头指针 last 尾指针 ^ 指针为空 单链表由头指针唯一确定，因此常用头指针的名字来命名。如表first. 单链表的存储映像 1）线性链表的描述 p28 typedef struct LNode{ ElemType data; Struct LNode *next; } LNode, *LinkList; LinkList L; //L是LinkList类型的变量， 表示单链表的头指针 2）术语 头指针：指向链表中第一个结点 第一个数据元素结点（开始结点） 头结点：有时在单链表的第一个数据元素结点之前附设一个结点，称之头结点。 说明：头结点的next域指向链表中的第一个数据元素结点。 对于头结点数据域的处理： a.加特殊信息 b.置空 c.如数据域为整型，则在该处存放链表长度信息。 3）带头结点的单链表示意图 p28图2.7 由于开始结点的位置被存放在头结点的指针域中，所以对链表第一个位置的操作同其他位置一样，无须特殊处理。 无论链表是否为空，其头指针是指向头结点的非空指针，因此对空表与非空表的处理也就统一了，简化了链表操作的实现。 非空表 空表 2. 基本操作 1）取元素 p29 算法2.8 2）插入元素 p30 算法2.9 3）删除元素 p30 算法2.10 4）建立链表 p30~p31 算法2.11 5）有序链表的合并 p31 算法2.12 6）查找（按值查找） 7）求长度 8）集合的并运算 取元素（按序号查找） p29 算法2.8 从链表的头指针出发，顺链域next逐个结点往下有哪些信誉好的足球投注网站，直至找到第i个结点为止（j=i) Status GetElem_L(LinkList L, i