数据结构课件：第二章 线性表.ppt

数据结构课件：第二章 线性表 本资源主要讲解了数据结构中线性表的概念、类型定义、顺序表示和实现、链式表示和实现、基本操作等内容。 线性表是一个数据元素的有序（次序）集，基本特征包括存在唯一的一个被称作“第一个”的数据元素，存在唯一的一个被称作“最后一个”的数据元素，每个数据元素均只有一个前驱和一个后继。 线性表的长度是表中元素的个数 n（n>=0），位序是元素 ai 在表中的位置数 i。逻辑关系特征是 ai 的直接前驱是 ai-1，ai 的直接后继是 ai+1。 抽象数据类型线性表的定义包括数据对象、数据关系和基本操作。数据对象是集合 D={ai | ai ∈ ElemSet，i=1,2,...,n, n>=0}。数据关系是 R1={<ai-1,ai>|ai-1,ai ∈ D, i=2,...,n}。基本操作包括 InitList(&L)、DestroyList(&L)、ListEmpty(L)、ListLength(L)、GetElem(L, i, &e)、LocateElem(L, e, compare())、PriorElem(L, cur_e, &pre_e)、NextElem(L, cur_e, &next_e)、ListTraverse(L, visit())、ClearList(&L)、PutElem(L, i, &e)、ListInsert(&L, i, e) 和 ListDelete(&L, i, &e)。 线性表的顺序表示和实现是使用数组来存储数据元素，链式表示和实现是使用链表来存储数据元素。两种存储结构的特点是顺序表访问元素的时间复杂度为 O(1)，链表访问元素的时间复杂度为 O(n)。 本资源还提供了一个例子，假设有两个集合 A 和 B 分别用两个线性表 LA 和 LB 表示，即：线性表中的数据元素即为集合中的成员。现要求一个新集合 C 是 A 和 B 的并集，可以使用 ListInsert 和 ListDelete 操作来实现。 本资源为学习数据结构的学生提供了一个系统的讲解线性表的知识点，包括线性表的概念、类型定义、顺序表示和实现、链式表示和实现、基本操作等内容。