资源描述：
《《数据结构》课件(C语言) 第02章顺序表.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。
1、《数据结构》第2章线性表第2页第2章线性表要求对数据的线性存储结构有较深刻的理解。理解线性表、向量的逻辑特性，熟悉掌握施加于它们的基本操作的算法和应用。重点1.线性表的逻辑特性及存储表示。2.顺序表上元素的操作。第3页基本内容1、线性表的逻辑结构定义和存储结构的描述方法。2、在线性表的顺序存储结构上如何实现基本操作。第2章线性表第4页学习要点1、了解线性表的逻辑结构特性2、掌握线性表顺序存储结构的描述方法3、掌握在顺序存储结构上实现线性表基本操作（查找、插入、删除等）的方法4、知道从时间和空间复杂度的角度分析线性表顺序存储结构
2、的特点及使用场合第2章线性表第5页线性结构的特点在数据元素的非空有限集中，1、线性表的逻辑结构第2章线性表(1)存在唯一的一个被称做“第一个”的数据元素；(2)存在唯一的一个被称做“最后一个”的数据元素；(3)除第一个数据元素之外，集合中的每个数据元素均只有一个前驱；(4)除最后一个数据元素之外，集合中的每个数据元素均只有一个后继。第6页线性表的定义1、线性表的逻辑结构线性表(LinearList)是由元素组成的一种有限序列，是一种具有线性结构特点的数据结构。其中元素的个数为线性表的长度。长度为零的线性表为空表。第7页线性表的
3、形式定义1、线性表的逻辑结构含有n个数据元素的线性表是一个数据结构Linear_list=(D,R)其中D={ai
4、ai∈D0,i=1,2,···,n,n≥0}R={N}N={
5、ai-1,ai∈D0,i=2,3,···,n}D0为某个数据对象N为一个序偶的集合若n>0，则通常将线性表记作L=(a1，a2，···,ai，···,an)(i=1,2,···,n)第8页1、线性表的逻辑结构上述线性表表明了1）同一线性表中的数据元素具有共同特性，属于同一数据对象。此乃线性表的均匀性；2）线性表中各数据元素之间是有位置
6、顺序的，即a1是第一个元素；an是最后一个元素；除a1外，ai（i=2,3,···,n）均有且仅有一个直接前趋ai-1；除an外，ai（i=1,2,···,n-1）均有且仅有一个直接后继ai+1；3）数据元素ai在该线性表中第i（i=1,2,···,n）个位置上；4）线性表中元素的值与元素的位置之间可以有联系，也可以没有联系。第9页可以定义若干种对线性表L的基本操作，其中大多数操作是与线性表的结构有关的函数，其余是查找和更新（插入、删除、修改等）线性表中数据元素的一些操作。1、线性表的逻辑结构(1)初始化操作InitList(
7、Linear_List&L);//初始化线性表，即生成一个空的线性表L。(2)求表长操作intLength(Linear_ListL);//返回给定线性表L的长度，即L中数据元素的个数。线性表的基本操作第10页1、线性表的逻辑结构(3)取表元素操作elemtypeGet(Linear_ListL,inti);/*若1≤i≤Length(L)，则返回给定线性表L中第i个数据元素否则，返回空元素。称i为该数据元素在线性表中的位序。*/(4)求表元素前驱操作elemtypePrior(Linear_ListL,elemtypeelm
8、);/*对于给定线性表L中的一个数据元素elm，若它的位序大于1，则返回elm的前驱；否则返回空元素。*/线性表的基本操作第11页1、线性表的逻辑结构(5)求表元素后继操作elemtypeNext(Linear_ListL,elemtypeelm);/*对于给定线性表L中的一个数据元素elm，若它的位序小于Length(L)，则返回elm的后继；否则返回空元素。*/(6)求表元素位序（即定位）操作intLocate(Linear_ListL,elemtypex);/*给定值x，若给定线性表L中存在其值和x相等的数据元素，则返回
9、表L中第一个值为x的数据元素在线性表中的位序；否则返回值-1。*/线性表的基本操作第12页1、线性表的逻辑结构(7)插入操作Insert(Linear_List&L,inti,elemtypeb)；/*在给定线性表L中第i(1≤i≤Length(L)+1)个数据元素之前插入一个新的数据元素b.当i=Length(L)+1时，表示应将数据元素b插入至表中最后一个元素之后。若i<1或i>Length(L)+1，则此操作无意义。*/(8)删除操作Delete(Linear_List&L,inti)；/*删除给定线性表L中第i(1≤i
10、≤Length(L))个数据元素。若i<1或i>Length(L)，则此操作无意义。*/线性表的基本操作(9)判空表操作StatusEmpty(Linear_ListL)；/*若给定线性表L为空表，则返回布尔值true，否则返回false。*/第13页1、线性表的逻辑结构(1
