chap2-课件-1.ppt

顺序结构线性表的删除算法 在表长为n的线性表中删除第i个数据元素（通常还需将第i+1个至第n个元素向前移动一个位置） int Delete_list(int i, Element s[] , int *n_pointer) { int j,n; n=*n_pointer; if ((i1)||(in)) return (0); for (j=i+1; j=n; j++) s[j-1]=s[j]; n--; *n_pointer=n; return (1); } 插入算法花费的时间，主要在于循环中元素的后移（其它语句花费的时间可以省去），即从插入位置到最后位置的所有元素都要后移一位，使空出的位置插入元素值x。但是，插入的位置是不固定的，当插入位置i=１时，全部元素都得移动，需n次移动，当i=n+１时，不需移动元素，故在i位置插入时移动次数为n-i+1，假设在每个位置插入的概率相等为 ，则平均移动元素的次数为 = 故时间复杂度为O(n)。 同理，可推出删除运算的平均移动次数为 ， 故时间复杂度为O(n)。 顺序结构线