数据结构课件2数据结构课件线性表幻灯片.ppt

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; //term用于本ADT, ElemType为LinkList(在P28定义)的数据对象名 typedef LinkList polynomial; 4. 抽象数据类型(Polynomial)的实现 多项式链表的相加 AH = 1 - 10x6 + 2x8 +7x14 BH = - x4 + 10x6 - 3x10 + 8x14 +4x18 两个多项式的相加 结果多项式另存 扫描两个相加多项式，若都未检测完： 若当前被检测项指数相等，系数相加。若未变成 0，则将结果加到结果多项式。 若当前被检测项指数不等，将指数小者加到结果多项式。 若有一个多项式已检测完，将另一个多项式剩余部分复制到结果多项式。 本章小结 线性表的逻辑结构特点是线性表逻辑结构特点是，只有一个首结点和尾结点；除首尾结点外其他结点只有一个直接前驱和一个直接后继。简言之，线性结构反映结点间的逻辑关系是一对一（1:1）的 线性表顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。 链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。 顺序存储的优点是存储密度大(＝1)，存储空间利用率高。缺点是插入或删除元素时不方便。 链式存储的优点是插入或删除元素时很方便，使用灵活。缺点是存储密度小（1），存储空间利用率低。 事实上，链表插入、删除运算的快捷是以空间代价来换取时间。 顺序/链式存储的优缺点： 1.阅读算法2.8 2.9 2.11 2.12 2.13 2.15 2.16； 2. 阅读并仿写P40 典型例题； 3.编写算法 2-6 2-8 2-9 作业 实验一 线性表的应用 1、掌握线性表的基本操作在两种存储结构上的实现 2、熟练掌握各种链表的操作以及在实际问题中的应用 编写程序实现 2-2 2-3 单链表的就地逆置 2-8 2-9 头指针 指示链表中第一个结点的存储位置，单链表可由头指针唯一确定。 1.整个链表的存取必须从头指针开始，只能往后有哪些信誉好的足球投注网站； 2.最后一个数据元素没有直接后即，则指针为空； 3.数据元素之间的逻辑关系式由节点的指针指示的； 4.只能找后继，不能找前驱。 单链表的存储映象 头结点 在链表的第一个结点之前附设一个结点，头指针指向头结点。设置头结点的目的是统一空表与非空表的操作，简化链表操作的实现。 首元结点 链表中存储线性表中第一个数据元素的结点。 单链表存储结构描述： typedef struct LNode  { ElemType data； struct LNode *next；  }LNode, *LinkList; 取表元素Status GetElem_L(LinkList L, int i, ElemType e) { p = L-next; j = 1; while( p j i){ p = p-next; ++j; } if (!p || ji) return ERROR; e = p-data; return OK; } 2. 单链表上的基本运算 从头指针L出发，从头结点（L-next）开始顺着链域扫描； 用j做计数器，累计当前扫描过的结点数，当j = i 时， 指针p所指的结点就是要找的第i个结点。 在单链