本题要求实现4个函数,分别在有序表(数组)中插入、删除、修改、查找一个值。 函数接口定义: int insert(int a[ ], int value); int del(int a[ ], int value); int modify(int a[ ], int value1, int value2); int query(int a[ ], int value); 函数insert在有序数组a中插入一个值为value的元素,如果在数组a中已有值为value的元素,则返回-1。 函数del删除有序数组a中等于value的元素,如果在数组a中没有找到值为value的元素,则返回-1。 函数modify将有序数组a中等于value1的元素,替换为value2 ,如果在数组a中没有找到值为value1的元素或者value2已在数组a中存在,则返回-1。 函数query用二分法在有序数组a中查找元素value,如果找到,则返回相应的下标;如果没有找到,则返回-1。
时间: 2024-02-01 08:16:57 浏览: 84
以下是题目要求的四个函数的实现:
```c++
// 在有序数组a中插入一个值为value的元素
// 如果在数组a中已有值为value的元素,则返回-1
int insert(int a[], int value) {
int n = sizeof(a) / sizeof(int);
int i;
for (i = 0; i < n; i++) {
if (a[i] == value) {
return -1; // 数组中已存在value元素
}
if (a[i] > value) {
break; // 在第i个位置插入value元素
}
}
for (int j = n - 1; j >= i; j--) {
a[j+1] = a[j];
}
a[i] = value;
return i;
}
// 删除有序数组a中等于value的元素
// 如果在数组a中没有找到值为value的元素,则返回-1
int del(int a[], int value) {
int n = sizeof(a) / sizeof(int);
int i;
for (i = 0; i < n; i++) {
if (a[i] == value) {
break; // 找到value元素
}
}
if (i == n) {
return -1; // 数组中不存在value元素
}
for (int j = i+1; j < n; j++) {
a[j-1] = a[j];
}
a[n-1] = 0; // 数组最后一个元素清零
return i;
}
// 将有序数组a中等于value1的元素替换为value2
// 如果在数组a中没有找到值为value1的元素或者value2已在数组a中存在,则返回-1
int modify(int a[], int value1, int value2) {
int n = sizeof(a) / sizeof(int);
int i;
for (i = 0; i < n; i++) {
if (a[i] == value1) {
break; // 找到value1元素
}
}
if (i == n) {
return -1; // 数组中不存在value1元素
}
for (int j = 0; j < n; j++) {
if (a[j] == value2) {
return -1; // 数组中已存在value2元素
}
}
a[i] = value2; // 将value1元素替换为value2元素
return i;
}
// 用二分法在有序数组a中查找元素value
// 如果找到,则返回相应的下标;如果没有找到,则返回-1
int query(int a[], int value) {
int n = sizeof(a) / sizeof(int);
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (a[mid] == value) {
return mid; // 找到value元素
} else if (a[mid] < value) {
left = mid + 1; // 在右半部分继续查找
} else {
right = mid - 1; // 在左半部分继续查找
}
}
return -1; // 数组中不存在value元素
}
```
需要注意的是,这里假设输入的有序数组a已经按照从小到大的顺序排好了序。函数中使用的sizeof(a) / sizeof(int)求出了数组a的长度n。
阅读全文