给 bjwj007 发消息

温馨提示：本信息由会员搜集整理发布，您如有异议可以 举报 或者 版权申诉。

分享链接 分享海报

冲刺必会代码100题
顺序表
1、已知线性表（a1,a2,…,an）按顺序结构存储且每个元素为不相等的整数。设计把所
有奇数移动到所有偶数前边的算法（要求时间最少，辅助空间最少）。
【算法思想】：对于顺序表L，从左向右找到偶数L.data[i]，从右向左找到奇数
L.data[j]，将两者交换。循环这个过程直到i 大于j 为止。对应的算法如下：
void move(SqList &L)
{
int i = 0, j = L.length-1, k;
ElemType temp;
while(i <= j)
{
while(L.data[i]%2 == 1)
i++; //i 指向一个偶数
while(L.data[j]%2 == 0)
j--; //j 指向一个偶数
if(i < j)
{
temp = L.data[i]; //交换L.data[i]和L.data[j]
L.data[i] = L.data[j];
L.data[j] = temp;
}
}
}
本算法的时间复杂度为O(n)，空间复杂度为O(1)。
2、设计一个高效算法，将顺序表L 中所有元素逆置，要求算法的空间复杂度为O(1)。
【算法思想】：扫描顺序表L 的前半部分元素，对于元素L.datai,将其与后半部分对
应元素L.data[L. length-i-1]进行交换。对应的算法如下:
void reverse(