第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;
2顺序表操作的实现 (1)初始化 Listlnitiate(l void ListInitiate(seq list*L) >size =0: /*定义初始数据元素个数 (2)求当前数据元素个数 Listlength(L) int ListLength (Seqlist L) return L size
2.顺序表操作的实现 （1）初始化ListInitiate(L) voidListInitiate(SeqList *L) { L->size = 0; /*定义初始数据元素个数*/ } （2）求当前数据元素个数ListLength(L) int ListLength(SeqListL) { return L.size; }
(3)插入数据元素 ListInserte(L,i,x) int ListInsert(Seqlist*L, int i, Data Type x) t int j; for(j= L->size;j>i;j--)L->list[il=L->list[j-1; /*依次后移*/ L->list=x; /插入x*/ >size ++. /元素个数加1*/ return 1
（3）插入数据元素ListInsert(L, i, x) int ListInsert(SeqList *L, int i, DataType x) { int j; for(j = L->size; j > i; j--) L->list[j] = L->list[j-1]; /*依次后移*/ L->list[i] = x; /*插入x*/ L->size ++; /*元素个数加1*/ return 1; }
0 5 MaxSize-1 list 10 11 12 15 16 SIze 012 5 6 MaxSize-1 list 10 11 12 14 15 size=7 插数据x 13
list 10 11 12 14 15 16 list 0 1 2 3 4 MaxSize-1 5 6 i=3 Size=6 size=7 待插数据 x 13 7 10 11 12 13 14 15 16 0 1 2 3 4 MaxSize-1 5 6 7 i=3 size=6 ...
(4)删除数据元素 ListDelete(L,i,x int ListDelete Seq list* L, int i, Data Type *x) int i: *x=L->list; /*保存删除的元素到x中*/ forgj=i+; jsize-l; j++)L->list[j-1=L->list[j; /*依次前移*/ sIze /*数据元素个数减1*/ return 1
（4）删除数据元素ListDelete(L, i, x) int ListDelete(SeqList *L, int i, DataType *x) { int j; *x = L->list[i]; /*保存删除的元素到x中*/ for(j = i +1; j size-1; j++) L->list[j-1] = L->list[j]; /*依次前移*/ L->size--; /*数据元素个数减1*/ return 1; }
MaxSize-l 删除前 list 10 12 13 14 15 16 sIze- 要删的数据x13 0 6 MaxSize-1 删除后 10 15 16 e=6
删除前 list 10 11 12 13 14 15 16 删除后 list 10 11 12 14 15 16 0 1 2 3 4 5 6 MaxSize-1 0 1 2 MaxSize-1 3 4 5 6 i=3 size=7 size=6 要删的数据 x 13 ...