SHANYIN'S SPACE

Logo

Blog | Notebooks | Sharing | Everything

View My GitHub Profile

C Lang Supplement Knowledge (Review)

C Lang

printf and scanf

Pre-definitions

See ‘Pre-processor’ for more

Data Types

int

sizeof(char) = 1 (byte = 8 bit (0 / 1))

char <= short <= int (~4) <= long

ASCII

(and Extended ASCII): 48(0) 49(1) … 65(A) … 97(a) … 127(DEL)

float

float (~4; >=6 decimal number) <= double (~8; >=10) <= long double (>=10)

Sign + Exp + matissa

Conversion / Promotion

char -> short -> int -> long -> float -> double

Expressions

Operations

Priority

  1. ()
  2. ++ / -- / + / - (signs) / (types)
  3. * / / / %
  4. + / -
  5. < / <= / > / >=
  6. == / !=
  7. &&
  8. ||
  9. ?=
  10. = / += / …

if & Switch

Example: Calculator

#include <stdio.h>

int main() 
{
    char op;
    int num1, num2, res;
    scanf("%d %c %d", &num1, &op, &num2);
    switch(op) {
        case '+': res = num1 + num2; break;
        case '-': res = num1 - num2; break;
        case '*': res = num1 * num2; break;
        case '/': res = num1 / num2; break;
        default: printf("Error: unknown operation.\n"); return 1;
    }
    printf(....);
    return 0;
}

Bool

Use #include<stdbool.h> to apply bool type var. (logic)

Usually don’t mix with other types of data.

#include <stdbool.h>

int main(){
    int n;
	scanf("%d", &n);
    bool notZero = n;	// n not zero => true; n is zero => false (int->bool)
    if(notZero) {
        printf("n is non-zero!\n");
    }
}

!5: 0; !!5: 1; 5 && 0: 0; 5 && 'A': 1; 5 || -5: 1; 5 || 0: 1

Loops

Example: Factorial loop

#include<stdio.h>

int main() 
{
    int n;
    if (scanf("%d", &n) < 1)
        printf("Input error.\n")
        return 1;
    if (n > MAX4FACT)
        printf("Too big a number.\n")
        return 2;
    int i = 2;
    int factorial = 1; // at most `12!`
    
    /* while loop
    while (i <= n) {
        factorial *= 1;	 // or just `factorial *= i++`
        i++;	// or `++i`
    }  */
    
    // for loop
    for (; i <= n; i++) {
        factorial *= 1;
    }
    
    printf("%d! = %d", n, factorial);
    return 0;
}

Example: Greatest Common Divisor

#include <stdio.h>

int main() {
    int m, n;
    scan("%d%d", &m, &n);
    if(m == 0 && n == 0)	printf("Input error.\n");
    int m_orig = m, n_orig = n;
    if(m < 0)	m = -m;
    if(n < 0)	n = -n;
    while (n != 0) {
        int temp = m % n;
        m = n;
        n = temp;
    }
    printf("The gcd of %d and %d is %d", m_orig, n_orig, m);
    return 0;        
}

Example: Check prime

#include<stdio.h>
#include<math.h>

int main() 
{
    int n;
    scanf("%d", &n);
    int n_orig = n;
    if (n < 0)	n = -n;
    int is_prime = 1;
    if (n < 2 || n != 2 && n % 2 == 0)
        is_prime = 0;
    else {
        for (int i = 3; i < sqrt(n) + 0.5; i += 2) {
            if (n % i == 0) {
                is_prime = 0;
                break;                    
            }
        }
    }
    printf("%d is %sa prime\n", n_orig, is_prime ? "": "not ");
    // if is a prime => %s = ""; if not %s = "not " 
    return 0;
}

Array

1D Array

int grades[800]: Array with 800 elements: grades[0] ~ grades[799]

The length should be an integer, it can’t be a var.

Initialization
Example: Sieve
#include <stdio.h>
#include <math.h>

#define N 37	// output all prime numbers under 37

int main() {
    int sqrt_N = sqrt(N) + 0.5;
    bool prime[N+1] = {false, false};	// 0 and 1 are not prime
    for (int i = 2; i < N+1; ++i) {
         prime[i] = true;
    }
    for (int p = 2; p <= sqrt_N; ++p) {
        if (prime[p]) {
            for (int i = p; i*p <= N; ++i) {
                prime[i*p] = false;
            }
        }
    }
    printf("The prime numbers below %d are \n", N);
    for (int i = 2; i <= N; i++) {
        if (prime[i]) {
            printf("%d ", i);
        }
    }
}

2D Array

Initialization
Example: Blur a Picture

Pixel -> RGB Values

Blur: Average color with neighbors

#include <stdio.h>

#define N 10
#define M 10
#define FALSE 0
#define TRUE 1

int inBound(int i, int j);
int meanAroundPixel(int picture[N][M], int i, int j);
void copy2dArray(int to[N][M], int from[N][M]);			// in the declaration of high dim arrays
void bluePicture(int picture[N][M]);					// from the 2nd dim on, the size should be spec.

int main()
{
    ...
    int picture [N][M] = {...};
    blurPicture(picture);
    ...
}

int inBound(int i, int j) 
{	// in the allowed range
    return (	j >= 0 && j < N 
             && j >= 0 && j < M);
}

int meanAroundPixel(int picture[N][M], int ii, int jj)
{
    int di, dj, sum = 0, neighbours = 0;
    for (di = -1; di <= 1; ++di)
        for (dj = -1; dj <= 1; ++dj)
            if (inBound(ii+di, jj+dj)) {
                sum += picture[ii+di][jj+dj];
                neighbours++;
            }
    return (int)((double)sum / neighbours + 0.5);
}

void copy2dArray(int to[][M], int from[][M])
{
    int i, j;
    for (i = 0; i < N; ++i)
        for (j = 0; j < M; ++j)
            to[i][j] = from[i][j];
    return;
}

void blurPicture(int picture[][M])
{
    int ii, jj;
    int blurred[N][M];
    for (ii = 0; ii < N; ++ii)
        for (jj = 0; jj < M; ++jj)
            blurred[ii][jj] = meanAroundPixel(picture, ii, jj);
    copy2dArray(picture, blurred);
    return;
}

Function

return-type fcn-name(par-list)
{
    var. def.;
    statements;
    return sta;
}

Call by value (the var. in main and in function is not the same)

Variable

Types

Stack

Last in first out (LIFO) - Usually stores local var.

Attention that due to the existance of the stacks, the functions are called by value, the value cannot pass from the smaller scope to the larger scope.

Pointer

Example: Swap

Use *a to point to the var. a’s position

void swap(int* a, int* b) {	// actually swap the 2 addresses
    int temp = *a;			// temp now points to the position where stores a
    *a = *b;				// &a (address) -> a (var/value); &b -> b
    *b = temp;
    return;
}

int main()
{
    int a = 3, b = 5;
    swap(&a, &b);	// extract the address of a and b
    printf("a = %d, b = %d", a, b);
    return 0;
}

Definition

type *: pointer to the type

(*p: p is a pointer pointing to sth; &a: a is a variable and this is its address; p = &a:OK; y = *p: y is now the value of a; *p = 7: OK, a = 7)

char c;
char *cp1, *cp2 = &c;

Return Multiple

Void cannot return value, but if use pointers, it can be used to “return” multiple values

Generic Pointer: void*

int a = 5, b, *p1;
char c = 'x';
void *p2, *p3 = &c;		// generic, can be used as a pointer of any type of data 
p1 = &a; 
p2 = p1;
b = *p1 + *(int*)p2;	// to use an undefined pointer, still need to add the type

// sizeof(*p1) = sizeof(int)
// sizeof(*p2) not defined

Operations

int *p, *q;
p = 300; q = 400;
// p + 1 == p++ == 304; p + 2 == 308 (sizeof(int) = 4); q - p == 25;
// (char*)p + 2 == 302; (char*)q - (char*)p == 100;
// q - (char*)p: invalid

Array with Pointer

Actually the name of the array is the pointer itself

For an array double s[3];

Arrays occupy memory at definition, pointers don’t (unless they are actually def. to point to sth).

So a pointer cannot be given a value (or given a value as an array elem)

Dynamic Allocation

double *p;	// still not know what is the size of p
int n;
...
p = (double*)malloc(n * sizeof(double));	// p points to double, so `(double*)` (same type) & `sizeof(double)` here
// the memory here is [n x sizeof(double)]
if (p == NULL)
    return 1;
...
for (i = 0; i < n; i++)
    scanf("%lf", &p[i]);
...
free (p);	// Release memory

String

chars + \0 (ASCII: 0)

Definition

The string length: No need to count \0; if as an array: Need to count \0

Use in checking:

Operations

Requires string.h

Complex Application: Sorting

Max-Sort
// Find the index of the maximal elem
int index_of_max(int a[], int n)
{
    int i, i_max = 0;
    for (i = 1; i < n; ++i)
        if (a[i] > a[i_max])
            i_max = i;
    return i_max;
}

void max_sort(int a[], int n)
{
    int length;
    for (length = n; length > 1; --length){
        int i_max = index_of_max(a, length);
        swap(&a[length - 1], &a[i_max]);
    }
    return;
}
Bubble Sort
int bubble(int a[], int n)
{
    int i, swapped = 0;
    for (i = 1; i < n; ++i)
        if (a[i-1] > a[i]){
            swap(&a[i], &a[i-1]);
            swapped = 1;
        }
    return swapped;
}

void bubble_sort(int a[], int n)
{
    int not_sorted = 1;
    while ((n > 1) && not_sorted)
        not_sorted = bubble(a, n--);
}
Merge

$\mathcal{O}(na + nb)$

void merge(int a[], int na, int b[], int nb, int c[])
{
    int ia, ib, ic;
    for (ia = ib = ic = 0; (ia < na) && (ib < nb); ic++) {
        if (a[ia] < b[ib]) {
            c[ic] = a[ia];
            ia++;
        }
        else {
            c[ic] = b[ib];
            ib++;
        }
    }
    for (; ia < na; ia++, ic++) c[ic] = a[ia];
    for (; ib < nb; ib++, ic++) c[ic] = b[ib];
}

Complexitiy

Worst case

Recursion

“n” <- “n-1”

Call the function in itself. Easier to use when do some reversely printing work

Example: Factorial

int factorial (int n)
{
    if (n == 0) return 1;	// halting (stop) condition (0! == 1) Here return and have jumped out of the `if`
    return n * factorial(n-1); 	// recursive step
}

int factorial (int n)	// wrapper fcn
{
    if (n < 0 || n > MAX)	return 0;
    return rec_fac(n);
}
int rec_fac (int n)
{
    if (n <= 1)	return 1;
    return n * rec_fac(n-1);
}

int binSearch(int a[], int n, int val)
{
    if (n == 1)	return a[0] == val? 0: NOT_FOUND;	// hauting cond
    int mid = n / 2;
    if (a[mid] < val) {
        int result = binSearch (a+mid+1, n-mid-1, val);
        return result == NOT_FOUND? NOT_FOUND: result + mid + 1;
    }
    return binSearch(a, mid+1, val);
}

#### Example: Fibonacci

0 1 1 2 3 5 8 13 21 34 55

int Fibo(int n)
{
    static int f[N] = {0, 1};	// use static to avoid wrong additions
    if (n < 0 || n >= N)	return -1;
    return recFibo(n, f);
}

int recFibo (int n, int f[])
{
    if (n > 2)	return n;
    if (f[n] != 0)	return f[n];
    return f[n] = recFibo(n-1, f) + recFibo(n-2, f);
}

Enumerated Types (enum) (C99)

Available in C99

Defines a new type and a set of named values

The names are more important than its given value since the values should only be integers.

// def
enum Gender {MALE, FEMALE};	// MALE -> 0; FEMALE -> 1
enum Month {JAN, FEB, MAR, /* ... */, DEC, MONTH_NUM};	// DEC -> 11; MONTH_NUM -> 12 (Useful trick to count)
enum Season {SUMMER = 1, FALL, WINTER = 8, SPRING};	// FALL -> 2; SPRING -> 9

// usage
enum Gender gender = MALE;
enum Season seasons[MONTH_NUM];	// number of elem in the array = 12
seasons[JAN] = WINTER;

enum Month next_month(enum Month current) {
    if (current == DEC)
        return JAN;
    return (enum Month) (current + 1);
}

Bool

Actually bool can be regarded as an enum type: enum bool {FALSE, TRUE};

Const Keyword (C99)

const type identifier = expression;	// cannot change after init.

const double PI = 3.141592654;
const double EPSILON = 1e-6;	// usually def as UPPERCASE -> divide from var.
double rad;

if (PI * rad * rad < EPSILON) {
    printf("circle is too small \n")
}

Inline Functions (C99)

A normal function call has a small overhead (managing stack, copying parameters values, etc.). It can become large if function is critical

To reduce the overhead, usually write the called function inside the loop other than call one outside. (not that clean)

-> Inline functions: Ask the compiler to replace each call to this function with efficient equivalent code that does not perform the call

inline int max(int a, int b){	// use `inline` before the type to indicate 
    return a > b ? a : b;		// return the larger
}

int a, b, c, d;
...					// when `max()` is inlined, the complier will compile the code as:
int x = max(a, b);	// int x = a > b ? a : b;
int y = max(c, d);	// int x = c > d ? c : d;
int z = max(3, 4);	// int z = 4; (for const, just compute intermediately)

Properties:

Pre-processor

C_Preprocessor

Pre-process Usage

User Headers

If there are some very complex functions needed to be defined. create a new header file to contain them.

// `functions.h` (only declarations, no details)
int function1(int n);
int function2(int n);

// `functions.c` (details of the functions)
int function1(int n) {
    ...
}

int function2(int n) {
    ...
}

// `main.c`
#include "functions.h"	// ok to just include the .h file, the .c file will automatically add (implicitly)

int main(){
    printf("%d\n", function1(5));
    return 0;
}

Use gcc -E main.c (only preprocess the code) => The code that actually generate for compiling will be (.c file will not show up but linked to be used)

int function1(int n);	// only show up the declarations
int function2(int n);

int main(){
    printf("%d\n", function1(5));
    return 0;
}

Macros

Exactly, macros are replacements

The preprocessor doesn’t know c codes. The job is replacing the texts exactly as it is directed

For example: if #define return :), for return 0; the result will be :) 0; [NOT compile]

Problems

If cannot be solved in macros, try inline functions (such as sqr(++i) called by value => OK)

For complex ones try to use inline functions, for type not important value macro is sufficient.

Advanced Techniques
Conditionals

Often be used in the macro part

Predefined Macros
Assert Macro
#ifdef NDEBUG
#define assert(x) ((void)0)		// call the assert function, if no debug nothing will be done
#else /* debugging enabled */
void _assert (const char* condition, const char* filenamem, int line);	// helper func
#define assert(e) ((e) ? (void)0 : _assert(#e, __FILE__, __LINE__))		// error @ which file and which line
	// `_assert` just prints an error msg and calls abort()
#endif	/* NDEBUG */

Possible Result: Assertion failed: arr.a != NULL, file main.c, line 23

File Inclusions

Most declarations must not appear more than once (must protect against including a file more than once)

DEMO

Type Definition

Declares a new type name. Commonly appear in a header file to share across code files. (if too many new types, a types.h could be useful)

typedef typename name-def (actually add a nickname of a type)

Structures (struct)

Basis for defining new types in C that can represent complicated objects

Each field has a type and a name

struct name { field-list };

Demo: Complex num

Usage:

Pointers (Advanced)

void* Pointers

void* is used as a generic pointer type. (we don’t know its exact type but want a pointer)

It cannot be dereferenced (i.e. with * or []) and cannot be used with pointer arithmetic, unless it is cast to its true type.

DEMO

int i = 1;
double d = 1.0;

void* ptr0 = &i;	// i and d's address (i's is int and d's is double)
void* ptr1 = &d;	// these two pointers are valid but without types

double e = *ptr0 + *ptr1;	// invalid (compilation error), cannot fetch result with *
e = *(int*)ptr0 + *(double*)ptr1;	// valid, because have spec. the types

void* pointer can be used for generic low-level memory operations (avoid such code whenever possible)

(Type char is guaranteed to occupy exactly 1 byte) -> casting a void* to char* allows accessing individual bytes in the memory

void swap (void* p, void* q, size_t nbytes) {	/* size_t is typedef from <stdlib.h> => counting bytes usually (unsigned) int */
    for (int i = 0; i < nbytes; i++) {
        char tmp = ((char*)p)[i];
        ((char*)p)[i] = ((char*)q)[i];
        ((char*)q)[i] = tmp;            
    }
}

double d1, d2;
int a[5], b[10];
//...
swap(&d1, &d2, sizeof(double));	// swap the storage address of d1 and d2
swap(a, b, 5*sizeof(int));		// swap the first 5 elems

Const and Pointers

Pointers to Functions

The type of a function => function’s signature

double sin(double);
double cos(double);
double fabs(double);	// in <math.h>, all these func have the same type

double (*fptr)(double);
// fptr can point to any func that takes one double and returns a double (in / output types)
fptr = cos;		// point fptr to the code of func `cos()`
fptr = printf;	// NOT compile => wrong type

DEMO

double derivative(double (*func)(double), double x) {	// deriv at x point
    const double h = 1e-6;
    double diff = func(x+h) - func(x-h);
    return diff/(2*h);	// at small h -> tends to be the derivative
}

double square(double x) {	// also double (*func)(double)	(same type)
    return x*x;
}

void compute() {	
    printf("%lf\n", derivative(square, 1));		// 2.000	x^2 derivative at 1.0 
    printf("%lf\n", derivative(sin, 0));		// 1.000
    printf("%lf\n", derivative(cos, PI/2));		// -1.000
}

Dynamic Memory Allocation (Advanced)

Predifined std func: (<stdlib.h>)

void* malloc (size_t num_bytes);
void* calloc (size_t num_elem, size_t elem_size);	// Contiguous allocation. Only function that zeros the allocated bytes
void* realloc (void* old_ptr, size_t new_size);		// Reallocations

void free (void* ptr);

Memory Management

image-20211108172732061

C99 added variable-length arrays. However not good: (not intro to C++)

Stack size - Small; Heap - Larger => Stack overflow can occur, which is unrecoverable error