数据结构线性表顺序表

关于数据结构线性表顺序表线性结构四大特点第一个元素无直接前驱最后一个元素无直接后继除第一个元素外，其他每个数据元素都有唯一一个直接前驱除最后一个元素外，其他每个数据元素都有唯一一个直接后面第2页,共48页，2024年2月25日，星期天线性表定义记法特点结构基本术语空表、表长直接前驱、直接后继位序最基本、最常用的线性结构。若n(n≥0)个数据特性相同的数据元素组成的有限序列。（a1,a2,…,ai-1,ai,ai+1,…,an)1.同一线性表中的数据元素必须具有相同特性2.具有线性结构的四大特性3.数据元素之间存在序偶关系逻辑结构（1对1）、物理结构（顺序存储和链式存储）第3页,共48页，2024年2月25日，星期天线性表的抽象数据类型数据对象数据关系操作集初始化、销毁、查找、插入、删除、求前驱（后继）、遍历线性表中的数据元素具有相同特性相邻数据元素之间存在序偶关系线性表的基本操作声明仅是模型定义，不涉及模型实现，参数不必考虑具体数据类型，实际应用中，具体问题具体分析。第4页,共48页，2024年2月25日，星期天顺序表定义特点C描述基本形态基本操作实现用一组地址连续的存储单元依次存放线性表中的数据元素。采用这种存储结构的线性表叫做顺序表。

a1a2

…ai-1ai

…an基地址1.数据元素在“逻辑关系上的相邻”用“物理地址相邻”来表示。2.顺序表中任一元素都可“随机存取”。第5页,共48页，2024年2月25日，星期天typedefstruct{

}SqList;//俗称顺序表#defineMAXSIZE100//线性表存储空间的分配量，即数组长度ElemTypeelem[MAXSIZE];int

length;//当前长度顺序表的C描述第6页,共48页，2024年2月25日，星期天顺序表空：条件L.length==0

不允许删除操作顺序表满：条件L.length==MAXSIZE

不允许插入操作不空也不满：可以插入，删除操作顺序表的基本形态第7页,共48页，2024年2月25日，星期天顺序表----基本算法根据顺序表的实现形式，表长length是类型定义的属性，可以实现求表长、初始化、取值、判空等操作，时间复杂度均为O(1)。而遍历算法、查找表中元素的存在、插入、删除等操作，时间复杂度均为O(n)。第8页,共48页，2024年2月25日，星期天（1）初始化空表时间复杂为：O(1)顺序表----基本算法L.length=0；第9页,共48页，2024年2月25日，星期天（2）判空时间复杂为：O(1)顺序表----基本算法if(L.length==0) returnOK;else returnERROR;第10页,共48页，2024年2月25日，星期天（3）求表长时间复杂为：O(1)顺序表----基本算法 returnL.length；第11页,共48页，2024年2月25日，星期天（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;}第12页,共48页，2024年2月25日，星期天顺序表----基本算法（5）遍历for(i=1;i<=L.length;i++)visit(L.elem[i-1]);时间复杂为：O(L.length)第13页,共48页，2024年2月25日，星期天顺序表----基本算法（6）查找搜索顺序表中是否存在指定的数据元素。存在，查找成功；否则，查找失败。第14页,共48页，2024年2月25日，星期天例如：顺序表23754138546217L.elem[0]L.length-1e=38i12341850可见，基本操作是：将顺序表中的元素逐个和给定值e相比较。第15页,共48页，2024年2月25日，星期天算法的时间复杂度为：

O(L.length)intLocateElem(SqListL,Elemtypee){ for(i=1;i<=L.length;i++){ if(e==L.elem[i-1]){ returni; } } return0;}第16页,共48页，2024年2月25日，星期天顺序表----基本算法（7）插入在顺序表中插入指定的数据元素，插入成功，表长增1。第17页,共48页，2024年2月25日，星期天线性表操作

ListInsert(&L,i,e)的实现：首先分析:插入元素时，线性表的逻辑结构发生什么变化？第18页,共48页，2024年2月25日，星期天

(a1,…,ai-1,ai,…,an)改变为

(a1,…,ai-1,e,ai,…,an)a1a2

…ai-1ai

…ana1a2

…ai-1

…aiean<ai-1,ai><ai-1,e>,<e,ai>表的长度增加第19页,共48页，2024年2月25日，星期天必备条件：表存在且不满i值的合法性检查：1~L.length+1将第i个到最后1个元素依次后移一个位置；在i个位置插入元素；表长增加1。分析：第20页,共48页，2024年2月25日，星期天2118307542568721183075例如：ListInsert_Sq(L,5,66)

L.length-1087564266第21页,共48页，2024年2月25日，星期天O(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;//插入e L.length++;//表长增1 returnOK;//插入成功

}else{ returnERROR;}}第22页,共48页，2024年2月25日，星期天插入算法时间复杂度分析：考虑移动元素的平均情况插入位置需要移动的结点次数1n2n-1……n1n+10平均次数:(1+2+…+n-1+n)/(n+1)=n/2T(n)=O(n)第23页,共48页，2024年2月25日，星期天顺序表----基本算法（8）删除在顺序表中删除指定位置的数据元素，删除成功，表长减1。第24页,共48页，2024年2月25日，星期天线性表操作

ListDelete(&L,i,&e)的实现：首先分析：删除元素时，线性表的逻辑结构发生什么变化？第25页,共48页，2024年2月25日，星期天

(a1,…,ai-1,ai,ai+1,…,an)改变为

(a1,…,ai-1,ai+1,…,an)ai+1…an<ai-1,ai>,<ai,ai+1><ai-1,ai+1>表的长度减少a1a2

…ai-1ai

ai+1

…ana1a2

…ai-1

第26页,共48页，2024年2月25日，星期天必备条件：表非空i值的合法性检查：1~L.length取出第i个元素；第i个元素以后的元素向前移动一个位置；表长减小1。分析：第27页,共48页，2024年2月25日，星期天2118307542568721183075L.length-10pppq8756例如：ListDelete_Sq(L,5,e)

p第28页,共48页，2024年2月25日，星期天算法时间复杂度为:

O(L.length)StatusListDelete(SqList&L,inti,ElemType&e){if(i>=1&&i<=L.length){ e=L.elem[i-1]; for(j=i+1;j<=L.length;j++)//元素前移

L.elem[j-2]=L.elem[j-1]; L.length--;//表长减1 returnOK;//删除成功

}else{ returnERROR;}}第29页,共48页，2024年2月25日，星期天

删除算法时间复杂度分析：考虑移动元素的平均情况删除位置需要移动的结点次数1n-12n-2……n0平均次数:(0+1+…+n-11)/n=(n-1)/2T(n)=O(n)第30页,共48页，2024年2月25日，星期天时间复杂度为O(1)顺序表----基本算法（9）求前驱pre=L.elem[i-2];在顺序表中查找元素cur_e，位序为ii=LocateElem(L,cur_e);cur_e是顺序表中元素，但不是第一个元素便有直接前驱pre第31页,共48页，2024年2月25日，星期天

顺序表----基本算法（10）求后继next=L.elem[i];在顺序表中查找元素cur_e，位序为ii=LocateElem(L,cur_e);cur_e是顺序表中元素，但不是最后一个元素便有直接后继next时间复杂度为O(1)第32页,共48页，2024年2月25日，星期天顺序表----经典算法分析算法插入删除基本操作移动元素移动元素平均移动次数时间复杂度O(n)O(n)最好情况在n+1处插入，不需移动删除第n个，不需移动第33页,共48页，2024年2月25日，星期天线性表应用举例例1：合并线性表例2：归并线性表第34页,共48页，2024年2月25日，星期天例1：合并线性表假设有两个集合A和B分别用两个线性表LA和LB表示，即：线性表中的数据元素即为集合中的成员。现要求一个新的集合A＝A∪B。——去掉重复元素第35页,共48页，2024年2月25日，星期天扩大线性表LA，将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去。问题分析：第36页,共48页，2024年2月25日，星期天1．从线性表LB中依次取得每个数据元素;2．依值在线性表LA中进行查访;3．若不存在，则插入之。GetElem(LB,i)→e

LocateElem(LA,e,equal())

ListInsert(LA,n+1,e)操作步骤：第37页,共48页，2024年2月25日，星期天

GetElem(Lb,i,e);//取Lb中第i个数据元素赋给e

if(!LocateElem(La,e,equal()))

ListInsert(La,++La_len,e);

//La中不存在和e相同的数据元素，则插入之voidunion(List&La,ListLb){La_len=ListLength(La);//求线性表的长度

Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){}}//union第38页,共48页，2024年2月25日，星期天算法分析时间复杂度：

O(ListLength(LA)*ListLength(LB))空间复杂度：

O(1)第39页,共48页，2024年2月25日，星期天例2：归并线性表已知线性表LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的数据元素仍按值非递减有序排列。——不去掉重复元素第40页,共48页，2024年2月25日，星期天LC中的数据元素或是LA中的数据元素，或是LB中的数据元素。则先设LC为空表，然后将LA或LB中的元素逐个插入到LC中。为使LC表按值非递减有序排列，可设两个整型变量i、j，分别指向LA和LB，比较i、j所指元素的大小，决定哪个元素插入LC。插入后，在LA或LB中顺序后移。问题分析：第41页,共48页，2024年2月25日，星期天voidMergeList(ListLa,ListLb,List&Lc){

//本算法将非递减的有序表La和Lb归并为Lc}//merge_listwhile((i<=La_len)&&(j<=Lb_len))

{……//La和Lb均不空

}while(i<=La_len)

//若La不空while(j<=Lb_len)//若Lb不空InitList(Lc);//构造空的线性表Lci=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);第42页,共48页，2024年2月25日，星期天GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai<=bj){ListInsert(Lc,++k,ai);++i;}else{ListInsert(Lc,++k,bj);++j;}

第43页,共48页，2024年2月25日，星期天

while(i<=La_len){//当La不空时

GetElem(La,i++,ai);ListInsert(Lc,++k,ai);

}

//插入La表中剩余元素

while(j<=Lb_len){//当Lb不空时

GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);

}

//插入Lb表中剩余元素第44页,共48页，2024年2月25日，星期天算法分析时间复杂度：O(ListLength(LA)+Li