ds_2010_21数据结构课件

《ds_2010_21数据结构课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章线性表(1)线性表是最常用、最简单的一种线性结构《数据结构》主讲:林华学习目标学习目标1.了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。2.熟练掌握这两类存储结构的描述方法，以及线性表的基本操作在这两种存储结构上的实现。3.能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。4.结合线性表类型的定义增强对抽象数据类型的理解。《数据结构》主讲

2、:林华•重点和难点–链表是本章的重点和难点。扎实的指针操作和内存动态分配的编程技术是学好本章的基本要求。•知识点–线性表、顺序表、链表、有序表《数据结构》主讲:林华2.12.12.12.1线性表的类型定义《数据结构》主讲:林华线性结构是一个有限数据元素的有序（次序）集线性结构的基本特征为:在数据元素的非空有限集合中，11．存在唯一的一个““第一元素””；22．必存在唯一的一个““最后元素””；33．除最后元素之外，均有唯一的后继；44．除第一元素之外，均有唯一的前驱。《数据结构》主讲:林华抽象数据类型线性表的定

3、义如下：ADTList{ADTList{数据对象：D＝{ai

4、ai∈ElemSet,i=1,2,...,n,n≥0}称nn为线性表的表长;称n=0n=0时的线性表为空表。数据关系：R1＝{

5、ai-1,ai∈D,i=2,...,n}设线性表为(a1，a2,...，ai，...，an),称i为《数据结构》主讲ai在线性表中的:林华位序。基本操作：结构初始化操作结构初始化操作结构初始化操作结构初始化操作结构销毁操作结构销毁操作结构销毁操作结构销毁操作引用型操作引用型操作引用型操作引用型操作加工型操作

6、加工型操作加工型操作加工型操作}}ADTADTListList《数据结构》主讲:林华结构初始化操作结构初始化操作结构初始化操作结构初始化操作InitListInitList(&L)(&L)操作结果：构造一个空的线性表L。《数据结构》主讲:林华结构销毁操作结构销毁操作结构销毁操作结构销毁操作DestroyListDestroyList(&L)(&L)初始条件：线性表L已存在。操作结果：销毁线性表L。《数据结构》主讲:林华引用型操作引用型操作::ListEmptyListEmpty(L)(L)ListLengthL

7、istLength(L)(L)PriorElemPriorElem(L,cur_e,&pre_e)(L,cur_e,&pre_e)NextElemNextElem(L,cur_e,&next_e)(L,cur_e,&next_e)GetElemGetElem(L,i,&e)(L,i,&e)LocateElemLocateElem(L,e,compare())(L,e,compare())ListTraverse(LListTraverse(L,visit()),visit())《数据结构》主讲:林华ListEm

8、ptyListEmpty(L)(L)（线性表判空）初始条件：线性表LL已存在。操作结果：若LL为空表，则返回TRUE，否则FALSE。《数据结构》主讲:林华ListLengthListLength(L)(L)（求线性表的长度）初始条件：线性表LL已存在。操作结果：返回LL中数据元素个数。《数据结构》主讲:林华PriorElemPriorElem(L,cur_e,&pre_e)(L,cur_e,&pre_e)（求数据元素的前驱）初始条件：线性表L已存在。若cur_e是L的数据元素，但操作结果：不是第一个，则用pr

9、e_e返回它的前驱，否则操作失败，pre_e无定义。《数据结构》主讲:林华NextElemNextElem(L,cur_e,&next_e)(L,cur_e,&next_e)（求数据元素的后继）初始条件：线性表L已存在。若cur_e是L的数据元素，但操作结果：不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。《数据结构》主讲:林华GetElemGetElem(L,i,&e)(L,i,&e)（求线性表中某个数据元素）初始条件：线性表LL已存在，且11≤ii≤LengthList(L)L

10、engthList(L)。操作结果：用e返回LL中第ii个元素的值。《数据结构》主讲:林华LocateElemLocateElem(L,e,compare())(L,e,compare())（定位函数）初始条件：线性表L已存在，e为给定值，compare()是数据元素判定函数。操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。若这样的数据元素不存在，则返回值为0。