第2章线性表 数据结构(C艹+描述)
第2章 线性表 数据结构（C++描述）
目录 2.1线性表的定义及其运算 2.2线性表的顺序存储结构 2.3线性表的链式存贮结构 结束放演
目录 2.1 线性表的定义及其运算 2.2线性表的顺序存储结构 ２.３ 线性表的链式存贮结构 结束放演
2.1线性表的定义及其运算 2.1.1线性表的定义 1.线性表的定义 入线性表( linear list)是n(m0)个数据元素a,a2,an组 成的有限序列。其中n称为数据元素的个数或线性表的长 度,当n=0时称为空表,m>0时称为非空表。通常将非空的 线性表记为(a1,a2,…an),其中的数据元素a;(1≤i≤n) 是一个抽象的符号,其具体含义在不同情况下是不同的, 即它的数据类型可以根据具体情况而定,本书中,我们将 它的类型设定为 elemtype,表示某一种具体的已知数据类 型
2.1 线性表的定义及其运算 2.1.1线性表的定义 1． 线性表的定义 线性表（linear list）是n（n≥0）个数据元素a1，a2，…an组 成的有限序列。其中n 称为数据元素的个数或线性表的长 度，当n=0时称为空表，n>0时称为非空表。通常将非空的 线性表记为（a1，a2，…,an），其中的数据元素ai（1≤i≤n） 是一个抽象的符号，其具体含义在不同情况下是不同的， 即它的数据类型可以根据具体情况而定，本书中，我们将 它的类型设定为elemtype，表示某一种具体的已知数据类 型
2.线性表的特征 从线性表的定义可以看出线性表的特征: (1)有且仅有一个开始结点(表头结点a1,它没 有直接前驱,只有一个直接后继; (2))有且仅有一个终端结点(表尾结点an,它没有 后继,只有一个直接前驱 (3)其它结点都有一个直接前驱和直接后继 (4)元素之间为一对一的线性关系
2． 线性表的特征 从线性表的定义可以看出线性表的特征： （1 ） 有且仅有一个开始结点(表头结点)a1，它没 有直接前驱，只有一个直接后继; （2） 有且仅有一个终端结点(表尾结点)an，它没有 直接后继，只有一个直接前驱; （3） 其它结点都有一个直接前驱和直接后继； （ 4）元素之间为一对一的线性关系
线性表是一种典型的线性结构,用二元组表示为: linear list=(A, R) 其中 A={a11≤isnn0,a1∈ elemtype} R={r} {|1sisn1} 对应的逻辑结构图如图2-1所示 图2-1线性表逻辑结构示意图
线性表是一种典型的线性结构，用二元组表示为： linear_list=(A,R) 其中 A={ai ∣1≤i≤n,n≥0,ai∈elemtype} R={r} r={ ∣1≤i≤n-1} 对应的逻辑结构图如图2-1所示。 a1 a2 …… an 图 2-1 线性表逻辑结构示意图
212线性表的运算 常见线性表的运算有 置空表 SETNULL(&L)将线性表L置成空表 2.求长度 LENGTH(L)求给定线性表L的长度 3.取元素GET(L,i)若l≤ length(L),则取第i个位 入置上的元素,否则取得的元素为NUL 4.求直接前趋 PRIOR(L,X)求线性表L中元素值为X 的直接前趋,若ⅹ为第一个元素,前驱为NUL
2.1.2 线性表的运算 常见线性表的运算有： 1．置空表 SETNULL（&L）将线性表L置成空表 2． 求长度 LENGTH（L） 求给定线性表L的长度 3． 取元素 GET（L，i） 若1≤i≤length(L),则取第i个位 置上的元素，否则取得的元素为NULL。 4．求直接前趋 PRI0R（L，X）求线性表L中元素值为X 的直接前趋，若X为第一个元素，前驱为NULL
5.求直接后继NEXT(L,Ⅹ)求线性表L中元素值 为ⅹ直接后继,若ⅹ为最后一个元素,后继为NUL 6.定位函数 LOCaTE(L,x)在线性表L中查找 值为X的元素位置,若有多个值为ⅹ,则以第一个为 准,若没有,位置为0 7.插入 INSERT(&L,X,i)在线性表L中第个 位置上插入值为Ⅹ的元素 8.删除 DELETE(&L,i)删除线性表L中第i个 位置上的元素
5．求直接后继 NEXT（L，X）求线性表L中元素值 为X直接后继，若X为最后一个元素，后继为NULL。 6．定位函数 LOCATE（L，X） 在线性表L中查找 值为X的元素位置，若有多个值为X，则以第一个为 准，若没有，位置为0。 7．插入 INSERT（&L，X，i）在线性表L中第i个 位置上插入值为X的元素。 8．删除 DELETE（&L，i） 删除线性表L中第i个 位置上的元素
213线性表的抽象数据类型描述 上述这些操作可用抽象数据类型描述为: adt Linearlist is Data 个线性表L定义为L(a12a2…,2a),当L=()时定义 为一个空表 operation void setnull(&L)∥.线性表L置成空表 int Length(L)/求给定线性表L的长度 elemtype Get(Li)∥取线性表L第个位置上的元素
2.1.3线性表的抽象数据类型描述 上述这些操作可用抽象数据类型描述为： ADT Linearlist is Data: 一个线性表L定义为L=(a1 ,a2 ,…,an )，当L=（ ）时定义 为一个空表 operation: void setnull(&L) //将线性表L置成空表 int Length(L) //求给定线性表L的长度 elemtype Get(L,i) //取线性表L第i个位置上的元素
gs' elemtype Prior(x)∥求线性表L中元素值为X的直接前 趋 elemtype Next(L2x)/求线性表L中元素值为x的直接 后继 int Locate(L,x)∥在线性表L中查找值为X的元素位 置 void Insert((&Lxi)∥在线性表L中第i个位置上插入 值为X的元素 void Delete((&L,i)∥删除线性表L中第讠个位置上的元 素 END Linearlist
elemtype Prior(L,x) //求线性表L中元素值为X的直接前 趋 elemtype Next(L,x) //求线性表L中元素值为X的直接 后继 int Locate(L,x) //在线性表L中查找值为X的元素位 置 void Insert(&L,x,i) //在线性表L中第i个位置上插入 值为X的元素 void Delete(&L,i) //删除线性表L中第i个位置上的元 素 END Linearlist
:?例21假设线性表L=2356.89,7618)1=3x=56y=88则 对L的一组操作及结果如下 x21egu所得结果为5 Ge(Li)∥所得结果为89 Pior(L,x)所得结果为23 Nex(L,x)∥所得结果为89 Locate((Lx)/所得结果为2 Insert(&L,yi)所得结果为(23,56,8889,76,18) Delete(&L,计+1)∥所得结果为(23,56,88,76,18)
例2-1 假设线性表L=(23,56,89,76,18),i=3,x=56,y=88,则 对L的一组操作及结果如下： Length(L); //所得结果为5 Get(L,i) //所得结果为89 Prior(L,x) //所得结果为23 Next(L,x) //所得结果为89 Locate(L,x) //所得结果为2 Insert(&L,y,i) //所得结果为(23,56,88,89,76,18) Delete(&L,i+1) //所得结果为(23,56,88,76,18)