题要求实现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-03 09:12:30 浏览: 114
实现一个宽度为8(用宏表示)的Hash表的插入,查找,删除函数。
以下是函数的实现代码:
```c++
// 在有序数组a中插入一个值为value的元素,如果在数组a中已有值为value的元素,则返回-1。
int insert(int a[], int value) {
int i;
for (i = 0; a[i] < value && a[i] != 0; i++);
if (a[i] == value) {
return -1;
}
for (int j = sizeof(a)/sizeof(*a) - 1; j > i; j--) {
a[j] = a[j-1];
}
a[i] = value;
return i;
}
// 删除有序数组a中等于value的元素,如果在数组a中没有找到值为value的元素,则返回-1。
int del(int a[], int value) {
int i;
for (i = 0; a[i] != value && a[i] != 0; i++);
if (a[i] == 0) {
return -1;
}
for (int j = i; a[j] != 0; j++) {
a[j] = a[j+1];
}
return i;
}
// 将有序数组a中等于value1的元素,替换为value2 ,如果在数组a中没有找到值为value1的元素或者value2已在数组a中存在,则返回-1。
int modify(int a[], int value1, int value2) {
int i;
for (i = 0; a[i] != value1 && a[i] != 0; i++);
if (a[i] == 0 || a[i] == value2) {
return -1;
}
a[i] = value2;
return i;
}
// 用二分法在有序数组a中查找元素value,如果找到,则返回相应的下标;如果没有找到,则返回-1。
int query(int a[], int value) {
int left = 0, right = sizeof(a)/sizeof(*a) - 1, mid;
while (left <= right) {
mid = (left + right) / 2;
if (a[mid] == value) {
return mid;
} else if (a[mid] < value) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
```
需要注意的是,以上代码没有考虑数组已满的情况,如果数组已满,则可能会出现越界的情况。另外,以上代码中的数组大小应该是在调用函数的时候传入,而不是在函数中计算。
阅读全文