Day 02 Prep Work - [homepage](http://gddh.github.io/)
========================
## Arrays
**Array** - A collection of items of the same type stored at continuous memory locations.
```int val[7] = {11, 22, 33, 44, 55, 66, 77}```
In the image above, the array is storing integers, but arrays can store any data type, whether it is characters, structs, pointers, etc.
**NOTE:**
- Index starts at zero
- To access the first element: `val[0]`
- The amount of memory that is allocated for an element of the array will differ depending on the the *type* of the data.
- The array has nothing inherently indicating the end of memory. This means I can (and I have multiple times), accessed memory past or before the array. Be careful!
- In the above code, we *initialize* the code to values. Consider```int num[7]```.
We've declared an array of integers that has 7 memory slots, but we didn't assign actual values to those slots. There will be "garbage value" in those slots, and it is possible to access them. It's very possible that neither the compiler nor the program will notice that you are accessing garbage values. Just as when you declare a variable without explicitly assigning a value. Be careful!
## Strings
**Strings in C** - an array of characters with a null terminator ``` \0 ``` at the end.
An example of a string declaration is as follows:
```
char greeting[6] = {'H', 'e', 'l', 'l', 'o', '\\0'};
```
When a String is initialized as follows, it will automatically put a null terminator in for you.
```
char greeting[] = "Hello";
```
## Pointers
**Pointers** - variables that hold the address of the variable they are pointing to.
Consider the following:
```
int x;
int *ptr; /* pointer variable declaration */
x = 2;
ptr = &x; /* store address of x in pointer variable*/
printf("variable x is at address: %p\n", (void*)&x);
printf("x is %d and *ptr is %d\n", x, *ptr);
```
- Assigned the value 2 to the variable `x`. To be specific, the memory location of `x` now holds the value two.
- Then assigned the address of the memory location of `x` to the value of ptr. To access the address of `x`, we use `&x`. So when we print p in the first `printf`, a memory address is printed.
- The final line prints the value of `x` and the value that `ptr` is pointing to.
**Explicit breakdown:** `ptr` has some memory space when we defined it. That memory space becomes the address of `x`. When we *dereference* by doing `*ptr`, we say "go the address that is in `ptr`'s memory space and get it's value."
### Dereferencing Definition
Brian Harvey's notes contain a great explanation of dereferencing.
If `*p` is used to the right of the assignment operater(=), it means get me the contents of the memory location whose address is in variable p,” or, if `*p` is used to the left of the assignment operator (=), “store something into the memory location whose address is in variable p.”
### Pointers in Detail
Consider the following example for further clarification on pointers
The first line assigns 1 and 2 to the variables `x` and `y`, respectively.
The second line declares an int pointer, `ip`.
In the following list, each number corresponds to the row in the example.
1. Put the *address* of variable `x` into the space of the pointer `ip`.
2. Dereference the pointer `ip` - go to the address that `ip` holds (which is 100) and get the value at that address, which in this case is 1. Then put the value at that address, 1, into the memory space that `y` holds.
3. Set the value of `x` to be the value of `ip`, which is the address of the value `x`.
* Notice that `ip` is a pointer, and its value is an address. The value of `ip` is not the value of the thing that it is pointing at.
* In the example, ip's `value` is 100, the address x, not x's value `1`.
* Note this is a compilation error when using compilation flags `-Wall -Wextra -Werror`
4. The `*ip` means derefence `ip`. This means go to the address that `ip` holds and get the value. Then set that value to three.
* the address that `ip` holds is 100. So we will go to memory location 100. We will get that value, which is 100 (do not be confused. `x` has the value of 100 and the memory location of 100).
* Then set that value at memory location 100 to 3.
The illustrated example I got from here if you are interested in further reading: (https://users.cs.cf.ac.uk/Dave.Marshall/C/node10.html#fig:point)
### Postfix Increment, Preix Increment, and Dereferencing. (Extra for Experts)
*Personal Opinion:* If you are still unfamiliar with developing functions and pointers, I highly recommend skipping this part and not worry about mixing postfix and prefix operations with derferencing. In fact, I would recommend staying away from postfix and prefix operations until you feel comfortable enough with developing functions.
#### Question:
How do I interpret the following?
```
*ptr++
*++ptr
++*ptr
```
#### Prerequisite for Understanding
Consider the following **Prefix and Postfix Increment**
```
1 int i = 0;
2
3 printf("%d\n", ++i); --> prints 1
4 printf("%d\n", i); --> prints 1
5 printf("%d\n", i++); --> prints 1
6 printf("%d\n", i); --> prints 2
```
To fully understand, consider three thing:
1. **Value of the expression**
- The expression: `d++`
- The value of the prefix expression evaluates to `d + 1` because prefix means you add then evaluate
- The value of the postfix expression evaluates to `d` because postfix means you evaluate then add.
2. **Side Effect**
- Prefix: C guarantees that **before** evaluating the expression, C will decrement the variable.
- Postfix: C guarantees that **after** evaluating the expression, C will increment the variable.
- to be clear consider the following dummy program:
```
int main(void) {
int i = 1;
if (i++ < 2 && i++ < 2) <--- i increments AFTER first condition, fails the second
printf("%d\n", i);
else
printf("oh no %d\n"); <--- prints "oh no 3\n"
}
```
**Note:** The program fails on the second condition. (Try taking it out!) The first i++ will evaluate to 1 < 2, which is true, while the second condition will evaluate 2 < 2 which is not true.
### Solving the Question
Now let's add dereferencing concept. To do so, we must consider one more thing.
3. **Precedence**
- Because dereferencing is an operation by itself, we have to consider whether the postfix/prefix operation has precedence over the dereference operation.
- This is just like multiplication has precedence over addition)
- Postfix has a higher precedence than dereferencing
- Prefix has the same precedence as dereferencing.
- When precedence are equivalent, `right to left` associativity takes over, meaning we evaluate from right to left.
```
1 int main() {
2 const char* p = "Hazuki";
3 printf ("%c\t", *p); // note space in format string
4 printf ("%c\t", *++p); // value of ++p is p after the increment
5 printf ("%c\t", *p++); // value of p++ is p before the increment
6 printf ("%c\t", *p); // value of p has been incremented as a side effect of p++
7
8 char p1[] = "Jeff";
9 printf("%c\n", *p1);
10 printf("%c\n", ++*p1);
7 }
```
Outputs
```
e1z2r8p36% ./a.out
H a a z
J
K
```
Explanation
- Line 2: create a pointer, `p`, that points to the beginning of the *string literal* "Hazuki"
- Line 3: prints the char that `p` is pointing at, `H`
- Line 4: since postfix has same precedence as derference, evaluate left to right.
- First increment `p`, `p` will point to character `a`
- THEN dereference
- Line 5: Since the postfix has priority, evalute value of `p++`, which is just `p`. `p` points to char `a`, so print `a`.
- The side effect of incrementing `p` occurs before the next use of `p`
- `p` now points to `z`
- Line 6: Dereference `p`, which points to `z`
- Line 8: create a string `p1` with the value `Jeff`
- Line 9: Print the first character
- Line 10: Since prefix has same priority as dereference, right to left associativity.
- Dereference p1
- Increment the value of p1 from `J` to `K`
- The ascii value of `J` is 112. 112 + 1 = 113, which is ascii value for `K`
Another [explanation](https://stackoverflow.com/questions/18481740/pointer-expressions-ptr-ptr-and-ptr?utm_medium=organic&utm_source=google_rich_qa&utm_campaign=google_rich_qa) of the same core concept.
## The Main()
When a C program starts, the computer will run a some machine code (same for every program) to prepare running C program. The next step is to run the ```main()``` function. The main definition is:
```int main(int argc, char **argv)```
**Basic Information**
- The return value of the main should be 0 when everything works properly.
- `int argc` is the argument count
- `char **argv` is an array of strings, or a pointer to pointers.
- The first argument that the main takes is the program name itself.
- Argv is indexed starting at 0.
Consider the following program:
```
int main(int argc, char **argv)
{
int i;
i = 0;
printf("%d\n", argc);
while (i < argc)
{
printf("%d\n", argv[i]);
i = i + 1;
}
}
```
If we go to the terminal compile and run ```./a.out "hello" "hi" "test"```, we will get:
```
4
./a.out
hello
hi
test
```
### **Argv
```**Argv``` is an array of pointers to strings. It can also be interpreted as a pointer to a pointer to a character (a string is a pointer to a character - the character is held in an array of characters with a null terminator). We can visualize the above example as follows:
```
argv [ ]
|
|
V Strings
argv[0] [ ] -----> [./a.out]
argv[1] [ ] -----> [hello]
argv[2] [ ] -----> [hi]
argv[3] [ ] -----> [test]
```
A couple things to keep in mind
- argv[i] is equivalent to *(argv + i). Meaning that argv itself is a pointer and if do: ```argv = argv + 1;```, the pointer will now point to what is argv[1] in our illustration above.
- Strings are character arrays with a null terminator, so the pointer at argv[i] is pointing at the first character of the character array.
- You will often see in our main function we use argv[1]. That means we are passing in the first argument after the program name.
### Multidimensional Arrays
The concept of pointers to pointers can actually be expanded to multidimensional arrays. The one that you will use in the near future is the 2D array. In fact argv is actually a 2D array, but let's consider an integer 2D array. (This is actually the concept that Isaac implemented in his BSQ.)
```
int a[3][4] = { {0, 1, 2, 3} , /* initializers for row indexed by 0 */
{4, 5, 6, 7} , /* initializers for row indexed by 1 */
{8, 9, 10, 11} }; /* initializers for row indexed by 3 */
a[0][0] ---> 0 a[0][1] ---> 1 a[0][2] ---> 2 a[0][3] ---> 3
a[1][0] ---> 4 a[1][1] ---> 5 a[1][2] ---> 6 a[1][3] ---> 7
a[2][0] ---> 8 a[2][1] ---> 9 a[2][2] ---> 10 a[2][3] ---> 11
```
The way I like to think about 2D arrays to simply substitute the second dimension with variables. I will show you with the above example.
```
int a[3][4] = { {0, 1, 2, 3} , /* initializers for row indexed by 0 */
{4, 5, 6, 7} , /* initializers for row indexed by 1 */
{8, 9, 10, 11} }; /* initializers for row indexed by 3 */
/* Let's subsitute the second dimension as follow */
first_row = {0, 1, 2, 3}
second_row = {4, 5, 6, 7}
third_row = {8, 9, 10, 11}
int a[3] = {first_row, second_row, third_row};
```
Now our 2d array is conceptually a 1d array. So what how do we access the 6 in the second row? We would do ```a[1][2]``` , but let's understand what is going on.
```
a[ ] The parenthesis emphasize that we are
| using what we accessed from the left.
|
V (a[y])[0] (a[y])[1] (a[y])[2] (a[y])[3]
(a[0]) [ ] ---> { 0 , 1 , 2 , 3 }
(a[1]) [ ] ---> { 4 , 5 , 6 , 7 }
(a[2]) [ ] ---> { 8 , 9 , 10 , 11 }
```
First access the array in the second row, by using ```a[1]```. In our earlier abstraction this will give us the array that we call `second_row`. We can then access the third element in `second_row` by doing `second_row[2]` (remember, it is 2 b/c index zero).
Putting it all together, we get `a[1][2]`.
Keep in mind that multidimensional arrays can go into as many dimensions as the programmer wants, but the fundamental idea is all the same. It is just pointers to pointers.
### Standard 2D Array Traversal
Oftentimes, we will have to traverse a 2D array. To traverse the 2D array, means we will go through the 2D array.
```
int i;
int j;
i = 0;
while (i < max_Y) /* traverse each row */
{
j = 0;
while (j < max_X) /* traverse each column in the ith row */
{
j = j + 1;
}
i = i + 1;
}
```
## Why separate functions are important.
Let's consider the pgcd question. https://github.com/gcamerli/examshell/blob/master/level3/pgcd/subject.en.txt
After reading the instructions, I break down the task as follows. (If you don't know what gcd is, google it.)
1. Write a program where if the number of parameters is not 2, display a newline.
- The word program tells me I need a main.
- number of parameters not 2 says I need to check argc.
- If it is 2, I need to find the gcd.
- If not simply display a new line.
2. It takes two strings representing two strictly positive integers that fit in an int.
- I need to convert the strings to integers so I can work mathematically with them.
3. Find their highest common denominator(It's always a strictly positive integer).
- I need to select the smaller of the two numbers
- Starting from the smaller of the two, I need to
- check if it is a divisor of both numbers.
- If it is, we've found the gcd
- decrement a copy of the smaller number and repeat
4. Print the number
As a problem, it seems like there are alot of things to do, so to make the problem manageable, we break down the problem into subproblems. Below is one take on how to break down the problem into subproblems. I will discuss the benefits of doing it in this way, but first back to the problem.
No. 1 is just a standard check that we do in our programs. No. 2 is preparing the input so that it can properly used in the actual calculations. We can convert strings to ints using atoi, a function we are familiar with. Let's focus on these tasks in the main.
```
int main(int argc, char **argv)
{
int v1;
int v2;
if (________________)
{
v1 = _______________;
v2 = _______________;
pgcd(v1, v2);
}
____________________;
}
```
This leaves us with no. 3 and no. 4. We can solve no. 3 using a simple check to see if ```v2``` is smaller than ```v1```. If it is we simply swap them, using ```ft_swap```. This way we "force" ```v1``` to be smaller than ```v2```. Then we just have to find the gcd using the method described above. Let's translate this to code:
```
#include ___________
#include ___________
void ft_swap(int *v1, int *v2)
{
_______________
______________
______________
______________
}
int is_divisor(int v1, int v2, int gcd)
{
return (v1 % gcd == 0 && _______________);
}
int find_gcd(int v1, int v2)
{
int gcd;
gcd = v1;
while (______________)
{
if (____________________)
return gcd;
____________________
}
return (1);
}
void pgcd(int v1, int v2)
{
int gcd;
if (______________)
___________________;
gcd = __________________;
printf("%d", gcd);
}
```
As you gain experience, you can get a feel for how broken down you want your subproblems to be.
### Reasons to separate functions
- **Reusability** You can reuse the functions elsewhere. For example imagine you were writing a program that performs different sorts at the scale of BSQ. It's very likely that you'll need to swap two integers in multiple places in the program. By encapsulating the swap logic in a separate function, I can use it in multiple places.
- **Manageability** It separates logic into manageable parts. This makes it easier for you to think about the problems. By separating the logic, I can focus on one particular part of the problem and solve that part. Then move on.
- It's easier to check. By separating your program into functions, you can go through each function logically easier and faster. It is easier on the eye when you are looking for a bug. For example, when you are looking at ```ft_swap```, you can ask yourself, what is ``ft_swap`` supposed to be doing and only check that particular part.
- **DRY - Don't repeat yourself.** It prevents you from repeating yourself. By placing the subroutine into a function, and simply calling that subroutine when we need to, we make it easy to change the subroutine. Let's say today you wrote a compare function to compare iphones and it works as part of a bigger program that sorts iphones into some order. Tomorrow you realize you need to compare samsung phones instead. You can simply change the compare function, rather than going through your bigger program and changing every part that used the compare subroutine.
- **Modularity** Just like you would replace car parts, you can also replace functions, depending on your needs. If you have a library of functions, you can always swap out functions that fit your needs for the given problem. Let's say you have ```ft_putstr``` and ```ft_putnbr```, depending on what your printing, you can simply choose between putnbr and putstr, but the rest of your program can stay the same.
# Problem Set
1. Write ```ft_putstr```
2. Write ```ft_strlen```
3. Write ```char *ft_strcpy(char *dest, char *src)```
- This will copy the contents of the source pointer into the space of the destination pointer.
- It will return the destination pointer
4. Write ```char *ft_strrev(char *str)```
- ft_strrev will take a string and reverse the string inplace.
- a => a
- ab => ba
- abcde => edcba
5. Write ```ft_atoi```
- Atoi will skip all whitespaces and take an optional + or -. It will then convert the ascii characters to integers and stop when you hit the first non integer character.
6. Write a function that will take a pointer to an int as an argument and change the value of that pointer to 42. It's prototype is```void ft_ft(int *nbr)```
```
#include _________________
void ft_ft(int *nbr)
{
_________________
}
```
7. Write a main to prove that your function works.
```
int main(void)
{
int x;
int *p;
x = 5;
_______________
printf("x before ft_ft is %d\n", x);
ft_ft(_____);
printf("x after ft_ft is %d\n", x);
}
```
8. Write a function ```void ft_ultimate(int *****ptr)``` that takes a pointer to pointer to pointer to pointer to pointer to int as a parameter and sets the value "42" to that int.
9. Write a main to prove that your function works.
10. Write a function that divides parameters `a` by `b`. The result of this division is stored in the int pointed by `a`. The remainder of the division is stored in the int pointed by `b`. It's prototype should look like this``` void div_mod(int *a, int *b) ```
11. Write a program called search_and_replace that takes 3 arguments, the first arguments is a string in which to replace a letter (2nd argument) by another one (3rd argument). If the number of arguments is not 3, just display a newline. If the second argument is not contained in the first one (the string) then the program simply rewrites the string followed by a newline.
```
$>./search_and_replace "Papache est un sabre" "a" "o"
Popoche est un sobre
```
12. Write a program that takes a string and reverses the case of all its letters. Other characters remain unchanged. You must display the result followed by a '\\n'. You may use the write function. If the number of arguments is not 1, the program displays '\\n'
```
$>./ulstr "L'eSPrit nE peUt plUs pRogResSer s'Il staGne et sI peRsIsTent VAnIte et auto-justification." | cat -e
l'EspRIT Ne PEuT PLuS PrOGrESsER S'iL STAgNE ET Si PErSiStENT vaNiTE ET AUTO-JUSTIFICATION.$
```
13. Write ```ft_strcmp(char *str1, char *str2)```;
--------------------------------------
--------------------------------------
--------------------------------------
# Solutions
Solution to gcd example
```
#include <stdlib.h>
#include <stdio.h>
void ft_swap(int *v1, int *v2)
{
int tmp;
tmp = *v1;
*v1 = *v2;
*v2 = tmp;
}
int is_divisor(int v1, int v2, int gcd)
{
return (v1 % gcd == 0 && v2 % gcd == 0);
}
int find_gcd(int v1, int v2)
{
int gcd;
gcd = v1;
while (gcd > 1)
{
if (is_divisor(v1, v2, gcd))
return gcd;
gcd = gcd - 1;
}
return (1);
}
void pgcd(int v1, int v2)
{
int gcd;
if (v2 < v1)
ft_swap(&v1, &v2);
gcd = find_gcd(v1, v2);
printf("%d", gcd);
}
int main(int argc, char **argv)
{
int v1;
int v2;
if (argc == 3)
{
v1 = atoi(argv[1]);
v2 = atoi(argv[2]);
pgcd(v1, v2);
}
printf("\n");
}
```
1. ft_putstr
```
#include <unistd.h>
void ft_putchar(char c)
{
write(1, &c, 1);
}
void ft_putstr(char *str)
{
int i;
i = 0;
while (str[i] != '\0')
{
ft_putchar(str[i]);
i = i + 1;
}
}
```
2. ft_strlen
```
int ft_strlen(char *str)
{
int i;
i = 0;
while (str[i] != '\0')
{
i = i + 1;
}
return (i);
}
```
3. ft_strcpy
```
char *ft_strcpy(char *dest, char *src)
{
int i;
i = 0;
while(src[i] != '\0')
{
dest[i] = src[i];
i = i + 1;
}
dest[i] = '\0';
return dest;
}
```
4. ft_strrev
```
int ft_strlen(char *str)
{
int i;
i = 0;
while (str[i] != '\0')
i = i + 1;
return (i);
}
void char_swap(int i1, int i2, char *str)
{
char tmp;
tmp = str[i1];
str[i1] = str[i2];
str[i2] = tmp;
}
char *ft_strrev(char *str)
{
int len;
int i;
char tmp;
i = 0;
len = ft_strlen(str);
while (i < len / 2)
{
char_swap(i, len - i - 1, str);
i = i + 1;
}
return (str);
}
```
Another way to write strrev is
```
char *ft_strrev(char *str)
{
int i;
int l;
char t;
l = 0;
while (str[l] != '\0')
l++;
i = -1;
while (++i < --l)
{
t = str[i];
str[i] = str[l];
str[l] = t;
}
return (str);
}
```
When I first started writing C, I personally preferred the first way, but as I became more and more familiar. I started liking the second way. On exams, however, I would probably stick to the first way because I know there is no way I can mess up ```ft_strlen```, and ```char_swap```, or if I do, I'm familiar enough with it that I won't be worried about debugging it. Then I can focus on ```ft_strrev```
5. ft_atoi
```
int is_whitespace(char c)
{
return ((c > 8 && c < 14) || (c == ' '));
}
int is_nbr(char c)
{
return (c >= '0' && c <= '9');
}
int convert_num(char c)
{
return (c - '0');
}
int ft_atoi(char *str)
{
int i;
int neg;
int total;
i = 0;
neg = 1;
total = 0;
while (str[i] != '\0' && is_whitespace(str[i]))
i = i + 1;
if (str[i] == '+' || str[i] == '-')
{
if (str[i] == '-')
neg = -1;
i = i + 1;
}
while (str[i] != '\0' && is_nbr(str[i]))
{
total = total * 10 + convert_num(str[i]);
i = i + 1;
}
return (total * neg);
}
```
Notice how I used the helper functions ```is_whitespace``` and ```convert_num```. I used ```is_whitespace``` more than I can remember during the exam prep process of the Piscine. ```convert_num``` will be useful when you do things like ```ft_atoibase```.
Learn this function well. Be able code this up whenever. This is just as important as functions such as```ft_strlen```.
6. and 7. ft_ft and proof
```
#include <stdio.h>
void ft_ft(int *nbr)
{
*nbr = 42;
}
int main(void)
{
int x;
int *p;
x = 5;
p = &x;
printf("x before ft_ft is %d\n", x);
ft_ft(p);
printf("x after ft_ft is %d\n", x);
}
}
```
8. and 9. ft_ultimate and proof
```
#include <stdio.h>
void ft_ft(int *****nbr)
{
*****nbr = 42;
}
int main(void)
{
int x;
int *p;
int **pp;
int ***ppp;
int ****pppp;
int *****ppppp;
x = 5;
p = &x;
pp = &p;
ppp = &pp;
pppp = &ppp;
ppppp = &pppp;
printf("x before ft_ft is %d\n", x);
ft_ft(ppppp);
printf("x after ft_ft is %d\n", x);
}
```
10. void div_mod
```
void ft_ultimate_div_mod(int *a, int *b)
{
int tmp;
tmp = *a;
*a = *a / *b;
*b = tmp % *b;
}
```
11. search_and_replace
```
#include <unistd.h>
void ft_putchar(char c)
{
write(1, &c, 1);
}
int ft_strlen(char *str)
{
int i;
i = 0;
while (str[i] != '\0')
i = i + 1;
return (i);
}
void search_and_replace(char *str, char c1, char c2)
{
int i;
i = 0;
while(str[i] != '\0')
{
if (str[i] == c1)
ft_putchar(c2);
else
ft_putchar(str[i]);
i = i + 1;
}
}
int main(int argc, char **argv)
{
if (argc == 4)
{
if (ft_strlen(argv[2]) == 1 && ft_strlen(argv[3]) == 1)
search_and_replace(argv[1], argv[2][0], argv[3][0]);
}
ft_putchar('\n');
}
```
12. ulstr
```
#include <unistd.h>
void ft_putchar(char c)
{
write(1, &c, 1);
}
void rvrsecase(char c)
{
int diff;
diff = 'A' - 'a';
if (c >= 'a' && c <= 'z')
ft_putchar(c + diff);
else if (c >= 'A' && c <= 'Z')
ft_putchar(c - diff);
else
ft_putchar(c);
}
void ulstr(char *str)
{
int i;
i = 0;
while (str[i] != '\0')
{
rvrsecase(str[i]);
i = i + 1;
}
}
int main(int argc, char **argv)
{
if (argc == 2)
{
ulstr(argv[1]);
}
ft_putchar('\n');
}
```
13. ft_strcmp
```
int ft_strcmp(char *str1, char *str2)
{
int i;
i = 0;
while (str1 != '\0' && str1[i] == str2[i])
i = i + 1;
return (unsigned char)str1[i] - (unsigned char)str2[i];
}
```
Note the cast to unsigned char is unnecessary.
Sign in with Wallet
Connect another wallet