资源描述：
《数据结构线性表(顺序表).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章线性表——顺序表线性结构四大特点第一个元素无直接前驱最后一个元素无直接后继除第一个元素外，其他每个数据元素都有唯一一个直接前驱除最后一个元素外，其他每个数据元素都有唯一一个直接后面线性表定义记法特点结构基本术语空表、表长直接前驱、直接后继位序最基本、最常用的线性结构。若n(n≥0)个数据特性相同的数据元素组成的有限序列。（a1,a2,…,ai-1,ai,ai+1,…,an)1.同一线性表中的数据元素必须具有相同特性2.具有线性结构的四大特性3.数据元素之间存在序偶关系逻辑结构（1对1）、物理结构（顺序存储和链式存储）线性表的抽象数据类型数据对象数据关系操作集初始化
2、、销毁、查找、插入、删除、求前驱（后继）、遍历线性表中的数据元素具有相同特性相邻数据元素之间存在序偶关系线性表的基本操作声明仅是模型定义，不涉及模型实现，参数不必考虑具体数据类型，实际应用中，具体问题具体分析。顺序表定义特点C描述基本形态基本操作实现用一组地址连续的存储单元依次存放线性表中的数据元素。采用这种存储结构的线性表叫做顺序表。a1a2…ai-1ai…an基地址1.数据元素在“逻辑关系上的相邻”用“物理地址相邻”来表示。2.顺序表中任一元素都可“随机存取”。typedefstruct{}SqList;//俗称顺序表#defineMAXSIZE100//线性表存储
3、空间的分配量，即数组长度ElemTypeelem[MAXSIZE];intlength;//当前长度顺序表的C描述顺序表空：条件L.length==0不允许删除操作顺序表满：条件L.length==MAXSIZE不允许插入操作不空也不满：可以插入，删除操作顺序表的基本形态顺序表----基本算法根据顺序表的实现形式，表长length是类型定义的属性，可以实现求表长、初始化、取值、判空等操作，时间复杂度均为O(1)。而遍历算法、查找表中元素的存在、插入、删除等操作，时间复杂度均为O(n)。（1）初始化空表时间复杂为：O(1)顺序表----基本算法L.length=0；（2）
4、判空时间复杂为：O(1)顺序表----基本算法if(L.length==0)returnOK;elsereturnERROR;（3）求表长时间复杂为：O(1)顺序表----基本算法returnL.length；（4）取元素（取第i个元素e）时间复杂为：O(1)顺序表----基本算法e=L.elem[i-1];i合法if(i>=1&&i<=L.length){e=L.elem[i-1];returnOK;}else{returnERROR;}顺序表----基本算法（5）遍历for(i=1;i<=L.length;i++)visit(L.elem[i-1]);时间复杂为：O
5、(L.length)顺序表----基本算法（6）查找搜索顺序表中是否存在指定的数据元素。存在，查找成功；否则，查找失败。例如：顺序表23754138546217L.elem[0]L.length-1e=38i12341850可见，基本操作是：将顺序表中的元素逐个和给定值e相比较。算法的时间复杂度为：O(L.length)intLocateElem(SqListL,Elemtypee){for(i=1;i<=L.length;i++){if(e==L.elem[i-1]){returni;}}return0;}顺序表----基本算法（7）插入在顺序表中插入指定的数据元素，
6、插入成功，表长增1。线性表操作ListInsert(&L,i,e)的实现：首先分析:插入元素时，线性表的逻辑结构发生什么变化？(a1,…,ai-1,ai,…,an)改变为(a1,…,ai-1,e,ai,…,an)a1a2…ai-1ai…ana1a2…ai-1…aiean,表的长度增加必备条件：表存在且不满i值的合法性检查：1~L.length+1将第i个到最后1个元素依次后移一个位置；在i个位置插入元素；表长增加1。分析：2118307542568721183075例如：ListInsert_Sq(L,5,66)L.leng
7、th-1087564266O(L.length)算法的时间复杂度为：StatusListInsert(SqList&L,inti,ElemTypee){if(i>=1&&i<=L.length+1){for(j=L.length;j>=i;j--)//元素后移L.elem[j]=L.elem[j-1];L.elem[i-1]=e;//插入eL.length++;//表长增1returnOK;//插入成功}else{returnERROR;}}插入算法时间复杂度分析：考虑移动元素的平均情况插入位置需要移动的结点次数1n2n-1……n1n+1
