1、顺序表的基本操作删除 (3)删除第个元素 时间复杂度:O( void Sqdel(sqlist l, int i) for(j=i+;j<L>len;j ++ L→>elem[j-1l=L→>elem[jl: /*上面语句从第i+1个元素开始,一次前移* L→len
顺序表(cont’d) 1、顺序表的基本操作(删除) void Sqdel(SQLIST *L, int i) { int j; for(j=i+1;j<L→len;j++) L→elem[j-1]=L→elem[j]; /*上面语句从第i+1个元素开始，一次前移*/ L→len--; } (3) 删除第i个元素 时间复杂度：O(n)
1、顺序表的基本操作插入 (4)在第个元素后插入 时间复杂度:O(m) int Sqins(sQLIST *L, int i, elemtype x) f int j; if(L→len= MAXSIZE) return-1;/*插入失败* for(j=L→≯en-1;j>=i+1;j-) Elem[j+1Fl-elemjl; L→>elem[i+1=x; L→>len++; return i+l
顺序表(cont’d) 1、顺序表的基本操作(插入) (4) 在第i个元素后插入 时间复杂度：O(n) int Sqins(SQLIST *L ,int i, elemtype x) { int j; if(L→len==MAXSIZE) return -1; /*插入失败*/ for(j=L→len-1;j>=i+1;j--) L→elem[j+1]=L→elem[j]; L→elem[i+1]=x; L→len++; return i+1; }
2、顺序表的操作实例 【例线性表的合并②、时复杂度,0+m void Sqmerge(sQLiST La SQLIST Lb, 依次将La,Lb SOLIST *Lc 中的较小者 续接到c中 i int i=0,j=0, k=0, m, n; 将La或Lb中n=Laen;m= Lb.len;Le-len=m+n; 的剩余部分 whiler(in&&jm) 续接到_c if(Laelemi]. key<=Lbelem[jl. key) Lc→> elema++]= Laelem[i计++l; else lc->elem[k++==Lb elem[j++; while(i<nlc>elem[k++=Laelemi++ while(j<m)Lc-elem( k++|=Lb elem[j++
顺序表(cont’d) 2、顺序表的操作实例 【例】线性表的合并 时间复杂度：O(n+m) void Sqmerge(SQLIST La,SQLIST Lb, SQLIST *Lc) { int i=0,j=0,k=0,m,n; n=La.len;m=Lb.len;Lc→len=m+n; while(i<n&&j<m) if(La.elem[i].key<=Lb.elem[j].key) Lc→elem[k++]=La.elem[i++]; else Lc→elem[k++]=Lb.elem[j++]; while(i<n)Lc→elem[k++]=La.elem[i++]; while(j<m)Lc→elem[k++]=Lb.elem[j++]; } 将La或Lb中 的剩余部分 续接到Lc 依次将La,Lb 中的较小者 续接到Lc中
2、顺序表的操作实例 例】线性表的合并 例如,设 LA=(3,5,8,11)→ LB=(2,6,8,9,11,15,20)->j LC=(2,3,56,8.8,9,11,11,15,20)→>k
顺序表(cont’d) 2、顺序表的操作实例 【例】线性表的合并 例如，设 LA = (3,5,8,11) → i LB = (2,6,8,9,11,15,20) → j 则 LC = (2,3,5,6,8,8,9,11,11,15,20) → k
3.3无之单键表 1、单链表定义 结点:数据元素与指向后继的指针存信在一起称为结点 数据域:结点中存放数据元素的部分 指针域:结点中存放指针的部分 单链表:结点中只有一个指针的链表 链表需要有个指向首结点的指针来标识; 或者用头结点来标识 head a2 a3 an 头结点 a1l12a3…-an
3.3 链表之单链表 1、单链表定义 结点：数据元素与指向后继的指针存储在一起称为结点 数据域：结点中存放数据元素的部分 指针域：结点中存放指针的部分 单链表：结点中只有一个指针的链表 链表需要有个指向首结点的指针来标识； 或者用头结点来标识 a1 a2 a3 an ^ head a1 a2 a3 an ^ L 头结点