Pointer, Memory Management, and Structs Concepts Explained in C Programming

CS& 131, Autumn 2022 Lecture 15: pointers; 2D arrays; structs Thank you to Marty Stepp and Stuart Reges for parts of these slides 1

Deallocating memory heap memory stays claimed until the end of your program garbage collector: A process that automatically reclaims memory that is no longer in use. keeps track of which variables point to which memory, etc. used in Java, Python, Javascript, VB and many other modern languages; not in C // VB Function F() As Integer() { Dim A1(1000) as Integer; Dim A2(1000) as Integer; Return A2; End Function // no variables refer to A1 here; can be freed 2

Memory leaks memory leak: Failure to release memory when no longer needed. easy to do in C can be a problem if your program will run for a long time when your program exits, all of its memory is returned to the OS void f(void) { int* a = (int*) calloc(1000, sizeof(int)); ... } // oops; the memory for a is now lost 3

free free(pointer); releases the memory pointed to by the given pointer precondition: pointer must refer to a heap-allocated memory block that has not already been freed int* a = (int*) calloc(8, sizeof(int)); ... free(a); it is considered good practice to set a pointer to NULL after freeing free(a); a = NULL; 4

Memory corruption if the pointer passed to free doesn't point to a heap- allocated block, or if that block has already been freed, bad things happen int* a1 = (int*) calloc(1000, sizeof(int)); int a2[1000]; int* a3; int* a4 = NULL; free(a1); // ok free(a1); // bad (already freed) free(a2); // bad (not heap allocated) free(a3); // bad (not heap allocated) free(a4); // bad (not heap allocated) you're lucky if it crashes, rather than silently corrupting something 5

Better IMDb answer 1 // Displays IMDB's Top 250 movies that match a search string. #include <stdio.h> #include <stdbool.h> #include <stdlib.h> #include <string.h> #include <ctype.h> // Displays the line in the proper format on the screen. void display(char* line) { int rank = atoi(strtok(line, ",")); char* tmp = strtok(NULL, ","); double rating = atof(tmp); int votes = atoi(strtok(NULL, ",")); char* title = strtok(NULL, ","); printf("%d\t%d\t%.1f\t%s\n", rank, votes, rating, title); } void to_lowercase(char s []) { for(int i = 0; i < strlen(s); i++) { s[i] = tolower(s[i]); } } 6

Better IMDb answer 2 bool contains_ignore_case(char* sub, char* str) { to_lowercase(sub); to_lowercase(sub); if (sub != NULL && str != NULL) { int lenstr = strlen(str); int lensub = strlen(sub); if (lenstr > 0 && lensub > 0) { for (int i = 0; i < lenstr; i++) { if (strncmp(sub, str + i, lensub) == 0) { return true; } } } } return false; } // Breaks apart each line, looking for lines that match the search word. char* search(FILE* file, char* search_word) { int matches = 0; char* line = (int*)(malloc(100 * sizeof(char))); while (fscanf(file, "%[^\n]\n", line) != EOF) { if (contains_ignore_case(search_word, line)) { matches++; return line; } } return NULL; } 7

Better IMDb answer 3 // Asks the user for their search word and returns it. char* get_word() { printf("Search word: "); char* search_word = (int*)(malloc(20 * sizeof(char))); scanf("%s", search_word); printf("\n"); return search_word; } int main() { char* search_word = get_word(); FILE* file = fopen("imdb.txt", "r"); char* line = search(file, search_word); int matches = 0; if (line != NULL) { printf("Rank\tVotes\tRating\tTitle"); while (line != NULL) { display(line); line = search(file, search_word); matches++; } } printf("%d matches.\n", matches); } 8

Exercise: counting substrings What if we want to count occurrences of a string in another string? We can see if strings are equal with strcmp or if they are equal from beginning to some index n with strncmp How could we test string equality starting from a location in a string other than index 0? Add a character offset to the string variable! char words[] = "this is a string"; char sub[] = "str" strncmp(words + 3, sub, 3); // compares "s i" with "str" 9

count_occurrences int count_occurrences(char* sub, char* str) { int count = 0; if (sub != NULL && str != NULL) { int lenstr = strlen(str); int lensub = strlen(sub); if (lenstr > 0 && lensub > 0) { for (int i = 0; i < lenstr; i++) { if (strncmp(sub, str + i, lensub) == 0) { count++; } } } } return count; } 10

What type is an array of strings? char* name[] or char** name or char name[][] What type is an array of integer arrays? int*name [] or int**name or intname [][] 11

Creating an array of strings char** a = (char**) malloc(10 * sizeof(char*)); char b[] = "the"; a[0] = &b; printf("string: %s\n\n", a[0]); // prints the The above code works but can the array of arrays be returned? no because the inner string memory will not exist afterward because it is in the current stack frame we need to malloc each string if we want them to exist after returning 12

Creating an array of arrays int data [10][8] creates an array of length 10 that stores arrays of length 8 Output: int data[10][8]; 0 1 2 3 4 5 6 7 10 11 12 13 14 15 16 17 20 21 22 23 24 25 26 27 30 31 32 33 34 35 36 37 40 41 42 43 44 45 46 47 50 51 52 53 54 55 56 57 60 61 62 63 64 65 66 67 70 71 72 73 74 75 76 77 80 81 82 83 84 85 86 87 90 91 92 93 94 95 96 97 for(int i = 0; i < 10; i++) { for(int j = 0; j < 8; j++) { data[i][j] = i * 10 + j; } } for(int i = 0; i < 10; i++) { for(int j = 0; j < 8; j++) { printf("%d ", data[i][j]); } printf("\n"); } 13

Creating an array of arrays int* data = (int*) malloc(10 * sizeof(int*)); creates an array on the heap with enough space to store pointers to 10 arrays of ints int* data = (int*) malloc(10 * sizeof(int*)); for(int i = 0; i < 10; i++) { data[i] = (int*) malloc(8 * sizeof(int)); } for(int i = 0; i < 10; i++) { for(int j = 0; j < 8; j++) { data[i][j] = i * 10 + j; } } for(int i = 0; i < 10; i++) { for(int j = 0; j < 8; j++) { printf("%d ", data[i][j]); } printf("\n"); } 14

Creating an array of arrays int* data = (int*) malloc(10 * 8 * sizeof(int)); creates an array on the heap with enough space to store our data We can compute offsets ourselves int* data = (int*) malloc(10 * 8 * sizeof(int)); for(int i = 0; i < 10; i++) { for(int j = 0; j < 8; j++) { data[i * 8 + j] = i * 10 + j; } } for(int i = 0; i < 10; i++) { for(int j = 0; j < 8; j++) { printf("%d ", data[i * 8 + j]); } printf("\n"); } 15

Array of arrays mystery void mystery(int* data[], int result[], int pos, int n) { for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { result[j] = data[i + pos][j + pos]; } } } Suppose that a variable called grid has been declared as follows: int grid[6][6] = {{8, 2, 7, 8, 2, 1}, {1, 5, 1, 7, 4, 7}, {5, 9, 6, 7, 3, 2}, {7, 8, 7, 7, 7, 9}, {4, 2, 6, 9, 2, 3}, {2, 2, 8, 1, 1, 3}} which means it will store the following 6-by-6 grid of values: 8 2 7 8 2 1 1 5 1 7 4 7 5 9 6 7 3 2 7 8 7 7 7 9 4 2 6 9 2 3 2 2 8 1 1 3 For each call at right, indicate what value is returned. If the function call results in an error, write error instead. Function Call Contents of List Returned mystery(grid, 2, 2) _____________________ mystery(grid, 0, 2) _____________________ mystery(grid, 3, 3) _____________________ 16

Exercise Write a function called flip that takes an array of arrays and two columns and swaps their contents. For example, if flip(data, size_outer, size_inner, 2, 3) were called on the following array int data [][] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}} data would contain the following afterwards: int data [][] = {{1, 3, 2}, {4, 6, 5}, {7, 9, 8}} 18

A programming problem Given a file of cities' (x, y) coordinates, which begins with the number of cities: 6 50 20 90 60 10 72 74 98 5 136 150 91 Write a program to output the cities that are affected by an earthquake with a user specified epicenter and radius: Epicenter x? 100 Epicenter y? 100 Affected radius? 75 Affected cities: (90, 60), (74, 98), (150, 91) 20

A bad solution FILE* input = fopen("cities.txt", "r"); int city_count; fscanf(input, "%d", &city_count); int x_coords[city_count]; int y_coords[city_count]; int index = 0; int x_temp; int y_temp; while(fscanf(input, "%d %d", &x_temp, &y_temp) != EOF) { x_coords[index] = x_temp; y_coords[index] = y_temp; } ... parallel arrays: 2+ arrays with related data at same indexes. Considered poor style. 21

Observations The data in this problem is a set of points. It would be better stored as a Point type. Some other languages that you may have used allow you to create objects that have state and behavior. C only allows you to store state (data) together in a new type. We can do this with a struct 22

Structured data struct typename { // declaring a struct type typename; type name; ... type name; // fields }; struct: A type that stores a collection of variables. like a Java, C#, Python or VB class, but with only fields instances can be allocated on the stack or on the heap struct Point { // defines a new structured int x; int y; // type named Point }; 23

Using structs a struct instance is declared by writing the type, name, and ; this allocates an instance of the structured type on the stack refer to the fields of a struct using the . operator struct Point { int x; int y; }; int main() { struct Point p1; // on stack struct Point p2 = {42, 3}; // initialized p1.x = 15; p1.y = -2; printf("p1 is (%d, %d)\n", p1.x, p1.y); return 0; } 24

typedef typedef typename; tell C to acknowledge your struct type's name with typedef typedef struct Point { int x, y; } Point; int main(void) { Point p1; // don't need to write 'struct' p1.x = 15; p1.y = -2; printf("p1 is (%d, %d)\n", p1.x, p1.y); return 0; } 25

A programming problem Given a file of cities' (x, y) coordinates, which begins with the number of cities: 6 50 20 90 60 10 72 74 98 5 136 150 91 Write a program to output the cities that are affected by an earthquake with a user specified epicenter and radius: Epicenter x? 100 Epicenter y? 100 Affected radius? 75 Affected cities: (90, 60), (74, 98), (150, 91) 26