C Programming: A Self-Learning Guide

C Programming: A Self-Learning Guide

The purpose of this page is to guide someone wishing to learn to program using the C programming language, specifically the ANSI Standard of 1989. Each section consists of

  • a link to a video that teaches an element of the language
  • sample problems for you to try. My solutions to the problems can be found at the bottom of the page. It’s OK if your solution isn’t the same as mine.

Some sections also include a link to a video demonstrating an application of the topic or a link to another page in which I go into more detail about my design process.

Note that the practice problems build upon your knowledge. Some of the practice problems assume you worked the earlier problems.

Introduction

start here: Introduction

Now you need to install the necessary software:


Statements

start here: Statements

Now try the following practice problems:

Practice #1: printf() has a very large number of format specifiers.  There are a number of options that can be used with the format specifiers for altering the way that information is displayed.  Run the following program with different values for the format specifiers (sorry about using loops before officially discussing them, but it makes this much simpler).

For the first printf(), some values to try are %2d and %4d. For the second printf(), some values to try are %2lf, %4.2lf, and %8.5lf (those are the letters ‘L’ and ‘F’ in lowercase). 

#include <stdio.h>
    
int main(void){
    int i;
    double x;
    
    for(i = 1; i < 10000; i *= 10)
        printf("%d\n", i);
    
    for(x = 1.234; x < 10000; x *= 10)
        printf("%lf\n", x);
}

Practice #2: Write a program that stores the values a = 4, b = 13, and c = 6 as variables of type int and produces d = (a + b + c)/5. Then print d to 2 decimal places.


Common Mistakes

Mistakes in syntax or logic are a part of programming. I have put together a video demonstrating many of the mistakes new (and not so new) C programmers make, with solutions.

There is a catch-22 to this video. If you are new to C programming and watch it now, you won’t understand much of it. If you wait until you have reached the end of this self-learning guide to watch the video, then you have likely already made some of these mistakes. I would encourage you to watch the video early on to at least plant some ideas in your head and then revisit the video as you gain experience.

video: Common C Mistakes


Conditionals

start here: Conditionals

then here: Logical Operators

then here: application of conditionals

Practice #1: Compare the output from the following programs.  Why is it different?

/* version 1*/
#include <stdio.h>
    
int main(void) {
    int x = 8;
    
    if(x < 6)
        printf("%d < 6\n", x);
    else if(x < 8)
        printf("%d < 8\n", x);
    else if(x < 10)
        printf("%d < 10\n", x);
    else if(x < 12)
        printf("%d < 12\n", x);
    else if(x < 14)
        printf("%d < 14\n", x);
}

/* version 2 */
#include <stdio.h>
    
int main(void) {
    int x = 8;
    
    if(x < 6)
        printf("%d < 6\n", x);
    if(x < 8)
        printf("%d < 8\n", x);
    if(x < 10)
        printf("%d < 10\n", x);
    if(x < 12)
        printf("%d < 12\n", x);
    if(x < 14)
        printf("%d < 14\n", x);
}

Practice #2: The following program doesn’t print anything.  Why?  Using only a set of curly braces, change the program such that the second printf() statement will print if age is less than or equal to 50.

#include <stdio.h>
     
int main(void) {
    int age = 40;
     
    if(age > 50)
        if(age < 75)
            printf("first printf\n");
        else
            printf("second printf\n");
}

Practice #3: Write a program that prompts a user for an integer, checks for divisibility by 2 and 3, and then prints the statements given by the truth table below. To prompt the user, you will need the following code:

#include <stdio.h>
     
int main(void) {
    int x;
    
    printf("enter an integer: ");
    scanf("%d", &x);
    
    /* put your logic here */
}

divisible  divisible
   by 2       by 3    prints
---------------------------------------------------
   True       True    both 2 and 3 are divisors
   True       False   only 2 is a divisor
   False      True    only 3 is a divisor
   False      False   neither 2 nor 3 is a divisor

Loops

start here: Loops

then here: application of loops

Practice #1: Rewrite the following program, replacing the for loop with a while loop.

#include <stdio.h>

int main(void) {
    int i;

    for(i = 8; i > 5; i--)
        printf("%d\n", i);
}

Practice #2: You have a program that prompts a user for two integers, which are stored in the variables start and stop.  Write the code that will produce an integer x in the range of start to stop, inclusive. If x is even then your program will print “x is Even”. Otherwise, print the value of x. You can assume that the starting integer is less than or equal to the stopping integer.

Practice #3: Write a program that prints the integers from 1 to 100 as a 10×10 table with the values right-aligned within their column.  Each row will begin with the character ‘X’. The results will be

X  1   2   3   4   5   6   7   8   9  10 
X 11  12  13  14  15  16  17  18  19  20 
X 21  22  23  24  25  26  27  28  29  30 
X 31  32  33  34  35  36  37  38  39  40 
X 41  42  43  44  45  46  47  48  49  50 
X 51  52  53  54  55  56  57  58  59  60 
X 61  62  63  64  65  66  67  68  69  70 
X 71  72  73  74  75  76  77  78  79  80 
X 81  82  83  84  85  86  87  88  89  90 
X 91  92  93  94  95  96  97  98  99 100

Functions

start here: Functions, part 1

then here: Functions, part 2

then here: application of functions, part 1

then here: application of functions, part 2

Practice #1: Write a function declaration for a function with the namecalcAge that will receive a variable of type int and has a return type of float.

Practice #2: The following program makes a function call to a function called multNums.  multNums takes two arguments, multiplies them together, and then returns the result. Write the function declaration and function definition for multNums.  The return type and variable types that you write for multNums should match those of the variables involved in the function call of the sample program. Your function definition will include whatever code is necessary to perform the calculation.

#include <stdio.h>

/* function declaration goes here */

int main( void ) {
   int hours = 3;
   float rate = 5;
   double cost;

   cost = multNums(hours, rate);
   
   printf("cost is %2.f\n", cost);
}

/* function definition goes here */

Practice #3: Write a function that when given a two positive integers a and b determines how many of the integers in the range of a to b inclusive are divisible by 3 and how many are divisible by 5. The function will print these two counts as well as how many of the integers in the range are not divisible by 3 or 5. If a number is divisible by 3 and 5, then update the counts for each of 3 and 5. As the function is performing the counts, have it print the matching number. For example, if the current number is 9 then the count for divisibility by 3 will be incremented and you will print that 9 is divisible by 3.

If the function is called with the code below

#include<stdio.h>

int main( void ) {
    int a = 6, b = 20;

    f(a, b);
}

then the output will be

6 is divisible by 3
7 is not divisible by 3 nor 5
8 is not divisible by 3 nor 5
9 is divisible by 3
10 is divisible by 5
11 is not divisible by 3 nor 5
12 is divisible by 3
13 is not divisible by 3 nor 5
14 is not divisible by 3 nor 5
15 is divisible by 3
15 is divisible by 5
16 is not divisible by 3 nor 5
17 is not divisible by 3 nor 5
18 is divisible by 3
19 is not divisible by 3 nor 5
20 is divisible by 5

divisible by 3 = 5
divisible by 5 = 3
divisible by neither = 8

Practice #4: Write a function that when given an integer x, returns the second smallest divisor of x (not counting 1).  For example, if x = 12, then the function would return 3 since the divisors are 1, 2, 3, 4, 6, and 12 (remember, we are not counting 1).  If x does not have a second smallest divisor, then the function should return zero.

Practice #5: Write a program that produces the integers in the range of 2 to 100, but only prints those that are prime.  If the number produced is not prime, print two periods instead.  Everything printed should result in a 10×10 table of either values printed or spaces.   The results will be

  ..   2   3  ..   5  ..   7  ..  ..  ..
  11  ..  13  ..  ..  ..  17  ..  19  ..
  ..  ..  23  ..  ..  ..  ..  ..  29  ..
  31  ..  ..  ..  ..  ..  37  ..  ..  ..
  41  ..  43  ..  ..  ..  47  ..  ..  ..
  ..  ..  53  ..  ..  ..  ..  ..  59  ..
  61  ..  ..  ..  ..  ..  67  ..  ..  ..
  71  ..  73  ..  ..  ..  ..  ..  79  ..
  ..  ..  83  ..  ..  ..  ..  ..  89  ..
  ..  ..  ..  ..  ..  ..  97  ..  ..  ..

Practice #6: Reading code is an invaluable skill as a programmer. You need to be able to read your own code as well as others.

What does this program print? Try constructing a table and filling it in as you process the loop. Your table might start like this:

  i    alpha   beta    prints
-----------------------------
  12     ?       ?        ?

#include <stdio.h>

int alpha(int a);
int beta(int b);

int main(void) {
    int i;
    
    for(i = 12; i < 26; i = i + 3)
        if( alpha(i) && beta(i) )
            printf("%d\n", i);
}

int alpha(int a) {
    if(a%3 == 0)
        return 1;
    else
        return 0;
}

int beta(int b) {
    if(b%2 == 0)
        return 1;
    else
        return 0;
}

Arrays

start here: One-Dimensional Arrays

then here: Multidimensional Arrays

then here: application of arrays, part 1

design discussion: Simulating a Perfect Shuffle

Practice #1: Write a program that stores the numbers 1, 2, 7, 18, 23, and 40 in an array. Then move through the array, producing the sum of the even integers.

Practice #2: For the program below, write the code that will store the values in array1 in array2, but in reverse order. Also write printArray() to print the arrays.

#include <stdio.h>
    
void printArray(int [], int);

int main(void) {
    int array1[5] = {17, 23, 9, 4, 12};
    int array2[5];
    int length = 5;
    int i;

      /* code to store array1 in array2 in 
         reverse order goes here            */

    printf("array1: ");
    printArray(array1, length);
    printf("array2: ");
    printArray(array2, length);
}

Practice #3: Modify the program below to swap the elements between the two arrays. That is, after you are done then array1[0] = 99 and array2[0] = 1 and so on for each corresponding array element.

#include <stdio.h>
    
void printArray(int [], int);

int main(void) {
    int array1[5] = {1, 2, 3, 4, 5};
    int array2[5] = {99, 88, 77, 66, 55};
    int temp;
    int length = 5;
    int i;

      /* code for swapping goes here */

    printf("array1: ");
    printArray(array1, length);
    printf("array2: ");
    printArray(array2, length);
}

void printArray(int data[], int length) {
    int i;

    for(i = 0; i < length; i++)
        printf("%2d ", data[i]);

    printf("\n");
}

Practice #4: Modify the looping structure of the program below so that it produces the output shown.  Hint: this can be done by changing only two lines.

#include <stdio.h>
    
int main(void){
    int data[2][3] = { {15, 72,  9},
                       { 4,  8, 11} };
    int i, k;
    
    for(i = 0; i < 2; i++) {
        for(k = 0; k < 3; k++) {
            printf("%2d ", data[i][k]);
        }
        printf("\n");
    }
}
    
/*****************
 ***   Output   ***
    15  4 
    72  8 
     9 11 
*****************/

Practice #5: Write a program that declares a 2D array with three columns. The program passes the array to a function that replaces each element in the center column with the sum of the other two elements on the same row. For example, if the first row of the array is

5, 8, 10

then after the call to your function this row would be

5, 15, 10

Note that this can be done with a single loop that generates the subscript of the row. Also create a second function that prints a 2D array with three columns.

Practice #6: Finish the program below by writing the code to change any number in the array to 99 if, and only if, the values immediately before and after the current number are both even. The first and last elements of the array should not be changed. The array should be processed beginning with the element at index 1. Note that when processing a number, if the value before it has been changed to 99 that is what should be considered, not the value in the initial version of the array. Your program should still work if I changed the array values.

#include <stdio.h>

int main(void)
{
    int d[] = {9, 8, 2, 15, 6, 32, 10, 4};

Practice #7: Write a function that when given a 2D array with three columns, prints the numbers in each row as a sum and then prints the actual sum of the row values. For example, given

#include <stdio.h>

int main(void) {
    int d[][3] = {{ 1,  2,  3},
                  { 4,  5,  6},
                  { 7,  8,  9},
                  {-1, -2, -3}};
    int rows;

    rows = sizeof(d)/sizeof(d[0]);
    printRowSums(d, rows);
} 

# output
  1 +  2 +  3 =  6
  4 +  5 +  6 = 15
  7 +  8 +  9 = 24
 -1 + -2 + -3 = -6

Practice #8: The program below calls the function findNum() to search an array for number. If it finds number in the array, it returns the index of the first occurrence (in case there are multiple occurrences) of number. If number is not in the array, the function returns -1. Write findNum().

#include <stdio.h>

int main(void) {
     int d[] = {-2, 14, 7, 61, 99, 7, 0, -10};
     int number;
     int index, size = sizeof(d)/sizeof(d[0]);
     
     number = 7; /* number to search for */
     index = findNum(d, size, number);
     
     if(index >= 0)
         printf("%d is at index %d\n", number, index);
     
     number = 123; /* number to search for */
     index = findNum(d, size, number);
     
     if(index >= 0)
         printf("%d is at index %d\n", number, index);
}

Variable Types

start here: Bits, Bytes, and Numbers Bases

then here: Integer Variable Types

then here: Floating-Point Variable Types

Practice #1: or the following program, which of the following is true? If you choose one of the first three answer, explain what the problem is and the solution to it.

  1. The value produced by y = w + x will be incorrect.
  2. The value produced by z = w – x will be incorrect.
  3. The values produced by y = w + x and z = w – x will both be incorrect.
  4. The values produced by y = w + x and z = w – x will both be correct.
/*
  on this machine, a short int is 2 bytes, an int 
  is 4 bytes, and a long int is 8 bytes
*/
    #include <stdio.h>
    
    int  main(void) {
        short w = 20000;
        short x = 15000;
        short y;
        short z;
    
        y = w + x;
        z = w - x;
    
        printf("w + x = %hd\n", y);
        printf("w - x = %hd\n", z);
    }

Practice #2: Run the following program. Is the output what you expected?

#include <stdio.h>

int main(void) {
    short int x = 32765;
    int i;

    for(i = 0; i < 5; i++) {
        printf("%d\n", x);
        x++;
    }
}

Practice #3: Why does the number of bytes reported from f() differs from in main()?

#include <stdio.h>

void f(int data[]) {
    printf("here data has a size of %d bytes\n", sizeof(data) );
}

int main(void) {
    int data[] = {1, 2, 3};

    printf("data has a size of %d bytes\n", sizeof(data) );

    f(data);
}

/**************************************
***             Output              ***
  data has a size of 12 bytes
  here data has a size of 8 bytes
*/

Pointers

start here: Introduction to Pointers

then here: Pointers and Arrays, part 1

then here: Pointers and Arrays, part 2

Pointers is difficult, yet very important, topic in C. I have put together a separate page that goes into a lot of detail: Pointers

Practice #1: What format specifiers (in order) should be used in the printf() statement in the following program?  Note that in the program the correct format specifiers have been replaced by Z.

#include <stdio.h>

int main(void) {
    int x = 5;
    int* x_ptr = &x;

    printf("%Z, %Z, %Z, %Z\n", x, *x_ptr, &x, x_ptr);
}

Practice #2: We have the following code snippet

int main(void) {
    int x = 5;
    int *ptrA = &x;
    int **ptrB = &ptrA;
}

What value does each of the following represent?  If the answer is an address, state such and include which variable the address is for.

  • x
  • ptrA
  • ptrB
  • *ptrA
  • *ptrB
  • **ptrB

Practice #3: On a machine in which addresses are 8 bytes, what is printed by the following program:

#include <stdio.h>

int  main(void) {
                    /*          1         2         3 */
                    /* 123456789012345678901234567890 */
    char fun[]      = "Programming is fun.";
    char favorite[] = "I love programming in C.";
    char *x = fun;

    printf("%d, ", sizeof(fun));
    printf("%d, ", sizeof(favorite));
    printf("%d\n", sizeof(x));
}

Practice #4: Rewrite the following program, replacing the subscript notation with the corresponding pointer notation.  Only change the parts of the program necessary for the replacement.

#include <stdio.h>
    
int main(void) {
    int data[] = {1, 2, 3, 4, 5, 6}; 
    int i;
    
    for(i = 0; i < 6; i++)
        printf("%2d", data[i]);
}

Practice #5: What does the following program print? Creating a table for the values of i and ptr will help.

#include <stdio.h>

int main(void) {
    int data[] = {1, 2, 3, 4, 5, 6, 7};
    int *ptr = data;
    int i;

    printf(" i  *ptr\n--------\n");

    for(i = 2; i > -4; i--) {
        printf("%2d,  %2d\n", i, *ptr);
        ptr += i;
    }
}

Practice #6: Rewrite the following program such that the function has a return type of void and the variable y gets its value using pointers.

#include <stdio.h>

int dbl(int num);

int main(void) {
    int x = 13;

    x = dbl(x);
    printf("x doubled is %d\n", x);
}

int dbl(int num) {
    return 2*num;
}

Practice #7: In this program is a function call to a function called getRange().  getRange() is passed the addresses of two variables, low and high, as well as a variable called mid.  getRange() calculates a value for low of 75% of the value of mid and a value of 125% of the value of mid for the value of high.  The values of all three variables are printed from main() after the function call. Write getRange().

#include <stdio.h>

int main(void) {
    double low, high, mid = 40;

    getRange(&low, &high, mid);

    printf("low = %5.2f, mid = %5.2f, high = %5.2f\n", \ 
            low, mid, high);
}
/**********************************************
***                output                   ***
  low = 30.00, mid = 40.00, high = 50.00
*/

Practice #8: The following program prints out the elements of the array. Why does this work since there is no row offset in the expression in the printf() statement?

#include <stdio.h>
    
int main(void) {
    int data[3][4] = { {11, 12, 13, 14},
                       {15, 16, 17, 18},
                       {19, 20, 21, 22} };
    int i;
        
    for(i = 0; i < 12; i++)
        printf("%d ", *(*data + i) );
}

Practice #9: Write the function change() such that it changes the value of x from 5 to 99.

#include <stdio.h>
  
int main(void) {
    int x = 5;
    int *p1 = &x;
    int **p2 = &p1;

    printf("before: x = %d\n", x);
    change(&p1);
    printf(" after: x = %d\n", x);
}

Strings

start here: Introduction to Strings

then here: String Library Functions

Practice #1: Change the program below to print “I love programming.” You
should do this by using the values in lovetext to change hatetext.  Hint:  think about the relationship between the index values of the letters in “love” and the index values for the word “hate”. This can be done without creating any new variables.

#include <stdio.h>

int  main(void) {
    int i;
    char hatetext[] = "I hate programming.";
    char lovetext[] = "love";

    /* Your code goes here. */

    printf("%s\n", hatetext);
}

Practice #2: What does the following program print?

#include <stdio.h>

int  main(void) {
                /*           1         2         3     */
                /* 01234567890123456789012345678901234 */
    char text[] = "D   kfa i ifr s nfi   gfn   .";
    int i = 0;

    while(text[i] != '\0')
        if(text[i] == 'f')
            printf("\n", text[i++]);
        else
            printf("%c", text[i++]);
}

Practice #3: Modify the program below such that it prints

one
two
three
four

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

int main(void) {
    char* s[] = {"four", "two", "three", "one"};
    int i;

    /* put your code here */

    for(i = 0; i < 4; i++)
       printf("%s\n", s[i]);
}

Practice #4: The following program has a bug.  What is it and how do you correct it?

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

int main(void) {
    char s[] = "Bob,53";
    char *token1, *token2, *del = ",";

    token1 = strtok(s, del);
    token2 = atoi( strtok(NULL, del) );

    printf("%s is %d years old.\n", token1, token2);
}

Practice #5: The following program has a bug.  What is it and how do you correct it?

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

int main(void) {
    char x1[] = "cat";
    char x2[] = "cadillac";
    
    /* are the first letters the same? */
    if( strcmp(x1[0], x2[0]) == 0 )
        printf("the same");
    else
        printf("different");
}

Practice #6: The program below calls a function, f(), that when given an array of strings will put the address of the shortest string in the first position (i.e., the one with index 0) and the address of the longest string in the last array position.  Assume that the array will not be used after printing the shortest and longest strings and therefore the other strings in the array are unimportant.

Write f() without hard-coding it to this particular set of strings.
The types of the function parameters should match their use in the program.

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

int main(void) {
    char* t[] = {"horse", "elephant", "cat", "rabbit"};
    int n;

    n = sizeof( t )/ sizeof( t[0] );
    f(t, n);

    printf("shortest is %s, longest is %s\n", t[0], t[n-1]);
}

File Input/Output

start here: File I/O, part 1

then here: File I/O, part 2

design example: Choosing an Electrical Plan

Practice #1: You have a file, payments.txt, that contains a list of people and the amount of payments made by each person. Write a program that can read each line, printing the name and payment of each line. After all of the lines have been printed, print the sum of all payments. Here is what payments.txt looks like: 

Bob 250
George 300
Suzanne 250
Tony 200

Practice #2: You have a file, people.txt, with an unknown number of lines and four words per line, with the words separated by spaces.  The size of the words can differ from line to line, but none will ever contain more than 30 characters and all of them plus the spaces separating the strings will not total more than 100 characters.

Write a program that can read each line of the file and, if the second word is “Smith”, writes the words from that line in reverse order to the file smith.txt. Otherwise, do nothing with the line. For example, if people.txt is

John Wiliams 45 Main
Mary Smith 33 Elm
Ralph Wiggum 12 Oak
Bart Simpson 10 King
John Smith 50 Sunset

then smith.txt will be

Elm 33 Smith Mary
Sunset 50 Smith John

Practice #3: Write a program that can read a file, names.txt, that contains a single name on each line.  If the name begins with a capital letter, print the name.  If it begins with a lowercase letter, don’t print it.  Each name contains less than 20 letters.


Structures

start here: Structures

then here: application of structures

Practice #1: Create a structure that could be used to store the following
book information:

The C Programming Language, 2nd Edition
by Brian W. Kernighan and Dennis M. Ritchie
ISBN 9780131103627

Practice #2: Write a program that stores the following information in an array of structures (note you will hard-code these values in your program). The values on a row represent a department, course number, section number, and enrollment. Print the structures.

CSE,1310,1,45
CSE,1310,2,50
MATH,1426,1,75
MATH,3330,2,60
IE,3301,1,40

Practice #3: Store the course information from the previous problem into a CSV file and then read the file to construct the array of structures.

Practice #4: Create a structure definition for storing a person’s first name and their age.  Then write a program that creates an array of three structures and populates the values by prompting the user using a loop.

Practice #5: The program below wants to add the cars from the array new to the array old, but only if the car is not already in the array (it’s in the array if both the make and model match). Write the function addCars().

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

struct car {
    char make[20];
    char model[20];
};

int main(void) {
    struct car old[20] = {{"Ford", "Explorer"}, 
                          {"Honda", "Civic"},
                          {"Honda", "Accord"},  
                          {"Chevy", "Malibu"},
                          {"Jeep", "Cherokee"}};
    struct car new[]   = {{"Ford", "Mustang"}, 
                          {"Honda", "Accord"},  
                          {"Chevy", "Malibu"}, 
                          {"Mazda", "RX-8"}};
    int i, oldCount = 5, newCount = 4;

    addCars(old, &oldCount, new, newCount);

    for(i = 0; i < oldCount; i++)
        printf("%s %s\n", old[i].make, old[i].model);
}

Practice #6: For the program below, write the function caps() that changes the first letter of each animal name and type to uppercase.

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

struct animal {
    char name[20];
    char type[20];
};


int main(void) {
    struct car a[] = { {"zebra", "mammal"},
                       {"gorilla", "mammal"},
                       {"shark", "fish"},
                       {"vulture", "bird"},
                       {"rhino", "mammal"}};
    int size = 5;

    caps(a, size);

    for(i = 0; i < size; i++)
        printf("%s, %s\n", a[i].name, a[i].type);
}

Dynamic Memory Allocation

start here: Variable Scope, Storage Duration, and Dynamic Memory

then here: Examples of Dynamic Memory Allocation

then here: application of dynamic memory

Practice #1: Using malloc(), allocate the memory for a 1D array
of type int that can store 5 integers.  Then prompt the user for integers and store them in this array.  The program should stop when either the user enters a negative integer or has provided 5 nonnegative integers.  Print the array values that were stored.

Practice #2: Using malloc(), allocate the memory for a 2D array of type int with 3 rows and 4 columns.  The positions in the array should be assigned the sum of the array indices, for example, the [2][3] position will be assigned 2 + 3 = 5. Print the array values that were stored.

Practice #3: Using malloc(), allocate the memory for a 1D array
of type int that can store 5 integers.  Then prompt the user for integers and store them in this array, stopping when the user enters a negative integer. Each time you need to store a number but there is insufficient space to do so, double the amount of space using realloc(). Print the array values that were stored.

You can help yourself understand if the reallocation is working by printing a message each time you do it.

Practice #4: Write a program that can read a file, storing each line of the file in a dynamically-allocated array of strings. You an assume that the number of lines in the file will not exceed 50 and that each line can be stored in 100 bytes. Test what you have stored by printing the lines in reverse order from how they appear in the file.

Practice #5: The program below calls a function, changeArray(), that when given the address of a dynamically-allocated array will free this memory and then allocate a new array with enough space to store size ints. Write this function and have it also store the integers 11 through 15 in the new array. The purpose of this problem is to see if you can change the contents of a pointer created in one function from another function.

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

void printArray(int d[], int size) {
    int i;

    for(i = 0; i < size; i++)
        printf("%d  ", d[i]);

    printf("\n");
}
  
int main(void) {
    int i, size = 5;
    int* d = malloc(size * sizeof(int));

    for(i = 0; i < size; i++)
        d[i] = i+1;

    printArray(d, size);

    changeArray(&d, size);
    printArray(d, size);

    free( d );
}

Recursion

start here: Introduction to Recursion

Practice #1: Write a function that when given an integer n returns the sum of the integers from 1 to n.  The function should use recursion to produce the sum.  No printing will occur in the function.

Practice #2: We can search a sorted array using a binary search. Implement the function to search an array based upon this slightly modified pseudocode (from https://rosettacode.org/wiki/Binary_search). The function either returns the index where it found an occurrence of value or returns -1 to indicate value is not in the array.

// initially called with low = 0, high = N-1
BinarySearch(A[0..N-1], value, low, high) {
    if (high < low)
        return -1 
    mid = (low + high) / 2
    if (A[mid] > value)
        return BinarySearch(A, value, low, mid-1)
    else if (A[mid] < value)
        return BinarySearch(A, value, mid+1, high)
    else
        return mid
}

Linked Lists

start here: Introduction to Linked Lists

then here: Constructing a Stack using a Linked List

then here: Constructing a Queue using a Linked List

Practice #1: The program below constructs a linked list. Write the functions:

  • printList() — given the head of the linked list, print it
  • findNum() — given the head of the linked list and a number x, counts how many times x occurs in the linked list. This count is returned by the function.
#include <stdio.h>
#include <stdlib.h>

struct node {
    int value;
    struct node *next;
};

struct node* addNode(struct node *h, int n) {
    struct node *temp = malloc( sizeof(struct node) );

    temp->value = n;    
    temp->next = h;    

    return temp;
}
  
int main(void) {
    struct node *head = NULL;
    int d[] = {5, -8, 99, 7, 13, 99, 0, 123};
    int i, len = sizeof(d)/sizeof(d[0]);
    int x, y;

    for(i = 0; i < len; i++)
        head = addNode(head, d[i]);

    printList(head);    

    x = 20;
    y = findNum(head, x);
    printf("%d occurs %d times\n", x, y);
    
    x = 13;
    y = findNum(head, x);
    printf("%d occurs %d times\n", x, y);
    
    x = 99;
    y = findNum(head, x);
    printf("%d occurs %d times\n", x, y);
}

Practice #2: Write a program that reads a file in which each line contains a single name. Store the names in a linked list and then print the list.

Practice #3: Write a program that reads a file in which each line contains a single name. Store the names in a linked list, but only if they are not already there. Print the list afterwards.

Practice #4: Write a program that creates two linked lists (using the same node definition) and then merges the two lists such that no values are duplicated. For example, if the list values are

// both lists contain 2 and 4
list1 = {1, 2, 3, 4, 5}
list2 = {99, 2, 13, 4, 7, 123}

then the merged list would have the following values (the order could differ)

merged = {99, 13, 7, 123, 5, 4, 3, 2, 1}

Binary Trees

start here: Introduction to Binary Trees

then here: Introduction to Binary Search Trees

then here: application of binary search tree

Practice #1: Write a function that can search a binary tree for all occurrences of a value.


Hash Tables

start here: Introduction to Hash Tables

One thing I forgot to mention in my video is that a downside of hash tables is order doesn’t typically matter. For example, I may create a hash table using the following as keys: “cat”, “dog”, “horse”, and “rabbit”, in that order. But if I look at the order of the keys in the hash table it could be something like “horse”, “dog”, “rabbit”, and “cat”. This is a problem if you care about retrieving things from the hash table in the order in which they were added to the hash table.

Practice #1: The partial program below creates a hash table (you should fill this in based on the example given in the video) that resolves collisions using chaining.  Write the function countValues(), which has the declaration given below and returns a count of how many key/values pairs have a specific value.

#define SIZE 10

struct node {
    char key[50];
    char value[50];
    struct node *next;
};

int hash(char key[]);
int countValues(struct node* table[], char value[]);

int main(void) {
    char key[50]; 
    char value[50]; 
    struct node *table[SIZE] = {NULL};  /* initialize all values to NULL */
    int count;

    /*   assume the logic for constructing the hash table is here.  */

    printf("Enter value:  ");
    fgets(value, sizeof(value), stdin);
    count = countValues(table, value);  /* write the function definition for countValues() */
    printf("%d pairs have a value of %s\n", count, value);
}

Graphs

start here: Introduction to Graphs

Practice #1: The partial program below calls maxSrc(), which receives a 2D array of type int representing an adjacency matrix.  The rows represent the source nodes and the columns represent the destination nodes of a directed graph. Write maxSrc() such that it returns the character representing the node with the most edges leaving it.  Assume that the first row represents node A, the second row represents node B, and so forth.

#include <stdio.h>

char maxSrc(int m[][4]);

int main(void) {
    int matrix[][4] = {{0, 0, 1, 0},
                       {1, 1, 1, 0},
                       {0, 0, 0, 1},
                       {0, 1, 1, 0}};

    printf("node %c has the most edges leaving it\n",
            maxSrc(matrix) );
}

Practice #2: It’s easy to understand what it means to sort a list of things, but what about a graph. Directed graphs show relationships. Assuming we don’t have any cycles (i.e., there is a path back to where we started) if A points to B and B points to C, then we can think of this in a ‘sorted’ fashion as A comes before B, which comes before C. Applying this reasoning to a directed graph is called a topological sort.

Store the following list of classes in an adjacency matrix. Then implement a topological sort using the pseudocode below.

 course      is a prerequisite to
----------------------------------------
CSE 1310     CSE 1320, CSE 2315 
CSE 1320     CSE 1325, CSE 2312, CSE 2320 
CSE 1325 
CSE 2312 
CSE 2315     CSE 2320 
CSE 2320 
MATH 1426    CSE 2315

/*  pseudocode of algorithm from 
      http://en.wikipedia.org/wiki/Topological_sorting

    L <- Empty list that will contain the sorted elements
    S <- Set of all nodes with no incoming edges
    while S is non-empty do
        remove a node n from S
        insert n into L
        for each node m with an edge e from n to m do
            remove edge e from the graph
            if m has no other incoming edges then
                insert m into S
    if graph has edges then
        return error (graph has at least one cycle)
    else 
        return L (a topologically sorted order)
*/

Solutions to Practice Problems

———- Statements, Practice #2

#include <stdio.h>

int main(void) {
    int a = 4;     
    int b = 13; 
    int c = 6;
    double d;

    d = (double)(a + b + c)/5;

    printf("d = %.2f\n", d);
}

———- Conditionals, Practice #1

In version 1, each else clause is only evaluated if all previous if statements fail. In version 2, each if statement is independent of the others so each is evaluated.

———- Conditionals, Practice #2

#include <stdio.h>
     
int main(void) {
    int age = 40;
     
    if(age > 50) {
        if(age < 75)
            printf("first printf\n");
    }
        else
            printf("second printf\n");
}

———- Conditionals, Practice #3

#include <stdio.h>
     
int main(void) {
    int x;
    
    printf("enter an integer: ");
    scanf("%d", &x);
    
    if(x%2 == 0 && x%3 != 0)
        printf("only 2 is a divisor\n");
    else if(x%2 != 0 && x%3 == 0)
        printf("only 3 is a divisor\n");
    else if(x%2 == 0 && x%3 == 0)
        printf("both 2 and 3 are divisors\n");
    else
        printf("neither 2 nor 3 is a divisor\n");
}

———- Loops, Practice #1

include <stdio.h>

int main(void) {
    int i;
    
    i = 8;
    
    while(i > 5) {
        printf("%d\n", i);
        
        i--;
    }
}

———- Loops, Practice #2

#include <stdio.h>

int main(void) {
    int start, stop, i;
    
    printf("enter a starting integer: ");
    scanf("%d", &start);
    printf("enter a stopping integer: ");
    scanf("%d", &stop);
    
    for(i = start; i <= stop; i++)
        if(i%2 == 0)
            printf("x is Even\n");
        else
            printf("%d\n", i);
}

———- Loops, Practice #3, version 1

#include <stdio.h>

int main(void) {
    int i; 
    
    for(i = 1; i < 101; i++) {
        if(i%10 == 1)
            printf("X");
        
        printf("%3d ", i);
        
        if(i%10 == 0) 
            printf("\n");
    }
}

———- Loops, Practice #3, version 2

#include <stdio.h>

int main(void) {
    int i, counter = 1;
    
    for(i = 1; i < 101; i++) {
        if(counter == 1)
            printf("X");

        printf("%3d ", i);

        if(counter == 10) {
            printf("\n");
            counter = 0;  /* reset counter */
        }

        counter++;
    }
}

———- Functions, Practice #1

float calcAge(int variableName);

———- Functions, Practice #2

double multNums(int hours, float rate); /* declaration */

/* definition */
double multNums(int hours, float rate) {
    double prod = hours * rate;

    return prod;
}

———- Functions, Practice #3

#include <stdio.h>

void f(int a, int b) {
    int i, div3 = 0, div5 = 0, other = 0;

    for(i = a; i <= b; i++) {
        if(i%3 == 0) {
            div3++;
            printf("%d is divisible by 3\n", i);
        }

        if(i%5 == 0) {
            div5++;
            printf("%d is divisible by 5\n", i);
        }

        if(i%3 != 0 && i%5 != 0) {
            other++;
            printf("%d is not divisible by 3 nor 5\n", i);
        }
    }

    printf("\n");
    printf("divisible by 3 = %d\n", div3);
    printf("divisible by 5 = %d\n", div5);
    printf("divisible by neither = %d\n", other);
}

———- Functions, Practice #4, version 1

int div2nd(int x) {           
    int i, count = 0;
    
    for(i = 2; i <= x; i++)
        if(x%i == 0)
            if(count == 0)
                count++;
            else
                return i; /* return on 2nd divisor */

    return 0;
}

———- Functions, Practice #4, version 2

int div2nd(int x) {
    int i, second = 0, flag = 0;

    for(i = 2; i <= x; i++) {
        if(x%i == 0)
            flag++;

        if(x%i == 0 && flag == 2)
            second = i;
    }

    return second;
}

———- Functions, Practice #5

#include <stdio.h>

int isPrime(int n) {
    int i;

    for(i = 2; i < n; i++)
        if(n%i == 0)
            return 0;

    return 1;
}
  
int main( void ) { 
    int i;

    printf("  ..");  /* 1 is special case */
    for(i = 2; i < 101; i++) {
        if( isPrime(i) )
            printf(" %3d", i);
        else
            printf("  ..");

        if(i%10 == 0)
            printf("\n");
    }
}

———- Functions, Practice #6

12
18
24

———- Arrays, Practice #1

#include <stdio.h>
  
int main(void) {
    int d[] = {1, 2, 7, 18, 23, 40};
    int sum = 0, i;

    for(i = 0; i < 6; i++)
        if(d[i]%2 == 0)
            sum += d[i];

    printf("sum = %d\n", sum);
}

———- Arrays, Practice #2

#include <stdio.h>
    
void printArray(int [], int);

int main(void) {
    int array1[5] = {17, 23, 9, 4, 12};
    int array2[5];
    int length = 5;
    int i;

    for(i = 0; i < length; i++)
        array2[length - 1 - i] = array1[i];

    printf("array1: ");
    printArray(array1, length);
    printf("array2: ");
    printArray(array2, length);
}

void printArray(int data[], int length) {
    int i;

    for(i = 0; i < length; i++)
        printf("%2d ", data[i]);

    printf("\n");
}

———- Arrays, Practice #3

#include <stdio.h>
    
void printArray(int [], int);

int main(void) {
    int array1[5] = {1, 2, 3, 4, 5};
    int array2[5] = {99, 88, 77, 66, 55};
    int temp;
    int length = 5;
    int i;

    for(i = 0; i < length; i++) {
        temp = array1[i];
        array1[i]= array2[i];
        array2[i]= temp;
    }

    printf("array1: ");
    printArray(array1, length);
    printf("array2: ");
    printArray(array2, length);
}

void printArray(int data[], int length) {
    int i;

    for(i = 0; i < length; i++)
        printf("%2d ", data[i]);

    printf("\n");
}

———- Arrays, Practice #4

#include <stdio.h>
    
int main(void){
    int data[2][3] = { {15, 72,  9},
                       { 4,  8, 11} };
    int i, k;
    
    /* I did not correct the formatting to make it
       more clear what changes I made.  */
        for(k = 0; k < 3; k++) {
    for(i = 0; i < 2; i++) {
            printf("%2d ", data[i][k]);
        }
        printf("\n");
    }
}

———- Arrays, Practice #5

#include <stdio.h>

void addColumns(int d[][3], int rows) {
    int i;

    for(i = 0; i < rows; i++)
        d[i][1] = d[i][0] + d[i][2];
}

void printArray(int d[][3], int rows) {
    int i, k;
    
    for(i = 0; i < rows; i++) {
        for(k = 0; k < 3; k++)
            printf("%2d ", d[i][k]);

        printf("\n");
    }
}
    
int main(void){
    int data[][3] = { { 1, 2, 3},
                      { 4, 5, 6},
                      { 7, 8, 9},
                      {10,11,12} };
    int i, k, rows = 4;
        
    addColumns(data, rows);
    printArray(data, rows);
}

———- Arrays, Practice #6

#include <stdio.h>

int main(void) {
    int d[] = {9, 8, 2, 15, 6, 32, 10, 4};
    int i, length;

    length = sizeof(d)/sizeof(d[0]);

    for(i = 0; i < length - 1; i++)
        if(d[i-1]%2 == 0 && d[i+1]%2 == 0)
            d[i] = 99;

    for(i = 0; i < length; i++)
        printf("%d ", d[i]);

    printf("\n");
}

———- Variable Types, Practice #1

Answer: The value produced by y = w + x will be incorrect. Why? The range of a short is -32,768 to 32,767, so it can’t store 35,000. The solution is to use an integer type than can represent a larger range of values.

———- Variable Types, Practice #2

Answer: After we reach the largest signed value of a short, which is 32,767, adding 1 to it forces the sign bit to flip. These bit patterns are then interpreted as negative numbers.

———- Variable Types, Practice #3

Answer: In main() we are returning the size of the array in bytes. We passed the address of the first element of the array to f(), not the array itself. Therefore, we are reporting the size of an address.

———- Pointers, Practice #1

printf("%d, %d, %p, %p\n", x, *x_ptr, &x, x_ptr);

———- Pointers, Practice #2

  • x = 5
  • ptrA = address of x
  • ptrB = address of ptrB
  • *ptrA = 5
  • *ptrB = address of x
  • **ptrB = 5

———- Pointers, Practice #3

20, 25, 8

———- Pointers, Practice #4

#include <stdio.h>
    
int main(void) {
    int data[] = {1, 2, 3, 4, 5, 6};
    int i;
    
    for(i = 0; i < 6; i++)
        printf("%2d", *(data + i));
}

———- Pointers, Practice #5

 i  *ptr
--------
 2,   1
 1,   3
 0,   4
-1,   4
-2,   3
-3,   1

———- Pointers, Practice #6

#include <stdio.h>

void dbl(int* num) {
    *num = 2 * *num;
}

int main(void) {
    int x = 13;

    dbl(&x);

    printf("x doubled is %d\n", x);
}

———- Pointers, Practice #7

void getRange(double *l, double *h, double m) {
    *l = 0.75*m;
    *h = 1.25*m;
}

———- Pointers, Practice #8

The statement

*(*data + i)

is equivalent to writing

*(*(data+0) + i)

This means that we have a row offset of 0 to get the row address, then after dereferencing we use a column offset of i. This never changes. Remember that when we create a 2D array like in this case, all of the rows are really next to each other in memory so the first number of the second row is after the last number of the first row. In this case we simply move down the line to each of the 12 numbers.

———- Pointers, Practice #9

void change(int **q) {
    **q = 99;
}

———- Strings, Practice #1

#include <stdio.h>

int  main(void) {
    int i;
    /*                 0123456            */
    char hatetext[] = "I hate programming.";
    char lovetext[] = "love";

    for(i = 0; i < 4; i++)
        hatetext[i+2] = lovetext[i];

    printf("%s\n", hatetext);
}

———- Strings, Practice #2

D   k
a i i
r s n
i   g
n   .

———- Strings, Practice #3

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

int main(void) {
    char* s[] = {"four", "two", "three", "one"};
    int i;

    char* temp;

    temp = s[0];
    s[0] = s[3];
    s[3] = temp;

    for(i = 0; i < 4; i++)
       printf("%s\n", s[i]);
}

———- Strings, Practice #4

atoi() receives the address of a string of digit characters and returns the corresponding integer. The bug is that this integer is saved in token2, which has type char*.

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

int main(void) {
    char s[] = "Bob,53";
    char *token1, *del = ",";
    int val;

    token1 = strtok(s, del);
    val = atoi( strtok(NULL, del) );

    printf("%s is %d years old.\n", token1, val);
}

———- Strings, Practice #5

strcmp() expects to receive two addresses but receives characters (a type of int) instead.

#include <stdio.h>

int main(void) {
    char x1[] = "cat";
    char x2[] = "cadillac";

    /* are the first letters the same? */
    if( x1[0] == x2[0] ) 
        printf("the same");
    else
        printf("different");
}

———- Strings, Practice #6

void f(char* t[], int size) {
    int i, min, max;
    char *shortest, *longest;

    min = strlen( t[0] );
    max = strlen( t[0] );

    for(i = 0; i < size; i++) {
        if( strlen(t[i]) < min ) {
            min = strlen(t[i]);
            shortest = t[i];
        }
        if( strlen(t[i]) > max ) {
            max = strlen(t[i]);
            longest = t[i];
        }
    }

    t[0] = shortest;
    t[size-1] = longest;
}

———- Files, Practice #1

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

int main(void) {
    FILE* fp;
    char* filename = "payments.txt";
    char buffer[50];
    char *name, *amt, *del = " \n";
    int sum = 0;

    if( (fp = fopen(filename, "r")) == NULL ) {
        printf("unable to open %s\n", filename);
        exit(1);
    }

    while( fgets(buffer, sizeof(buffer), fp) != NULL ) {
        name = strtok(buffer, del);
        amt = strtok(NULL, del);
        printf("%s make a payment of $%s\n", name, amt);
        sum += atoi(amt);
    }

    fclose( fp );

    printf("total payments were %d\n", sum);
}

———- Files, Practice #2

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

int main(void) {
    FILE* inFile, *outFile;
    char* inName = "people.txt";
    char* outName = "smith.txt";
    char buffer[100];
    char *t1, *t2, *t3, *t4, *del = " \n";
    
    if( (inFile = fopen(inName, "r")) == NULL ) {
        printf("unable to open %s\n", inName);
        exit(1);
    }

    if( (outFile = fopen(outName, "w")) == NULL ) {
        printf("unable to open %s\n", outName);
        exit(1);
    }
    
    while( fgets(buffer, sizeof(buffer), inFile) != NULL ) {
        t1 = strtok(buffer, del);
        t2 = strtok(NULL, del);
        t3 = strtok(NULL, del);
        t4 = strtok(NULL, del);

        if( strcmp(t2, "Smith") == 0 )
            fprintf(outFile, "%s %s %s %s\n", t4, t3, t2, t1);
    }
    
    fclose( inFile );
    fclose( outFile );
}

———- Files, Practice #3

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

int main(void) {
    FILE* fp;
    char* filename = "names.txt";
    char buffer[20]; 
    char *name, *del = " \n";
    
    if( (fp = fopen(filename, "r")) == NULL ) {
        printf("unable to open %s\n", filename);
        exit(1);
    }   
    
    while( fgets(buffer, sizeof(buffer), fp) != NULL ) {
        name = strtok(buffer, del);
        
        if( 'A' <= name[0] && name[0] <= 'Z' )
            printf("%s\n", name);
    }

    fclose( fp );
}

———- Structures, Practice #1

The answer really depends on how detailed you want to be.

struct book {
    char title[100];
    int edition;
    char author1[100];
    char author2[100];
    char author3[100];
    int isbn;
} ;

———- Structures, Practice #2

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

struct collegeCourse {
    char dept[5];
    short course;
    short section;
    short enrollment;
};

int main(void) {
    struct collegeCourse d[] = { {"CSE", 1310, 1, 45},
                                 {"CSE", 1310, 2, 50},
                                 {"MATH", 1426, 1, 75},
                                 {"MATH", 3330, 2, 60},
                                 {"IE", 3301, 1, 40} };
    int i;
    
    for(i = 0; i < 5; i++) 
        printf("%s %d.%03d has %d students\n", 
                d[i].dept, d[i].course,
                d[i].section, d[i].enrollment);
}

———- Structures, Practice #3

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

struct collegeCourse {
    char dept[5];
    short course;
    short section;
    short enrollment;
};

int main(void) {
    FILE* fp;
    struct collegeCourse d[10];  /* assume not more than 10 courses */
    char buffer[100];
    char *dept, *del = ",\n";
    int i, counter = 0, course, section, enrollment;
    char* filename = "courses.csv";

    if( (fp = fopen(filename, "r")) == NULL ) {
        printf("unable to open %s\n", filename);
        exit(1);
    }

    while( fgets(buffer, sizeof(buffer), fp) != NULL) {
        strcpy(d[counter].dept, strtok(buffer, del));
        d[counter].course = atoi(strtok(NULL, del));
        d[counter].section = atoi(strtok(NULL, del));
        d[counter].enrollment = atoi(strtok(NULL, del));

        counter++;
    }

    fclose( fp );

    for(i = 0; i < counter; i++)
        printf("%s %d.%03d has %d students\n",
                d[i].dept, d[i].course, 
                d[i].section, d[i].enrollment);
}

———- Structures, Practice #4

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

struct person {
    char name[20];
    int age;
};

int main(void) {
    struct person d[3];
    char name[20];
    int i, age;

    for(i = 0; i < 3; i++) {
        printf("name %d? ", i+1);
        scanf("%s", name);
        strcpy(d[i].name, name);
        
        printf("age %d? ", i+1);
        scanf("%d", &age);
        d[i].age = age;
    }

    for(i = 0; i < 3; i++) 
        printf("%s is %d years old\n", d[i].name, d[i].age);
}

———- Structures, Practice #5

void addCars(struct car old[], int *oCount, struct car new[], int nCount) {
    int i, k, found = 0;
    
    /* for each new car, compare it to list of old cars */
    for(i = 0; i < nCount; i++) {
        for(k = 0; k < *oCount; k++) 
            if( strcmp(old[k].make, new[i].make) == 0 &&  
                strcmp(old[k].model, new[i].model) == 0 ) 
                found = 1;  /* found match, so don't add */

        if( !found ) {
                strcpy(old[*oCount].make, new[i].make);
                strcpy(old[*oCount].model, new[i].model);
                
                *oCount += 1;
        }   
    }
}

———- Structures, Practice #6

void caps(struct animal d[], int size) {
    int i;
    
    for(i = 0; i < size; i++) {
        d[i].name[0] -= 32;
        d[i].type[0] -= 32;
    }
}

———- DynamicMemory, Practice #1

#include <stdio.h>
#include <stdlib.h>
  
int main(void) {
     int i = 0, used, number;
     int* d = malloc(5 * sizeof(int));

     while(i < 5) {
         printf("enter integer (negative to stop): ");
         scanf("%d", &number);

         if(number >= 0)
             d[i] = number;
         else
             break;

         i++;
     }

     used = i;

     for(i = 0; i < used; i++)
         printf("%d  ", d[i]);

     printf("\n");

     free( d );
}

———- DynamicMemory, Practice #2

#include <stdio.h>
#include <stdlib.h>
  
int main(void) {
     int i, k, rows = 3, cols = 4;
     int** d = malloc(rows * sizeof(int*));

     for(i = 0; i < rows; i++)
         d[i] = malloc(cols * sizeof(int));
     
     for(i = 0; i < rows; i++)
         for(k = 0; k < cols; k++)
             d[i][k] = i+k;

     for(i = 0; i < rows; i++) {
         for(k = 0; k < cols; k++)
             printf("%2d ", d[i][k]);

         printf("\n");
    }

     for(i = 0; i < rows; i++) 
         free(d[i]);

     free( d );
}

———- DynamicMemory, Practice #3

#include <stdio.h>
#include <stdlib.h>
  
int main(void) {
     int i = 0, used, number, maxSize = 5;
     int* d = malloc(maxSize * sizeof(int));

     /* create infinite loop */
     while( 1 ) {
         printf("enter integer (negative to stop): ");
         scanf("%d", &number);

         if(number >= 0) {
             if(i == maxSize) { 
                 maxSize = 2*maxSize;
                 d = realloc(d, maxSize*sizeof(int));
                 printf("*** realocated to store %d ints\n", maxSize);
             }

             d[i] = number;
         }
         else
             break;

         i++;
     }

     used = i;

     for(i = 0; i < used; i++)
         printf("%d  ", d[i]);

     printf("\n");

     free( d );
}

———- DynamicMemory, Practice #4

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
  
int main(void) {
    FILE* fp;
    char* filename = "people.txt";
    char** lines;
    char buffer[100];
    int i, count = 0;

    if( (fp = fopen(filename, "r")) == NULL ) {
        printf("unable to open %s\n", filename);
        exit(1);
    }

    lines = malloc(50 * sizeof(char*));

    while( fgets(buffer, sizeof(buffer), fp) != NULL ) {
        lines[count] = malloc( strlen(buffer) + 1 );
        strcpy(lines[count], buffer);

        count++;
    }


    fclose( fp );

    for(i = count-1; i >= 0; i--)
       printf("%s", lines[i]);


    for(i = 0; i < count; i++)
        free(lines[i]);

    free(lines);
}

———- DynamicMemory, Practice #5

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

void changeArray(int **p, int size) {
    int i;

    free(*p);
    *p = malloc(size * sizeof(int));

    for(i = 0; i < size; i++)
        (*p)[i] = i+11;
}

void printArray(int d[], int size) {
    int i;

    for(i = 0; i < size; i++)
        printf("%d  ", d[i]);

    printf("\n");
}
  
int main(void) {
    int i, size = 5;
    int* d = malloc(size * sizeof(int));

    for(i = 0; i < size; i++)
        d[i] = i+1;

    printArray(d, size);

    changeArray(&d, size);
    printArray(d, size);

    free( d );
}

———- Recursion, Practice #1

int recSum(int n) {
    if(n == 0)
        return n;

    return n + recSum(n - 1);
}

int main(void) {
    int n = 10;

    printf("%d\n", recSum( n ));
}

———- Recursion, Practice #2

#include <stdio.h>

int binarySearch(int a[], int value, int low, int high) {
      int mid = (low + high) / 2;

      if(high < low)
          return -1;

      if(a[mid] > value)
          return binarySearch(a, value, low, mid-1);
      else if (a[mid] < value)
          return binarySearch(a, value, mid+1, high);
      else
          return mid;
}

printResults(int x[], int size, int value) {
    int index;

    index = binarySearch(x, value, 0, size-1);

    if(index >= 0)
        printf("%d has index %d\n", value, index);
    else
        printf("%d is not in the array\n", value);
}

int main(void) {
    int d[] = {1, 2, 6, 14, 21, 33, 59, 60, };
    int n = sizeof(d)/sizeof(d[0]);
    
    printResults(d, n, 2);
    printResults(d, n, 123);
    printResults(d, n, 60);
}

———- LinkedLists, Practice #1:

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

struct node {
    int value;
    struct node *next;
};

struct node* addNode(struct node *h, int n) {
    struct node *temp = malloc( sizeof(struct node) );

    temp->value = n;    
    temp->next = h;    

    return temp;
}

void printList(struct node* h) {
    while(h != NULL) {
        printf("%d  ", h->value);
        h = h->next;
    }

    printf("\n");
}

int findNum(struct node *h, int x) {
    int count = 0;

    while(h != NULL) {
        if(h->value == x)
            count++;

        h = h->next;
    }

    return count;
}

int main(void) {
    struct node *head = NULL;
    int d[] = {5, -8, 99, 7, 13, 99, 0, 123};
    int i, len = sizeof(d)/sizeof(d[0]);
    int x, y;

    for(i = 0; i < len; i++)
        head = addNode(head, d[i]);

    printList(head);    

    x = 20;
    y = findNum(head, x);
    printf("%d occurs %d times\n", x, y);
    
    x = 13;
    y = findNum(head, x);
    printf("%d occurs %d times\n", x, y);
    
    x = 99;
    y = findNum(head, x);
    printf("%d occurs %d times\n", x, y);
}

———- LinkedLists, Practice #2:

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

struct node {
    char name[20];
    struct node *next;
};

struct node* addNode(struct node *h, char n[]) {
    struct node *temp = malloc( sizeof(struct node) );

    strcpy(temp->name, n);    
    temp->next = h;    

    return temp;
}

void printList(struct node* h) {
    while(h != NULL) {
        printf("%s  ", h->name);
        h = h->next;
    }

    printf("\n");
}

int main(void) {
    struct node *head = NULL;
    FILE* fp;
    char* filename = "people.txt";
    char buffer[20];
    char *token, *del = "\n";

    fp = fopen(filename, "r");

    while( fgets(buffer, sizeof(buffer), fp) != NULL ) {
        token = strtok(buffer, del);  /* eliminate the newlines */
        head = addNode(head, token);
    }

    printList(head);
}

———- LinkedLists, Practice #3:

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

struct node {
    char name[20];
    struct node *next;
};

struct node* addNode(struct node *h, char n[]) {
    struct node *temp = malloc( sizeof(struct node) );

    strcpy(temp->name, n);    
    temp->next = h;    

    return temp;
}

void printList(struct node* h) {
    while(h != NULL) {
        printf("%s  ", h->name);
        h = h->next;
    }

    printf("\n");
}

int inList(struct node* h, char n[]) {
    while(h != NULL) {
        if( strcmp(h->name, n) == 0 )
            return 1;

        h = h->next;
    }

    return 0;
}

int main(void) {
    struct node *head = NULL;
    FILE* fp;
    char* filename = "people.txt";
    char buffer[20];
    char *token, *del = "\n";

    fp = fopen(filename, "r");

    while( fgets(buffer, sizeof(buffer), fp) != NULL ) {
        token = strtok(buffer, del);  /* eliminate the newlines */

        if( !inList(head, token) )
            head = addNode(head, token);
    }

    printList(head);
}

———- LinkedLists, Practice #4:

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

struct node {
    int value;
    struct node *next;
};

struct node* addNode(struct node *h, int n) {
    struct node *temp = malloc( sizeof(struct node) );

    temp->value = n;    
    temp->next = h;    

    return temp;
}

void printList(struct node* h) {
    while(h != NULL) {
        printf("%d  ", h->value);
        h = h->next;
    }

    printf("\n");
}

void mergeLists(struct node **f, struct node *s) {
    struct node *temp;
    int found;

    /* for each node value in s, search *f */
    while(s != NULL) {
        temp = *f;
        found = 0;

        while(temp != NULL) {
            if(s->value == temp->value)
                found = 1;

            temp = temp->next;
        }

        if( !found ) {
            temp = malloc( sizeof(struct node) );

            temp->value = s->value;
            temp->next = *f;  /* add at head of *f */

            (*f) = temp;
        }

        s = s->next;
    }
}

int main(void) {
    struct node *first = NULL, *second = NULL;
    int f[] = {1, 2, 3, 4, 5};
    int s[] = {99, 2, 13, 4, 7, 123};
    int i, fLen = 5, sLen = 6;

    for(i = 0; i < fLen; i++)
        first = addNode(first, f[i]);
    printList(first);

    for(i = 0; i < sLen; i++)
        second = addNode(second, s[i]);
    printList(second);

    mergeLists(&first, second);
    printList(first);
}

———- BinaryTrees, Practice #1:

void search(struct node* root, int x, int *p) { 
   /*
       root: address of current node
          x: number to search for
          p: address of counter
   */
   if(root == NULL)
       return;

   if(root->n == x)
       *p += 1;

   search(root->left, x, p);
   search(root->right, x, p);
}

———- HashTables, Practice #1:

int countValues(struct node* table[], char value[]) {
    int i, count = 0;
    struct node *temp;

    for(i = 0; i < SIZE; i++)
        if(table[i] != NULL)
            for(temp = table[i]; temp != NULL; temp = temp->next) {
                if( strcmp(temp->value, value) == 0 )
                    count++;
            }
    
    return count;
}

———- Graphs, Practice #1:

#include <stdio.h>

char maxSrc(int m[][4]);

int main(void) {
    int matrix[][4] = {{0, 0, 1, 0},
                       {1, 1, 1, 0},
                       {0, 0, 0, 1},
                       {0, 1, 1, 0}};

    printf("node %c has the most edges leaving it\n",
            maxSrc(matrix) );
}

char maxSrc(int m[][4]) {
    int i, k, max = 0, maxCount = 0, rowMax;

    for(i = 0; i < 4; i++)
    {
        rowMax = 0;
        for(k = 0; k < 4; k++)
            rowMax += m[i][k];

        if(rowMax > maxCount) {
            maxCount = rowMax;
            max = i;
        }
    }

    return (char) (max + 'A');
}

———- Graphs, Practice #2:

#define SIZE 8
#include <stdio.h>
#include <stdlib.h>

struct node {
    int index;
    struct node *next;
} ;

struct node * topSort(int d[][SIZE]);
int hasIncoming(int d[][SIZE], int col);
void enqueue(struct node **head, int index, int *queueLength);
struct node * dequeue(struct node * head, int *queueLength);

void printGraph(int d[][SIZE], char *label[]);
void printList(struct node *head, char *label[]);
void freeMemory(struct node *head);


int main(void) {
    char *label[] = {"CSE 1310", "CSE 1320", "CSE 1325", "CSE 2312", "CSE 2315", "CSE 2320", "CSE 3310", "MATH 1426"};
    /*  directed graph 10 20 25 12 15 20 10 26  */
    int dir[][SIZE] = {{0, 1, 0, 0, 1, 0, 0, 0},    /* CSE 1310  */
                       {0, 0, 1, 1, 0, 1, 0, 0},    /* CSE 1320  */
                       {0, 0, 0, 0, 0, 0, 1, 0},    /* CSE 1325  */
                       {0, 0, 0, 0, 0, 0, 0, 0},    /* CSE 2312  */
                       {0, 0, 0, 0, 0, 1, 1, 0},    /* CSE 2315  */
                       {0, 0, 0, 0, 0, 0, 0, 0},    /* CSE 2320  */
                       {0, 0, 0, 0, 0, 0, 0, 0},    /* CSE 3310  */
                       {0, 0, 0, 0, 1, 0, 0, 0}};   /* MATH 1426 */
    int i;
    struct node *L;
    
    printf("directed\n");
    printGraph(dir, label);

    printf("\ntopological sort\n");
    L = topSort(dir);
    printList( L, label );
    freeMemory( L );
}

void printList(struct node *head, char *label[]) {
    for( ; head != NULL; head = head->next) {
        printf("%s, ", label[ head->index ]);
    }
    printf("\n");
}

struct node * topSort(int d[][SIZE]) {
    int i, m, n, queueLengthL = 0, queueLengthS = 0;
    struct node *L = NULL, *S = NULL;

    /* find nodes without incoming edges */
    for(i = 0; i < SIZE; i++)
        if( !hasIncoming(d, i) )
            enqueue( &S, i, &queueLengthS );

    /* while S is non-empty */
    while( queueLengthS > 0 ) {
        n = S->index;
        S = dequeue( S, &queueLengthS );
        enqueue( &L, n, &queueLengthL );

        for (m = 0; m < SIZE; m++) {
            if(d[n][m] != 0) {
                d[n][m] = 0;

                /* if m has no other incoming edges */
                if( !hasIncoming(d, m) )
                    enqueue( &S, m, &queueLengthS );
            }
        }
    }

    return L;
}

int hasIncoming(int d[][SIZE], int c) {
    int r, incoming_edges = 0;
    for(r = 0; r < SIZE; r++)
        if( d[r][c] != 0 )
            incoming_edges = 1;

    return incoming_edges;
}

void printGraph(int d[][SIZE], char *label[]) {
    int i, k;

    for(i = 0; i < SIZE; i++) {
        printf("%9s: ", label[i]);
        for(k = 0; k < SIZE; k++)
            if(d[i][k] == 1)
                printf("%9s ", label[k]);

        printf("\n");
    }
}

void enqueue(struct node **head, int index, int *queueLength) {
    /*
        since queues will be short, don't keep track of tail
    */
    if( *queueLength == 0 ) {
        *head = malloc( sizeof(struct node) );
        (*head)->next = NULL;
        (*head)->index = index;
    } else {
        struct node *tail;
        struct node *temp = malloc( sizeof(struct node) );
        temp->next = NULL;
        temp->index = index;

        /*  find end of queue  */
        for(tail = *head ; 
            tail->next != NULL; 
            tail = tail->next )
            ;

        tail->next = temp;
    }

    *queueLength += 1;
}

struct node * dequeue(struct node * head, int *queueLength){
    struct node *temp = head->next;

    free( head );
    *queueLength -= 1;

    return temp;
}

void freeMemory(struct node *head) {
    struct node *temp;

    for( ; head != NULL; head = temp->next) {
        temp = head; 
        free( head );
    }
}
Comments are closed.