Time limit: 500ms
Memory limit: 256mb
Description:
In this exercise, you are required to maintain an array of sorted integers in descending order and support the following operations.
1. Insert an integer
2. Delete an integer
3. Check whether an integer exists
4. Update one matching integer
5. Update all matching integers in a range (inclusive)
6. Print all elements in the array in descending order
You can assume that there are 100 integers at most, so an array A[100] is enough to store all the integers (i.e. length A <= 100). What’s more, all the integers of A[] are not distinct, which means that A[0] >= A[1] >= … >= A[n-1].
Then the program performs Insert, Delete, Update and Print operations. The user will be prompted to input the integers for insertion, deletion, update.
The code template has been provided. Your task is to complete the following functions.
int Insert(int value, int A[], int n);
Insert one value into A[] of length n and return the new length. After insertion, A[] should still be in descending order.
Example:
insert 1 to [8,6,4,2,1]
Array will be something like: [8,6,4,2,1,1], the function returns new length n’ = 6
int Delete(int value, int A[], int n);
Delete one value from A[] of length n and return the new length. You could assume that the value exists in A[] before deletion. After deletion, A[] should still be in descending order.
Example:
delete 1 from [8,6,4,2,1,1]
Array will be something like: [8,6,4,2,1], the function returns new length n’ = 5
int Exist(int value, int A[], int n)
Check whether an integer exists in the array A[]. If exist, return 1, if not, return 0.
Example
Check whether [8,8,6,2,1,1] exists 6
The function will return 1 as 6 exists.
Check whether [8,8,6,2,1,1] exists 5
The function will return 0 as 5 does not exist.
int Update_one(int old_value, int new_value, int A[], int n);
Change one old_value to new_value in A[] of length n and return the new length. After the update, A[] should still be in descending order.
Example:
update one 1 in [8,8,6,2,1,1] to 2
Array will be something like: [8,8,6,2,2,1] (i.e. only one 1 becomes 2), the function returns length n’ = 6
int Update_all(int old_value_min, int old_value_max, int new_value, int A[], int n);
Change all matching integers in a range (inclusive) from old_value_min to old_value_max to new_value in A[] of length n and return the new length. After the update, A[] should still be in descending order.
Example:
Let old_value_min = 6, old_value_max = 9, new_value = 7, update all integers in [8,8,6,2,2,1] with values not greater than 9 (<= 9) and not less than 6 (>= 6) to 7
Array will be something like: [7,7,7,2,2,1] (i.e. all 8,8,6 will become 7s as they are in range (inclusive) 6 to 9), the function returns length n’ = 6
void Print(int A[], int n);
Print all elements in the array in descending order, separated by space.
Example:
7 7 7 2 2 1
Tips: You may use Exist(), Insert() and Delete() to implement the Update() and do not forget to update n after insertion and deletion.
Sample input:
5
1 3 2 5 3
4
1
2 8
2 4 1
Sample output:
8 5 1 1 1
-------------------------Copy the following code, complete it and submit-------------------------
#include <stdio.h>
int Insert(int value, int A[], int n)
{
// insert value into A[], return new length n
}
int Delete(int value, int A[], int n)
{
// delete value from A[], return new length n
}
int Exist(int value, int A[], int n){
// check whether value exists in array A[]
}
int Update_one(int old_value, int new_value, int A[], int n)
{
// change old_value to new_value, return new length n
}
int Update_all(int old_value_min, int old_value_max, int new_value, int A[], int n)
{
// change old_value in range (inclusive) from old_value_min to old_value_max to new_value, return new length n
}
void Print(int A[], int n)
{
// print values in A[] in one line, every two integers are separated by a space
}
int main()
{
int A[100];
int n; // the number of integers in A
int value, value_min, value_max, new_value;
// printf("Array initialization: \n");
// printf("How many integers in array initially: ");
scanf("%d", &n);
// printf("What are the integers: ");
int temp = 0;
for(int i=0; i<n; i++){
scanf("%d", &value);
temp = Insert(value, A, temp);
}
// printf("Input a value for insertion: ");
scanf("%d", &value);
n = Insert(value, A, n);
// printf("Input a value for deletion: ");
scanf("%d", &value);
n = Delete(value, A, n);
// printf("Input the old and new values for update(one): ");
scanf("%d%d", &value, &new_value);
n = Update_one(value, new_value, A, n);
// printf("Input the min old value, max olf value and new value for update(all): ");
scanf("%d%d%d", &value_min, &value_max, &new_value);
n = Update_all(value_min, value_max, new_value, A, n);
// printf("Current array: \n");
Print(A, n);
return 0;
}
-------------------------------------------End of Code-------------------------------------------