《数据结构》课程教学课件（讲稿，C语言描述）第2章 线性表

第2章线性表数据结构j（C描述）

第2章 线性表 数据结构（C描述）

目 录2.1线性表的定义及其运算2.2线性表的顺序存储结构2.33线性表的链式存贮结构本章作业

目 录 2.1 线性表的定义及其运算 2.2线性表的顺序存储结构 2.3 线性表的链式存贮结构 本章作业

2.1线性表的定义及其运算2.1.1线性表的定义1．线性表的定义线性表（linear list）是n（n≥0）个数据元素ay，a2，..a,组成的有限序列。其中n称为数据元素的个数或线性表的长度，当n=0时称为空表，n>0时称为非空表。通常将非空的线性表记为（aj，a，,a,），其中的数据元素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 有且仅有一个开始结点(表头结点)aj，它没有直接前驱，只有一个直接后继：(2)有且仅有一个终端结点(表尾结点)a，它没有直接后继，只有一个直接前驱；其它结点都有一个直接前驱和直接后继；3)4)元素之间为一对一的线性关系

2． 线性表的特征 从线性表的定义可以看出线性表的特征： （1 ） 有且仅有一个开始结点(表头结点)a1，它没 有直接前驱，只有一个直接后继; （2） 有且仅有一个终端结点(表尾结点)an，它没有 直接后继，只有一个直接前驱; （3） 其它结点都有一个直接前驱和直接后继； （ 4）元素之间为一对一的线性关系

线性表是一种典型的线性结构，用二元组表示为linear list-(A,R)其中A={a, I 10,a, Eelemtype}R=(r)r=[ 1<i<n-1}对应的逻辑结构图如图2-1所示，aiLr图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 线性表逻辑结构示意图

2.1.2线性表的运算常见线性表的运算有：1.置空表ClearList（&L）将线性表L置成空表2．求长度 ListLength（L）求给定线性表L的长度3．取元素 GetElem （L,i.e）若1<i<length(L),则取 第i个位置上的元素用e返回，否则取得的元素为NULL。4．求直接前趋 PriorElem（L，X,&pre e）求线性表L中元素值为X的直接前趋用pre e返回，若X为第一个元素前驱为NULL

2.1.2 线性表的运算 常见线性表的运算有： 1．置空表 ClearList（&L）将线性表L置成空表 2． 求长度 ListLength（L） 求给定线性表L的长度 3． 取元素 GetElem（L,i,e） 若1≤i≤length(L),则取 第i 个位置上的元素用e返回，否则取得的元素为NULL。 4．求直接前趋 PriorElem（L，X,&pre_e）求线性表L中 元素值为X的直接前趋用pre_e返回，若X为第一个元素， 前驱为NULL

5．求直接后继 NextElem（L，X,&next e）求线性表L中元素值为X直接后继用nexte返回，若X为最后一个元素，后继为NULL。6．定位函数 LocateElem（L,X）在线性表L中查找值为X的元素位置，若有多个值为X，则以第一个为准，若没有，位置为0。7．插入ListInsert（&L，i，X）在线性表L中第i个位置上插入值为X的元素。8. 删除ListDelete（&L，i）删除线性表L中第i个位置上的元素

5．求直接后继 NextElem（L，X,&next_e）求线性 表L中元素值为X直接后继用next_e返回，若X为最 后一个元素，后继为NULL。 6．定位函数 LocateElem（L,X） 在线性表L中查找 值为X的元素位置，若有多个值为X，则以第一个为 准，若没有，位置为0。 7．插入 ListInsert（&L，i，X）在线性表L中第i个 位置上插入值为X的元素。 8．删除 ListDelete（&L，i） 删除线性表L中第i个 位置上的元素

2.1.3线性表的抽象数据类型描述上述这些操作可用抽象数据类型描述为：ADT List (Data:一个线性表L定义为L=(ai,a2.…,an)，当L=（）时定义为一个空表operation:voidClearList(&L）//将线性表L置成空表intListLength(L)//求给定线性表L的长度1/取线性表L第i个位置上的elemtype GetElem(L,I,&e)元素

2.1.3 线性表的抽象数据类型描述 上述这些操作可用抽象数据类型描述为： ADT List { Data: 一个线性表L定义为L=(a1 ,a2 ,.,an )，当L=（ ）时定义 为一个空表 operation: void ClearList(&L) //将线性表L置成空表 int ListLength(L) //求给定线性表L的长度 elemtype GetElem(L,I,&e) //取线性表L第i个位置上的 元素

elemtype PriorElem(L,x,&pre e）//求线性表L中元素值为X的直接前趋elemtype NextElem(L,x,&next_e) //求线性表L中元素值为X的直接后继intLocateElem(L,x)//在线性表L中查找值为X的元素位置voidListInsert(&L,x,i)//在线性表L中第i个位置上插入值为X的元素voidListDelete(&L,i)//删除线性表L中第i个位置上的元素}ADT List

elemtype PriorElem(L,x,&pre_e) //求线性表L中元素值 为X的直接前趋 elemtype NextElem(L,x,&next_e) //求线性表L中元素 值为X的直接后继 int LocateElem(L,x) //在线性表L中查找值为X的元 素位置 void ListInsert(&L,x,i) //在线性表L中第i个位置上插 入值为X的元素 void ListDelete(&L,i) //删除线性表L中第i个位置上 的元素 }ADT List

例2-1 假设线性表L=(23,56,89,76,18),i=3,x=56,y=88,则对L的一组操作及结果如下：1/所得结果为5ListLength(L);//所得结果为89GetElem(L,i)//所得结果为23PriorElem(L,x)//所得结果为89NextElem(L,x)//所得结果为2LocateElem(L,x)）//所得结果为(23,56,88,89,76,18)ListInsert(&L,y,i)ListDelete(&L,i+1)//所得结果为(23,56,88,76,18)

例2-1 假设线性表L=(23,56,89,76,18),i=3,x=56,y=88,则 对L的一组操作及结果如下： ListLength(L); //所得结果为5 GetElem(L,i) //所得结果为89 PriorElem(L,x) //所得结果为23 NextElem(L,x) //所得结果为89 LocateElem(L,x) //所得结果为2 ListInsert(&L,y,i) //所得结果为(23,56,88,89,76,18) ListDelete(&L,i+1) //所得结果为(23,56,88,76,18)