SLC21 Week3 - Strings in C
Task # 1
Practically (i.e., with code examples) explain the theory from the first part of this lesson, where the concept of two sizes of an array is discussed. Demonstrate how to make it look like the array size can be incrthe eased/decreased. All loops should work with the array size stored in the size variable. Keep the physical, awasal size in the constant N.
In the programming language C, the size of the array is fixed at compile time. Like in the previous lesson, we had to solve a problem of finding divisors and store them in an array, but we didn't know what size of array to set as all numbers have different numbers of divisors, and the total number of divisors of a number can't be known beforehand. Therefore, we randomly chose the size of the array, which was large enough and had the capacity to store all the possible divisors.
It's not technically possible to resize the array, but interestingly, we can simulate that using two sizes like in the divisor problem.
Physical Size
It's the actual size of the array—the memory for the array, which we allocate before the compile time and which remains constant throughout.Logical Size
This size can be changed during execution based on the need or requirement of the problem we are solving. It represents the number of current elements stored in the array.
In that divisor problem, the total number of divisors was the logical size of the array. Let's see this through a simpler example.
I have written 4 functions that print an array, add/remove elements to the array, and remove elements from a specific position. Since the size will be changing, I have used two array sizes. Variable N will remain constant, which is the actual or physical size of the array. There's also a variable size that will change depending on the operations on the array.
In all the functions, I have set some conditions that will make sure the changing size of the array doesn't exceed the physical size Nor if the specific position falls in the range of the array. At first, I didn't write these conditions, but while checking the functions with different outputs, I got some garbage values, then I realised these conditions are necessary.
To add elements to the array, I wrote a function that takes the array address, current size, and number of elements that need to be added as input. Then, I increased the size by adding the total number of new elements to the original size. Then I just filled values in new positions.
To remove elements, I wrote a function with similar arguments; here the total number of elements that need to be removed are passed. I decreased the size of the array by subtracting the total number of removed elements from the current size. Then I just printed out the remaining array. Those values are still there in the physical storage but are not part of the logical size.
To remove an element from a specific position, I wrote a function that takes an array address, size, and position as arguments. I shifted all the next positions to the left meaning if pos 3 value needs to be removed, I shifted pos 4 value to pos 3, pos 5 value to pos 4, and so on. I then decreased the size of the array by 1 and printed the modified array.
Now the problem was that the value of size only changed locally in the respective functions. For this, I had to update the value of size after each function as well.
This is because a function cannot change the value of a variable when its value is passed as an argument. To change the value, we need to pass the address of the variable. I don't know if it was required in this lesson, but out of curiosity, when globally declaring the variable didn't work too, I made changes to the code—passed the address of the size instead of its value and the value changed outside the functions too. (:
Task#2
Declare a string variable (store any sentence in the array). Task: reverse the string, i.e., write it backward. For example: char s[]="ABCDEF";.....your code.....cout<<s; => FEDCBA
Logic:
To reverse the string, I swapped the first and last characters, 2nd and 2nd last characters, 3rd and 3rd last characters, and so on, until there was no or just 1 character left.
Implementation:
The first character is, of course, at position 0, but what about the last character? Since we are not supposed to use the library functions, I ran a loop until '\0' , counted the total characters, and stored them in the variable len. The first position starts from zero in the array, so the last character would be at len-1.
Now that I have 1st and last position (last_pos), I will swap both. For swapping, I have stored the first position in another variable, temp_char, assigned the last position to the first, and the first position, which was temporarily shifted to another variable, assigned to the last position.
Then I moved to the 2nd position by i++ and the 2nd last position by last_pos--. I performed the same swapping procedure on the new pair.
Repeated this until i<last_pos. It will make sure that i is always behind last_pos and they don't cross paths. Both pointers/positions reach the middle point because if they go beyond that in their respective directions, then they will get already swapped characters, and we don't want that. When the length of the string is odd, the left-out character will not be touched, meaning it will remain in the original position.
This approach will keep the total iterations half of the length of the string (strlen/2) because we are tackling two positions/characters at a time.
I have commented out the printf functions; remove the comment commands and run the program to see the entire process step by step.
Task#3
Swap neighboring letters char s[]="ABCDEF";.....your code.....cout<<s; => BADCFE
Logic:
To swap adjacent characters, I have used the same swapping commands on 1st and 2nd characters, 3rd and 4th characters, and so on, until the end of the array.
Implementation:
Integer i tells the current position and temp_char does the same job as in the previous code. I swapped characters at first (i=0) and second (i+1) positions, then updated the current position to the 3rd character (i=i+2). Then swapped third and fourth characters and updated the new position to 5th character, and so on.
Now, the big question was when to stop. Initially, I made the loop run until the first character in the swapping pair was a null character. But I realized my mistake as soon as I entered the input with an odd length. So, I corrected it by running the loop until the second character in the swapping pair was a null character. This means the program stops at the 2nd last character when the length of the string is odd because the last pair would be of a substantial character and a null character. I shouldn't swap the last character with the null character. Doing so will cut the last character of the string because it will then be a null character.
This while loop condition (string[i+1]!= '\0') was giving correct results for both even and odd lengths. But then I had another thought—what comes after the null character? When the length is even, then the last pair string[i] would be a null character and string[i+1]some garbage value, which is out of the bound for our array.
I was wondering why that garbage value didn't swap with null. It didn't show when I allocated extra space for the array and even not when I didn't. Then I tried directly accessing the value after the null character, and again, nothing showed. Apparently, it was all null afterwards or was it?
To be on the safe side and fearing that garbage value might show up in unforeseen scenarios, I thought to change the condition of the while loop and make it run until the current position is less than one minus length of the array. It will ensure that the last swapping pair is valid and doesn't have a null or out-of-bound value.
I have commented out the printf functions; remove the comment commands and run the program to see the entire process step by step.
Task#4
Shift the string cyclically to the left (it’s easier to start with this), then cyclically to the right. char s[]="ABCDEF", x[]="abrakadabra";.....your code.....cout<<s<<"\n"<<x; => BCDEFA aabrakadabr
In left cyclic shift, each character moves back (left) to its immediate previous position, and the first character cycles back to the last position.
The function shift_left() takes an array of characters as input. Stores the first character in temp. Starts the loop from the first position and assigns the next character to the current position. Updates the current position to the next and repeats the assigning instruction and stops when it reaches the end (null character). After the loop, it assigns the original value of the first position, which was stored in temp, to the last position.
In right cyclic shift, each character moves (right) to its immediate next position, and the last character cycles back to the first position.
The function shift_right() also takes a character array as input. Finds the length of the array and stores the last character at (length-1) in temp. It then assigns the 2nd last character to the last position, updates the current position to the 2nd last position, and repeats till the 2nd position. After the loop, it assigns the original value of the last position, which was stored in temp to the first position.
I tried traversing the array in a forward direction, like in left shift, but it required saving each next character before assigning a new value to it. Therefore, I went with reverse traversing; it required saving only the last character.
Task#5
Remove all vowel letters char s[]="this is some text";...your code...cout<<s; => ths s sm txt
Logic:
After writing codes for cyclic shifts, my first thought was to find a vowel and shift left the array from the end till the vowel position and repeat until all vowels are removed. I even wrote the code, and it worked fine, but I must admit the nested loops made me crazy. But most importantly, it wasn't an efficient approach time-wise. It would require numerous shift lefts for large data for every detected vowel. But there's also a simpler approach—skipping vowels and copying/re-assigning only the consonants to new positions.
Implementation:
I created a function vowel_check() that takes a character array as input. There are two indices, i and p, i reads the array, and p re-assigns consonants. When a consonant is found, it is copied in index p and then both indices are incremented. When the character is a vowel, p remains the same, but i is incremented (we move to the next character by skipping the vowel). If the next is a consonant, we assign it to the currentp index (which had a vowel initially) repeat until the null character, and finish the string by placing the null character at the last/current p index.
I have placed a flag is_vowel_removed to print different messages when the vowels are found and when not.
Task#6
Double each vowel letter char s[]="this is some text";...your code...cout<<s; => thiis iis soomee teext
I reserved some extra memory for the array, whose size will probably increase.
Logic:
Similar to my previous approach to the last problem, I am finding the vowel, shifting right all the characters that come after it, and adding a duplicate vowel next to the found vowel. Repeating until all characters are checked.
Implementation:
When the vowel is found, I shifted the last character to the next position, the 2nd last to the last position, and the 3rd last to the 2nd last—shifting right basically. This shift is only for the characters after the vowel. Now we have an overwritten location next to the vowel, I changed it to the duplicate vowel. Updated the current position by incrementing the current position twice to skip the duplicate vowel and check the next new character. I updated the new length of the array then.
If a vowel is not found, I simply moved to the next position.
Repeated this until the current position was less than the new length, which ensured that we have reached and checked the last character.
Additional Task
as a replacement for any of the tasks 2-6: Choose any number, preferably slightly larger than the length of the text. Increase the text length to the specified number by adding spaces between words. char s[]="this is some text";...your code...cout<<s; => (this is some text) len of s => 17 number =27
I barely managed to complete the homework due to health and commitments. No time for the extra task this week. :(