Basic Linux `tar` usage

tar -xvf xxx.tar unzip
tar -cf xxx.tar ... xxx.c zip

basic data types

Integer: int
Character: char
Valueless type: void
Fractional numbers: Single
precision: float
Double precision: double
Various types variations:
char: signed char, unsigned char
int: short int, signed short int, unsigned short int, signed int, unsigned int, long int, signed long int, unsigned long int, long long int, signed long long int, unsigned long long int
double: long double

Basic number types

float: 7 digits of precision, from 1 10^-38 to 3 10^38
double: 13 digits of precision, from 2 10 ^-308 to 1 10^308

Characters

Characters are enclosed in single quotes,e.g.char a=’a’;
Character are encoded using the American Standard Codes for Information Interchange(ASCII)
C do not have a string type, instead strings are viewed as arrays of characters(explanation later)
Strings are enclosed in double quotes

Arithmetic operator

+,-, *, /
except %, all arithmetic operator acceptes floating number!
Difference between i += j; and i =+ j;?
first == i = i + j; second == i = j;

logic statement

if…else

if(expression){ 
statements 
} 
elseif (expresssion2){
statements}  
else{ 
 }

switch

switch (variable) { 
case label1: statement1 // use break to skip to end 4 
case label2: statemment2; 
			break; 
default: statement3  
}

loop

for

1
2
3

for(init;test;step){  
statements; 
}

while

1
2
3

while (expression){
statements
}

do-while

1
2
3

do {
statements
} while(expression);

do will execute the statements at least once.
break, continue are also useful

`getchar()` and `putchar`

Character specific I/O
getchar(): reads one character (in the input zone) and return this character
putchar(cha): prints one character cha

conditional operator

The only ternary operator in C: condition ? expression1 : expression2

array

is series of values following the same data type, and stored sequentially
In C an array is defined by three parameters:

The data type of its elements
A name
A size, i.e. the number of elements compositing it
Array index starts from 0!!!
sizeof can be used to calculate the size of an array by byte.

multidimensional arrays

Initializing: int m[5][9] = {{1,1,1,1,1}, {1,1,1,1,1}};
Not large enough to fill in the array, remaining will be zero
Designated initializers: double indent[2][2] = {[0][0]= 1.0, [1][1]= 1.0};
row-major order to store element in C
nested for loops for accessing

char array

size of it is actual size *4(4 bytes per char)
example:

#include <stdio.h> 
int main(int argc, char const »argv[]) 
{ 
int x[12]; 
printf("$zu\n", sizeof(x)); // 48 
printf("$zu\n!", sizeof(int)); //4 bytes 
printf("$zu\n", sizeof(x)/sizeof(int)); 
return 0;
}

another example:

#include <stdio.h> 
#include <string.h> //Provides strlen() protetype 
#define PRAISE "You are doing great!" 

int main(int argc, char const ::argv[]) 
{ 
	char fName[40]; 
	char IName[40]; 
	char name[40]; 
	printf("What is your name? "); 
	scanf("%s, %s", fName, IName); 
	printf("Hello, %s %s. %s\n",fName, IName, PRAISE ); 
	printf("Your name has %zd letters occupies %zd memory 
	", strlen(name), 
	sizeof name); 
	return 0; 
}

function

function prototype
function calling

function definition
example:

1
2
3

double average(double a, double b){ 
	return (a+b)/2; 
}

When a one-dimensional array is used a function parameter, the length of the array needs to be specified.

int sum_array(int a[], int n){ 
int i, sum = 0; 
for(i = 0; 1 <n; i++) 
	sum += a[i]; 
return sum; 
}

Notice:

sizeof operator no longer gives the right answer: 必须在数组定义处的函数才能用sizeof!
The change to the element of the array within a function is reflected in the corresponding arugment.

function prototype

Definition before calling. Or using prototypes
Function prototypes provides the compiler with a brief glimpse of the function.
return-type function-name (parameters);
function prototype can be placed within main(), as long as it is declared before usage. (But not recommended)
variable name is not a must in function prototyping (dummy name)

recursion

like what mentioned in MATLAB

pointer

Pointer:

Something that directs, indicates, or points
Low level but powerful facility available in
C Pointer vs. variable:
Variable: area of the memory that has been given a name
Pointer: variable that stores the address of another variable

declaration

Defining a pointer: type * variable;
Handling pointers:
The address of a variable x is &x
The value stored at address y is *y
The operator “*” is called dereferencing operator
example:

intx =1, y =2, z[10]; 
int *ip; 

ip = &x; 
y = *ip; 
xip = 0; 
ip = &z[0]; 

//Other pointer arithmatic 
sip += 1; 
t++xip; 
(«ip)++; //otherwise, the expression would increment ip instead of what it points to

pointers and array

Array name is also the address of the first element of the array.
name == &name[0] returns true!
example:

#include <stdio.h> 
#define SIZE 4 

int main(void){ 
	int dates[SIZE]; 
	int * pti; 
	pti = dates; 
	double bills[SIZE]; 
	double ptf = bills; 
	
	printf("S23s %15s\n", "int", "double"); 
	for (int i = 0; i < SIZE; i++) 
	{ 
		printf("Pointers + %d: %10p %10p \n",i, ptiti, ptf+i); 
	} 
	//adding one to the pointer moves to the next item of that type directly after it in memory 
}

Pointer notation and array notation are the same: date[i] is the same as *(date+i)

pointer and function

#include <stdio.h> 
void swap(int, int); 
int main(void) 
{ 
inta=2,b=5; 
swap(a,b); 

printf("Address of a: %p, 
value of a:%d\n", &a, a); 

printf("Address of b: %p, 
value of b:%d\n", &b, b); 

return 0; 
} 
void swap(int a, int b) {
	int temp = a; a = b;  b = temp;
	printf("Address of a in swap: %p, value of a in swap :%d\n", &a, a); 
	printf("Address of b in swap: %p, value of b in swap :%d\n", &b, b);}
}

we introduced pointer as an arguments.
Pointer can also serve as the return value

limitation of C

No limit on the number of input
Only one output
Output cannot be an array

Dynamic memory allocation

Functions to manage memory:

Allocate n bytes of memory, and get a pointer on the first chunk: malloc(n)
Allocate n blocks of size s each, set the memory to 0, and get a pointer on the first chunk: calloc(n,s)// e.g., s->sizeof(int)
Adjust the size of the memory block pointed to by ptr to s bytes, and get a pointer on the first chunk: realloc(ptr,s)
Frees the memory space pointed to by ptr: free(ptr)
Variable Length Array after C99, Array size can be determined during the runing of a program
But still, malloc and pointer are the fundamental tools to achieve complex data structures

character strings

a char array terminated with a null character '\0'， cannot be changed!!!
string.h can be used for a char array

strcpy : The function takes two arguments: a destination buffer where the copied string will be stored, and a source string that will be copied. The function copies the entire source string, including the null terminator, into the destination buffer.
- char* strcpy(char* destination, const char* source);
strcat: accepts two pointer variable as parameters(say dest, src) and, appends the string pointed to by src to the end of the string pointed to by dest.
- char *strcat(char *dest_str, const char *src_str)
strcmp: This function takes two strings (array of characters) as arguments, compares these two strings lexicographically, and then returns 0,1, or -1 as the result.
- strcmp(_first_str_, _second_str_ );

struct

Structures: better way to represent data with hidden relationship

struct { 
	int id; 
	char name[NAME_LEN +1]; 
	int remaining_num; 
} bookl={l,"C Primer Plus", 10}, 
book2={2,"C Modern Approach", 
10};

accessing field

1
2
3

printf("Book ID is %d \n",bookl.id); 
bookl.remaining_num--; 
scanf("%d", &bookl.remaining_num);

Naming a structure for reusability

wrong def:

struct book { 
int id; 
char name[NAME_LEN +1]; 
int remaining_num; 
};
struct book bookl1, book2; // Cannot omit struct

good example:

typedef struct { 
	int id; 
	char name[NAME_LEN +1]; 
	int remaining_num; 
} Book; 
Book bookl, book2;

pointer to a struct

Why we need pointers to the struct?

Easier to manipulate
Passing as input argument

Complex data structures

int main(void){ 
	struct book book[2] = { 
		{{"Joanne", "Rowling"}, "Harry Potter", 50.0 
		 }, 
		{ {"Cixin", "Liu "},"The Three Body Problem" , 30.0 
		}
	};
	struct book * ptrBook; 
	ptrBook = &book[0]; 
	printf("ptr->price: %f, lastName%s", ptr—>price, ptr—->handle.lastName);
	return 0; 
}

adding `malloc`

int main(void){ 
	int registerNum; 
	struct book * books; //pointer to a structure 
	printf("How many books you wanna register\n"); 
	scanf("%d", &registerNum); 
	books = (struct book *) malloc(registerNum * sizeof(struct book)); 
	return 0; 
}

Advanced Pointer & file IO

advanced use of pointer

telling the functions about the structures:

just pass over the address of the function

save more space than either passing structure members or structures!
example:

#include <stdio.h> 

#define NAME_LENGTH 50 

struct patient{ 
	char name[NAME_LENGTH]; 
	double weight; 
	double height; 
};
double calculate_BMlI(const struct patient «); 

int main(void) 
{ 
	struct patient patient! = { 
	"Alpha", 70, 180 
	};
	printf("This patient’s BMI is %f", calculate_BMI(&patient1)); 
	return 0; 
} 

double calculate_BMI(const struct patient « patient_id) 
{ 
	return(patient_id—>weight/(patient_id—>height « patient_id—>height)); 
}

linked list

why linked list instead of the array

Array supports random access but insertion and deletion takes more time. Array are of fixed size.

implementation

declaration

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

initialization

struct node *first = NULL;

node creation

Assigning memory to the node
Storing value into the field;

Inserting node into a list

struct node *new_node; 
new_node = (struct node «)malloc(sizeof(struct node)); 
(new_node).value = 10;// Or rather 
new_node—>value = 10;

insert at the beginning

struct node *add_to_list(struct node «list, int n) 
{ 
	struct node *new_node; 
	new_node = malloc(sizeof(struct node)); 
	if (new_node == NULL) 
	{ 
		printf("Failed to allocate mem"); 
		exit(EXIT_FAILURE); 
	} 
	new_node-—>value = n; 
	new_node—>next = list; 
	return new_node;
}

search

struct node *search_list(struct node *list, 
int n) {
	for (; list!= NULL && list->value !=n; list = list->next);
	return list;
}

deletion

struct node *delete_from_list(struct node *list, int n) 
{ 
	struct node *cur, *prev; 	
	for (cur = list, prey = NULL; cur != NULL && cur—>value != n; prev = cur, cur = cur—>next) 
	
	if (cur == NULL) 
	return list;// n was not found 
	
	if (prev == NULL) 
	list = list—>next; // n is in the first 
	node 
	
	else 
	prev—>next = cur—>next; // n is in 
	middle of list 
	
	free(cur); 
	
	return list;
}

double pointers

arrays of strings

charJICSProfs[][11]={"YifeiZhu","PaulWeng","YutongBan","Yibo Pi"};

its principle: double pointers

A pointer to a pointer is a form of multiple indirection. A pointer that is a pointer to a pointer must be defined by introducing additional asterisk in front of its name.
The basis of 2D arrays!
example:

#include <stdio.h> //doublePtrSimple.c 
int main(int argc, char const »argv[]) 
{ 
	int var; 
	int »ptr; 
	int **pptr; 
	var = 3000; 
	ptr = &var; /* take the address of var */ 
	pptr = &ptr; 
	printf("Value of var = %d, address of var = %p\n", var, &var); 
	printf("Value available at »ptr = %d, value of ptr = %p, address of ptr = %p \n", »ptr, ptr, &ptr);
	printf("Valueavailableat **pptr=%d,valueof *pptr=%p,valueofpptr=%p,addressofpptr=%p\n",**pptr,*pptr,pptr ,&pptr);
}

If we want to manipulate or dereference to any of its levels, we have to use Asterisk ( * ) operator the number of times down the level we want to go.

Why we need double pointers

main function parameter
used as function arguments to manipulate the address stored in the local pointer (demo)
dynamic memory allocation of multidimensional arrays

used in data structures to directly manipulate the address of the nodes without copying.
example: OPTIMIZATION for add_to_list:
Suppose we want to assign new_node to list, instead of returning new_node

void add_to_list(struct node **list, 
int n) 
{ 
		struct node *new_node; 
		new_node = malloc(sizeof(struct node)); 
		if (new_node == NULL) 
		{ 
			printf("Failed to allocate mem"); 
			exit(EXIT_FAILURE); 
		} 
		new_node—>value = n; 
		new_node—>next = *list; 
		*list = new_node;
	   }

algs (Algorithms)

Most common types of algorithms:

Brute force: often obvious, rarely best
Greedy: most common used heuristic
Divide and conquer: often recursive
Dynamic programming: memorization
Search and enumeration: model problem using a graph
Randomized algorithms: feature random choices
Complexity reduction: rewrite a problem into an easier one

complexity

time&space complexity

time complexity

Approximate description of the relationship between running time and problem size

search

linear search

as mentioned as the name

Binary search

example:

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 
#define SIZE 200 
int main () 
{ 
	int i, n, mid; 
	int k=0, low=0, high=SIZE-1; 
	int *data = malloc(SIZE*sizeof(int)); 
	srand(time(NULL)); 
	for(i=0;i<SIZE;i++) 
		*(data+i)=2*i; 
	n=rand() % *(data+i—1); 
	while(high >= low) 
	{ 
		mid=(low + high)/2; 
	}
	if(n < *(data+mid)) 
		high = mid — 1; 
	else if(n> *(data+mid)) 
		low = mid + 1;
	else
		return 0;
}

sorting

selection sort

Sorts an array by repeately finding the smallest element
Maintain a sorted array

Maintain an unsorted one
example:

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 
#define SIZE 200 
#define MAX 1000 
int main () { 
	int data[SIZE]; 
	srand(time(NULL)); 
	for(int i=0; 1<SIZE; i++) data[i]=randQ%MAX; 
	for(int i=0; 1<SIZE; i++) { 
		int t, min_idx =1; 
	for(int j=1; j<SIZE; j++) {
		if(data[min_idx]>data|[j]) 
			min_idx =j; 
		t = data[i]; 
		data[i] = data[min_idx]; 
		data[min_idx] = t; 
	} 
	printf("Sorted array: "); 
	for(int i=0; i<SIZE; i++) printf("sd_ ",data[i]);
	return 0;
}

merge sort(O(n^2))

![[Pasted image 20240711212642.png]]

I/O

standard I/O

stream

a a abstract, high-level concept representing a communication channel to a file, device, or process

single character I/O

getchar() and putchar()
the end of the file:
#define EOF -1 in stdio.h

file I/O

open

FILE *fopen(const char *path, const char *mode)

mode: one of the r, r+, w, w+, a, a+
NULL: error

close

int fclose(FILE *fp)

return 0 as success

stream

standard output: FILE *stdout
standard input FILE * stdin
standard error output: FILE * stderr

reading & writing

writing: int fprintf(FILE *stream, const char *format, ...);
reading: int scanf(FILE *stream, const char *format, ...);
read size - 1 characters: char _fgets(char *s, int size, FILE *stream)
write characters to a stream: char *fputs(char *s, FILE *stream)

other head files

`string.h`

length: strlen(const char *s)
copy a string: char *strcpy(char *dest, const char *src)
Copy at most n bytes of src: char *strncpy(char *dest, const char *src, size_t n)
Compare two strings: int strcmp(const char *s1, const char *s2) return value is < 0 0 > 0, if s1 < s2 s1 = s2 s1 > s2
Compare the first n bytes of two strings: int strncmp(const char *s1, const char *s2, size_t n);
Locate a character is a string: `char *strchr(const char *s, int c);

`time.h`

Getting time:time_t time(time_t *t);

calculating the time difference: double difftime(time_t time1, time_t time0);

`ctype.h`

various types of C:
![[Pasted image 20240718165252.png]]

`math.h`

![[Pasted image 20240718165316.png]]

`stdlib.h`

![[Pasted image 20240718165337.png]]

`getopt()`

getopt(int argc, char * const argv[], const char *optstring)：解析命令行参数。

argc 表示参数个数
argv 表示参数列表
optstring 表示选项字符串，选项字符串中的字母表示选项，冒号表示选项后面需要参数（必填）,两个冒号表示选项后面参数选填。返回值为当前选项字母，如果没有选项了则返回 -1。

在本例中，选项字符串为 hvs:E:b:t:，表示有 5 个选项，其中 s、E、b、t 后面需要参数。h、v 后面不需要参数。

关于 optarg，可以理解为是用来保存选项的参数的，而且虽然你没有定义它，但是因为你引入了 getopt.h 头文件，所以它是一个外部变量，你可以直接使用它。

本次测评不要求 h 和 v 选项，所以你也可以用 s:E:b:t: 作为选项字符串（当然后面的逻辑也要对应修改）。

Basic Linux tar usage

basic data types

Basic number types

Characters

Arithmetic operator

logic statement

if…else

switch

loop

for

while

do-while

getchar() and putchar

conditional operator

array

multidimensional arrays

char array

function

function prototype

recursion

pointer

declaration

pointers and array

pointer and function

limitation of C

Dynamic memory allocation

character strings

struct

accessing field

Naming a structure for reusability

pointer to a struct

adding malloc

Advanced Pointer & file IO

advanced use of pointer

linked list

why linked list instead of the array

implementation

declaration

initialization

node creation

insert at the beginning

search

deletion

double pointers

arrays of strings

its principle: double pointers

Why we need double pointers

algs (Algorithms)

complexity

time complexity

search

linear search

Binary search

sorting

selection sort

merge sort(O(n^2))

I/O

standard I/O

stream

single character I/O

file I/O

open

close

stream

reading & writing

other head files

string.h

time.h

ctype.h

math.h

stdlib.h

getopt()

Basic Linux `tar` usage

`getchar()` and `putchar`

adding `malloc`

`string.h`

`time.h`

`ctype.h`

`math.h`

`stdlib.h`

`getopt()`