《程序设计基础》 第十章 函数与程序结构 6-12 有序表的简单增删查操作 (20 分)

首先输入一个正整数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<stdio.h>
#define MAXN 1000
int Count = 0;        /* 用全局变量Count表示数组a中待处理的元素个数 */
void select(int a[], int option, int value); /* 决定对有序数组a进行何种操作的控制函数 */
int input_array(int a[ ]);    /* 输入有序数组a的函数 */
void print_array(int a[ ]);    /* 输出有序数组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] Insert\n");
    printf("[2] Delete\n");
    printf("[3] Query\n");
    printf("[Other option] End\n");
    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[j + 1] = a[j];
		}
		a[i] = value;
		Count++;
		print_array(a);
}
void delete(int a[ ], int value){
	int i,index = -1;
	for (i = 0;i < Count;i++){
		if (value == a[i]){
			index = i;
			break;
		}
	}
	if (index == -1){
		printf ("Deletion failed.");
		return;
	}else{
		for (i = index;i < Count - 1;i++){
			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.");
}