第二章线性表
第二章 线 性 表
2.1线性表的逻辑结构 2.2线性表的顺序表示和实现 2.3线性表的链式表示和实现 2.4顺序表和链表的比较
2．1 线性表的逻辑结构 2．2 线性表的顺序表示和实现 2．3 线性表的链式表示和实现 2．4 顺序表和链表的比较
2.1线性表的逻辑结构 2.1,1线性表的定义 1.线性表的定义 线性表(linear list)是n(n≥0)个类型相同数据元 素a1,a2,.an组成的有限序列
2．1 线性表的逻辑结构 2.1.1 线性表的定义 1． 线性表的定义 线性表（linear list）是n（n≥0）个类型相同数据元 素a1，a2，…an组成的有限序列
!其中n称为线性表的长度，当O时称为空表： 4通常将非空的线性表记为(a,a2,,a)，数 据元素a,(I≤i≤n)的数据类型可以根据具体情 况而定； 4a.1(2≤i≤n)是a,的直接前驱，有且只有一个： a+(1≤i≤n-1)a的直接后继，有且只有一个； 所有元素的性质是相同的：
其中n 称为线性表的长度，当n=0时称为空表； 通常将非空的线性表记为（a1，a2，…,an），数 据元素ai（1≤i≤n）的数据类型可以根据具体情 况而定； a i-1 (2≤i≤n)是a i 的直接前驱，有且只有一个； a i+1(1≤i≤n-1)a i的直接后继，有且只有一个； 所有元素的性质是相同的；
2.线性表的逻辑结构特征 生有且仅有一个开始结点（表头结点）a,它没有直接 前驱，只有一个直接后继 牛有且仅有一个终端结点（表尾结点）a。,它没有直接 后继，只有一个直接前驱 !其它结点都有一个直接前驱和直接后继 半元素之间为一对一的线性关系
2． 线性表的逻辑结构特征 有且仅有一个开始结点(表头结点)a1，它没有直接 前驱，只有一个直接后继 有且仅有一个终端结点(表尾结点)an，它没有直接 后继，只有一个直接前驱 其它结点都有一个直接前驱和直接后继 元素之间为一对一的线性关系
线性表是一种典型的线性结构，用二元组表示为： linear list =(D,R) 其中 D=fa;1<isn,n20,a,Eelemtype) R={r} ={(a,a+1)|1≤in-1} 对应的逻辑结构图如图所示 1一L2一3—4—L5一46
线性表是一种典型的线性结构，用二元组表示为： linear_list = (D,R) 其中 D={ai ∣1≤i≤n ,n≥0, ai∈elemtype} R={r} r={（ai ,ai+1） ∣1≤i≤n-1} 对应的逻辑结构图如图所示 a1 a2 a3 a4 a5 a6
2.1.2线性表的基本操作 常见线性表的运算有： 1.线性表的初始化Init List(L) 2.求线性表的长度Length List(L) 3.取表元Get List(L,i) 4.求直接前趋Prior(L,x)
2.1.2 线性表的基本操作 常见线性表的运算有： 1．线性表的初始化 Init_List（L） 2． 求线性表的长度 Length_List（L） 3． 取表元 Get_List（L，i） 4．求直接前趋 Prior（L，x）
5.求直接后继Next(L,x) 6.按值查找Locate List(L,x) 7.插入操作Insert List (L,i,x)在线性表L中第 个位置之前插入值为X的元素 8:删除操作Delete List(L,i) 删除线性表L中 第个位置上的元素
5．求直接后继 Next（L，x） 6．按值查找 Locate_List（L，x） 7．插入操作 Insert_List（L，i，x）在线性表L中第 i个位置之前插入值为X的元素 8．删除操作 Delete_List（L，i） 删除线性表L中 第i个位置上的元素
列：设线性表L=(23,56,89,76,18), i=3,x=56y=88, Length List(L); /所得结果为5 Get List(L,i) /所得结果为89 Prior(L,x) /所得结果为23 Next(L,x) 1/所得结果为89 Locate List(L,x) 所得结果为2 Insert(&L,i,y) /所得结果为(23,56,88,89,76,18) Delete(&L,i)1/所得结果为(23,56,76,18)
例: 设线性表L=(23,56,89,76,18), i=3,x=56,y=88, Length_List(L); //所得结果为5 Get_List(L,i) //所得结果为89 Prior(L,x) //所得结果为23 Next(L,x) //所得结果为89 Locate_List(L,x) //所得结果为2 Insert(&L,i,y) //所得结果为(23,56,88,89,76,18) Delete(&L,i) //所得结果为(23,56,76,18)
2.2线性表的顺序表示和实现 2.2.1顺序表 线性表的顺序存储结构，也称为顺序表。 其存储方式为：在内存中开辟一片地址连续存储空 间，但该连续存储空间的大小要大于或等于顺序表的 长度，然后让线性表中第一个元素存放在连续存储空 间第一个位置，第二个元素紧跟着第一个之后，其 余依此类推
线性表的顺序存储结构,也称为顺序表。 其存储方式为：在内存中开辟一片地址连续存储空 间，但该连续存储空间的大小要大于或等于顺序表的 长度，然后让线性表中第一个元素存放在连续存储空 间第一个位置，第二个元素紧跟着第一个之后，其 余依此类推。 2．2 线性表的顺序表示和实现 2.2.1 顺序表