中国科学技术大学：《数据结构》课程教学课件（PPT讲稿）第2章 线性表

第2章线性表2.1线性表的基本概念2.2线性表的顺序表示2.3线性表的链式表示2.4线性结构的深入中国科学技术大学ypb@ustc.edu.cn

ypb@ustc.edu.cn 1 中国科学技术大学 第2章 线性表 2.1 线性表的基本概念 2.2 线性表的顺序表示 2.3线性表的链式表示 2.4线性结构的深入

2.1线性表的基本概念·线性表的定义线性表是n(n>=0)个数据元素的有限序列，表中各个元素具有相同地属性，表中相邻元素间存在“序偶”关系。记做：(ai,a2......aj,a,ai+1....,an-1,an)ai-,称为a的直接前驱元素，aii是a;的直接后继元素线性表的长度：表中的元素个数n位序：称元素ai在线性表中的位序中国科学技术大学ypb@ustc.edu.cn

ypb@ustc.edu.cn 2 中国科学技术大学 2.1线性表的基本概念 • 线性表的定义 线性表是n(n>=0)个数据元素的有限序列，表中 各个元素具有相同地属性，表中相邻元素间存 在“序偶”关系。 记做：(a1 ,a2 ,.ai-1 ,ai ,ai+1 ,.,an-1 ,an ) ai-1称为ai 的直接前驱元素，ai+1是ai的直接后继 元素 线性表的长度：表中的元素个数 n 位序：i称元素ai在线性表中的位序

线性表的基本操作ADT List数据对象D=aaElemSet,i=1,2.....n,n0！数据结构:R={<ai-1,a;>ai-1,a;eD,i-2,3,,n)基本操作：InitList(&L)Destroy(&L)ClearList(&L)ListEmpty(L)ListLength(L)GetElem(L,i,&e)1<=i<= ListLength (L)Locateltem(L,e)PriorElem(L,Cur e,&pre_e)NextElem(L,cur_e,&next_e)ListInsert(&L,i,e)1<=<= ListLength (L)+1ListDelete(&L,i,&e)1<=i<= ListLength (L)ListTraverse(L)End ADT List323中国科学技术大学ypb@ustc.edu.cn

ypb@ustc.edu.cn 3 中国科学技术大学 ADT List{ 数据对象:D={ ai |aiElemSet,i=1,2,.,n,n0} 数据结构:R={<ai-1 ,ai>|ai-1 ,aiD,i=2,3,.,n} 基本操作： 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) }End ADT List 线性表的基本操作

【例】对两个线性表La、Lb表示的集合A和B，求一个新集合AAUB算法2.1Va）从Lb中取一个元素，并删除b)在La中查询c）若La中不存在，则将其插入La，重复直至Lb空【例】对两个线性表La、Lb表示的集合A和B，求A=A-B算法2.2a）从Lb中取一个元素，并删除b)在La中查询）若La中存在，则将从La删除，重复直至Lb空中国科学技术大学ypb@ustc.edu.cn

ypb@ustc.edu.cn 4 中国科学技术大学 【例】对两个线性表La、Lb表示的集合A和B，求一个 新集合A＝AUB 算法2.1 a) 从Lb中取一个元素，并删除 b) 在La中查询 c) 若La中不存在，则将其插入La，重复直至Lb空 【例】对两个线性表La、Lb表示的集合A和B ，求 A=A-B 算法2.2 a) 从Lb中取一个元素，并删除 b) 在La中查询 c) 若La中存在，则将从La删除，重复直至Lb空

2.2线性表的顺序表示顺序表线性表的顺序存储表示(C++规范)Const LIST INIT SIZE=100:Const LISTINCREMENT=10:(C规范)#define LIST INIT SIZE 100typedef struct {* elem,Elemtypeintlength;intlistsize;intincrementsize;fSqList;O5中国科学技术大学ypb@ustc.edu.cn

ypb@ustc.edu.cn 5 中国科学技术大学 2.2线性表的顺序表示 • 顺序表——线性表的顺序存储表示 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;