数据结构线性表顺序表.pptx

会计学线性结构四大特点线性表线性表的抽象数据类型顺序表typedefstruct
{

}SqList;//俗称顺序表顺序表空：条件L.length==0
不允许删除操作
顺序表满：
条件L.length==MAXSIZE
不允许插入操作
不空也不满：
可以插入，删除操作顺序表----基本算法（1）初始化（2）判空（3）求表长（4）取元素（取第i个元素顺序表----基本算法顺序表----基本算法例如：顺序表算法的时间复杂度为：顺序表----基本算法线性表操作
ListInsert(&L,i,e)的实现：(a1,…,ai-1,ai,…,an)改变为
(a1,…,ai-1,e,ai,…,an)
必备条件：表存在且不满
i值的合法性检查：1~L.length+1
将第i个到最后1个元素依次后移一个位置；
在i个位置插入元素；
表长增加1。21183075425687O(L.length)插入算法时间复杂度分析：
考虑移动元素的平均情况顺序表----基本算法线性表操作
ListDelete(&L,i,&e)的实现：(a1,…,ai-1,ai,ai+1,…,an)改变为
(a1,…,ai-1,ai+1,…,an)
必备条件：表非空
i值的合法性检查：1~L.length
取出第i个元素；
第i个元素以后的元素向前移动一个位置；
表长减小1。21183075425687算法时间复杂度为:删除算法时间复杂度分析：
考虑移动元素的平均情况时间复杂度为O(1)顺序表----经典算法分析线性表应用举例例1：合并线性表扩大线性表LA，将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去。1．从线性表LB中依次取得每个数据元素;GetElem(Lb,i,e);//取Lb中第i个数据元素赋给e
if(!LocateElem(La,e,equal()))
ListInsert(La,++La_len,e);
//La中不存在和e相同的数据元素，则插入之算法分析例2：归并线性表LC中的数据元素或是LA中的数据元素，或是LB中的数据元素。则先设LC为空表，然后将LA或LB中的元素逐个插入到LC中。为使LC表按值非递减有序排列，可设两个整型变量i、j，分别指向LA和LB，比较i、j所指元素的大小，决定哪个元素插入LC。插入后，在LA或LB中顺序后移。voidMergeList(ListLa,ListLb,List&Lc){
//本算法将非递减的有序表La和Lb归并为Lc

}//merge_listGetElem(La,i,ai);
GetElem(Lb,j,bj);
if(ai<=bj){
ListInsert(Lc,++k,ai);
++i;
}else{
ListInsert(Lc,++k,bj);
++j;
}
while(i<=La_len){//当La不空时
GetElem(La,i++,ai);
ListInsert(Lc,++k,ai);
}//插入La表中剩余元素算法分析voidMergeList(SqListLa,SqListLb,SqList&Lc){
pa=La.elem;pb=Lb.elem;
Lc.length=La.length+Lb.length;
pc=Lc.elem;
pa_last=La.elem+La.length-1;
pb_last=Lb.elem+Lb.length-1;
while(pa<=pa_last&&pb<=pb_last){
if(*pa<=*pb)
*pc++=*pa++;
else
*pc++=*pb++;

}
while(pa<=pa_last) *pc++=*pa++;
while(pb<=pb_last) *pc++=*pb++;
}一元多项式一元多项式