数据结构 设计高效算法问题

Question

如题所述

Answer 1

// 要求是删除顺序表中在范围[x, y]内的元素。
// 按常规思路，每删除一个顺序表元素，则要将其后的元素整体前移一个位置。这种算法用到了双重for循环，时间复杂度为O(n^2)。
// 以下的算法只用到了单重for循环，时间复杂度为O(n)。原理是把所有不在范围[x, y]内的元素依次保存到顺序表的前部，而不处理本来要删除的、在范围[x, y]内的元素。当把所有不需要删除的元素都保存到了顺序表前部，只需要重新设置一下顺序表的长度为“前部”的最大下标+1，就模拟了删除操作。

void fun(SqList *&L, ElemType x)
{
// i为循环计数器。
// j为不需要删除的元素个数，初始化为0。
int i, j = 0;

// 依次遍历顺序表的每个元素
for (i = 0; i < L->length; ++i)
{
// 只处理不需要删除的元素，即不属于区间[x, y]的元素
if (!(L->data[i] >= x && L->data[i] <= y))
{
// 每找到一个不需要删除的元素，就把该元素保存到下标j的位置。
L->data[j] = L->data[i];
// 随后令j自增1。之前j代表的是处理后的顺序表的最大下标，现在j代表的是处理后的顺序表的长度。由于下标从0开始，所以长度永远比最大下标大1。
++j;
}
}

// 设置顺序表的长度为j，这样以后遍历顺序表只能访问前j个元素。即使下标j之后可能还存在属于[x, y]的元素，但是不会访问到它们，自然相当于“删除”了。
L->length = j;
}追问

谢谢！！

Answer 2

1、正确性，首先保证能够解决问题。2、高效性，这样能够保证时间上的优势。3、容错性、程序能妥善处理错误细节。4、可读性、便于交流嘛5、简洁行、尽量不要把问题复杂化。