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()操作。
这些基本操作是线性表的基础,其他高级操作都是基于这些基本操作的。