2_线性表.ppt

第二章 线性表 2.1 线性表的类型定义 线性表的定义 线性表举例 ADT List ADT List 关于基本操作集 2.2 线性表的顺序存储及其实现 线性表的顺序存储 元素位置 连续内存申请 顺序表类SqList的定义 SqList的定义 构造函数 析构函数 模板类示例 顺序表初始化 算法2.1 顺序表初始化 异常处理 算法2.2 销毁顺序表 算法2. 3 顺序表插入操作步骤 顺序表插入操作步骤 顺序表插入的类C++语言描述 顺序表删除元素操作步骤 算法2.4 算法2.4 ：删除顺序表中元素算法分析 算法2.5 ：顺序表按值查找类语言描述 2.3 线性表的链式存储及其实现 线性表的链式存储 线性表的链式存储有关概念 单链表的实现：结点定义 单链表类的C++语言描述 续 基本操作实现举例与分析 算法2.6 初始化一个单链表 算法2.7 销毁一个单链表 算法2.8 单链表按位查找类 续 算法2.9 单链表插入元素 算法2.9 单链表插入元素操作步骤 算法2.9 单链表插入元素类 续 算法2.10 单链表删除元素 算法2.10 单链表删除元素 算法2.10 单链表删除元素 续 算法2.11 创建一个单链表 方法二：尾插法 算法2.11 创建一个单链表头插法 其它形式的单链表 循环链表 双向链表 双循环链表 双向链表特性 双向链表中插入结点 (2) 双向链表中结点的删除 2.4 线性表的其它存储方式 顺序存储优、缺点 链式存储优、缺点 静态链表 静态链表示意 续 间接寻址 间接寻址特点 2.5 线性表应用举例 算法2.1类C++语言描述 例2.2: 一元多项式的表示和运算 稀疏多项式表示 结点定义 希疏多项式的链表表示示例 多项式类定义 多项式类定义 操作解析 操作解析 操作解析 操作解析 操作解析 Case 2、3 多项式求和算法描述 本 章 要 点 qa-exp=qb-exp sum=9-9=0 P=P+Q 三 种 情 况： while (qa qb ) // 两个表达式均不空 if (qa) // 表达式PA不空 if (qb) // 表达式PB不空 Case 2: Case 3: Case 1: 1.1 qa.exp qb.exp 1. 2 qa.exp qb.exp 1.3 qa.exp = = qb.exp pa=qa; qa=qa-next ; 结点qb插入到单链表LA的qa结点之前，pa、qb指针分别后移 计算系数和sum = qa-coef+qb-coef 1.3.1 如果sum≠0，修改qa结点系数域，值为sum，qa、pa后移，删除qb结点，qb后移 1.3.2否则，删除qa、qb结点，qa、qb后移， Case 1—两个多项式均不空 Case 2: A不空，B空，则删除B头结点 Case 3: LA空，LB不空，把qb结点为首的链表LB的剩余结点链到链表LA的pa结点之后，删除链表LB的头结点。 类C++语言描述： void Poly：：Add (Poly LB) { pa=head； //初始化 qa=pa-next； pb=LB.head ； qb=pb-next； if (qa-exp qb-exp ) // case 1.1 { pa=qa； qa=qa-next； } else if ( qa-exp qb-exp ) //case 1.2 { pb-next =qb-next； qb-next=qa； pa-next=qb； pa=qb； qb=pb-next； } else //1.3 { sum=qa-coef+qb-coef； if (sum==0 ) //1.3.2 { pa-next=qa-next； delete qa； qa=pa-next； pb-next=qb-next； delete qb； qb=pb-next； }//if }//else else //1.3.1 { qa-coef=sum； pa=qa； qa=qa-next； pb-next=qb-next； delete qb； qb=pb-next； } } }//whi