数据结构与算法设计（第二版）课件 第2章 线性表 .pptx

第二章线性表;第一章复习;1.教学目标;3．教学重点：;2.1线性表的定义及逻辑结构;2.1线性表的定义及逻辑结构;2.1线性表的定义及逻辑结构;2.1线性表的定义及逻辑结构;例2-3、在校学生的健康信息表是一个线性表，表中每个学生的信息由学号、姓名、性别、年龄、班级和健康状况等组成;数据元素ai(1≤i≤n)只是一个抽象的符号，其具体含义在不同的情况下可以不同，可以是一个节气，可以是一个数字，可以是一个学生信息。共同的特点就是：一个线性表中的数据元素必须属于同一数据对象。

;表中相邻元素间存在着顺序关系，对于任一对相邻结点

ai，ai+1

ai称为ai+1的前驱，ai+1称为ai的后继;ai，ai+1ai称为ai+1的前驱，ai+1称为ai的后继;ai，ai+1ai称为ai+1的前驱，ai+1称为ai的后继;ai，ai+1ai称为ai+1的前驱，ai+1称为ai的后继;线性表的特点：

线性表由同一类型的数据元素组成，每个ai必须属于同一数据类型。

线性表中的数据元素个数是有限的，表长就是表中数据元素的个数。

存在唯一的“第一个”数据元素；存在唯一的“最后一个”数据元素。

除第一个数据元素外，每个数据元素均有且只有一个前驱元素。

除最后一个数据元素外，每个数据元素均有且只有一个后继元素。;2.1.2线性表的基本操作

(1)初始化InitList(L)

(2)线性表判空EmptyList(L)

(3)求长度LengthList(L)

(4)取元素函数GetList(L,i)

(5)按值查找LocatList(L,x)

(6)插入操作InsertList(L,i,x)

(7)删除操作DeleteList(L,i);2.2线性表的顺序存储结构;线性表的顺序存储结构可用C语言定义如下：;线性表的顺序存储结构可用C语言定义如下：;SeqList*L；;2.2.2顺序表上插入与删除操作的实现;2.2.2顺序表上插入与删除操作的实现;2.2.2顺序表上插入与删除操作的实现;本算法的主要运算是比较。;3插入运算;1intInsertList(SeqList*Lp,inti,datatypex)

2{intj;

3if(Lp-last==MAXSIZE-1)

4{printf(″表满″);

5return(-1);

6}

if(i1||iLp-last+2)

{printf(??位置错″);

9return(0);

10}

for(j=Lp-last;j=i-1;j--)

Lp-elem[j+1]=Lp-elem[j];

13Lp-elem[i-1]=x;/*新元素插入*/

14Lp-last++; /*last仍指向最后元素*/

15return(1); /*插入成功，返回*/

16};1intInsertList(SeqList*Lp,inti,datatypex)

2{intj;

3if(Lp-last==MAXSIZE-1)

4{printf(″表满″);

5return(-1);

6}

if(i1||iLp-last+2)

{printf(″位置错″);

9return(0);

10}

for(j=Lp-last;j=i-1;j--)

Lp-elem[j+1]=Lp-elem[j];

13Lp-elem[i-1]=x;/*新元素插入*/

14Lp-last++; /*last仍指向最后元素*/

15return(1); /*插入成功，返回*/

16}