Question

求关于数据结构的一些问题答案

指出以下算法中的错误和低效（即费时）之处，并将它改写为一个既正确又高效的算法。
Status DeleteK(SqList&a, int i, int k){
//本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素
if ( i<1 || k<0 || i+k> a.length ) return INFEASIBLE; //参数不合法
else{
for(count = 1; count <k; count ++ ) {
//删除一个元素
for ( j = a.length; j>=i+1; j--) a.elem[j-1] = a.elem[j];
a.length - -;
}
return OK;
} // DeleteK

注：上题涉及的类型定义如下：
# define LIST INIT SIZE 100
# define LISTINCREMENT 10
typedef struct {
Elem Type *elem; //存储空间基址
Int length; //当前长度
Int listsize; //当前分配的存储容量
}SqList;

Answer 1

Status DeleteK(SqList&a, int i, int k){
//本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素
if ( i<1 || k<0 || i+k> a.length ) return INFEASIBLE; //参数不合法
else{

///循环嵌套,费时费力,时间复杂度很高,改为一个循环即可.
/*for(count = 1; count <k; count ++ ) {
//删除一个元素
for ( j = a.length; j>=i+1; j--) a.elem[j-1] = a.elem[j];
a.length - -;
}
return OK; */

///改正后的
for ( j=i; j<=k+i; j++) a.elem[j] = a.elem[j+k];

} // DeleteK
return OK;