第三讲 线性表(修改版).pptVIP

数据结构 刘晋萍 785297343@ QQ:785297343 第三讲 线性表 线性表的逻辑结构 线性表基本操作的定义 线性表的存储结构 顺序存储结构 链式存储结构 线性表基本操作的实现 基于顺序结构 基于链式结构 顺序存储结构和链式存储结构特点分析 顺序存储结构特点分析 链式存储结构特点分析 学习目标 明确线性表的逻辑结构特性是 数据元素之间存在着线性关系 明确在计算机中表示这种关系的两类不同的存储结构是 顺序存储结构和链式存储结构 用前者表示的线性表简称为顺序表 用后者表示的线性表简称为链表 能够对这两类存储结构进行描述 能够写出线性表的基本操作在这两种存储结构上的实现算法 重点和难点 链表是本章的重点和难点 学好本章的基本要求是 扎实的指针操作和内存动态分配的编程技术 分清链表中指针 p 和结点 *p 之间的对应关系 区分链表中的头结点、头指针和首元结点的不同 学习指南 本章讨论的线性表 是本课程学习的第一种数据结构 是最简单的一种数据结构 是整个课程的基础 熟练掌握链表的操作对以后各章的学习将有很大帮助 本章要求完成一定的算法设计题 和上机实验题 线性表的逻辑结构 用二元组表示： L=（D，R） D={ai | ai ∈ElemSet，i=1，2，……n，n≥0} R={ai-1，ai | ai-1，ai ∈D，i= 2，……n} 序偶 ai-1，ai 表示ai-1是 ai的直接前驱，反之，ai 是 ai-1的直接后继 用图示： 或 （ a1， a2 ，a3，……， an ） 线性表中的数据元素可以是各种各样的，只要是属于同一个集合即可 例如，26个小写英文字母是一个线性表 （a，b，…，z） 同一花色的13张扑克牌可以构成一个线性表 （2，3，4，5，6，7，8，9，10，J，Q，K，A） 线性表基本操作的定义 线性表的操作很多，为讨论方便，将它归为四类： 结构初始化（1个） InitList（L） 操作结果：构造一个空的线性表L 结构销毁（1个） DestroyList( L ) 初始条件：线性表 L 已存在 操作结果：销毁线性表 L 引用型操作（7个） 加工型操作（4个） 线性表基本操作的定义 线性表的操作很多，为讨论方便，将它归为四类： 结构初始化 （1个） 结构销毁（1个） 引用型操作（7个） ListEmpty( L ) 初始条件：线性表L已存在 操作结果：若 L 为空表，则返回 TRUE，否则返回 FALSE ListLength( L ) 初始条件：线性表 L 已存在 操作结果：返回 L 中元素个数 PriorElem( L, cur_e, pre_e ) 初始条件：线性表 L 已存在 操作结果：若 cur_e 是 L 中的数据元素，则用 pre_e 返回它的前驱， 否则操作失败，pre_e 无定义 NextElem( L, cur_e, next_e ) 初始条件：线性表 L 已存在 操作结果：若 cur_e 是 L 中的数据元素，则用 next_e 返回它的后继， 否则操作失败，next_e 无定义 GetElem( L, i, e ) 初始条件：线性表 L 已存在，1≤i≤LengthList(L) 操作结果：用 e 返回 L 中第 i 个元素的值 LocateElem( L, e, compare( ) ) 初始条件：线性表 L 已存在，compare( ) 是元素判定函数 操作结果：返回 L 中第1个与 e 满足关系 compare( ) 的元素的位序 若这样的元素不存在，则返回值为0 ListTraverse(L, visit( )) 初始条件：线性表 L 已存在，visit( ) 为元素的访问函数 操作结果：依次对 L 的每个元素调用函数 visit( )。一旦 visit( ) 失败，则操作失败 加工型操作（4个） 线性表基本操作的定义 线性表的操作很多，为讨论方便，将它归为四类： 结构初始化 （1个） 结构销毁（1个） 引用型操作 （7个） 加工型操作（4个） ClearList( L ) 初始条件：线性表 L 已存在 操作结果：将 L 重置为空表 PutElem( L, i, e ) 初始条件：线性表L已存在，1≤i≤LengthList(L) 操作结果：L 中第 i 个元素赋值同 e 的值 Lis