新教案第二章线性表.pptVIP

① p-prior-next=p-next ② p-next-prior=p-prior ③ delete p; ● 双向链表的基本操作 2.3 线性表的链式表示和实现 基本操作删除 删除 a b p 删除前 删除后 c a b p c ① ② ● 两种存储结构的比较 优缺 顺序结构实现的线性表的特点 空间结构简单，易于管理 便于随机访问 有存储上限 增删元素不方便 链式结构实现的线性表的特点 空间结构复杂，不易管理 不能进行随机访问 没有存储上限（仅受物理空间的限制） 便于增删元素 回顾 回顾 ● 线性表链式表示 （1） 单链表（表示、初始化、销毁、插入、删除、创建、查找） （2） 循环链表 （3） 双向链表（表示、插入、删除） a1 a2 L 头结点 a1 a2 head 头结点 a3 rear a1 a2 head a3 ● 表示 2.4 一元多项式的表示和相加 (1)(2,3,0,5,2) (2)((2,0),(3,1),(5,3),(2,4)) 链式表示 2 + 3X + 5X3 + 2X4 一元多项式可看作是以单项式为数据元素的线性表，为方便操作，可约定单项式按指数有序排列。 1+ 3X1000 + 2X2000 2.4 一元多项式的表示和相加 链式表示 2 + 3X + 5X3 + 2X4 ● 链式存储结构描述 struct PolyNode { double coef; //系数 int exp; //指数 PolyNode *next; }; typedef PolyNode * PolyList; 2 3 L 5 2 头结点 0 1 3 4 ● 基本操作 2.4 一元多项式的表示和相加 基本操作 - 初始化、撤消、增删、求导、相乘、相加 ● 相加操作 2 + 3X + 5X3 + 2X4 3+ 2X + 4X2 C=A+B; A,B被保留 A=A+B; B被保留 A=A+B; B被破坏 2.4 一元多项式的表示和相加 基本操作 ● 相加操作 While (两个链都没处理完) { if(指针指向的当前结点指数项相同) { 系数相加，非零则在C链中添加新的结点； A、B链的指针均后移； } else { 指数小的项的系数添入C链的新结点； 指数小的链指针后移； } } While(A链未处理完) { 顺序处理A链；} While(B链未处理完) { 顺序处理B链；} ●相加操作 2.4 一元多项式的表示和相加 基本操作 2 3 A 5 2 头结点 0 1 3 4 例如,多项式 2 + 3X + 5X3 + 2X4和 3+ 2X + 4X2 相加 3 2 B 4 头结点 0 1 2 C 头结点 p1 p2 p3 ●相加操作 2.4 一元多项式的表示和相加 基本操作 2 3 A 5 2 头结点 0 1 3 4 例如,多项式 2 + 3X + 5X3 + 2X4和 3+ 2X + 4X2 相加 3 2 B 4 头结点 0 1 2 5 C 头结点 0 p3 p1 p2 * * 回顾语言基础 　 ● define ● typedef 　　● 指针 　 ● 结构 ● 引用 　 ● 动态内存分配 回顾 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 第二章 线性表 2.3 线性表的链式表示和实现 2.3.1 单链表 2.3.2 循环链表 2.3.3 双向链表 2.4 一元多项式的表示及相加 ● 线性结构的特点 2.1 线性表的类型定义 定义 ● 线性表的定义 一个线性表是n个数据元素的有限序列。 常将非空的线性表记作:(a1，a2，…an) 线性表中元素的个数称为线性表的长度，n=0时为空表。 在数据元素的非空有限集中， （1）存在唯一的一个被称做“第一个”的数据元素； （2）存在唯一的一个被称做“最后一个”的数据元素； （3）除第一个之外，集合中的每个数据元素均只有一个前驱； （4）除最后一个之外，集合中每个数据元素均只有一个后继。 ● 线性表的示例 2.1 线性表的类型定义 示例 例3、学生健康情况登记表如下： ……. ……. ……. …….. …….. 神经衰弱 17 男 790634 张立立 健康 21 男 790633 刘建平