编写程序已知线性表(a1,a2, a3 ,…,an)按顺序存于内存,每个元素都是整数,试设计用最少时间把所有值为负数的元素移到全部非负数值元素前边的算法:例:(x,-x,-x,x,x,-x …x)变为(-x,-x,-x…x,x,x)。
时间: 2023-10-09 13:05:38 浏览: 42
解题思路:
可以使用两个指针,分别指向左右两端,左指针从左往右遍历,右指针从右往左遍历,当左指针指向的元素为正数,右指针指向的元素为负数时,交换两个元素,直到左指针和右指针相遇为止。
代码实现:
```
void moveNegative(int a[], int n) {
int left = 0, right = n-1;
while (left < right) {
while (a[left] < 0 && left < right) left++;
while (a[right] >= 0 && left < right) right--;
if (left < right) {
int temp = a[left];
a[left++] = a[right];
a[right--] = temp;
}
}
}
```
时间复杂度:O(n)
相关问题
已知线性表(a1,a2,a3,…,an)每个元素都是整数,试用c语言设计该线性表的一种存储结构
线性表是一种常见的数据结构,它是由n个数据元素a1,a2,a3,...,an组成的有限序列。线性表的存储结构有两种:顺序存储和链式存储。在C语言中,可以使用数组来实现线性表的顺序存储结构。
具体实现方法如下:
```c
#define MAXSIZE 100 // 定义线性表的最大长度
typedef struct {
int data[MAXSIZE]; // 存储线性表元素的数组
int length; // 线性表的当前长度
} SqList; // 定义顺序存储结构
// 初始化线性表
void InitList(SqList *L) {
L->length = 0;
}
// 插入元素
int ListInsert(SqList *L, int i, int e) {
if (i < 1 || i > L->length + 1) {
return 0; // 插入位置不合法
}
if (L->length >= MAXSIZE) {
return 0; // 线性表已满
}
for (int j = L->length; j >= i; j--) {
L->data[j] = L->data[j - 1]; // 将第i个元素及之后的元素后移
}
L->data[i - 1] = e; // 插入新元素
L->length++; // 线性表长度加1
return 1;
}
// 删除元素
int ListDelete(SqList *L, int i) {
if (i < 1 || i > L->length) {
return 0; // 删除位置不合法
}
for (int j = i; j < L->length; j++) {
L->data[j - 1] = L->data[j]; // 将第i个元素之后的元素前移
}
L->length--; // 线性表长度减1
return 1;
}
```
1. 已知线性表(a1,a2,a3,...an)按顺序存储,且每个元素都是互不相等的整数。设计把所有奇数移到所有的偶数前面的程序。
可以使用两个指针,一个指向第一个元素,一个指向最后一个元素。首先让第一个指针从前往后扫描,找到第一个偶数。接着让第二个指针从后往前扫描,找到第一个奇数。然后交换这两个数,继续重复上述过程,直到两个指针相遇为止。
具体步骤如下:
1. 初始化指针i指向第一个元素,指针j指向最后一个元素;
2. 当i<j时,执行以下循环:
- 如果a[i]是偶数,i指针向右移动;
- 如果a[j]是奇数,j指针向左移动;
- 如果a[i]是奇数且a[j]是偶数,交换a[i]和a[j]的值;
3. 循环结束后,所有奇数都会被移到偶数前面。
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)