reveal.js

# Strings, Arrays, and Pointers

---

CS 130 // 2024-11-19

# Review

#### average of four numbers

```c 
#include <stdio.h>

int main()
{
    int a, b, c, d;
    printf("Enter an integer: ");
    scanf("%d",&a);
    printf("Enter an integer: ");
    scanf("%d",&b);
    printf("Enter an integer: ");
    scanf("%d",&c);
    printf("Enter an integer: ");
    scanf("%d",&d);

printf("The average is %f\n",(a+b+c+d)/4.0);

return 0;
}
```

#### Address of operator

**NB:** The `&` operator means "address of" - read from keyboard and store in a specific address in memory

```c 
    int a;
    scanf("%d",&a);
```

What do `"%d"` and `"%f"` mean?

#### reverse array function

```c 
#include <stdio.h>

void reverse(int arr[], int n)
{
    int rev = n-1;
    int start = 0;

while(start < rev)
    {
        int temp = arr[start];
        arr[start] = arr[rev];
        arr[rev] = temp;
        start++;
        rev--;
    }

}

int main()
{
    int arr[5] = {1, 2, 3, 4, 5};
    reverse(arr, 5);
    for (int i = 0; i < 5; i++) 
    {
        printf("The next value is: %d\n", arr[i]);
    }
    return 0;
}
```

## `printf` and `scanf`

https://www.cplusplus.com/reference/cstdio/printf/

https://www.cplusplus.com/reference/cstdio/scanf/

# Strings

## Strings
- There is no **String** type in C
- 
 Strings are just arrays of type `char`
    ```c
    char str[20] = "abc";
    printf("The string is %s", str);
    ```
- 
 The above code is shorthand for the following:
    ```c
    char str[20];
    str[0] = 'a';
    str[1] = 'b';
    str[2] = 'c';
    str[3] = '\0';   // String terminating character
    ```
- 
 The remaining 16 characters are unused

## Strings
- Suppose we forget to include the `'\0'` character
    ```c
    char str[20];
    str[0] = 'a';
    str[1] = 'b';
    str[2] = 'c';
    printf("The string is %s", str);
    ```
- What do you think happens?
- 
 `printf` continues printing characters until it finds some random `'\0'` character in memory

## Strings
- Very simple string operations now become complicated...
- 
 Suppose I want to concatenate two strings:
    ```c
    char s1[20] = "hello";
    char s2[20] = "world";
    char s3[20] = ??? // how do I concatenate s1 and s2?
    ```
- 
 Manually copy all the characters into `s3`...

## Strings
```c
char s1[20] = "hello";
char s2[20] = "world";
char s3[20];

int j = 0;   // keeps track of the next spot in s3
for (int i = 0; s1[i] != '\0'; i++) {
    s3[j] = s1[i];
    j++;
}
for (int i = 0; s2[i] != '\0'; i++) {
    s3[j] = s2[i];
    j++;
}
s3[j] = '\0';
```

## Strings
- Luckily, there is a `string.h` library with a few helpful functions that does some of this for us, but they just do the same thing as above
```c
#include <string.h>
char s1[20] = "hello";
char s2[20] = "world";
strcat(s1, s2);
printf("The new string is: %s", s1);
```

## Strings
- Here is a common issue:
    ```c
    char s[3] = "abc";
    int x = 10;
    printf("The values are %s and %d", s, x);
    ```
- 
 We did not allocate enough space in `s` to store the string termination character `'\0'`
    ```c
    char s[4] = "abc";
    int x = 10;
    printf("The values are %s and %d", s, x);
    ```

# Pointers

## Address-of Operator

Try this out and discuss what you think is going on

```c
#include  <stdio.h>

int main()
{ 
    int var = 0;
    int arr[3] = {1,2,3};
    printf("Address of var: %p\n", &var);
    printf("Address of arr[0]: %p\n", &arr[0]);
    printf("Address of arr[1]: %p\n", &arr[1]);
    printf("Address of arr[2]: %p\n", &arr[2]);
}
```

## Arrays are addresses

```c
#include  <stdio.h>

int main()
{ 
    int var = 0;
    int arr[3] = {1,2,3};
    printf("Address of var: %p\n", &var);
    printf("Address of arr[0]: %p\n", arr);
    printf("Address of arr[1]: %p\n", arr+1); //does this add 1 or 4?
    printf("Address of arr[2]: %p\n", arr+2);
}
```

## Address vs. Pointer

* A **pointer** is a variable that contains an address of some other thing in memory

* Arrays *are* pointers in C

## Pointers
- One of the most powerful features of C is declaring "pointers" to values
- 
 A **pointer** is a variable whose value is the address of a memory location
- 
 To declare a variable as a pointer, you use a `*` before the variable name:
    ```c
    int *p;    // p contains an address to an int
    ```

## Pointers
- To get the memory address of a variable, we use `&`, the address operator
    ```c
    int x = 5;
    printf("Address of x is: %p\n", &x);
    int *p = &x;   // p is pointing to x's memory location
    ```
- 
 To access the value a pointer is "pointing to", you can **dereference** it using the `*` operator
    ```c
    int y = *p;  // gets the int p is pointing to
    printf("p was pointing to %d\n", y);
    ```

## Arrays are Pointers
- In C, arrays are just **pointers**
    ```c
    int arr[10];  // arr is a pointer to the address of the
                  // first element of the array
    ```
- 
 You can use array notation on pointers and pointer notation on arrays
    ```c
    int *p = arr; // p points to what arr is pointing to
    p[0] = 100;   // changes arr[0] to be 100
    int x = *arr; // gets 100 back
    ```

## Exercise 1
- Suppose we want to write a function that computes the average of a bunch of `double` values
- 
 What would the prototype of this function be?
    ```c
    double average(double arr[], int n)
    ```

- 
 Finish writing the function

## Exercise 2
- Write a program that asks the user to enter in 10 doubles, computes the average, and prints it off
- Use an array and a loop to get input from the user
- Use the `average` function to compute the average

## Exercise 3
- How can we modify this program so that the user can enter **any** number of inputs?

# C and The Computer's Memory

## A Problem
- Suppose I want to create a function called `duplicate` that takes an array of integers as input, creates an identical copy of it, and returns it
- What are some issues we have to think about when implementing this?

## A First Attempt

```c
int * duplicate(int *arr, int n) {
    int new_arr[n];
    for (int i = 0; i < n; i++) {
        new_arr[i] = arr[i];
    }

return new_arr;
}
```
- 
 This is incorrect!
- 
 The array `new_arr` is **locally scoped** and its memory is freed once the function returns!

## Try it yourself and see what happens

```c
#include  <stdio.h>

int * duplicate(int *arr, int n) 
{
    int new_arr[n];
    for (int i = 0; i < n; i++) 
    {
        new_arr[i] = arr[i];
    }

return new_arr;
}

int main()
{
    int myarr[5] = {1,2,3,4,5};
    int *myarr_copy = duplicate(myarr,5);

for(int i=0; i< 5; i++)
    {
        printf("%d\n",myarr_copy[i]);
    }
    return 0;
}
```

# Stack / Heap Memory

## Review: Memory Structure
![MIPS memory structure](/Fall2024/CS130/assets/images/COD/mips-memory.png)

## Review: Stack Frames
![Procedure frame](/Fall2024/CS130/assets/images/COD/stack-frame.png)

## Stack Memory
- **Stack memory** is the space where local variables, function calls, etc., are allocated
- 
 Locally scoped variables are freed when the code block they were defined in finishes

## A First Attempt

```c
int * duplicate(int *arr, int n) 
{
    int new_arr[n]; //memory created like this is put on the stack!
    for (int i = 0; i < n; i++) 
    {
        new_arr[i] = arr[i];
    }

return new_arr;
}
```

## Heap Memory

- **Heap memory** persists between function calls
    + 
 In C, we must manually create and destroy heap memory

## Heap Memory
- `malloc(n)`  creates `n` bytes of heap memory
    ```c
    // Creates an array on the heap with enough
    // space to hold 10 ints
    int *arr = malloc(10*sizeof(int));
    ```
- 
 `sizeof(int)` is the number of bytes of one `int`
- 
 `free(...)` is destroys heap memory
    ```c
    free(arr);  // releases the memory
    ```
- 
 Must call `free` on the pointer returned by `malloc`
- 
 These functions are in the `stdlib.h` library

## A Second Attempt
```c
int * duplicate(int *arr, int n) 
{
    int *new_arr = malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) 
    {
        new_arr[i] = arr[i];
    }

return new_arr;
}
```

## Visualize it and then run it yourself

[C Tutor Visualization](https://pythontutor.com/c.html#code=int%20*duplicate%28int%20*arr,%20int%20n%29%20%7B%0A%20%20%20%20int%20*new_arr%20%3D%20malloc%28n%20*%20sizeof%28int%29%29%3B%0A%20%20%20%20for%20%28int%20i%20%3D%200%3B%20i%20%3C%20n%3B%20i%2B%2B%29%20%7B%0A%20%20%20%20%20%20%20%20new_arr%5Bi%5D%20%3D%20arr%5Bi%5D%3B%0A%20%20%20%20%7D%0A%0A%20%20%20%20return%20new_arr%3B%0A%7D%0A%0Aint%20main%28%29%20%7B%0A%20%20int%20arr%5B5%5D%20%3D%20%7B100,%20200,%20300,%20400,%20500%7D%3B%0A%20%20%0A%20%20int%20*dup%20%3D%20duplicate%28arr,%205%29%3B%0A%20%20dup%20%3D%20duplicate%28arr,%205%29%3B%0A%20%20%0A%20%20return%200%3B%0A%7D&curInstr=0&mode=display&origin=opt-frontend.js&py=c_gcc9.3.0&rawInputLstJSON=%5B%5D)

```c
#include <stdio.h>
#include <stdlib.h>

int * duplicate(int *arr, int n) 
{
    int *new_arr = malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) 
    {
        new_arr[i] = arr[i];
    }

return new_arr;
}

int main()
{
    int myarr[5] = {1,2,3,4,5};
    int *myarr_copy = duplicate(myarr,5);

for(int i=0; i< 5; i++)
    {
        printf("%d\n",myarr_copy[i]);
    }
    free(myarr_copy);
    return 0;
}
```

## Example
- Let's write a function that does this:
    + Takes two strings as input
    + Concatenates them together into a new string
    + Returns the string

- We'll make use of the `strlen` function in `<string.h>`:
https://cplusplus.com/reference/cstring/strlen/

## Example Solution

```c
char *str_concat(char *s1, char *s2)
{
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    int len3 = len1 + len2 + 1;
    char *s3 = malloc(len3*sizeof(char));

int pos = 0;

for (int i = 0; i < len1; i++, pos++) 
    {
        s3[pos] = s1[i];
    }

for (int i = 0; i < len2; i++, pos++) 
    {
        s3[pos] = s2[i];
    }

s3[pos] = '\0';
    return s3;
}
```

[C Tutor Visualization](http://www.pythontutor.com/c.html#code=%23include%20%3Cstdio.h%3E%0A%23include%20%3Cstdlib.h%3E%0A%23include%20%3Cstring.h%3E%0A%0Achar*%20str_concat%28char%20*s1,%20char%20*s2%29%0A%7B%0A%20%20%20%20int%20len1%20%3D%20strlen%28s1%29%3B%0A%20%20%20%20int%20len2%20%3D%20strlen%28s2%29%3B%0A%20%20%20%20int%20len3%20%3D%20len1%20%2B%20len2%20%2B%201%3B%0A%20%20%20%20char%20*s3%20%3D%20%28char*%29%20malloc%28len3*sizeof%28char%29%29%3B%0A%0A%20%20%20%20int%20pos%20%3D%200%3B%0A%20%20%20%20for%20%28int%20i%20%3D%200%3B%20i%20%3C%20len1%3B%20i%2B%2B,%20pos%2B%2B%29%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20s3%5Bpos%5D%20%3D%20s1%5Bi%5D%3B%0A%20%20%20%20%7D%0A%20%20%20%20for%20%28int%20i%20%3D%200%3B%20i%20%3C%20len2%3B%20i%2B%2B,%20pos%2B%2B%29%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20s3%5Bpos%5D%20%3D%20s2%5Bi%5D%3B%0A%20%20%20%20%7D%0A%20%20%20%20s3%5Bpos%5D%20%3D%20'%5C0'%3B%0A%20%20%20%20%0A%20%20%20%20return%20s3%3B%0A%7D%0A%0Aint%20main%28%29%0A%7B%0A%20%20%20%20char%20*arr1%20%3D%20%22abc%22%3B%0A%20%20%20%20char%20arr2%5B7%5D%20%3D%20%22defghi%22%3B%0A%20%20%20%20char%20*arr3%20%3D%20str_concat%28arr1,%20arr2%29%3B%0A%0A%20%20%20%20printf%28%22arr1%20is%3A%20%25s%5Cn%22,%20arr1%29%3B%0A%20%20%20%20printf%28%22arr2%20is%3A%20%25s%5Cn%22,%20arr2%29%3B%0A%20%20%20%20printf%28%22arr3%20is%3A%20%25s%5Cn%22,%20arr3%29%3B%0A%0A%20%20%20%20free%28arr3%29%3B%0A%7D&curInstr=0&mode=display&origin=opt-frontend.js&py=c&rawInputLstJSON=%5B%5D)

## Exercise 4
- One convenient method in Python is the `str.join()` method. For example:
```py
>>> " ".join(["The", "quick", "brown", "fox"])
"The quick brown fox"
```
- 
 What would the function prototype have to be?
    ```c
    // Takes an array of n strings and returns
    // a new string allocated on the heap
    char *join(char **arr, int n)
    ```

- 
 Finish implementing this