王道数据结构-线性表中顺序表的一些综合应用题 王道操作系统-PV操作综合大题总结
需积分: 2 146 浏览量
2022-12-31
10:55:05
上传
评论 5
收藏 244KB PDF 举报
王道数据结构——线性表中顺序表的一些综合应用题
1.长度为 n 的顺序表中，编写一个时间复杂度为 O(n)，空间复杂度为 O(1)的算法，
用于删除线性表中所有值为 x 的数据元素。（满足要求的数放在第 k 位上）
#include <cstdio>
/*输出数组名为 a、长度为 n 的数组*/
void print(int *a, int n){
for(int i = 0;i < n; i++){
printf("%d ", a[i]);
}
puts("");
}
/*解法 1，第几个不等于 x 的数就应该在结果的第几个位置上,千万记得最后修改删除后的
数组长度为 k*/
void f1(int *a, int n, int x){
int k = 0;
for(int i = 0; i < n; i++){
if(a[i] != x){
a[k++] = a[i];
}
}
n = k;
print(a,k);
}
/*解法 2，用 k 记录等于 x 的个数，那么下一个不等于 x 的数在结果中的位置应该提前 k 个
位置，最后数组的长度减去 k*/
void f2(int *a, int n, int x){
int k = 0;
for(int i = 0; i < n; i++){
if(a[i] == x)
k++;
else
a[i - k] = a[i];
}
n -= k;
print(a, n);
}
int main()
{
int a[10] = {1,2,3,2,4,2,5,2,6,2};
剩余62页未读，继续阅读
资源评论
