数据结构第二章学案.ppt

2.1 线性表概念及基本操作 2.2 线性表的顺序存储和实现 2.3 线性表的链式存储和实现 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表 2.4 一元多项式的表示及相加; 在本课程介绍的几种数据结构中，线性表是最简单的，也是最常用的数据结构，线性表在实际应用中大量使用，并不是一个陌生的概念。; 基本内容： 1 线性表的概念； 2 线性表两类存储结构和它们的类型定义； 3 在两类存储结构下，线性表基本操作的算法； 学习要点： 1 了解线性表逻辑结构的特征； 2 重点掌握线性表的顺序存储结构和链式存储结构，它们如何表达线性表中数据元素之间的结构关系；如何用C语言描述它们的类型定义； 3 掌握在顺序存储结构下，线性表的基本操作的算法； 4 掌握在链式存储结构下，线性表的基本操作的算法； 5 能够从时间复杂度的角度，比较线性表两类存储结构 的不同特点及适用场合； ; 线性表是n 个类型相同数据元素的有限序列，通常记作:（a1, a2, a3, …, an ）。;说明：设 A=（a1, a2, ... , ai-1, ai , ai+1, …, an ）是一线性表 1） 线性表的数据元素可以是各种各样的，但同一线性表中的元素必须具有相同特性； 2） 在表中 ai-1 领先于ai ，ai 领先于ai+1 ，称ai-1 是ai 的直接前趋，ai+1 是ai 的直接后继； 3） 在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前趋，有且仅有一个直接后继，具有这种结构特征的数据结构称为线性结构； 4） 线性表中元素的个数n称为线性表的长度，n=0时称为空表； 5） ai是线性表的第i 个元素，称i 为数据元素ai 的序号，每一个元素在线性表中的位置，仅取决于它的序号；; 线性表的其他表示方式 二元组表示 L= D,S ，其中D={ a1,a2, a3, ... an} S= {R} R={ a1,a2, a2,a3 , a3,a4 … an-1, an } 图示表示;设L=（a1,a2, ...ai-1, ai , ai+1, …, an ）是一线性表 1 初始化操作 InitList(L) 功能：建立空的线性表L； 2 销毁操作DestroyList(L) 功能：回收为线性表L动态分配的存储空间； 3 置空操作ClearList(L) 功能：L中已存在，重新将其置成空表； 4 判空操作ListEmpty(L) 功能：判断线性表L是否为空表，若为空表返回TRUE，否则返回FALSE； 5 求表长操作 ListLength(L) 功能：返回线性表L的表长； 6 取元素操作：GetElem(L, i, e) 功能：将线性表L中第i 个元素赋值给 e；;7 查找操作 LocateElem (L, e,compare() ) 功能：在线性表L中查找与元素e满足compare()的第1个元素，返回该元素在表中的序号（或位置），若表中不存在这样的元素，则返回0； 8 前驱操作 PriorElem(L,cur_e,pre_e) 功能：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败。 9 后继操作 NextElem(L,cur_e,next_e) 功能：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败。 10 插入操作 ListInsert(L, i, e ) 功能：在线性表L的第i个元素之前插入一个新元素e; 11 删除操作 ListDelete(L, i, e ) 功能：删除线性表L的第i个元素，并用e返回； 12 遍历操作 ListTraverse (L,visit( ) ) 功能：依次对线性表L的每一个元素调用函数visit( )。若visit( )失败，则返回ERROR，否则返回OK；;说明： 1 上面列出的操作，只是线性表的一些常用的基本操作； 2 不同的应用，基本操作可能是不同的； 例如：上面列出的删除操作Delete( L, i, e ), 功能是在线性表L中删除第i个元素，并用e返回其值。 在电话号码查询系统中，一旦某用户撤掉某部电话，则需在系统的电话号码簿中删除该用户对应的数据，因此电话号码查询系统，需要提供这样的功能，在电话号码簿中删除与给定元素e值相同的数据元素； 线性表的复杂操作可通过基本操作