首先输入一个正整数N（1≤N≤1000）和一个无重复元素的、从小到大排列的、N个元素的有序表，然后在屏幕上显示以下菜单（编号和选项）：
[1] Insert [2] Delete [3] Query [Other option] End
用户可以反复对该有序表进行插入、删除和查找操作，也可以选择结束。当用户输入编号1～3和相关参数时，将分别对该有序表进行插入、删除和查找操作，输入其他编号，则结束操作。
本题要求实现3个函数，分别在有序表（数组）中插入、删除、查找一个值。
函数接口定义：
void insert(int a[ ], int value);
void delete(int a[ ], int value);
void query(int a[ ], int value);
函数insert在有序数组a中插入一个值为value的元素，并调用函数print_array(a)输出插入后的有序数组a 。
函数delete删除有序数组a中等于value的元素，并调用函数print_array(a)输出删除后的有序数组a ；如果在数组a中没有找到值为value的元素，则输出Deletion failed.。
函数query用二分法在有序数组a中查找元素value，如果找到，则输出相应的下标；如果没有找到，则输出Not found.
裁判测试程序样例：
#include
#define MAXN 1000
int Count = 0;
void select(int a[], int option, int value);
int input_array(int a[ ]);
void print_array(int a[ ]);
void insert(int a[ ], int value);
void delete(int a[ ], int value);
void query(int a[ ], int value);
int main(void)
{
int option, value, a[MAXN];
if(input_array(a) == -1){
return 0;
}
printf("[1] Insertn");
printf("[2] Deleten");
printf("[3] Queryn");
printf("[Other option] Endn");
while (1) {
scanf("%d", &option);
if (option < 1 || option > 3) {
break;
}
scanf("%d", &value);
select(a, option, value);
printf("n");
}
printf("Thanks.");
return 0;
}
void select(int a[ ], int option, int value)
{
switch (option) {
case 1:
insert(a, value);
break;
case 2:
delete(a, value);
break;
case 3:
query(a, value);
break;
}
}
int input_array(int a[ ])
{
scanf("%d", &Count);
for (int i = 0; i < Count; i ++) {
scanf("%d", &a[i]);
if(i > 0 && a[i] <= a[i-1]){
printf("Error");
return -1;
}
}
return 0;
}
void print_array(int a[ ])
{
for (int i = 0; i < Count; i ++) {
if(i == 0){
printf("%d", a[i]);
}else{
printf(" %d", a[i]);
}
}
}
输入样例1：
插入一个值，输入数据如下：
6 -2 3 7 9 101 400 1 96 0
输出样例1：
[1] Insert
[2] Delete
[3] Query
[Other option] End
-2 3 7 9 96 101 400
Thanks.
输入样例2：
删除一个值，输入数据如下：
6 -2 3 7 9 101 400 2 400 0
输出样例2：
[1] Insert
[2] Delete
[3] Query
[Other option] End
-2 3 7 9 101
Thanks.
输入样例3：
查询一次，输入数据如下：
6 -2 3 7 9 101 400 3 -2 0
输出样例3：
[1] Insert
[2] Delete
[3] Query
[Other option] End
0
Thanks.
输入样例4：
连续增删查，输入数据如下：
6 -2 3 7 9 101 400 2 101 1 -10 3 101 0
输出样例4：
[1] Insert
[2] Delete
[3] Query
[Other option] End
-2 3 7 9 400
-10 -2 3 7 9 400
Not found.
Thanks.
void insert(int a[ ], int value){
int i,j;
for (i = 0;i < Count;i++){ //定位：找到待插入的位置
if (value < a[i]){
break;
}
}
for(j = Count - 1; j >= i;j--){ //腾位：将a[i]~a[Count-1]后移一位
a[j + 1] = a[j];
}
a[i] = value; //插入：将value的值赋给a[i]
Count++; //将数组a中待处理的元素数量加一
print_array(a);
}
void delete(int a[ ], int value){
int i,index = -1;
for (i = 0;i < Count;i++){ //for循环找出待删除的元素
if (value == a[i]){
index = i;
break;
}
}
if (index == -1){ //未找到，输出Deletion failed.;
printf ("Deletion failed.");
return; //输出之后记得return
}else{
for (i = index;i < Count - 1;i++){ //将a[Count-1]~a[i+1]向前移一位
a[i] = a[i + 1];
}
}
Count--;
print_array(a);
}
void query(int a[ ], int value){ //二分查找找函数
int mid,left = 0,right = Count - 1; //全范围内查找
while (left <= right){
mid = (left + right) / 2; //取中间数来二分查找
if (value == a[mid]){
printf ("%d",mid);
return; //老规矩，记得返回
}else if(value < a[mid]){ //判断向左查找还是向右查找
right = mid -1;
}else{
left = mid + 1;
}
}
printf ("Not found."); //最后输出即可
}
