③第三章线性表 3.1线性表的类型定义 32顺序存储的线性表 3.3链式存储的线性表 34有序表 3.5顺序表和链表的综合比较 pboustc. edu. cn 中国科学技术大学
ypb@ustc.edu.cn 1 中国科学技术大学 第三章 线性表 3.1 线性表的类型定义 3.2 顺序存储的线性表 3.3 链式存储的线性表 3.4 有序表 3.5 顺序表和链表的综合比较
(B3.1线性表的类型定义 3.1线性表的定义 线性表是n(n>=0)个数据元素的有限序列,表中 各个元素具有相同地属性,表中相邻元素间存 在“序偶”关系。 记做:(a1,a2,a1a1a11…,an1an) a1称为a1的直接前驱元素,a*1是a的直接后继 元素 线性表的长度:表中的元素个数n 位序:i元素a在线性表中的位序 pboustc. edu. cn 中国科学技术大学
ypb@ustc.edu.cn 2 中国科学技术大学 3.1线性表的类型定义 3.1.1线性表的定义 线性表是n(n>=0)个数据元素的有限序列，表中 各个元素具有相同地属性，表中相邻元素间存 在“序偶”关系。 记做：(a1 ,a2 ,…….ai-1 ,ai ,ai+1 ,…,an-1 ,an ) ai-1称为ai 的直接前驱元素，ai+1是ai的直接后继 元素 线性表的长度：表中的元素个数 n 位序：i称元素ai在线性表中的位序
G3.12线性表的基本操作 Initlist(&l) Destroy(&l) Clearlist(&l Listempty(l ListLength(L GetElem(l,i, &e 1 ListLength(l Locateltem(l,e) PriorElem(l, cur e, &pre e) NextElem l, cur e, &next e) ListInsert(&l,i, e) 1<=i<= ListLength(l)+ ListDelete(&l, i, &e)1<=k<= Listlength l) ListTraverse(l pboustc. edu. cn 中国科学技术大学
ypb@ustc.edu.cn 3 中国科学技术大学 InitList(&L) Destroy(&L) ClearList(&L) ListEmpty(L) ListLength(L) GetElem(L,i,&e) 1<=i<= ListLength (L) LocateItem(L,e) PriorElem(L,Cur_e,&pre_e) NextElem(L,cur_e,&next_e) ListInsert(&L,i,e) 1<=i<= ListLength (L)+1 ListDelete(&L,i,&e) 1<=i<= ListLength (L) ListTraverse(L) 3.1.2线性表的基本操作
【例3.4】对两个线性表La、Lb表示的集合A和B,求 一个新集合A=AUB算法3.1四 a)从Lb中取一个元素,并删除 b)在La中查询 c)若La中不存在,则将其插入La,重复直至Lb空 【例3.5】对两个线性表La、Lb表示的集合A和B,求 A=A-B算法3.2D a)从Lb中取一个元素,并删除 b)在La中查询 c)若La中存在,则将从La删除,重复直至Lb空 pboustc. edu. cn 中国科学技术大学
ypb@ustc.edu.cn 4 中国科学技术大学 【例3.4】对两个线性表La、Lb表示的集合A和B，求 一个新集合A＝AUB 算法3.1 a) 从Lb中取一个元素，并删除 b) 在La中查询 c) 若La中不存在，则将其插入La，重复直至Lb空 【例3.5】对两个线性表La、Lb表示的集合A和B ，求 A=A-B 算法3.2 a) 从Lb中取一个元素，并删除 b) 在La中查询 c) 若La中存在，则将从La删除，重复直至Lb空
③32线性表的顺序表示和实现 321顺序表线性表的顺序存储表示 Const List INit size=100;(C++规范) Const LIStincrement=10 # define listⅠ NIT SIZE100(C规范) typ pede struct Elemtype elem int length int listsIze Incrementsize ISalist pboustc. edu. cn 5 中国科学技术大学
ypb@ustc.edu.cn 5 中国科学技术大学 3.2线性表的顺序表示和实现 3.2.1顺序表——线性表的顺序存储表示 Const LIST_INIT_SIZE=100; (C++规范) Const LISTINCREMENT=10; #define LIST_INIT_SIZE 100 (C规范) typedef struct { Elemtype * elem; int length; int listsize; int incrementsize; }SqList;