- 1.奇数移到偶数前
- 2.顺序表元素逆置
- 3.两个有序表合并保持有序
- 4.删除顺序表最小值元素
- 5.删除所有值为x的元素
- 6.删除值在x~y之间的所有数据
- 7.元素循环左移指定长度
题目：已知线性表（a1,a2,…,an）按顺序结构存储且每个元素为不相等的整数。
设计把所有奇数移动到所有偶数前边的算法（要求时间最少，辅助空间最少）。
【算法思想】：对于顺序表 L，从左向右找到偶数 L.data[i]，从右向左找到奇数 L.data[j]，将两者交换。
循环这个过程直到 i 大于 j 为止。
对应的算法如下：
时间复杂度O(n)，空间复杂度O(1)
void move(SqList &L)
{
int i=0,j=L.length-1,k;
ElemType temp;
while(i题目：设计一个高效算法，将顺序表 L 中所有元素逆置，要求算法的空间复杂度为 O(1)。
【算法思想】：扫描顺序表 L 的前半部分元素，对于元素 L.data[i],将其与后半部分对应元素 L.data[L.length-i-1]进行交换。
对应的算法如下:
void reverse(SqList &L)
{
int i;
ElemType x;
//只扫描前半部分
for(i=0;i=L.length/2;i++)
{
x=L.data[i];
//L.data[i]后半部分对应元素为L.data[L.length-i-1]
/*
角标 0 1 2 3 4 5 6
元素 a b c d e f g
长度 length=7
L.data[0]=L.data[L.length-0-1]=L.data[7-1-0]=L.data[6]
*/
L.data[i]=L.data[L.length-i-1];
L.data[L.length-i-1]=x;
}
}
题目：将两个有序表合并为一个新的有序顺序表，并由函数返回结果顺序表。
【算法思想】 基本思路：首先，按照顺序不断取下两个顺序表表头较小的结点存入新的顺序表中。
然后，看看哪个表还有剩余，将剩下的部分加到新的顺序表后面。
下面，我们在此基本思路上进行具体举例及详解： 将两个非递减有序顺序表 A 和 B 合并成一个新的非递减有序的顺序表 C，可以用 三个数组指针 i、j、k 分别指向 A、B、C 三个数组。
数组中 A、B、C 的合并过 程以及元素的变化如下图所示。
图中，首先数组 A 的第 0 个元素与数组 B 的第 0 个元素相比较，发现 1 小于 4，将 1 加入顺序表 C，i++，k++；插入元素 2、3 皆是如此；当 i=4 时，数组 A 的元素 5 与数组 B 的元素 4 作比较，发现 5 大于 4，于是将 4 加入顺序表 C， j++，k++；如此比较下去，直到将 A 表中的元素全部插入到 C 表中。
当 A 的元 素已经全部插入到 C 表中，而另一个表 B 还有元素没有插入，则直接将表 B 剩 余的元素插入到表 C 中。
bool Merge(SqList A, SqList B, SqList &C)
{
//表长超过
if(A.length+B.length>C.length)
return false;
int i=0,j=0,k=0;
//循环将A，B元素两两比较，将较小数存入C中
while(i题目：从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删除元素的 值。
空出的位置由最后一个元素填补。
**【算法思想】**搜素整个顺序表，查找最小值元素并记在其位置，搜索结束后用最后一个元素填 补空出的原最小值元素的位置。
bool Delete_Min(SqList &L,ElemType &value)
{
//表长为0不成立
if(L.length==0)
return false;
//假设第一个元素为最小值
value=L.data[0];
//记录最小值元素下标
int pos=0;
int i;
//从第二个元素开始比较
for(i=1;i题目：已知长度为 n 的线性表 L 采用顺序存储结构,编写一个时间复杂度为 O(n)、空间 复杂度为 O(1)的算法,该算法删除线性表中所有值为 x 的数据元素。
【算法思想】
解法 1：用 k 记录顺序表 L 中等于 x 的元素个数,边扫描 L 边统计 k,并将不为 x 的元 素前移 k 位,最后修改 L 的长度。
对应的算法如下:
void del_x(SqList &L, ElemType x)
{
//k用于记录x的个数
int k,i=0;
while(i解法 2：用 i 从头开始遍历顺序表 L，k 置初始 0。
若 L.data[i]不等于 x，则将其存放在 L.data[k]中，k 增 1;若 L.data[i]等于 x，则跳过继续判断下一个元素。
最后顺序表长度置为 k。
对应算法如下。
void del_x(SqList &L,ElemType x)
{
int i;
int k=0;
for(i=0;i题目：设计一个算法，从一给定的顺序表 L 中删除元素值在 x 到 y(x≤y)之间的所有元素， 要求以较高的效率来实现，空间复杂度为 O(1)。
【算法思想】
解法一：本题是上述题目的变形。
可以采用上述解法一的方法，只是将 L.data[i] == x 的条件改成 L.data[i] >= x && L.data[i] <= y。
void del_xy(SqList &L, ElemType x, ElemType y)
{
int i;
int k=0;
for(i=0;i=x&&L.data[j]<=y)
{
L.data[k]=L.data[i];
k++;
}
}
L.length=k;
}
解法二：
void del_xy(SqList &L,ElemType x, ElemType y)
{
int i=0,k=0;
while(i=x&&L.data[i]<=y)
k++;
else
L.data[i-k]=L.data[i];
}
L.length=L.length-k;
}
题目：【2010 年统考】设将 n(n>1)个整数存放在一维数组 R 中。
试着设计一个在时 间复杂度和空间复杂度都尽可能高效的算法，将 R 中保存的序列循环左移 p （ 0
要求： （1）给出算法的基本设计思想；
（2）根据算法设计思想，采用 C 或 C++语言描述，关键之处给出注释 （3）说明你所设计算法的时间复杂度和空间复杂度。
【算法思想】先将 n 个数据 x0,x1, …,xn-2,xn-1 原地逆置，得到 xn-1,xn-2,…,x,x0,然 后 再 将 n-p 个 数 据 和 后 p 个 数 据 分 别 原 地 逆 置 ， 得 到 最 终 结 果 ： xp, xp+1,…,xn-1,x0,x1,…,xp-1
//逆置函数，将数组原地逆置
void Reverse(int R[],int left,int right)
{
i=left,j=right;
while(i0&&p 欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）