②插入p24算法24 函数rea|lc的格式及功能 格式:void*real|lc(void* p, unsigned size) 功能:将p所指向的已分配内存区域的大小 改为size。 size可以比原来分配的空间大或小
②插入 p24算法2.4 函数realloc的格式及功能 格式： void *realloc(void *p,unsigned size) 功能：将p所指向的已分配内存区域的大小 改为size。 size可以比原来分配的空间大或小
②插入(续) q=&(Lelem[i-1]) for (p=&(L elem[L length-1]: P>=: --p *( )=*p 大q=e; ++. length return OK
②插入（续） q=&(L.elem[i-1]); for (p=&(L.elem[L.length-1]);p>=q;--p) *(p+1) = *p; *q=e; ++L.length; return OK; }
③删除p24p25算法2.5 Status ListDelete_sq(sqList &L, int i, Elem Type &e) f(i<1 i>L length)return ERROR p=&(L elem[i-1]) q=Lelem+ ength-1://表尾 -1)=x fo(++pp<=q;++p)*(P-1)=*p -L length return OK ◆需将第i+1至第 L length个元素向前移动一个位置
③删除 p24~p25算法2.5 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+length-1;//表尾 for (++p;p<=q;++p) *(p-1)=*p; --L.length; return OK } ◆ 需将第i+1至第L.length个元素向前移动一个位置
插入和删除算法时间分析 ■用“移动结点的次数”来衡量时间复杂度。与表长及插 入位置有关 插入 ◆最坏:i=1,移动次数为n ◆最好:ⅰ表长+1,移动次数为0 平均:等概率情况下,平均移动次数n/2 ■删除: ◆最坏:i=1,移动次数为n-1 ◆最好:表长,移动次数为0 ◆平均:等概率情况下,平均移动次数(n-1)/2
插入和删除算法时间分析 ◼ 用“移动结点的次数”来衡量时间复杂度。与表长及插 入位置有关。 ◼ 插入： ◆ 最坏：i=1，移动次数为n ◆ 最好: i=表长+1，移动次数为0 ◆ 平均：等概率情况下，平均移动次数n/2 ◼ 删除： ◆ 最坏：i=1，移动次数为n-1 ◆ 最好: i=表长，移动次数为0 ◆ 平均：等概率情况下，平均移动次数(n-1)/2
查找 p25p26算法26 Int Locatetlem-sq(SqList L, Elem Type while( k<=L length &&e!=L elem[i-1])++i; if (i<=L length)return i; else return 0:
查找 p25~p26算法2.6 int LocateElem_Sq(SqList L, ElemType e) { i=1; while ( i<=L.length && e != L.elem[i-1]) ++i; if (i<=L.length) return i; else return 0; }