nodelist size nodelist Item maize (a)在t位置插入元素item nodelist size nodelist mize (b)删除t位置的元素
北京大学信息学院 ©版权所有，转载或翻印必究 Page 26
插入算法 (设元素的类型为ELEM, nodelist是存储顺序表的 向量, size是此向量的最大长度, curr en是此向 量的当前长度,curr为此向量当前下标)米/ # include <assert .h> viod insert(ELEM item) ∥需要检査当前长度不能等于msie,当前游标指针 ur不能小于0,也不能大于当前长度 北京大学信息学院 版权所有,转载或翻印必究 Page 27
北京大学信息学院 ©版权所有，转载或翻印必究 Page 27 插入算法 /*（设元素的类型为ELEM，nodelist是存储顺序表的 向量，msize是此向量的最大长度，curr_len是此向 量的当前长度，curr为此向量当前下标）*/ ＃include <assert.h> viod insert(ELEM item) { //需要检查当前长度不能等于msize，当前游标指针 //curr不能小于0,也不能大于当前长度
assert(curr len msize)&&(curr>=0) &&curr <=curr len)); ∥此条件不满足时,程序异常,退出运 ∥0表尾 curr en-1起往右移动直到curr for(int i=curr len; i>curr; i--) nodelist= nodelist i-1 ∥前指针处插入新元素 nodelist curr= item; 表的实际长度 curr en加1 curr len++ 北京大学信息学院 版权所有,转载或翻印必究 Page 28
北京大学信息学院 ©版权所有，转载或翻印必究 Page 28 assert((curr_len < msize) && (curr >= 0) && ( curr <= curr_len)); //此条件不满足时，程序异常，退出运行 //从表尾curr_len-1起往右移动直到curr for(int i=curr_len; i>curr; i--) nodelist[i] = nodelist[i-1]; //当前指针处插入新元素 nodelist[curr] = item; //表的实际长度curr_len加1 curr_len++; }
算法执行时间 元素总个数为k,各个位置插入 的概率相等为p=1/k 平均移动元素次数为 ∑1/k·(k-)≈ i=0 2 总时间开销估计为O(k) 北京大学信息学院 版权所有,转载或翻印必究 Page 29
北京大学信息学院 ©版权所有，转载或翻印必究 Page 29 算法执行时间 ◼ 元素总个数为k，各个位置插入 的概率相等为p＝1/k ◼ 平均移动元素次数为 ◼ 总时间开销估计为O（k） k-1 i 0 1/ ( - ) 2 k k k i = •
删除算法 /(设元素的类型为ELEM, nodelist是存储顺序 表的向量,msie是此向量的最大长度, curr en是此向量的当前长度,curr为此向量 当前下标) 返回cur所指的元素值,并从表中删去此元素 ELEM remove ∥首先需要检验当前长度不能等于0,当前指针 rur不能小于0,不能等于 curr en 北京大学信息学院 版权所有,转载或翻印必究 Page 30
北京大学信息学院 ©版权所有，转载或翻印必究 Page 30 删除算法 /*（设元素的类型为ELEM，nodelist是存储顺序 表的向量，msize是此向量的最大长度， curr_len是此向量的当前长度，curr为此向量 当前下标）*/ //返回curr所指的元素值，并从表中删去此元素 ELEM remove() { //首先需要检验当前长度不能等于0, 当前指针 //curr不能小于0,不能等于curr_len