资源描述：
《数据结构(严蔚敏)课件第2章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章线性表8/6/2021第页【课前思考】1.抽象数据类型的定义由哪几部分组成？数据对象、数据关系和基本操作三部分。2.按数据元素之间的逻辑关系不同，数据结构有哪几类？线性结构、树型结构、图状结构和集合四类。3.你能举出几个你熟悉的"序列"的例子来吗？如："0，1，2，…，9","A，B，C，…，Z"。8/6/2021第页【学习目标】1.了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。2.熟练掌握这两
2、类存储结构的描述方法以及线性表的基本操作在这两种存储结构上的实现。3.能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。4.结合线性表类型的定义增强对抽象数据类型的理解。8/6/2021第页【重点和难点】链表是本章的重点和难点。扎实的指针操作和内存动态分配的编程技术是学好本章的基本要求，分清链表中指针p和结点*p之间的对应关系，区分链表中的头结点、头指针和首元结点的不同所指以及循环链表、双向链表的特点等。【知识点】线性表、顺序表、链表、有序表.8/6/2021第页【学习指南】正如课程概况中所提，学习数据结构的目标
3、是为了编出质量更高的程序，因此重在“实践”。本章讨论的线性表是学习的第一种也是最简单的一种数据结构，是整个课程的基础，特别是熟练掌握链表的操作对以后各章的学习将有很大帮助。本章要求必须完成的算法设计题为：2.11，2.19，2.21，2.22，2.24，2.27，2.28，2.37，2.38。其中2.19，2.21和2.37要求书面作业完成。8/6/2021第页线性结构的基本特征为:1．集合中必存在唯一的一个“第一元素”；2．集合中必存在唯一的一个“最后元素”；3．除最后元素在外，均有唯一的后继；4．除第一元素之外，均有唯一的前驱。线性结构
4、是一个数据元素的有序（次序）集线性表是一种最简单的线性结构8/6/2021第页2.1线性表的类型定义2.3线性表类型的实现链式映象2.4一元多项式的表示2.2线性表类型的实现顺序映象8/6/2021第页2.1线性表的类型定义8/6/2021第页抽象数据类型线性表的定义如下：ADTList{数据对象：D＝{ai
5、ai∈ElemSet,i=1,2,...,n,n≥0}{称n为线性表的表长;称n=0时的线性表为空表。}数据关系：R1＝{
6、ai-1,ai∈D,i=2,...,n}{设线性表为(a1，a2,...，ai，...，
7、an),称i为ai在线性表中的位序。}8/6/2021第页基本操作：结构初始化操作结构销毁操作引用型操作加工型操作}ADTList8/6/2021第页InitList(&L)操作结果：构造一个空的线性表L。初始化操作8/6/2021第页结构销毁操作DestroyList(&L)初始条件：操作结果：线性表L已存在。销毁线性表L。8/6/2021第页ListEmpty(L)ListLength(L)PriorElem(L,cur_e,&pre_e)NextElem(L,cur_e,&next_e)GetElem(L,i,&e)LocateEle
8、m(L,e,compare())ListTraverse(L,visit())引用型操作:8/6/2021第页ListEmpty(L)初始条件：操作结果：线性表L已存在。若L为空表，则返回TRUE，否则FALSE。（线性表判空）8/6/2021第页ListLength(L)初始条件：操作结果：线性表L已存在。返回L中元素个数。（求线性表的长度）8/6/2021第页PriorElem(L,cur_e,&pre_e)初始条件：操作结果：线性表L已存在。若cur_e是L的元素，但不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定
9、义。（求数据元素的前驱）8/6/2021第页NextElem(L,cur_e,&next_e)初始条件：操作结果：线性表L已存在。若cur_e是L的元素，但不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。（求数据元素的后继）8/6/2021第页GetElem(L,i,&e)初始条件：操作结果：线性表L已存在，且1≤i≤LengthList(L)。用e返回L中第i个元素的值。（求线性表中某个数据元素）8/6/2021第页LocateElem(L,e,compare())初始条件：操作结果：线性表L已存在，e为给定
10、值，compare()是元素判定函数。返回L中第1个与e满足关系compare()的元素的位序。若这样的元素不存在，则返回值为0。（定位函数）8/6/2021第页ListTrav
