东北大学C语言数据结构ppt讲义

C语言数据结构之线性表类型定义和基本操作 在计算机科学中，线性表是一种基本的数据结构，广泛应用于各个领域。东北大学的C语言数据结构PPT对线性表的定义和基本操作进行了详细的讲解。 **线性表的定义** 线性表是一种最简单的线性结构，具有以下四个基本特征： 1. 集合中必存在唯一的一个“第一元素”； 2. 集合中必存在唯一的一个“最后元素”； 3. 除最后元素在外，均有唯一的后继； 4. 除第一元素之外，均有唯一的前驱。 线性表可以看作是一个数据元素的有序（次序）集。线性表的类型定义可以抽象为抽象数据类型ADTList，包括数据对象、数据关系和基本操作三个部分。 **线性表的类型定义** 抽象数据类型线性表的定义如下： ADTList{ 数据对象： D＝{ai|ai∈ElemSet,i=1,2,,n,n≥0} ∈ {称n为线性表的表长; 称n=0时的线性表为空表 数据关系： R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,,n} ∈ {设线性表为(a1，a2,，ai，，an), 称i为ai在线性表中的位序 } 基本操作： 结构初始化操作 结构销毁操作 引用型操作 加工型操作 } **基本操作** 基本操作包括结构初始化操作、结构销毁操作、引用型操作和加工型操作四种。 1. 结构初始化操作：InitList(&L)，操作结果是构造一个空的线性表L。 2. 结构销毁操作：DestroyList(&L)，操作结果是销毁线性表L。 3. 引用型操作： * ListEmpty(L)：判断线性表L是否为空表，如果为空表则返回TRUE，否则返回FALSE。 * ListLength(L)：返回线性表L中的元素个数。 * PriorElem(L,cur_e,&pre_e)：返回数据元素cur_e的前驱pre_e。 * NextElem(L,cur_e,&next_e)：返回数据元素cur_e的后继next_e。 * GetElem(L,i,&e)：返回线性表L中第i个元素的值。 * LocateElem(L,e,compare())：返回线性表L中元素e的位序。 * ListTraverse(L,visit())：遍历线性表L，并对每个元素进行visit()操作。 这些基本操作是线性表的基础，其他高级操作都是基于这些基本操作的。