数据结构-线性表1new

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

1、第二章线性表曹迎春yccao@nju.edu.cn学习目标•了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。•熟练掌握这两类存储结构的描述方法以及线性表的基本操作在这两种存储结构上的实现。•能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。•结合线性表类型的定义增强对抽象数据类型的理解。重点和难点•链表是本章的重点和难点。扎实的指针操作和内存动态分配的编程技术是学好本章的基本要求，分清链表中指针p和结

2、点*p之间的对应关系，区分链表中的头结点、头指针和首元结点的不同所指以及循环链表、双向链表的特点等。知识点•线性表•顺序表•链表•有序表学习指南•学习数据结构的目标是为了编出质量更高的程序，因此重在"实践"。本章讨论的线性表是学习的第一种也是最简单的一种数据结构，是整个课程的基础，特别是熟练掌握链表的操作对以后各章的学习将有很大帮助。课前思考•抽象数据类型的定义由哪几部分组成？•按数据元素之间的逻辑关系不同，数据结构有哪几类？•你能举出几个你熟悉的"序列"的例子来吗？线性结构•线性结构是一个数据元素的有序（次序）集合。•四个基本特征：–集合中必存在唯一的一个“第一元

3、素”；–集合中必存在唯一的一个“最后元素”；–除最后元素之外，其它数据元素均有唯一的“后继”；–除第一元素之外，其它数据元素均有唯一的"前驱"。抽象数据类型线性表的定义•通常可以下列“n个数据元素的序列”表示线性表(Linear_List)：(a1,a2,…,ai,…,an)•序列中数据元素的个数n定义为线性表的表长•n=0时的线性表被称为空表•称i为ai在线性表中的位序•抽象数据类型的定义ADTList{D＝{

4、aiai∈ElemSet,i=1,2,...,n,n≥0}R1＝{

5、,,ai1,aiai1ai∈D,i=2,...,n}InitList(&L)Des

6、troyList(&L)ListEmpty(L)ListLength(L)PriorElem(L,cur_e,&pre_e)NextElem(L,cur_e,&next_e)GetElem(L,i,&e)LocateElem(L,e,compare())ListTraverse(L,visit())ClearList(&L)PutElem(&L,i,&e)ListInsert(&L,i,e)ListDelete(&L,i,&e)}ADTList线性表的基本操作•结构初始化•结构销毁•引用型操作•加工型操作结构初始化•InitList(&L)–操作结果：构造一个空的线

7、性表L。结构销毁•DestroyList(&L)–初始条件：线性表L已存在。–操作结果：销毁线性表L。引用型操作•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已存在

8、。–操作结果：若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()为元素的访

9、问函数。–操作结果：依次对L的每个元素调用函数visit()。一旦visit()失败，则操作失败加工型操作•ClearList(&L)–初始条件：线性表L已存在。–操作结果：将L重置为空表。•PutElem(&L,i,&e)–初始条件：线性表L已存在，1≤i≤LengthList(L)。–操作结果：L中第i个元素赋值同e的值。•ListInsert(&L,i,e)–初始条件：线性表L已存在，1≤i≤LengthList(L)+1。–操作结果：在L的第i个元素之前插入新的元素e，L的长度增1。•ListDelete(&L,i,&e)–初始条件：线性表L已存在且非空