数据结构-线性表1.pdf

第二章 线性表 曹迎春 yccao@nju.edu.cn 学习目标 • 了解线性表的逻辑结构特性是数据元素之间存在着线性关 系，在计算机中表示这种关系的两类不同的存储结构是顺 序存储结构和链式存储结构。用前者表示的线性表简称为 顺序表，用后者表示的线性表简称为链表。 • 熟练掌握这两类存储结构的描述方法以及线性表的基本操 作在这两种存储结构上的实现。 • 能够从时间和空间复杂度的角度综合比较线性表两种存储 结构的不同特点及其适用场合。 • 结合线性表类型的定义增强对抽象数据类型的理解。 重点和难点 • 链表是本章的重点和难点。扎实的指针操作和内 存动态分配的编程技术是学好本章的基本要求， 分清链表中指针p 和结点*p 之间的对应关系，区 分链表中的头结点、头指针和首元结点的不同所 指以及循环链表、双向链表的特点等。 知识点 • 线性表 • 顺序表 • 链表 • 有序表 学习指南 • 学习数据结构的目标是为了编出质量更高的程序， 因此重在实践。本章讨论的线性表是学习的第 一种也是最简单的一种数据结构，是整个课程的 基础，特别是熟练掌握链表的操作对以后各章的 学习将有很大帮助。 课前思考 • 抽象数据类型的定义由哪几部分组成？ • 按数据元素之间的逻辑关系不同，数据结 构有哪几类？ • 你能举出几个你熟悉的序列的例子来吗？ 线性结构 • 线性结构是一个数据元素的有序 （次序）集合。 • 四个基本特征： – 集合中必存在唯一的一个“第一元素” ； – 集合中必存在唯一的一个“最后元素” ； – 除最后元素之外，其它数据元素均有唯一的“后继” ； – 除第一元素之外，其它数据元素均有唯一的前驱。 抽象数据类型线性表的定义 • 通常可以下列“ n 个数据元素的序列”表示线性表 (Linear_List)：(a ,a ,…,a ,…,a ) 1 2 i n • 序列中数据元素的个数n 定义为线性表的表长 • n=0 时的线性表被称为空表 • 称i 为a 在线性表中的位序 i • 抽象数据类型的定义 ADT List { a a D＝{ | ∈ElemSet, i=1,2,...,n, n≥0 } i i a a R1＝{ |, , ∈D, i=2,...,n } a ,a i1 i i1 i InitList( L ) DestroyList( 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 ) } ADT List 线性表的基本操作 • 结构初始化 • 结构销毁 • 引用型操作 • 加工型操作