<Typical Applications of One-Dimensional Arrays (Part 2) >From beginner to expert, from Hello World to ACMAll practical content, no textbooks required!
<Lecture>
1. Insertion and Deletion of Array Elements1.1 Insertion of Array ElementsThe basic idea: To insert a new element at a specified position in the array, all elements from that position onward need to be moved one position back to make space for the new element.Analysis of Insertion Position:Insert at the end: The simplest, directly place it at the end of the array.Insert in the middle: Requires moving some elements.Insert at the beginning: Requires moving all elements.Code Implementation:
#include <stdio.h>
int main() {
int arr[20] = {10, 25, 36, 48, 52, 67}; // Reserve enough space
int n = 6; // Current number of elements
int pos, value, i;
printf("Original array: ");
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
// Input the position and value to insert
printf("Please enter the position to insert (0-%d) and the value: ", n);
scanf("%d %d", &pos, &value);
// Validate position legality
if (pos < 0 || pos > n) {
printf("Invalid insertion position!\n");
return 0;
}
// Move elements from back to front to make space for the new element
for (i = n; i > pos; i--) {
arr[i] = arr[i-1];
}
// Insert the new element at the specified position
arr[pos] = value;
n++; // Increase the number of elements
printf("Array after insertion: ");
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}Test Case:Input:
Position: 2, Value: 30Output:
Original array: 10 25 36 48 52 67 Array after insertion: 10 25 30 36 48 52 67Common Mistakes:Always move elements from back to front to avoid data overwriting.Check if the array has enough space before insertion.Position validation is crucial to prevent out-of-bounds access.1.2 Deletion of Array ElementsThe basic idea: Delete the element at the specified position, then move all elements after that position one position forward.Code Implementation:
#include <stdio.h>
int main() {
int arr[] = {10, 25, 36, 48, 52, 67};
int n = 6;
int pos, i;
printf("Original array: ");
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
printf("Please enter the position to delete (0-%d): ", n-1);
scanf("%d", &pos);
// Validate position legality
if (pos < 0 || pos >= n) {
printf("Invalid deletion position!\n");
return 0;
}
// Move elements from front to back to overwrite the element to be deleted
for (i = pos; i < n-1; i++) {
arr[i] = arr[i+1];
}
n--; // Decrease the number of elements
printf("Array after deletion: ");
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}Test Case:Input:
Position: 3Output:
Original array: 10 25 36 48 52 67 Array after deletion: 10 25 36 52 67Common Mistakes:Check if the array is empty before deletion.Move direction is from front to back.Remember to update the value of the number of elements n.In-Class Exercise 1: Self-Designed Problem – Basic Student Grade Management SystemProblem Description: Implement a simple student grade management function that can insert new grades and delete grades at specified positions.Input Format: The first line inputs the initial number of grades n, the second line inputs n grades, the third line inputs the operation type (1 for insert, 2 for delete), and the fourth line inputs parameters based on the operation type.Test Case:Input:
585 92 78 90 8812 95Output:
Grades after operation: 85 95 92 78 90 88Input:
585 92 78 90 8823Output:
Grades after operation: 85 92 78 88Reference Answer:
#include <stdio.h>
int main() {
int scores[100]; // Reserve enough space
int n, op, pos, value, i;
// Read initial data
printf("Input number of grades: ");
scanf("%d", &n);
printf("Input %d grades: ", n);
for (i = 0; i < n; i++) {
scanf("%d", &scores[i]);
}
printf("Select operation (1 for insert, 2 for delete): ");
scanf("%d", &op);
if (op == 1) {
printf("Input position and grade to insert: ");
scanf("%d %d", &pos, &value);
if (pos < 0 || pos > n) {
printf("Invalid position!\n");
return 0;
}
// Move elements back
for (i = n; i > pos; i--) {
scores[i] = scores[i-1];
}
scores[pos] = value;
n++;
} else if (op == 2) {
printf("Input position to delete: ");
scanf("%d", &pos);
if (pos < 0 || pos >= n) {
printf("Invalid position!\n");
return 0;
}
// Move elements forward
for (i = pos; i < n-1; i++) {
scores[i] = scores[i+1];
}
n--;
}
printf("Grades after operation: ");
for (i = 0; i < n; i++) {
printf("%d ", scores[i]);
}
printf("\n");
return 0;
}2. Array Merging and Splitting2.1 Array MergingThe basic idea: Merge two arrays into a new array, which can be done in an ordered manner or simply concatenated.Ordered merge code implementation:
#include <stdio.h>
int main() {
int arr1[] = {3, 8, 15, 22, 30};
int arr2[] = {2, 9, 18, 25, 35, 40};
int n1 = 5, n2 = 6;
int result[20]; // Merged array
int i = 0, j = 0, k = 0;
// Ordered merge: both arrays are sorted in ascending order
while (i < n1 && j < n2) {
if (arr1[i] < arr2[j]) {
result[k++] = arr1[i++];
} else {
result[k++] = arr2[j++];
}
}
// Copy remaining elements to the result array
while (i < n1) {
result[k++] = arr1[i++];
}
while (j < n2) {
result[k++] = arr2[j++];
}
printf("Merged array: ");
for (i = 0; i < k; i++) {
printf("%d ", result[i]);
}
printf("\n");
return 0;
}Simple concatenation code implementation:
#include <stdio.h>
int main() {
int arr1[] = {5, 10, 15};
int arr2[] = {20, 25, 30, 35};
int n1 = 3, n2 = 4;
int result[20];
int i, k = 0;
// First copy the first array
for (i = 0; i < n1; i++) {
result[k++] = arr1[i];
}
// Then copy the second array
for (i = 0; i < n2; i++) {
result[k++] = arr2[i];
}
printf("Concatenated array: ");
for (i = 0; i < k; i++) {
printf("%d ", result[i]);
}
printf("\n");
return 0;
}2.2 Array SplittingThe basic idea: Split the array into multiple parts based on specific conditions.Split by odd and even code implementation:
#include <stdio.h>
int main() {
int original[] = {12, 7, 25, 8, 13, 6, 19, 4, 11, 9};
int n = 10;
int odd[20], even[20]; // Odd and even arrays
int odd_count = 0, even_count = 0;
int i;
for (i = 0; i < n; i++) {
if (original[i] % 2 == 0) {
// Even
even[even_count++] = original[i];
} else {
// Odd
odd[odd_count++] = original[i];
}
}
printf("Original array: ");
for (i = 0; i < n; i++) {
printf("%d ", original[i]);
}
printf("\n");
printf("Odd array: ");
for (i = 0; i < odd_count; i++) {
printf("%d ", odd[i]);
}
printf("\n");
printf("Even array: ");
for (i = 0; i < even_count; i++) {
printf("%d ", even[i]);
}
printf("\n");
return 0;
}In-Class Exercise 2: Luogu P3156 [Deep Foundation 15. Example 1] Query Student IDProblem Description: There are n (n ≤ 2×10⁶) students, each with a student ID. The teacher asks for the student ID of the i-th student who entered the classroom, with the first student entering numbered as 1.Input Format: The first line contains two integers n and m, representing the number of students and the number of queries. The second line contains n integers, representing the student IDs in the order of entry. The next m lines each contain one integer, representing the query for the student ID of the i-th student who entered the classroom.Output Format: Output m lines, each containing one integer representing the corresponding student ID.Test Case:Input:
5 210 20 15 12 832Output:
1520Reference Answer:
#include <stdio.h>
int main() {
int n, m, i, query;
// Read data
scanf("%d %d", &n, &m);
int students[2000000]; // Maximum support for 2×10⁶ elements as per problem requirements
for (i = 0; i < n; i++) {
scanf("%d", &students[i]);
}
// Process queries
for (i = 0; i < m; i++) {
scanf("%d", &query);
// Directly output the corresponding student ID (note that the first number in the problem is 1, corresponding to array index 0)
printf("%d\n", students[query-1]);
}
return 0;
}3. Analysis of Array Application Examples3.1 Grade Statistics and Analysis SystemProblem Description: Implement a complete grade management system that includes grade entry, statistics, sorting, and analysis functions.Code Implementation:
#include <stdio.h>
int main() {
int scores[100];
int n, i, j, choice;
int sum, max, min;
double average;
printf("Please enter the number of students: ");
scanf("%d", &n);
printf("Please enter %d grades: ", n);
for (i = 0; i < n; i++) {
scanf("%d", &scores[i]);
}
do {
printf("\n=== Grade Management System ===\n");
printf("1. Display all grades\n");
printf("2. Calculate average score\n");
printf("3. Find highest and lowest scores\n");
printf("4. Sort grades\n");
printf("5. Count score ranges\n");
printf("0. Exit\n");
printf("Please select an operation: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("All grades: ");
for (i = 0; i < n; i++) {
printf("%d ", scores[i]);
}
printf("\n");
break;
case 2:
sum = 0;
for (i = 0; i < n; i++) {
sum += scores[i];
}
average = (double)sum / n;
printf("Average score: %.2f\n", average);
break;
case 3:
max = scores[0];
min = scores[0];
for (i = 1; i < n; i++) {
if (scores[i] > max) max = scores[i];
if (scores[i] < min) min = scores[i];
}
printf("Highest score: %d, Lowest score: %d\n", max, min);
break;
case 4:
// Use selection sort to sort grades
for (i = 0; i < n-1; i++) {
int max_idx = i;
for (j = i+1; j < n; j++) {
if (scores[j] > scores[max_idx]) {
max_idx = j;
}
}
if (max_idx != i) {
int temp = scores[i];
scores[i] = scores[max_idx];
scores[max_idx] = temp;
}
}
printf("Grades sorted from high to low!\n");
break;
case 5:
{
int level[5] = {0}; // 0-59, 60-69, 70-79, 80-89, 90-100
for (i = 0; i < n; i++) {
if (scores[i] < 60) level[0]++;
else if (scores[i] < 70) level[1]++;
else if (scores[i] < 80) level[2]++;
else if (scores[i] < 90) level[3]++;
else level[4]++;
}
printf("Score range statistics:\n");
printf("0-59: %d people\n", level[0]);
printf("60-69: %d people\n", level[1]);
printf("70-79: %d people\n", level[2]);
printf("80-89: %d people\n", level[3]);
printf("90-100: %d people\n", level[4]);
}
break;
case 0:
printf("Thank you for using!\n");
break;
default:
printf("Invalid choice!\n");
}
} while (choice != 0);
return 0;
}In-Class Exercise 3: HDOJ 2009 Calculate the Sum of a SequenceProblem Description: The sequence is defined as follows: the first term is n, and each subsequent term is the square root of the previous term. Calculate the sum of the first m terms.Input Format: Multiple groups of input data, each group occupies one line, containing two integers n and m, with n and m both being 0 indicating the end of input.Output Format: For each group of input data, output the sum of the sequence, with each test instance occupying one line, and the precision retained to two decimal places.Test Case:Input:
81 42 20 0Output:
94.73 3.41Reference Answer:
#include <stdio.h>
#include <math.h>
int main() {
int n, m, i;
while (scanf("%d %d", &n, &m) != EOF) {
if (n == 0 && m == 0) break;
double sum = 0;
double current = n;
for (i = 0; i < m; i++) {
sum += current;
current = sqrt(current); // Calculate the next term (square root)
}
printf("%.2lf\n", sum);
}
return 0;
}4. Common Questions and AnswersQ:Why do we need to move elements from back to front when inserting into an array?A:If we move from front to back, it will overwrite the data of the elements behind. For example, if we move arr[2] to arr[3] first, then the original value of arr[3] will be overwritten, making it impossible to correctly move subsequent elements.Q:What if both arrays are very large during merging?A:We need to ensure that the target array has enough space to accommodate all elements. In actual programming, we can dynamically calculate the required space or use a sufficiently large fixed array.Q:What are the practical applications of array splitting?A:Array splitting is useful in many scenarios, such as dividing classes by grades (honor class, regular class), grouping by gender, or categorizing by age groups.Q:How can we improve the efficiency of array operations?A:For frequent insert and delete operations, consider using a linked list data structure. For search operations, sort first and then use binary search.5. Summary of Common Mistakes1. Out-of-bounds access: Array indices start from 0, the maximum index is n-1, pay attention to boundary conditions when accessing.2. Insufficient space: Check if the array has enough space before insertion operations.3. Move direction: Move from back to front when inserting, and from front to back when deleting.4. Update the number of elements: Remember to update the value of n after insertion or deletion.5. Position validation: Validate the legality of the position before operations.<Exercise Class>
1. Detailed Explanation of Typical Example Problems
1.1 Practical Array Insertion Operation – Self-Designed Problem
Problem Description: Insert a new element into a sorted ascending array, ensuring that the array remains sorted after insertion.
Solution Idea:
- Find the position where the new element should be inserted (the first position greater than the element).
- Move all elements from that position onward one position back.
- Insert the element at the new position.
Detailed Code Analysis:
#include <stdio.h>
int main() {
int arr[20] = {10, 20, 30, 40, 50, 60}; // Sorted array, reserve space
int n = 6; // Current number of elements
int newValue, i, pos;
printf("Original array: ");
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
printf("Please enter the value to insert: ");
scanf("%d", &newValue);
// Find the insertion position (the first position greater than newValue)
pos = 0;
while (pos < n && arr[pos] < newValue) {
pos++;
}
// Move elements from back to front to make space for insertion
for (i = n; i > pos; i--) {
arr[i] = arr[i-1];
}
// Insert the new element
arr[pos] = newValue;
n++; // Increase the number of elements
printf("Array after insertion: ");
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
Test Case:
Input:25
Output:10 20 25 30 40 50 60
Input:5
Output:5 10 20 30 40 50 60
Input:65
Output:10 20 30 40 50 60 65Common Mistakes Reminder:
- When moving elements, always move from back to front to avoid data overwriting.
- The insertion position may be at the beginning, middle, or end, so consider all possibilities.
- Remember to update the value of the number of elements n.
1.2 Practical Array Deletion Operation – Luogu P3156 Query Student ID
Problem Description: There are n students, each with a student ID. The teacher asks for the student ID of the i-th student who entered the classroom.
Solution Idea: Although this problem does not directly involve deletion, it tests the basic access operations of arrays, laying the foundation for understanding deletion operations.
Code Implementation:
#include <stdio.h>
int main() {
int n, m, i, query;
scanf("%d %d", &n, &m);
int students[2000000]; // Allocate enough space as per problem requirements
// Read student IDs
for (i = 0; i < n; i++) {
scanf("%d", &students[i]);
}
// Process queries
for (i = 0; i < m; i++) {
scanf("%d", &query);
// Note: The problem numbers start from 1, while array indices start from 0
printf("%d\n", students[query - 1]);
}
return 0;
}
Key Knowledge Points:
- Array indices start from 0, while problem numbers start from 1, requiring conversion.
- Large arrays should be defined outside the function or use dynamic memory.
- Use scanf/printf for input and output to improve efficiency.
1.3 Practical Array Merging – Self-Designed Problem
Problem Description: Merge two sorted arrays into a new sorted array.
Solution Idea: Use the two-pointer method to compare the current elements of the two arrays and place the smaller one into the result array.
Code Implementation:
#include <stdio.h>
int main() {
int arr1[] = {3, 8, 15, 22, 30};
int arr2[] = {2, 9, 18, 25, 35, 40};
int n1 = 5, n2 = 6;
int result[20]; // Result array
int i = 0, j = 0, k = 0;
// Two-pointer merge
while (i < n1 && j < n2) {
if (arr1[i] < arr2[j]) {
result[k++] = arr1[i++];
} else {
result[k++] = arr2[j++];
}
}
// Handle remaining elements
while (i < n1) result[k++] = arr1[i++];
while (j < n2) result[k++] = arr2[j++];
printf("Merged sorted array: ");
for (i = 0; i < k; i++) {
printf("%d ", result[i]);
}
printf("\n");
return 0;
}
Algorithm Analysis:
- Time Complexity: O(n1 + n2)
- Space Complexity: O(n1 + n2)
- This is the core step of merge sort.
2. Summary of Problem Types and Solution Techniques
2.1 Template for Solving Array Insertion Problems
// 1. Validate the legality of the insertion position
if (pos < 0 || pos > n) {
printf("Invalid position\n");
return;
}
// 2. Move elements from back to front
for (int i = n; i > pos; i--) {
arr[i] = arr[i-1];
}
// 3. Insert the new element
arr[pos] = value;
n++; // Update the number of elements
2.2 Template for Solving Array Deletion Problems
// 1. Validate the legality of the deletion position
if (pos < 0 || pos >= n) {
printf("Invalid position\n");
return;
}
// 2. Move elements from front to back
for (int i = pos; i < n-1; i++) {
arr[i] = arr[i+1];
}
// 3. Update the number of elements
n--;
2.3 Template for Solving Array Merging Problems
int i = 0, j = 0, k = 0;
// Two-pointer merge
while (i < n1 && j < n2) {
if (arr1[i] < arr2[j]) {
result[k++] = arr1[i++];
} else {
result[k++] = arr2[j++];
}
}
// Handle remaining elements
while (i < n1) result[k++] = arr1[i++];
while (j < n2) result[k++] = arr2[j++];
3. Comprehensive Application Examples
3.1 HDOJ 2009 Calculate the Sum of a Sequence – Application of Array Concepts
Problem Description: The first term of the sequence is n, and each subsequent term is the square root of the previous term. Calculate the sum of the first m terms.
Solution Idea: Although it can be calculated directly, we can use an array to store each term, experiencing the application of arrays in sequence processing.
Code Implementation:
#include <stdio.h>
#include <math.h>
int main() {
int n, m, i;
while (scanf("%d %d", &n, &m) != EOF) {
if (n == 0 && m == 0) break;
double sequence[100]; // Store each term of the sequence
double sum = 0;
sequence[0] = n;
sum = sequence[0];
for (i = 1; i < m; i++) {
sequence[i] = sqrt(sequence[i-1]);
sum += sequence[i];
}
printf("%.2lf\n", sum);
}
return 0;
}
Test Case:
Input:81 4
Output:94.73
Input:2 2
Output:3.414. Analysis of Common Mistakes and Debugging Techniques
4.1 Common Types of Errors
1. Array out-of-bounds access: Accessing illegal positions like arr[-1] or arr[n].Solution: Carefully check loop conditions to ensure indices are within the range of 0 to n-1.2. Incorrect element move direction: Moving from front to back during insertion leads to data overwriting.Solution: Remember to move from back to front for insertion and from front to back for deletion.3. Forgetting to update the number of elements: Forgetting to modify the value of n after insertion or deletion.Solution: Immediately update n after insertion or deletion operations.4. Improper handling of boundary conditions: Errors when operating at the beginning or end of the array.Solution: Test boundary cases separately.
4.2 Debugging Techniques
// Add print statements at key positions for debugging
printf("Debug info: current n=%d, processing position %d\n", n, i);
// Function to check the state of the array
void printArray(int arr[], int n, char* message) {
printf("%s: ", message);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
5. Homework
5.1 Required Problems
Problem 1: Luogu P3156 [Deep Foundation 15. Example 1] Query Student ID(Review Problem)
- Content: n students, each with a student ID, query the student ID of the i-th student who entered the classroom.
- Key Points: Basic access operations of arrays.
- Problem Number: P3156
Problem 2: Self-Designed Problem – Array Management System
- Content: Implement insertion, deletion, search, and statistics functions for array elements.
- Requirements: Menu-driven, able to handle various boundary cases.
- Key Points: Comprehensive array operation ability.
Problem 3: HDOJ 2014 Youth Singer Grand Prix Judge Scores
- Content: Remove the highest and lowest scores, calculate the average score.
- Key Points: Array traversal, finding extremes, statistical calculations.
- Problem Number: HDOJ 2014
5.2 Optional Problems (Challenge Problems)
Problem 4: Self-Designed Problem – Upgraded Version of Merging Sorted Arrays
- Content: Merge k sorted arrays (k>2).
- Requirements: Design an efficient merging algorithm.
- Key Points: Algorithm design ability, understanding of multi-dimensional arrays.
6. Answers to Homework
Answer to Problem 1: Luogu P3156
#include <stdio.h>
int main() {
int n, m, i, query;
scanf("%d %d", &n, &m);
int students[2000000];
for (i = 0; i < n; i++) {
scanf("%d", &students[i]);
}
for (i = 0; i < m; i++) {
scanf("%d", &query);
printf("%d\n", students[query-1]);
}
return 0;
}
Answer to Problem 2: Array Management System
#include <stdio.h>
int main() {
int arr[100];
int n = 0, choice, pos, value, i, found;
printf("Input initial number of elements: ");
scanf("%d", &n);
printf("Input %d elements: ", n);
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
do {
printf("\n=== Array Management System ===\n");
printf("1. Display array\n");
printf("2. Insert element\n");
printf("3. Delete element\n");
printf("4. Search element\n");
printf("5. Statistics\n");
printf("0. Exit\n");
printf("Please select: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Current array: ");
for (i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n");
break;
case 2:
printf("Input position and value to insert: ");
scanf("%d %d", &pos, &value);
if (pos < 0 || pos > n) {
printf("Invalid position!\n");
break;
}
for (i = n; i > pos; i--) arr[i] = arr[i-1];
arr[pos] = value;
n++;
printf("Insertion successful!\n");
break;
case 3:
printf("Input position to delete: ");
scanf("%d", &pos);
if (pos < 0 || pos >= n) {
printf("Invalid position!\n");
break;
}
for (i = pos; i < n-1; i++) arr[i] = arr[i+1];
n--;
printf("Deletion successful!\n");
break;
case 4:
printf("Input value to search: ");
scanf("%d", &value);
found = 0;
for (i = 0; i < n; i++) {
if (arr[i] == value) {
printf("Element found, position: %d\n", i);
found = 1;
}
}
if (!found) printf("Element not found\n");
break;
case 5:
if (n > 0) {
int sum = 0, max = arr[0], min = arr[0];
for (i = 0; i < n; i++) {
sum += arr[i];
if (arr[i] > max) max = arr[i];
if (arr[i] < min) min = arr[i];
}
printf("Number of elements: %d\n", n);
printf("Total: %d, Average: %.2f\n", sum, (double)sum/n);
printf("Maximum: %d, Minimum: %d\n", max, min);
}
break;
}
} while (choice != 0);
return 0;
}
Answer to Problem 3: HDOJ 2014
#include <stdio.h>
int main() {
int n, i;
while (scanf("%d", &n) != EOF) {
int scores[100];
int sum = 0, max, min;
for (i = 0; i < n; i++) {
scanf("%d", &scores[i]);
}
max = min = scores[0];
for (i = 0; i < n; i++) {
if (scores[i] > max) max = scores[i];
if (scores[i] < min) min = scores[i];
}
for (i = 0; i < n; i++) {
sum += scores[i];
}
// Remove the highest and lowest scores
sum = sum - max - min;
double average = (double)sum / (n - 2);
printf("%.2lf\n", average);
}
return 0;
}
In the next class, we will learn about:
Two-Dimensional Arrays
If you have questions, feel free to comment!
Follow YunJie Algorithmer, no textbooks needed, just a finger tap to systematically learn programming!