2.线性表的类型定义 线性表的抽象数据类型表示(教材P1g ADT List 数据对象:D={a1|1∈ ElemNet,i=1,,n 数据关系:R={a1-1,G1>a1-1,G1∈D,i=2,,n 基本操作: Initlist( &l) /建空表,初始化 Destorylist( &l ) //撤销表,释放内存 int LengthList(L); //求表中元素个数,即表长 Priorelem(L,cure,&pree);/求当前元素cure的前驱 Nextel(L,cure,& next e);/求当前元素cure的后继 ListInsert Before(&L,e);/在第个元素之前插入新的元素e istDelete( &l, i, &e ) //删除第i个元素并返回此元素 ADT List 数据结构 ③◎@
32 二、线性表的抽象数据类型表示(教材P19) ADT List { } ADT List 数据对象： 数据关系： 基本操作： D={ai | ai∈ElemSet, i=1,2,…,n,n≥0} R={< ai –1 , ai > | ai –1 , ai ∈D, i=2,…,n} InitList( &L ); //建空表，初始化 DestoryList( &L ); //撤销表，释放内存 int LengthList( L ); //求表中元素个数，即表长 PriorElem( L, cur_e, &pre_e ); //求当前元素cur_e的前驱 NextElem( L, cur_e, &next_e ); //求当前元素cur_e的后继 ListInsertBefore(&L, i, e ); //在第i个元素之前插入新的元素e ListDelete( &L, i,&e ); //删除第i个元素并返回此元素 2.1 线性表的类型定义
22线性表的顺序表示和实现 顺序表的表示采用顺序存储结构存储的线性表 顺序存储定义:把逻辑上相邻的元素存储在物理 位置上相邻的存储单元中。 简言之:逻相,物理也相↓ 顺序存储方法:用一组地址连续的存储单元依次 存放线性表的数据元素。 数据结构 ③◎@
33 一、顺序表的表示 顺序存储定义：把逻辑上相邻的元素存储在物理 位置上相邻的存储单元中。 采用顺序存储结构存储的线性表 简言之：逻辑相邻，物理也相邻 顺序存储方法：用一组地址连续的存储单元依次 存放线性表的数据元素。 2.2 线性表的顺序表示和实现
22线性表的顺序表示和实现 已知:L=(a,a2,…a1,apa+,…,an) a占k个存储单元 b+1 b+2 i-I b+(i-1) b+(i-1)*k +1 ■■■ n Loc(a)表示线性表第1个元素ml的存储位置, 若每个元素占用k个存储单元 Loc(aid)= Loc(ai ) +k Loc(ai =loc(an+(i-1)*k 数据结构 ③◎@
34 已知：L=（a1,a2,… ai-1,ai,ai+1,…an） b b+1 b+2 b+(maxlen-1) a1 a2 … ai-1 ai ai+1 … an b+(i-1) 占k个存储单元 b+(i-1)*k Loc(ai+1 ) Loc(ai ) 存储单元的个数 = +k Loc(ai ) loc(a1 = +(i ) -1)*k Loc(a1 )表示线性表第1个元素a1的存储位置， 若每个元素占用k个存储单元 2.2 线性表的顺序表示和实现
22线性表的顺序表示和实现 线性表顺序存储结构的特点 1、逻辑上相邻的物理元素,其物理位置上也相邻 2、若已知线性表中第1个元素的存储位置,则线性表中任意 一个元素的位置都可由公式计算得出。 即,线性表的顺序存储结构是一种随机存取的存储结构 例:一个一维数组M,下标范围是0到9,每个数组元素用 相邻的5个字节存储。存储器按字节编址,设存储数组元素 M0的第一个字节的地址是98,则M3的第一个字节的地 址是113。 数据结构 35 ③@
35 线性表顺序存储结构的特点 1、逻辑上相邻的物理元素，其物理位置上也相邻 2、若已知线性表中第1个元素的存储位置，则线性表中任意 一个元素的位置都可由公式计算得出。 即，线性表的顺序存储结构是一种随机存取的存储结构。 例：一个一维数组M，下标范围是0到9，每个数组元素用 相邻的5个字节存储。存储器按字节编址，设存储数组元素 M[0]的第一个字节的地址是98，则M[3]的第一个字节的地 址是 113 。 2.2 线性表的顺序表示和实现
22线性表的顺序表示和实现 线性表的动态分配顺序存储结构 先为顺序表空间设定一个初始分配量,一旦因插入元素而空 间不足时,可为顺序表增加一个固定长度的空间增量。 存储结构描述如下(见教材P22) # define isT INIT size100/存储空间的初始分配量 # define listincrement10/存储空间的分配增量 pede struct y ElemType *elem;/表基址(用指针*elem表示) int length;/表长度(表中有多少个元素) int listsize;//当前分配的表尺寸(字节单位) JSlist; 数据结构 ③◎@
36 先为顺序表空间设定一个初始分配量，一旦因插入元素而空 间不足时，可为顺序表增加一个固定长度的空间增量。 线性表的动态分配顺序存储结构 #define LIST_INIT_SIZE 100 //存储空间的初始分配量 #define LISTINCREMENT 10//存储空间的分配增量 Typedef struct{ ElemType *elem; //表基址(用指针*elem表示） int length; //表长度（表中有多少个元素） int listsize; //当前分配的表尺寸（字节单位） }SqList; 存储结构描述如下（见教材P22）： 2.2 线性表的顺序表示和实现