[CS50] Week 4 Review

CS50

[CS50] Week 4 Review

jeearchive 2024. 10. 9. 13:46

Week 4

: Memory

Lecture Contents

1. Hexadecimal (base-16)

: a system of counting that has 16 counting values, which are:

0 1 2 3 4 5 6 7 8 9 A B C D E F

When counting is hexadecimal, each column is a power of 16.

number	0	1	9	10	15	16	255
represented	00	01	09	0A	0F	10	FF

digit1 digit2

□ □

16^1 16^0

ex) FF : 16 x 15 + 1 x 15 = 255 (the highest number you can count using a two-digit hexadecimal system.)

Hexadicamal is useful because it can be represented using fewer digits. It allows us to represent information more succinctly.

2. Memory

When you apply hexadicimal numbering to each of blocks of memory, it can be visualized like this:

However, there may be confusion regarding whether the '10' block represents a location in memory of the value '10'.

Accordingly, all hexadecimal numbers are often represented with the '0x' prefix as follows:

C language has two powerful operators that relate to memory:

&	provides the address of something stored in memory
*	instructs the compiler to go to a location in memory

#include <stdio.h>

int main(void)
{
	int n = 50;
    printf("%p\n", &n);
}

→ would return an address of memory beginning with '0x.'

%p : allows us to view the address of a location in memory

&n : "the address of n"

3. Pointers

: a variable that contains the address of some value.

#include <stdio.h>

int main(void)
{
	int n = 50;
    int *p = &n;
    printf("%p\n", p);
 }

Notice that p is a pointer that contains the address of an integer n.

It has the same effect as our previous code. We have simply leveraged our new knowledge of the & and * operators.

#include <cs50.h>

int main(void)
{
	int n = 50;
    int *p = &n;
    printf("%i\n", *p);
}

'printf' line prints the integer at the location of p.

'int *p' creates a pointer whose job is to store the memory address of an integer.

P is a pointer storing the address of the 50.

4. Strings

Recall that string is simply an array of characters.

ex) string s = "HI!" :

→ What is s really?

Notice how a pointer called s tells the compiler where the first byte of the string exists in memory.

#include <cs50.h>
#include <stdio.h>

int main(void)
{
	string s = "HI!";
    printf("%p\n", s);
    printf("%p\n", &s[0]);
    printf("%p\n", &s[1]);
    printf("%p\n", &s[2]);
    printf("%p\n", &s[3]);
}

→ In this code, it prints the memory locations of each character in the string s.

When running this code, elements 0, 1, 2, and 3 are next to one another in memory.

#include <stdio.h>

int main(void)
{
	char *s = "Hi!";
    printf("%s\n", s);
}

This code will present the string that starts at the location of s.

string = char *

Struct allows one to use a custom data type called string :

typedef char *string

5. Pointer Arithmetic

To print each character at the location of s :

#include <stdio.h>

int main(void)
{
	char *s = "HI!";
    printf("%c\n", *s);
    printf("%c\n", *(s+1));
    printf("%c\n", *(s+2));
}

6. String Comparison

In case of comparing two integers:

#include <cs50.h>
#include <stdio.h>

int main(void)
{
	//Get two integers
    int i = get_int("i: ");
    int j = get_int("j: ");
    
    //Compare integers
    if (i == j)
    {
    	printf("Same\n");
    }
    else
    {
    	printf("Different\n");
    }
}

In case of comparing two strings:

#include <cs50.h>
#include <stdio.h>

int main(void)
{
	//Get two strings
    char *s = get_string("s: ");
    char *t = get_string("t: ");
    
    //Compare strings' addresses
    if (s == t)
    {
    	printf("Same\n");
    }
    else
    {
    	printf("Different\n");
    }
}

→ If you type in HI! for both strings, it still results in the output of Different. But Why?

Now you realize that the code above is actually attempting to see if the memory addressess are different: not the strings

We can correct our code using strcmp :

#include <cs50.h>
#include <stdio.h>

int main(void)
{
	//Get two strings
    char *s = get_stirng("s: ");
    char *t = get_string("t: ");
    
    //Compare strings
    if (strcmp(s,t) == 0)
    {
    	printf("Same\n");
    }
    else
    {
    	printf("Different\n");
    }
}

6. Copying

: to copy one string to another

#include <stdio.h>
#include <cs50.h>
#include <string.h>
#include <ctype.h>

int main(void)
{
	//Get a string
    string s = get_string("s: ");
    
    //Copy string's address
    string t = s;
    
    //Capitalize first letter in string
    t[0] = toupper(t[0]);
    
    //Print string twice
    printf("s: %s\n", s);
    printf("t: %s\n", t);
}

string t = s : copies the address of s to t.

But the string is not copied - only the address is.

Notice that s and t are still pointing at the same blocks of memory.

We should not experience a segmentation fault through our code.
We attempt to copy string s to string t, but string t does not exist.

We can employ the strlen function as follows:

#include <stdio.h>
#include <cs50.h>
#include <string.h>
#include <ctype.h>

int main(void)
{
	//Get a string
    string s = get_string("s: ");
    
    //Copy string's address
    string t = s;
    
    //Capitalize first letter in string
    if (strlen(t) > 0)
    {
		t[0] = toupper(t[0]);
    }
    
    //Print string twice
    printf("s: %s\n", s);
    printf("t: %s\n", t);
}

strlen is used to make sure string t exists.

To be able to make an authentic copy of the string, we need two new building blocks.

1) malloc : allows you to allocate a block of a specific size of memory

2) free : allows you to tell the compiler to free up that block of memory you previously allocated

#include <stdio.h>
#include <cs50.h>
#include <string.h>
#include <ctype.h>

int main(void)
{
	//Get a string
    char *s = get_string("s: ");
    
	//Allocate memory for another string
    char *t = malloc(strlen(s) + 1);
    
    //Copy string into memory, including '\0'
    for (int i = 0, n = strlen(s); i <= n; i++)
    {
    	t[i] = s[i];
    }
    
    //Capitalize first letter in string
    t[0] = toupper(t[0]);
    
    //Print string twice
    printf("s: %s\n", s);
    printf("t: %s\n", t);
}

malloc(strlen(s) + 1) : includes the null (\0) character in our final, copied string.
for loop : walks through the string s and assigns each value to the same location on the string t.
i <= n : the equal sign (=) includes the null (\0) character

C language has a built-in function to copy strings called strcpy.

#include <cs50.h>
#include <ctype.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
	char *s = get_string("s: ");
    char *t = malloc(strlen(s) + 1);
    
    strcpy(t, s);
    
    t[0] = toupper(t[0]);
    
    printf("s: %s\n", s);
    printf("t: %s\n", t);
}

strcpy does the same work that our for loop previously did.

You can write code that can check for NULL condition as follows:

#include <cs50.h>
#include <ctype.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
	char *s = get_string("s: ");
	if(s == NULL)
    {
    	return 1;
    }
    
    char *t = malloc(strlen(s) + 1);
    if(s == NULL)
    {
    	return 1;
    }
    
    strcpy(t, s);
    
    if (strlen(t) > 0)
    {
    	t[0] = toupper(t[0]);
    }
    
    printf("s: %s\n", s);
    printf("t: %s\n", t);
    
    free(t);
    return 0;
}

If the string obtained is of length 0 or malloc fails, NULL is returned.
free lets the computer know you are done with this block of memory you created via malloc.

7. malloc and Valgrind

Valgrind : a tool that can check to see if there are memoroy-related issues with programs wherein you utilized malloc.

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

int main(void)
{
    int *x = malloc(3 * sizeof(int));
    x[1] = 72;
    x[2] = 73;
    x[3] = 33;
}

In your terminal window, type in make memory and valgrind ./memory

: Notice that it points out some bugs here, which are

① Invalid write of size 4 (in line 9)

② 12 bytes in 1 blocks are definitely lost in loss record 1 of 1 (in line 6)

We can fix this by

① x[0] = 72;

x[1] = 73;

x[2] = 33;

② We never freed x after using malloc, so this code below has to be involved at last

free(x);

8. Garbage Values

When you ask the compiler for a block of memory → Is this memory empty?

: We cannot guarantee !

It's possible that this memory you allocated was previously utilized by the computer, so you may see junk or garbage values.

★ After you allocate a block of memory, you have to initialize it.

#include <stdio.h>

int main(void)
{
    int scores[1024];
    for (int i = 0; i < 1024; i++)
    {
        printf("%i\n", scores[i]);
    }
}

Running this code will allocate 1024 locations in memory for your array. In your terminal window, you'll see this:

9. Swap

How do we swap two values?

#include <stdio.h>

void swap(int a, int b);

int main(void)
{
    int x = 1;
    int y = 2;

    printf("x is %i, y is %i\n", x, y);
    swap(x, y);
    printf("x is %i, y is %i\n", x, y);
}

void swap(int a, int b)
{
    int tmp = a;
    a = b;
    b = tmp;
}

Here, we created our own swap function whose arguments are int a and int b.

We used a temporary holding space 'int tmp' to swap a and b. But will it work?

Hmm... seems like two values are not swapped. Why?

Let's learn about scope first.

scope: (변수에 접근할 수 있는) 범위
Global scope : 전역 스코프. 전역에 선언되어 있어 어느 곳에서든 해당 변수에 접근 가능.

▷ The values of x and y created in the { } of the main function only have the scope of the main function :

Various functions are stored in the stack in memory.

Now, consider the following image:

Notice that main and swap have two spearate frames or areas of memory.

Even though we swapped two variables in swap(), the function will not exist afterwards.

#include <stdio.h>

void swap(int *a, int *b);

int main(void)
{
    int x = 1;
    int y = 2;

    printf("x is %i, y is %i\n", x, y);
    swap(&x, &y);
    printf("x is %i, y is %i\n", x, y);
}

void swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

Now it works! What did I change?

★ Notice that variables are not passed by value but by reference.

That is, the addresses of a and b are provided to the function.

Therefore, the swap function can know where to make changes to the actual a and b from the main function.

10. scanf ★

Instead of functions like get_int in CS50, scanf is a built-in function that can get user input :

#include <stdio.h>

int main(void)
{
	int x;
    printf("x: ");
    scanf("%i", &x);
    printf("x: %i\n", x);
}

★ Notice that the value of x is stored at the location of x in the line (scanf("%i", &x))

However, attempting to reimplement get_string is not easy :

#include <stdio.h>

int main(void)
{
	char *s;
    printf("s: ");
    scanf("%s", s);
    printf("x: %s\n", s);
}

★ Notice that no & is required because strings are special.

The program will not function, because we never allocated the amount of memory required for our string.

Indeed, we don't know how long of a string may be inputted by the user. (100? 123456?)

#include <stdio.h>

int main(void)
{
	char *s = malloc(4);
    if (s == NULL)
    {
    	return 1;
    }
    printf("s: ");
    scanf("%s", s);
    printf("s: %s\n",s);
    
    free(s);
    return 0;
}

We provided 4 bytes, so we might get an error if the user input is more than 4 bytes.

#include <stdio.h>

int main(void)
{
	char s[4];
    printf("s: ");
    scanf("%s", s);
    printf("s: %s\n", s);
}

We pre-allocate an array of size 4, but a string larger than this could create an error.

- Sometimes, the compiler or the system running it may allocate more memory than we indicate.

- We cannot trust the user will input a string that fits into our pre-allocated memory.

11. File I/O

You can read from and manipulate files.

#include <cs50.h>
#include <stdio.h>
#include <string.h>

int main(void)
{
    //Open CSV file
    FILE *file = fopen("phonebook.csv", "a");

    //Get name and number
    char *name = get_string("Name: ");
    char *number = get_string("Number: ");

    //Print to file
    fprintf(file, "%s,%s\n", name, number);

    //Close file
    fclose(file);
}

If we want to ensure that phonebook.csv exists prior to running the program, we can modify our code as follows :

#include <cs50.h>
#include <stdio.h>
#include <string.h>

int main(void)
{
    //Open CSV file
    FILE *file = fopen("phonebook.csv", "a");
    if(!file)
    {
    	return 1;
    }

    //Get name and number
    char *name = get_string("Name: ");
    char *number = get_string("Number: ");

    //Print to file
    fprintf(file, "%s,%s\n", name, number);

    //Close file
    fclose(file);
}

We can implement our own copy program :

#include <stdio.h>
#include <stdint.h>

typedef uint8_t BYTE;

int main(int argc, string argv[])
{
    FILE *src = fopen(argv[1], "rb");
    FILE *dst = fopen(argv[2], "wb");

    BYTE b;

    while(fread(&b, sizeof(b), 1, src) != 0)
    {
        fwrite(&b, sizeof(b), 1, dst);
    }

    fclose(src);
    fclose(dst);
}

This file creates our own data type called a BYTE that is the size of a uint8_t.
The file reads a BYTE and writes it to a file.

4주차에는 컴퓨터의 메모리에 대해서 알아보았다.
우리가 쓰는 코드에 따라서 메모리가 어디에, 어떻게, 얼마나 저장되는지 알 수 있었고

pointer라는 개념을 통해서 메모리에서 변수와 값이 이동하는 복합적인 구조도 이해할 수 있었다!

또한 메모리와 관련된 debug는 valgrind를 통해 해결할 수 있어 더 간편하다고 생각했다.

메모리라는 것이 눈으로 직접 보이지 않아 추상적이고 어렵게 느껴졌던 것도 분명하지만, 기기마다 메모리의 용량은 정해져 있기 때문에 메모리의 적절한 관리가 눈으로 보이는 코드보다 오히려 더 중요하다고 느껴졌다.

내일 4주차 section으로 돌아오겠숴! 그럼 오늘도 수고많았다 나 자신 ㅎ ㅏ ㅎ ㅏ