PE1 Review
Important Concepts
Fixed-Length Array
Declaration and Initialization
The method below declares a fixed-length array of length 10 and initializes some of the elements' value. The elements that are not initialized will be set to 0 instead.
Note that, after the declaration, we can no longer use this technique to reinitialize or initialize the array.
Passing Fixed-Length Array as Parameter to Functions
There are two ways to pass the array as a parameters to functions.
Passing in the array with
[
,]
and the constant size of the array.
Passing in the array with
[
,]
Note that in method 1, we explicity specify the array length to be 10. So, if you pass an array whose length is not 10, the compiler will generate a warning. But in method 2, len
is not explicitly related to list
in C, and would have to depend on the comments of the code to tell the reader what len
is for.
Return Array from a Function
If you want to return a fixed-length array from a function, please don't do that! There is no meaning of doing that since if you create a fixed-length array in a function, it is stored on the stack. So, after you return from the function call, the memory will be destroyed!
This part is useful if you create an array on the heap in the function, and then you can return the address to that array on the heap.
Pointer
Declaration and Initialization
Line 1 declares a pointer variable and Line 2 initializes the pointer variable to the address of a long
variable c
, which is same as making the pointer point to the variable c
.
Dynamic-Length Array
size_t
size_t
is just a fancy way of saying non-negative integer.
While both size_t
and long
are integer types, they are not compatible with each other. Explicit casting is needed to assign the value of one type to the other.
malloc() and calloc()
calloc
allocates memory for count
items, each of size
number of bytes, in a contiguous region in the memory and initializes all bits in this memory region to 0.
Always use calloc()
instead of malloc()
since it can initialize the content of the memory address to 0, which saves lots of trouble.
Declare a dynamic-length array
Passing a Dynamic-Length Array as Parameter to Functions
The most common way we use is to pass the length of the array and the its address
String
char
To print a char
, use putchar()
String
To declare a string, we have two ways
However, using the Line 2 version, the string is called a String Literal. And we cannot change the element in a string literal.
Note that Line 1 stores the string on the stack while Line 2 stores the string in a read-only memory. However, the most common way is to store strings on the heap so that we can modify it easily.
To create a string on the heap, we can use the function provided by CS1010 I/O library.
Multidimensional Array
Based on our requirements, we may choose what kind of array we want to declare in our code.
A Fixed size 2-D Array
Suppose before we run our program, we already know the dimension of our matrix (num of rows and num of cols). We can use the following method to declare a fixed-size 2-D array.
A Fixed-Size Array of Dynamically Allocated Array
This is used when we already know the number of rows in your array before we run our program, but we don't know the number of cols before we run our program. So, we may use dynamic array for each row.
Dynamically Size 2D Array
Now, suppose we know neither the number of rows and the number of cols before we run our program. We should use the following convention to declare our dynamically size 2D array.
CS1010 I/O Library
Read a single value
size_t cs1010_read_size_t()
size_t cs1010_read_size_t()
char* cs1010_read_word()
char* cs1010_read_word()
Returns a char *
pointing to the next white-space-separated string from the standard input.
char* cs1010_read_line()
char* cs1010_read_line()
Returns a char *
pointing to the next new-line-separated string from the standard input.
Read multiple values
long* cs1010_read_long_array(size_t k)
long* cs1010_read_long_array(size_t k)
Returns k
numbers of long
values read from the standard input stored in an array. (Read an array of long
).
double* cs1010_read_double_array(size_t k)
double* cs1010_read_double_array(size_t k)
Returns k
numbers of double
values read from the standard input stored in an array. (Read an array of double
).
char** cs1010_read_word_array(size_t k)
char** cs1010_read_word_array(size_t k)
Returns k
white-space-separated words read from the standard input stored in an array. The notion of "word" is the same as cs1010_read_word()
. (A quicker way to read in a jagged array)
char** cs1010_read_line_array(size_t k)
char** cs1010_read_line_array(size_t k)
Returns k
new-line-separated words read from the standard input stored in an array. The notion of a line is the same as cs1010_read_line()
. (A quicker way to read in a jagged array)
Using char** cs1010_read_word_array(size_t k) and char** cs1010_read_line_array(size_t k) can save us the trouble from dealing with the inner Null pointer check. We only need to judge whether the pointer returned is NULL or not. (Applies to all four I/O functions here)
Important Functions
Dynmaic-Length 1-D Array
There are four methods provided by CS1010 I/O Library
Read an array of long, use long* cs1010_read_long_array(size_t k)
Read an array of double, use double* cs1010_read_double_array(size_t k)
Read an array of char (word), use char* cs1010_read_word()
Read an array of char (line), use char* cs1010_read_line()
Multidimensional Array
Null Pointer Check
Combine it with the Dynamically Size 2D Array, we have
Another method is to use char** cs1010_read_word_array(size_t k)
Read a 2-D Array of long
or double
long
or double
With this, the usage in main()
should be
String
Length of a String
Traverse through a string
To traverse from the end of a string (knowing the length of a string), it is recommended to cast the loop variable (e.g. i
) as long
. For example
Cast the string index i
to be long
! It can save lots of trouble!
Check the existence of a word in a line
Find the position of the first occurrance of a word
In this code, pos
stores the first occurrance of a word in the line, if DNE, then it is -1. cur_pos
stores the current position of char
we are about to match in the line.
String.h
size_t strlen(const char *s)
, which will return the length of a string assize_t
.
Sliding Window
To find the maximum sum of all subarrays of size K
Given an array of integers of size ‘n’, Our aim is to calculate the maximum sum of ‘k’ consecutive elements in the array.
The most important idea is to remove the first element and add the last element of the current window.
Classic Problem
Write a program social
, that reads from standard input two positive integers n and k, followed by n lines of strings consisting of '1' or '0' representing the social network of degree 1 of these n people. Print, to the standard output, the social network of degree k formed by friendship chains of up to k hops.
Tips
(
char
andlong
difference) Don't mixchar
andlong
in your code. For example, casting fromlong
tochar
(e.g.long
9 tochar
9), use(char) 9 + '0'
. Fromchar
tolong
(e.g.char 9
tolong 9
), use'9'-'0'
(
size_t
always bigger than 0) To avoid the trouble thatsize_t
cannot be negative in thefor
loop, we can convert them intolong
explicitly.(Start and end of 1-D array in the function in recursion) When writing recursion including 1-D Array, pay attention to the inclusiveness of the start and end in your function of recursion.
(Frequency Table of a number) The idea is to treat every digit of a number as the frequency table's index and iterate through each digit to count its frequency.
(2-D Array in solving hard problems) Make wise use of the 2-D Array, while each element's index (
i
andj
) can represent some "relationship" between thei
andj
. This "relationship" is stored as the value of this element.
Last updated