100% Tested with Dartmouth x IMT Online Judge/Task Grader

何強豪の C code log and learning journey

---

Unit 4.1: Memory and Pointers

Defining and dereferencing pointers

Review

When you parse variable into a function block, the function block only copy the value and cannot access the real variable in the main block.

So we need to find the address of the variable to be able to change it from a function block.

Using pointers with functions

// Swap function for integers
void swap_int(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Swap function for strings
void swap_str(char **a, char **b) {
    char *temp = *a;
    *a = *b;
    *b = temp;
}

// Function to print an array of integers or strings
void print_array(void *arr, size_t size, size_t elem_size, void (*print_elem)(void *)) {
    for (size_t i = 0; i < size; i++) {
        print_elem((char *)arr + i * elem_size);
        printf(" ");
    }
    printf("\n");
}

// Function to print an integer
void print_int(void *elem) {
    printf("%d", *((int *)elem));
}

// Function to print a string
void print_str(void *elem) {
    printf("%s", *((char **)elem));
}

int main() {
    int int_array[] = {5, 2, 9, 1, 5, 6};
    char *str_array[] = {"apple", "banana", "orange", "grape"};

    size_t int_size = sizeof(int);
    size_t str_size = sizeof(char *);

    printf("Before int swap: ");
    print_array(int_array, sizeof(int_array) / sizeof(int), int_size, print_int);
    
    swap_int(&int_array[0], &int_array[1]); //Get the address
    
    printf("After int swap:  ");
    print_array(int_array, sizeof(int_array) / sizeof(int), int_size, print_int);

    printf("\nBefore str swap: ");
    print_array(str_array, sizeof(str_array) / sizeof(char *), str_size, print_str);
    
    swap_str(&str_array[0], &str_array[1]); //Get the address
    
    printf("After str swap:  ");
    print_array(str_array, sizeof(str_array) / sizeof(char *), str_size, print_str);

    return 0;
}

Working with pointer arithmetic

    int array[] = {6, 2, -4, 8, 5, 1};
    
    printf("Array contains %d, %d, ... , %d\n", array[0], array[1], array[5]);
    printf("These are stored at %p, %p, ..., %p\n", &array[0], &array[1], &array[5]);
    // array == &array[0]

    *ptr = 10;
    *(ptr + 1) = 5; 
    *(ptr + 2) = -1;
    
    *array = 3;
    *(array + 1) = 10;
    *(array + 2) = 99;
    
    ptr++;
    *ptr = 7;
    
    ptr += 3;
    *ptr = 8;

Passing arrays to functions

void squareArray(int * ptr, int size) {
    int i;
    for (i=0; i<size; i++) {
        ptr[i] = ptr[i]*ptr[i];
        // *(ptr+i) = (*(ptr+i))*(*(ptr+i));
    }
}

void printArray(int * ptr, int size) {
    int i;
    for (i=0; i<size; i++) {
        // printf("%d ", *(ptr+i));
        printf("%d ", ptr[i]);
    }
    printf("\n");
}

Passing array to function to find score

You are participating in a game in which players collect points for various solved puzzles. In the end, the player with the highest score wins. You would like to know how far behind the highest-scoring person everyone else is in order to know whether you still have a chance at winning.

Please write a C program that uses a function "behind()" (which you also have to write) in order to help with this task. Your program should first read, from the user input, the number of players participating in the game. There are never more than 10 players in the game. Next, your program should read the current scores of each player and store them in an array. Then you should call the function behind(), to which you pass as a first argument, the array holding the player's scores, and as a second argument the number of players in the game. The function behind should replace the scores stored in the array with the number of points by which each individual player is behind the top-scoring player.

To help you out, the main function of the program has already been written, so your job is simply to write the function behind(), whose protype is also given to you.

Provided code

#include <stdio.h>

void behind(int *, int);

int main(void) {
    int array[10];
    int N, i;
    
    scanf("%d", &N);
    for (i=0; i<N; i++) {
        scanf("%d", &array[i]);
    }
    behind(array, N);
    for (i=0; i<N; i++) {
        printf("%d\n", array[i]);
    }
    
    return 0;
}

Example
Input
5
8 12 7 15 11

Output
7
3
8
0
4

Solution

void behind(int * arr, int players){
    int max= 0;
    for(int i = 0; i < players; i++){
        if(arr[i] > max) max = arr[i];
    }
    
    for(int  i = 0; i < players; i++){
        arr[i] = max - arr[i];
    }
    
}

Unit 4.2: Multidimensional arrays

Working with arrays and pointers

    int main(void){
     //! showMemory(cursors=[a, arrays[0], b, arrays[1], c, arrays[2]], start=65520)
    short a[3] = {234,655, 843};
    short b[2] = {12, 62};
    short c[4] = {3456, 3467, 23, 276};
    short * arrays[3] = {a, b, c};
    * arrays[0] = 5;
    arrays[0][0] = 0;
    * (arrays[0] + 1) = 6;
    arrays[0][1] = 0;
    * (arrays[0] + 2) = 7;
    arrays[0][2] = 0;
    * arrays[1] = 3;
    arrays[1][0] = 0;
    * (arrays[1] + 1) = 4;
    arrays[1][1] = 0;
    return 0;
}

Use pointers to pointers and dereference

int main(){
     //! showMemory(cursors=[t, t[0], t[1]],start=65520)
    short a[3] = {1245, 1924, 234};
    short b[2] = {24, 256};
    short * t[2] = {a,b};
    setToZero(t);
    return 0;
}
void setToZero(short ** t){
    *(*t) = 0; //t[0][0]  OR  *(t[0] + 0)
    *((*t) + 1) = 0;//t[0][1]  OR *(t[0] + 1)
    *((*t) + 2) = 0;//t[0][2]  OR *(t[0] + 2)
    *(*(t+1)) = 0;//t[1][0]  OR *(t[1] + 0)
    *(*(t+1)+1) = 0;//t[1][1]  OR *(t[1] + 1)
}

arrays and memory

You are designing a new cookie recipe and are experimenting with different amounts of wet (water, oil) and dry (flour, sugar, cocoa powder) ingredients in order to get the proportions just right. All of these amounts are initially read from the user input, and the code to do so, along with all variable declarations, had already been completed. You are interested in the total amount of wet and dry ingredients used in the recipe as well as the ratio of these two quantities.

Take a look at the code that is already given to you. Your job is to add four lines of code, precisely where indicated by a comment such as

//Add one line here
Beneath each such line you will find an explanation of what precisely your line of code is supposed to do as well as what type of array addressing you are to use. Please read and follow these directions carefully. Do not change anything else in the code that is provided as our grading system will detect such changes and mark your solution as incorrect.

Example
Input
10.5 20.2
30.3 40.4 50.5

Output
Total amount of wet ingredients: 30.70 grams.
Total amount of dry ingredients: 121.20 grams.
Ratio of wet to dry ingredients: 3.95.
New water amount: 15.35 grams, new oil amount: 15.35 grams.

Provided code & Solution

#include <stdio.h>

int main(void) {

    double totalWet, totalDry, ratio;

    double wet[2];
    double dry[3];
    double * cookie[2] = {wet,dry};
    
    scanf("%lf%lf", &wet[0], &wet[1]);
    scanf("%lf%lf%lf", &dry[0], &dry[1], &dry[2]);

    // Add one line here! 
    totalWet = *(*cookie) + *(*cookie + 1);
    /* The line you add should use the array cookie (and not the array wet) to 
       find the sum of the wet ingredients of the cookie recipe and store that sum
       in the variable totalWet. Use only indexed notation to address the cookie
       array (that is, you need to use two pairs of brackets [..]). 
    */

    printf("Total amount of wet ingredients: %.2lf grams.\n", totalWet);
    
    // Add one line here! 
    totalDry = *(*(cookie+1)) + *(*(cookie+1) + 1) + *(*(cookie+1) + 2);
    /* The line you add should use the array cookie (and not the array dry) to 
       find the sum of the dry ingredients of the cookie recipe and store that sum
       in the variable totalDry. This time, use only one pair of brackets [..] each 
       time you address the cookie array. 
    */

    printf("Total amount of dry ingredients: %.2lf grams.\n", totalDry);
    ratio = totalDry/totalWet;
    printf("Ratio of wet to dry ingredients: %.2lf.\n", ratio);

    // Add two lines here.
    (*(cookie)) = totalWet/2;
    *(*(cookie)+1) = totalWet/2;
    /* The lines you add should use the array cookie (and not the array wet) to
       update the amounts of water and oil in your recipe. 
       You believe that any cookie recipe should use equal amounts of water and oil.
       Without changing the total amount of wet ingredients, update the values for
       water and oil, using only the array cookie (and not the array wet) so that 
       these amounts will be equal. The easiest way to do so is to assign the value
       totalWet/2 to both the water and the oil entry. When addressing the array cookie,
       do not use any brackets at all this time.
    */
    
    printf("New water amount: %.2lf grams, new oil amount: %.2lf grams.\n", wet[0], wet[1]);
    
    return 0;
}

Storing and manipulating strings in arrays

Store multiple strings in arrays

    for (i=0; i<3; i++) {
        scanf("%s", words[i]);
    }

Matrix

    int matrix[2][3];
    int line, col;
    for(line = 0; line < 2; line++){
        for(col = 0; col < 3; col++){
            scanf("%d",&matrix[line][col]);
        }
    }

print text in reverse order

Your goal is to read a 68-word text from the input and then print it to the screen backwards. Individual words do not have to be spelled backwards, but rather your program should print out the last word first, then the second-to-last word, etc. No word has more than 40 characters.

Example
Input
Science Computer on Papers Selected Knuth, Ervin Donald ― correct." be will results the that reader a convince to and works algorithm an way the communicate to concepts, mathematical as well as forms literary and aesthetic traditional with works who essayist an ideally is programmer A clearly. them understand can beings human that so and quickly them perform can machines computing that so written are programs best "The

Output
"The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as well as mathematical concepts, to communicate the way an algorithm works and to convince a reader that the results will be correct." ― Donald Ervin Knuth, Selected Papers on Computer Science

//Science Computer on Papers Selected Knuth, Ervin Donald ― correct." be will results the that reader a convince to and works algorithm an way the communicate to concepts, mathematical as well as forms literary and aesthetic traditional with works who essayist an ideally is programmer A clearly. them understand can beings human that so and quickly them perform can machines computing that so written are programs best "The
//68 words no more than 40 char
#include <stdio.h>

int main(void){
    char text[68][40];
    int len = 68;
    int i;
    for(i = 0; i < len; i++){
        scanf("%s", text[(len-1)-i]);
    }
    
    for(i = 0; i < len; i++){
        printf("%s ", text[i]);
    }
    return(0);
}

Unit 4.3: Dynamic memory allocation

Allocating memory at runtime

heap precompiled before the stack
Malloc is in heap and ptr in stack

//casting with sizeof

float * fptr;
fptr = (float *) malloc(sizeof(float));

Freeing dynamically allocated memory

After freeing the memory, the value is still reserved. It can be overwrite or if you lucky, access it with the same pointer/address

Storing and addressing arrays in dynamically allocated memory

Dynamic allocation (with pointer arithmetic)

#include <stdlib.h>
int main(void) {
    //! showMemory(start=272)
    int * array;
    array = (int *) malloc(5*sizeof(int));
    array[0] = 3;
    array[1] = 44;
    array[2] = 2;
    * (array + 3) = 7;
    * (array + 4) = -1;
    free(array);
    return 0;
}

Example

//new example of the use of malloc
#include <stdio.h>
#include <stdlib.h>

int * allocateIntArray(int);
double findAverage(int *,int);

int main(void){
    //! showMemory(start=272)
    int num, i;
    int * array;
    double average;
    printf("How many grades would you like to enter?");
    scanf("%d",&num);
    array = allocateIntArray(num);
    printf("Please enter %d grades: ",num);
    for(i=0;i<num;i++){
        scanf("%d",array+i); 
        //pointer arithemetic of the address; save to address
    }
    average = findAverage(array,num);
    printf("The average grade is %.2f.\n",average);
    free(array);
    return 0;
}

int * allocateIntArray(int num){
    int * ptr = (int *) malloc(num * sizeof(int));
    return ptr;
}

double findAverage(int * array, int num){
    int i;
    double average = 0.0;
    for(i=0;i<num;i++){
        average += array[i];
    }
    average = average / num;
    return average;
}

dynamically allocate memory for strings
You are working on programming a toaster (again!). The user of the toaster has the option to have their bread toasted "light" or "dark", and you are working on implementations in different languages of this particular setting. For example, in the German model, the settings would be stored as "hell" and "dunkel" instead. In order to be as efficient as possible with the use of the limited memory on the computer chip in the toaster you need to write a function "allocateString()" that allocates memory for strings (and you will then use this function to allocate just enough memory to store the settings on a particular model).

This function "allocateString()" takes as argument an integer (of type int), representing the number of characters to allocate space for in memory. The function returns a pointer (of type char *), containing the address of the allocated memory. The function should use memory allocation to reserve the correct amount of space in memory. In order to receive credit for your solution you need to use sizeof (char) in this line, even if sizeof (char) returns 1.

In your main() function you should call the function allocateString() twice: once for the label containing the "light" setting and once for the "dark" setting. You are provided with some code already that explains precisely what you need to do. Please do not change the code that has been given to you. Please only change those lines that say "// add a line of code…".

Example
Input
4 6
hell
dunkel

Output
Local settings: hell - dunkel

Provided code & Solution

#include <stdio.h>
// Be sure to include any other library you may need...

// Write your allocateString() prototype here
char * allocateString(int);

int main(void) {
    int lengthLight, lengthDark;
    char *strLight, *strDark;
    
    scanf("%d %d", &lengthLight, &lengthDark); 
    // Write a line of code here that calls the function allocateString(). 
    strLight = allocateString(lengthLight); 
    
    /* The goal is to reserve space for the light setting label, therefore you 
       need to pass the number lengthLight to the function allocateString()
       Store the return value of this function call in the variable strLight. */
     
    // Write a line of code here that calls the function allocateString().
    strDark = allocateString(lengthDark);
    
    /* This time the goal is to reserve space in memory for the dark setting label.
       Store the return value of the function call in the variable strDark. */
   
    scanf("%s", strLight);
    scanf("%s", strDark);
    printf("Local settings: %s - %s\n", strLight, strDark);
    // Write a line of code here to free the memory allocated for strLight
    free(strLight);
    
    // Write a line of code here to free the memory allocated for strDark
    free(strDark);
    
	
    return 0;
}

char * allocateString(int numChars){
    // declare your variable(s) here
    char * ptr;
    
    // Write a line of code here that performs the memory allocation.
    ptr = (char *) malloc((numChars + 1) * sizeof(char));
    /* You should allocate space in memory for the number of characters specified 
       via the input parameter to the function and the null terminator and store the 
       address of the allocated memory in a pointer named ptr. In order to receive credit 
       for your solution you need to use sizeof(char) in this line, even if sizeof(char) 
       returns 1. */
    
    return ptr;
}

Final Project

You have been hired to assist firefighters locate wildfires in a large geographic area. The area is divided into smaller zones. Each zone is scanned via satellite for its average temperature. If a zone has an average temperature strictly greater than 1000°F, we assume there is a fire in that zone. If the temperature is between 100 degrees (included) and 1000 degrees (included), we have to further investigate, so it becomes a "zone to watch."

The large geographic area you are watching is a rectangle with a certain length and width, each given in terms of zones. For example, if the area to be scanned has a length of 6 and width of 9 then it will be divided into 6*9 zones:

––length = 6––
[ ][ ][ ][ ][ ][ ] |
[ ][ ][ ][ ][ ][ ] w
[ ][ ][ ][ ][ ][ ] i
[ ][ ][ ][ ][ ][ ] d
[ ][ ][ ][ ][ ][ ] t
[ ][ ][ ][ ][ ][ ] h
[ ][ ][ ][ ][ ][ ] =
[ ][ ][ ][ ][ ][ ] 9
[ ][ ][ ][ ][ ][ ] |
Because your program will be used for a variety of geographic areas (each with its own length and width) your program needs to dynamically allocate the memory for the number of zones it is to handle (vertically and horizontally).

To do so, you must use the two following functions without changing the code in them:

int ** allocateIntStarArray(int num){
    int ** ptr = (int **) malloc(num * sizeof(int *));
    return ptr;
}

int * allocateIntArray(int num){
    int * ptr = (int *) malloc(num * sizeof(int));
    return ptr;
}

The function allocateIntArray() will be used to allocate the space required to store the average temperatures in one row of zones, that is, an array of integers. The function therefore returns a pointer to such an array of integers.

The function allocateIntStarArray() will be used to allocate an array of pointers, each of which will store a pointer to a row of integers (temperatures of zones). That is, the function returns a pointer to an array of pointers. Each cell of this array will point to an array of integers containing the temperature values for the zones.

The inputs of the program are first the length, then the width of an area, then the average temperatures of all zones, row by row.

Please remember to free the memory you have allocated.

The output should pinpoint the possible zones with fires with [X] and the watch zone with a [*], the other zone are displayed with [ ].

Look at the example at the bottom and make sure to format your output in the exact same way.

Input:

6
9
70 71 70 72 70 69
71 73 68 71 73 72
70 71 70 76 1900 78
69 71 100 800 75 71
70 70 71 79 70 69
70 71 112 1005 75 72
70 71 70 900 70 70
72 70 70 72 70 69
73 74 73 72 70 70
Output:

[ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][X][ ]
[ ][ ][s][s][ ][ ]
[ ][ ][ ][ ][ ][ ]
[ ][ ][s][X][ ][ ]
[ ][ ][ ][s][ ][ ]
[ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ]

/*
6
9
70   71   70   72   70   69
71   73   68   71   73   72
70   71   70   76   1900 78
69   71   100  800  75   71
70   70   71   79   70   69
70   71   112  1005 75   72
70   71   70   900  70   70
72   70   70   72   70   69
73   74   73   72   70   70
*/

#include <stdio.h>

int ** allocateIntStarArray(int);
int * allocateIntArray(int);
int ** create2dArr(int, int);
void deleteArr(int **, int);

int main(void){
    int rows, cols;
    
    scanf("%d", &cols);
    scanf("%d", &rows);
    
    int ** temperatures = create2dArr(rows, cols);
    
    int i, j;
    
    for(i = 0; i < rows; i++){
        for(j = 0; j < cols; j++){
            scanf(" %d", &temperatures[i][j]);
        }
    }
    
    
    for(i = 0; i < rows; i++){
        for(j = 0; j < cols; j++){
            int temp = temperatures[i][j];
            
            if(temp > 1000){
                printf("[X]");    
            }
            else{
                if(temp >= 100){
                    printf("[*]");
                }else{
                    printf("[ ]");
                }
            }
            
            
        }
        printf("\n");
    }
    
    
    
    
    deleteArr(temperatures, rows);
    
    return(0);
}

void deleteArr(int ** Arr, int rows){
    int i;
    for(i = 0; i < rows; i++){
        //cut the head first
        free(Arr[i]);
    }
    //cut the holder
    free(Arr);
}

//Storage for temperatures value in 2D 
int ** create2dArr(int rows, int cols){
    //Create address holder for all possible rows
    int ** tempArr = allocateIntStarArray(rows);
    
    int i;
    //Save the address of allocated each rows (cols head)
    for(i = 0; i < rows; i++){
        tempArr[i] = allocateIntArray(cols);
    }
    
    return tempArr;
}

//store a pointer to a row of integers (temperatures of zones)
int ** allocateIntStarArray(int num){
    int ** ptr = (int **) malloc(num * sizeof(int *));
    return ptr;
}

//store the average temperatures in one row of zones, that is, an array of integers
int * allocateIntArray(int num){
    int * ptr = (int *) malloc(num * sizeof(int));
    return ptr;
}

Quicksort

#include <stdio.h>

void swap(int *, int *);
int hoare_split(int *, int, int);
void quicksort(int *, int, int);


int main(void){
    int size;
    scanf("%d", &size);

    int array[size];

    for(int i = 0; i < size; i++){
        scanf("%d", &array[i]);
    }

    quicksort(array, 0, size-1);

    for(int i = 0; i < size; i++)
        printf("%d", array[i]);
    printf("\n");
    return(0);
}

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


int hoare_split(int * a, int low, int high){
    int e = a[low];
    int i = low - 1, j = high + 1;

    for(;;){
        do{
            i++;
        }while(a[i] < e); //Put lesser on the left

        do{
            j--;
        }while(a[j] > e); //Put greater on the right

        if(i >= j) return j; //Exit condition

        swap(&a[i], &a[j]);
    }
}

void quicksort(int * a, int low, int high){
    if(low == high) return; //Termination
    int middle;
    middle = hoare_split(a, low, high);
    quicksort(a,low, middle);
    quicksort(a,middle+1,high);
}