212线性表的抽象数据类型定义 ADT LinearList Typedef struct List L InitList(L, maxSize); 说明:构造空表L,即表的初始化 ListLength(L); 说明:求表L的长度 IsEmpty L; 说明:判断表L是否为空表 isFull(l); 说明:判断表L是否已“满 GetNode (L,i, e); 说明:取表L中的第个数据元素存入e
ADT LinearList{ Typedef struct List L; InitList(L,maxSize); 说明：构造空表L，即表的初始化 ListLength(L); 说明：求表L的长度 isEmpty(L); 说明：判断表L是否为空表 isFull(L) ; 说明：判断表L是否已“满” GetNode (L,i,e); 说明：取表L中的第i个数据元素存入e 2.1.2 线性表的抽象数据类型定义
LocateNode l, e; 说明:查找表L中值为e的数据元素 LocateNode(, e, low, up) 说明:在表L的loW-up范围内查找值为e的数据元素 InsertNode(L, e, i); 说明:在表L的第个位置插入值为e的新数据元素 InsertNode(L, e); 说明:值为e的数据元素插入到有序表L,保持有序 DeleteNode ( L, i, e); 说明:删除表中第个数据元素,被删元素值存入e ClearList L); 说明:将线性表L清空
LocateNode(L,e); 说明：查找表L中值为e的数据元素 LocateNode(L,e,low,up); 说明：在表L的low-up范围内查找值为e的数据元素 InsertNode (L,e,i); 说明：在表L的第i个位置插入值为e的新数据元素 InsertNode (L,e); 说明：值为e的数据元素插入到有序表L，保持有序 DeleteNode (L,i ,e); 说明：删除表L中第i个数据元素，被删元素值存入e ClearList (L); 说明：将线性表L清空 } ;
22顺序表221线性表的顺序存储结构 将个线性表存储到之斜地址 存地址 0 al Loc ai 计算机中,可以采用许 a Loc a2) 多不同的方法,其中既 简单又自然的是顺序存 白i Loc ai) 储方法:用一组地址连 续的存储单元依它们的 逻辑次序存储线性表的 各个数据元素,称作线 空 CC &a1 性表的顺序存储结构, 简称为顺序表。 图2.1顺序表的示意图
将一个线性表存储到 计算机中，可以采用许 多不同的方法，其中既 简单又自然的是顺序存 储方法：用一组地址连 续的存储单元依它们的 逻辑次序存储线性表的 各个数据元素，称作线 性表的顺序存储结构， 简称为顺序表。 2.2 顺序表 2.2.1线性表的顺序存储结构
设线性表L=(a1,a2;…,an),每个元素占用d个存 储单元,则线性表中第1个元素a的存储位置 Loc(a)和第个元素a的存储地址LOc(aj之间满足 关系: LoC(a +1=Loc(ai)+ d 因此,表中第个元素a的存储位置可通过下式计算: LOC(a=Loc(a1+(i-1)*d 其中,Loc(a1)是第一个元素的地址称为基地址
设线性表L = (a 1 , a 2 ,···, a n )，每个元素占用d个存 储单元，则线性表中第i+1个元素a i+1的存储位置 LOC(a i+1)和第i个元素a i的存储地址LOC(a i )之间满足 关系： LOC(a i+1) = LOC(a i ) + d 因此，表中第i个元素ai的存储位置可通过下式计算： LOC(a i ) = LOC(a 1 ) + (i -1) * d 其中，LOC(a1 )是第一个元素的地址称为基地址
顺序表的特点是 逻辑上相邻的元素其物理位置亦相邻。 222顺序表的基本运算 下面,我们先给出整数表的结构声明 Typedef struct int *elen;∥数据元素数组指针 int Size: ∥线性表中当前元素数目 int maxsize;∥初始化操作中为线性表分配的单元数 JslIst;
顺序表的特点是： 逻辑上相邻的元素其物理位置亦相邻。 2.2.2顺序表的基本运算 下面，我们先给出整数表的结构声明： Typedef struct { int *elem; // 数据元素数组指针 int Size; // 线性表中当前元素数目 int maxSize; // 初始化操作中为线性表分配的单元数 }sqList;