数据结构线性表顺序表ppt课件.ppt

第二章线性表——顺序表*线性结构四大特点第一个元素无直接前驱最后一个元素无直接后继除第一个元素外,其他每个数据元素都有唯一一个直接前驱除最后一个元素外,其他每个数据元素都有唯一一个直接后面*线性表定义记法特点结构基本术语空表、表长直接前驱、直接后继位序最基本、最常用的线性结构。若n(n≥0)个数据特性相同的数据元素组成的有限序列。(a1,a2,…,ai-1,ai,ai+1,…,an)(1对1)、物理结构(顺序存储和链式存储)*线性表的抽象数据类型数据对象数据关系操作集初始化、销毁、查找、插入、删除、求前驱(后继)、遍历线性表中的数据元素具有相同特性相邻数据元素之间存在序偶关系线性表的基本操作声明仅是模型定义,不涉及模型实现,参数不必考虑具体数据类型,实际应用中,具体问题具体分析。*顺序表定义特点C描述基本形态基本操作实现用一组地址连续的存储单元依次存放线性表中的数据元素。采用这种存储结构的线性表叫做顺序表。a1a2…ai-1ai…“逻辑关系上的相邻”用“物理地址相邻”来表示。“随机存取”。*typedefstruct{}SqList;//俗称顺序表#defineMAXSIZE100//线性表存储空间的分配量,即数组长度ElemTypeelem[MAXSIZE];intlength;//当前长度顺序表的C描述*顺序表空:==0不允许删除操作顺序表满:==MAXSIZE不允许插入操作不空也不满:可以插入,删除操作顺序表的基本形态*顺序表----基本算法根据顺序表的实现形式,表长length是类型定义的属性,可以实现求表长、初始化、取值、判空等操作,时间复杂度均为O(1)。而遍历算法、查找表中元素的存在、插入、删除等操作,时间复杂度均为O(n)。*(1)初始化空表时间复杂为:O(1)顺序表----=0;*(2)判空时间复杂为:O(1)顺序表----基本算法if(==0) returnOK;else returnERROR;*