22线性表的顺序表示和实现 Status ListInsert sq(sqlist &L, int i, Elem Type e) if (i<1 l iL length+1 )return ERROR, (L length>=L listsize newbase=(Elem Type *)realloc(L elem L listsize+LISTINCREMENT) *sizeof(Elem Type)); if(! newbase)exit(OVERFLOW) L elem=newbase L listsize+-LISTINCREMENT &Lelem[i-1 for(p=&(, elem[L, length-1),p 3*(p+1 +Llength, return OK
2.2 线性表的顺序表示和实现 Status ListInsert_sq(Sqlist &L, int i, ElemType e) { if (i<1 || i>L.length+1) return ERROR; if (L.length>=L.listsize) { newbase=(ElemType *) realloc(L.elem, ( L.listsize+LISTINCREMENT)*sizeof(ElemType)); if (! newbase) exit(OVERFLOW); L.elem=newbase; L.listsize+=LISTINCREMENT; } q=&(L.elem[i-1]); for (p=&(L.elem[L.length-1]); p>=q; --p) *(p+1)=*p; *q=e; ++L.length; return OK; }
22线性表的顺序表示和实现 删除前:(a1,a2.a1,an,an)、表长:n 后:(a1,a2.a1ia+1an)表长:n-1 向前移动数据元素,以保证“位置相邻”来体现数据元素的顺序 关系 Status List Delete sq(sqlist &L, inti, Elem Type & [if((<) (>L length)return ERROR; =&(Leem-]) L elem+L length-1 o(+p:p<=q,+中)*(p-1) L. length; return OK
2.2 线性表的顺序表示和实现 删除: 前：（a1 ,a2 ,…,ai-1 ,ai ,…,an） 表长：n 后：（a1 ,a2 ,…,ai-1 ,ai+1,…,an ） 表长：n-1 （向前移动数据元素，以保证“位置相邻”来体现数据元素的顺序 关系。） Status ListDelete_sq(Sqlist &L, int i, ElemType &e) { if ((i<1) || (i>L.length)) return ERROR; p=&(L.elem[i-1] ); e=*p; q=L.elem+L.length-1; for (++p; p<=q; ++p ) *(p-1)=*p; --L.length; return OK; }
22线性表的顺序表示和实现 查找 int Locate Elem sq(SqList L, Elem Type e Status( *compare)(Elem Type, ElemType) p=Lelem; while((i<=Llength)&&!(*compare)(p++,e) if(i<-L.length) return i, else return 0
2.2 线性表的顺序表示和实现 • 查找： int LocateElem_sq(SqList L, ElemType e, Status (*compare)(ElemType, ElemType)) { i=1; p=L.elem; while((i<=L.length) && !(*compare)(*p++,e)) ++i; if (i<=L.length) return i; else return 0; }
22线性表的顺序表示和实现 公式(移动数据元素的平均次数) E1/(n+1)*(n+(n-1)+2+1+0)=D/2 E=1/7(1)+(n-2)+212+1+0)=-12 在顺序存储结构的线性表中插入和删除一个数据元素 平均移动表中半元素 若表长为n,则算法 ListInsert sq和 lList Delete s的时间 复杂度为O(n)。 特点 优点:直观、随机存取。 缺点插入删除时,需大量移动数据元素
2.2 线性表的顺序表示和实现 • 公式: (移动数据元素的平均次数) Eins=1/(n+1)*(n+(n-1)+…+2+1+0)=n/2 Edel=1/n*((n-1)+(n-2)+…+2+1+0)=(n-1)/2 在顺序存储结构的线性表中插入和删除一个数据元素， 平均移动表中一半元素。 若表长为n，则算法ListInsert_sq和ListDelete_sq的时间 复杂度为O（n）。 • 特点： 优点：直观、随机存取。 缺点：插入、删除时，需大量移动数据元素
2.3线性表的链式表示和实现 为弥补上述存储结构的不足,引入链式存储结构 线性表的链式表示:用一组任意的存储单元存放数据 元素 链表:动态链表:用指针来实现(单链表、双链表、 循环链表等)。 静态链表:用数组来实现。 单链表建立、查找、插入和删除。 双链表:插入、删除。 循环链表:合并
2.3 线性表的链式表示和实现 为弥补上述存储结构的不足，引入链式存储结构。 • 线性表的链式表示：用一组任意的存储单元存放数据 元素。 • 链表：动态链表：用指针来实现（单链表、双链表、 循环链表等）。 静态链表：用数组来实现。 • 单链表：建立、查找、插入和删除。 • 双链表：插入、删除。 • 循环链表：合并