人民邮电出版社：高职高专现代信息技术系列教材《数据结构》课程电子教案（PPT课件讲稿）第二章 线性表

第2章线性表 本章主要介绍下列内容 线性表的定义和基本操作 线性表的顺序存储结构 线性表的链式存储结构 线性表的应用举例 请单鼠标左键换页! 退出

第2章 线性表 本章主要介绍下列内容 ⚫ 线性表的定义和基本操作 ⚫ 线性表的顺序存储结构 ⚫ 线性表的链式存储结构 ⚫ 线性表的应用举例 退出

2.1线性表的定义和基本操作 2.2线性表的版序存结构 2.3线性表的链式存值结构 2.4线性表的应用举例 请单赤鼠标左键换页!

2.1 线性表的定义和基本操作 2.2 线性表的顺序存储结构 2.3 线性表的链式存储结构 2.4 线性表的应用举例

2.1线性表的定义和甚 本操作 211线性表的定义 线性表是由n(n≥0)个类型相同的数据元素组 成的有限序列。通常表示成下列形式 L=(ar, a2,-;-,a; a; +1s.., a 其中:L为线性表名称,习惯用大写书写; a1为组成该线性表的数据元素,习惯用小写书写; 线性表中数据元素的个数被称为线性表的长度, 当n=0时,线性表为空,又称为空线性表。 请单鼠标左键换页!

2.1 线性表的定义和基 本操作 2.1.1 线性表的定义 线性表是由n（n≥0）个类型相同的数据元素组 成的有限序列。通常表示成下列形式： L=( a1 , a2 ,...,ai-1 ,ai ,ai+1,...,an ) 其中：L为线性表名称，习惯用大写书写； ai为组成该线性表的数据元素，习惯用小写书写； 线性表中数据元素的个数被称为线性表的长度， 当n=0时，线性表为空，又称为空线性表

举例 La=(34,89,765,12,90,-34,22)数据元 素类型为int Is=(Helo";"word"," China"," Welcome")数据 元素类型为 string Lb=(bok1book2,book100数据元素类型为下列 所示的结构类型: struct bookinfot int no: ∥图书编号 char *name;/图书名称 char *auther, ∥作者名称 请单鼠标左键换页!

举例 La=（34，89，765，12，90，-34，22） 数据元 素类型为int。 Ls=(Hello , World , China , Welcome) 数据 元素类型为string。 Lb=(book1 ,book2 ,...,book100) 数据元素类型为下列 所示的结构类型： struct bookinfo{ int No; //图书编号 char *name; //图书名称 char *auther; //作者名称 ...; }

21.2线性表的基本操作 1.初始化线性表 L Initlist( 2.销毁线性表 L Destorylist(L 3.清空线性表 L Clearlist(L) 4.求线性表L的长度 ListLength(L) 5.判断线性表L是否为空 IsEmpty(L 6.获取线性表L中的某个数据元素内容 Getelem(Li,e) 7.检索值为e的数据元素 Locateelem(I,e) 8.返回线性表L中e的直接前驱元素 Priorelem(L,e) 9.返回线性表L中e的直接后继元素 Nextel(L,e) 10.在线性表L中插入一个数据元素 ListInsert(e) 1l删除线性表L中第个数据元素 Listdelete(L,i,e) 请单赤鼠标左键换页!

2.1.2 线性表的基本操作 1. 初始化线性表L InitList(L) 2. 销毁线性表L DestoryList(L) 3. 清空线性表L ClearList(L) 4. 求线性表L的长度 ListLength(L) 5. 判断线性表L是否为空 IsEmpty(L) 6. 获取线性表L中的某个数据元素内容 GetElem(L,i,e) 7. 检索值为e的数据元素 LocateELem(L,e) 8. 返回线性表L中e的直接前驱元素 PriorElem(L,e) 9. 返回线性表L中e的直接后继元素 NextElem(L,e) 10. 在线性表L中插入一个数据元素 ListInsert(L,i,e) 11. 删除线性表L中第i个数据元素 ListDelete(L,i,e)

2.2线性表的顺序存情结构 221线性表的顺序存储结构 线性表的顺序存储结构是指用一组连续的存储单 元依次存储线性表中的每个数据元素。如下图2-1所示: 请单赤鼠标左键换页!

2.2 线性表的顺序存储结构 2.2.1 线性表的顺序存储结构 线性表的顺序存储结构是指用一组连续的存储单 元依次存储线性表中的每个数据元素。如下图2-1所示：

存储地址内存单元 d+L d+2L d+(i-1)L a d+(n-1)L 图2-1线性表顺序存储结构示意图 请单鼠标左键换页!

存储地址 内存单元 ... d a1 d+L a2 d+2L a3 ... d+(i-1)L ai ... d+(n-1)L an ... ... 图2-1 线性表顺序存储结构示意图

其中,L为每个数据元素所占据的存储单元数目 相邻两个数据元素的存储位置计算公式 LOC(a d=Loc(ai+L 线性表中任意一个数据元素的存储位置的计算公 式为: LOC(aHd=LOC(a+(i-1)*L 顺序存储结构的特点 (1)利用数据元素的存储位置表示线性表中相邻 数据元素之间的前后关系,即线性表的逻辑结构与存 储结构(物理结构)一致; 请单鼠标左键换页!

其中，L为每个数据元素所占据的存储单元数目。 相邻两个数据元素的存储位置计算公式 LOC(ai+1)=LOC(ai )+L 线性表中任意一个数据元素的存储位置的计算公 式为： LOC(ai+1)=LOC(a1 )+(i-1)*L 顺序存储结构的特点 （1）利用数据元素的存储位置表示线性表中相邻 数据元素之间的前后关系，即线性表的逻辑结构与存 储结构（物理结构）一致；

(2)在访问线性表时,可以利用上述给出的数学 公式,快速地计算出任何一个数据元素的存储地址。 因此,我们可以粗略地认为,访问每个数据元素所花 费的时间相等。这种存取元素的方法被称为随机存取 法,使用这种存取方法的存储结构被称为随机存储结 构义 在C语言中,实现线性表的顺序存储结构的类型定 # define Lst maX length100∥线性表的 最大长度 typedef struct Entry Type *item;∥指向存放线性表中数据元 素的基地址 int length;∥线性表的当前长度 ISQ LIST: 请单赤鼠标左键换页!

（2）在访问线性表时，可以利用上述给出的数学 公式，快速地计算出任何一个数据元素的存储地址。 因此，我们可以粗略地认为，访问每个数据元素所花 费的时间相等。这种存取元素的方法被称为随机存取 法，使用这种存取方法的存储结构被称为随机存储结 构。 在C语言中，实现线性表的顺序存储结构的类型定 义 #define LIST_MAX_LENGTH 100 //线性表的 最大长度 typedef struct { EntryType *item; //指向存放线性表中数据元 素的基地址 int length; //线性表的当前长度 }SQ_LIST；

222典型操作的算法实现 1.初始化线性表L int InitList(SQ LIST*L) L->item=(Entry Type*)malloc( LIST MAX LENGTH sizeof( Entry Type);∥分配空间 if(L->item=NULL) return Error;/若分配空间不 成功,返回 ERROR L->length=0; 将当前线性表长度置0 return OK: ∥成功返回OK 请单赤鼠标左键换页!

2.2.2 典型操作的算法实现 1. 初始化线性表L int InitList(SQ_LIST *L) { L->item=(EntryType*)malloc(LIST_MAX_LENGTH *sizeof(EntryType)); //分配空间 if (L->item==NULL) return ERROR; //若分配空间不 成功，返回ERROR L->length=0; //将当前线性表长度置0 return OK; //成功返回OK }