第2章线性表 线性表抽象数据类型 主顺序表 要单链表 知〈循环单链表 识|循环双向链表 点 静态链表 设计举例
第2章 线性表 主 要 知 识 点 线性表抽象数据类型 顺序表 单链表 循环单链表 循环双向链表 静态链表 设计举例
21线性表抽象数据类型 1线性表的定义 线性表是一种可以在任意位置插入和删除数 据元素操作、由n(m0)个相同类型数据元素a a1…,an组成的线性结构 线性结构:
2.1 线性表抽象数据类型 1.线性表的定义 线性表是一种可以在任意位置插入和删除数 据元素操作、由n(n≥0)个相同类型数据元素a0 , a1 ,…, an-1组成的线性结构。 线性结构:
2线性表抽象数据类型 数据:{an,a1,…,an1},a的数据类型为 Data Type (1) Listlnitiate(L)初始化线性表 (2) Listlength(L)求当前数据元素个数 操作: (3) Listlnserte(L,,x)插入数据元素 (4) ListDelete(L,x)删除数据元素 (5) Listget(Lx)取数据元素 an,a1…,an1}表示数据元素有次序关系简称序列
2.线性表抽象数据类型 数据:｛ a0 , a1 , … , an-1 ｝, ai的数据类型为DataType 操作: (1) ListInitiate(L) 初始化线性表 (2) ListLength(L) 求当前数据元素个数 (3) ListInsert(L,i,x) 插入数据元素 (4) ListDelete(L,i,x) 删除数据元素 (5) ListGet(L,i,x) 取数据元素 ｛ a0 , a1 , … , an-1 ｝表示数据元素有次序关系,简称序列
22线性表的顺序表示和实现 顺序存储结构的线性表称作顺序表 1顺序表的存储结构 实现顺序存储结构的方法是使用数组。数组把线性表的 数据元素存储在一块连续地址空间的内存单元中,这样线性 表中逻辑上相邻的数据元素在物理存储地址上也相邻。数据 元素间的逻辑上的前驱、后继逻辑关系就表现在数据元素的 存储单元的物理前后位置上。 顺序表的存储结构如图际示
2.2 线性表的顺序表示和实现 1.顺序表的存储结构 实现顺序存储结构的方法是使用数组。数组把线性表的 数据元素存储在一块连续地址空间的内存单元中，这样线性 表中逻辑上相邻的数据元素在物理存储地址上也相邻。数据 元素间的逻辑上的前驱、后继逻辑关系就表现在数据元素的 存储单元的物理前后位置上。 顺序表的存储结构如图所示 顺序存储结构的线性表称作顺序表
list o a1 a2 a3( size=60123456 Maxsize-1 其中a0,a1,a2等表示顺序表中存储的数据元素,lis表示 顺序表存储数据元素的数组, Maxsize表示存储顺序表的数 组的最大存储单元个数,size表示顺序表当前存储的数据元 素个数。 typedef struct DataType list MaxSize int size. 3 Seqlist
list a0 a1 a2 a3 a4 a5 … size=6 MaxSize-1 0 1 2 3 4 5 6 其中a0 ,a1 , a2等表示顺序表中存储的数据元素，list表示 顺序表存储数据元素的数组，MaxSize表示存储顺序表的数 组的最大存储单元个数，size表示顺序表当前存储的数据元 素个数。 typedef struct { DataType list[MaxSize]; intsize; } SeqList;