I. In-Class Exercises

Programming Exercises

1. String Comparison: L2061
2. String Compression: L2062
3. String Decompression: L2063

II. Knowledge Summary

✨ Core Idea of Character Arrays

A character array is an array of the char type. What makes it special is that it can be used together with strings:

1. It can be initialized using a string
2. A string can be read directly into the entire character array
3. The entire contents of a character array can be output directly
4. Built-in functions can be used to operate on character arrays

✨ Initializing Character Arrays

Brace Initialization

Initialize a character array directly using braces. Remember to leave space for the '\0' terminator.

char chArr[5] = {};
char chArr[5] = {'h', 'e'};
char chArr[5] = {'h', 'e', 'l', 'l', 'o'};
char chArr[6] = {'h', 'e', 'l', 'l', 'o'};

String Initialization

Initialize a character array using a string. Note that the string automatically appends '\0' at the end, so the array size must be one more than the string length.

char chArr[5] = "";
char chArr[5] = "he";
char chArr[5] = "hello"; // Error
char chArr[6] = "hello";
char chArr[] = "hello";

✨ Using Character Arrays

Common operations with character arrays include:

1. Read a string directly into a character array:

char chs[100];
cin >> chs;

2. Output the entire contents of a character array directly:

char chs[100] = "hello";
cout << chs;

3. Access the character at index i:

char chs[100] = "hallo";
chs[1] = 'e';
for (int i = 0; i < 5; ++i) {
    cout << chs[i];
}

✨ Built-in Functions for Character Arrays

strlen

The strlen function gets the length of a string. It takes one parameter — the string whose length you want to get — and returns an integer representing the string length.

char chs[100] = {'h', 'e'};
int length = strlen(chs);

strcpy

The strcpy function copies one string into another. It takes two parameters: the first is the destination string, and the second is the source string. This function has no return value.

Note: The destination string must have enough space to store the result — its size must be greater than the length of the source string.

char chs[100] = {'h', 'e'};
char chs1[100] = "hello";
strcpy(chs, "123"); // chs:123
strcpy(chs, chs1); //chs: hello

strncpy

The strncpy function copies a specified number of characters from one string to another. It takes three parameters: the destination string, the source string, and the number of characters to copy.

Note: After using strncpy, it is best to manually add a '\0' character at the end of the destination string to ensure it is a valid string.

1char chs[100] = {'h', 'e'};
2char chs1[100] = "hello";
3strncpy(chs, "123", 1); // chs:1
4chs[1] = '\0';
5strncpy(chs, chs1, 3); //chs: hel
6chs[3] = '\0';

strcat

The strcat function appends one string to the end of another. It takes two parameters: the first is the string to be appended to, and the second is the string to append. This function has no return value.

Note: The destination string must have enough space to store the result — ensure the concatenated string does not exceed the total size of the character array.

char chs[100] = {'h', 'e'};
char chs1[100] = "hello";
strcat(chs, "123"); // chs:he123
strcat(chs, chs1); //chs: hehello

strcmp

The strcmp function compares the lexicographic order of two strings. It takes two parameters representing the two strings to be compared.

The return value rules are as follows:

• If the first string is lexicographically less than the second, it returns -1
• If the two strings are identical, it returns 0
• If the first string is lexicographically greater than the second, it returns 1

strcmp("12", "123"); // Returns -1
strcmp("234", "12"); // Returns 1
strcmp("234", "34"); // Returns 1
strcmp("123", "123"); // Returns 0
strcmp("Zebra", "apple"); // Returns -1

Lexicographic Order

Lexicographic order comparison works as follows: compare characters at the same position in both strings one by one — the string with the smaller ASCII code at the first differing position is considered smaller. If all characters are identical, the shorter string is considered smaller.

✨ Character Array Execution Example

Problem: Compress the string "aaabbc" into "a3b2c1".

Approach: Traverse the string, count the number of consecutive identical characters, and output the character followed by the count.

1char str[100] = "aaabbc";
2int len = strlen(str);
3int i = 0;
4while (i < len) {
5    char ch = str[i];
6    int count = 0;
7    while (i < len && str[i] == ch) {
8        count++;
9        i++;
10    }
11    cout << ch << count;
12}

Step-by-step execution:

Final output: a3b2c1

✨ Core Idea of Simulation

The core idea of simulation is: do exactly what the problem says. Follow the rules described in the problem and use code to "reproduce" the entire process step by step — no need to find mathematical formulas or clever algorithms.

Simulation is the most intuitive problem-solving approach — if you can solve the problem by hand on paper, then translate each step of your manual calculation into code, and that is simulation.

✨ Algorithm Principle of Simulation

Problem-solving steps for simulation:

1. Read the problem carefully: Understand the rules of each step — do not miss any details
2. Manual simulation: Walk through the complete process with pen and paper on small data to confirm you understand the problem
3. Break into steps: Decompose the manual simulation into clear steps, each of which can be precisely described
4. Translate into code: Convert each step into code logic, typically using loops + conditional statements
5. Handle edge cases: Pay special attention to boundaries — beginning and end of arrays, empty strings, single characters, etc.

✨ Common Problem Types for Simulation

Simulation commonly appears in the following types of problems:

1. String Operation Problems

Transform strings according to rules, such as compression, decompression, encryption, reversal, etc. The string compression example above is a typical case.

2. Process Simulation Problems

The problem describes an operational process, and you need to output the final state. For example:

• Simulate a card shuffling process
• Simulate a robot walking on a grid following instructions
• Simulate the time after a clock rotation

3. Rule Translation Problems

The problem provides a set of complex rules that you must faithfully implement in code. These problems have no algorithmic difficulty — the challenge lies in not missing any rules and not getting the order wrong.

Characteristics of simulation:

• Advantages: Straightforward approach, no advanced algorithm knowledge required — "if you can do it, you can code it"
• Challenges: Code is usually long with many details, making bugs easy to introduce. It tests patience and coding ability

✨ Execution Example of Simulation

Problem: Decompress the compressed string "a3b2c1" back to "aaabbc". (The inverse of the compression above)

Manual simulation:

• Read 'a', followed by '3', output 3 'a's → "aaa"
• Read 'b', followed by '2', output 2 'b's → "aaabb"
• Read 'c', followed by '1', output 1 'c' → "aaabbc"

Translate into code:

1char str[100] = "a3b2c1";
2int len = strlen(str);
3for (int i = 0; i < len; i += 2) {
4    char ch = str[i];           // Current character
5    int count = str[i + 1] - '0'; // Next position is the repeat count (char to int)
6    for (int j = 0; j < count; j++) {
7        cout << ch;
8    }
9}

Step-by-step execution:

Final output: aaabbc

Note: This simplified version assumes the repeat count is a single digit (1-9). If the count could be multi-digit (e.g., "a12"), more complex parsing logic would be needed — this is an example of the "detail handling" aspect of simulation.

✨ Common Mistakes

1. Forgetting the '\0' terminator: Character arrays use '\0' to mark the end of a string. If you forget to add '\0' at the end after manually modifying a character array, you will get garbled or extra characters when outputting.
2. Insufficient array space: When using strcpy or strcat, if the destination array does not have enough space for the result, it will cause an out-of-bounds access.
3. Calling strlen repeatedly in a loop: for(int i=0; i<strlen(str); i++) recalculates the string length on every iteration (O(n)), making the entire loop O(n²). Save the length in a variable first: int len = strlen(str);
4. Confusing characters and strings: Single quotes 'a' denote a character, while double quotes "a" denote a string (containing 'a' and '\0' — two characters). strcpy(chs, 'a') is wrong — use strcpy(chs, "a") or chs[0] = 'a' instead.
5. Misjudging strcmp return values: strcmp does not necessarily return exactly -1, 0, or 1 — the standard only guarantees negative, zero, or positive values. Although most implementations return -1/0/1, it is better to use strcmp(a, b) < 0 rather than strcmp(a, b) == -1 for comparisons.

III. Homework

Knowledge Quiz

• Character Arrays and Simulation - Quiz## Programming Exercises

1. Check if It Forms a Palindrome: L2064
2. Occurrences of a String: L2065