StuDocu is not sponsored or endorsed by any college or university
COMP10002 - Summary Programming Problem Solving and
Abstraction with C
Foundations Of Algorithms (University of Melbourne)
Downloaded by Sarry Bi ([email protected])
lOMoARcPSD|5554842
Numbers In, Numbers Out
Identifier - a name used in a C program to represent a value
An Identifier must:
● Begin with underscore or letter
● Alphanumerics and underscores
● No reserve words
Constants
E.g.
#define SEC_PER_MIN 60
Traditionally in all capital letters
Definition does not need a semicolon
Can be defined in terms of another constant
Redefining constants can cause issues with the program
Variables
E.g. (defining and declaring shorthand)
Int sum=0;
Must be assigned a value before use
Integers must be between -2^31 and 2^31-1
Floating point numbers are approximations (do not try and compute small numbers with big
numbers)
Inputs
E.g.
scanf(control string, variable)
scanf(%d, &n_pass)
Num_of_obj = scanf(%d, &n_pass) #gets number of inputs
Outputs
E.g.
printf(control string, expression)
Control Strings
%f - float/double
Downloaded by Sarry Bi ([email protected])
lOMoARcPSD|5554842
%d - int
%s - string
%c - char
Making Choices
Operators:
Operator Description Example
+ Adds two operands. A + B = 30
− Subtracts second operand from the first. A − B = -10
* Multiplies both operands. A * B = 200
/ Divides numerator by de-numerator. B / A = 2
% Modulus Operator and remainder of after an integer division. B % A = 0
++ Increment operator increases the integer value by one. A++ = 11
-- Decrement operator decreases the integer value by one. A-- = 9
If Statements:
if(boolean_expression) {
/* statement(s) will execute if the boolean expression is true */
} else {
/* statement(s) will execute if the boolean expression is false */
}
Switch Statements:
switch(expression) {
case constant-expression :
statement(s);
break; /* optional */
case constant-expression :
statement(s);
break; /* optional */

/* you can have any number of case statements */
default : /* Optional */
statement(s);
}
Downloaded by Sarry Bi ([email protected])
lOMoARcPSD|5554842
Loops
Three types of loops:
● For Loops
● Do Loops
● While Loops
For Loops:
for (initialize ; guard ; update)
statement
While Loops:
while (guard)
statement
Used when the number of iterations is not known.
However an identical for statement can be written:
for (; guard ; )
statement
Do Loops:
do
statement
while (guard)
Functions and Pointers
The main function is called by the operating system when a program commences execution
Return - pops a single stack frame
Exit - is an abrupt termination that strips all frames associated with the program
A function with no arguments are declared with the argument void
E.g.
int
print_helloword(void){
...
}
Functions that do not have to return a value are declared with type void (but can use return if
needed)
E.g.
void
print_double(double x){
...
Downloaded by Sarry Bi ([email protected])
lOMoARcPSD|5554842
}It is not possible for any function to use or modify a variable local to another function
Types of variable declaration
Variables declared outside of any function are global to all functions defined in that space.
Variables declared within a function are local to that function.
Local variables declarations always supersede global variables (this includes functions)
Static variables allow functions to retain the value of variables when called multiple times
without them being accessible to other functions. (they are an alternative to using global
variables)
E.g.
void
func(int x) {
static int z = 7;
z = z + 1;
}
Pointers
A pointer variable stores the memory address of another variable
& - address of - returns the location in memory that is currently allocated to that variable.
* - dereferencing operator - can be used to alter the value of an underlying variable whose
address is stored in a pointer variable
E.g.
int n = 123, *pi;
pi = &n;
*pi = *pi + 1;
(code changes the underlying pointer value hence n also equals 124)
Arrays
An array is a collection of the same type of variable that is guaranteed to be laid out in a regular
pattern in memory.
E.g.
Int A[10];
A reference to an index that is not apart of the array can affect another variable that points to
that memory.
Downloaded by Sarry Bi ([email protected])
lOMoARcPSD|5554842
Sorting and Searching
Linear search - looking linearly through all indices in an array to find an element.
Insertion sort - is a simple sorting algorithm that builds the final sorted array one item at a time
Insertion sort computational steps:
Best Case Average Case Worst Case
n n
2
/2 n
2
/ 4
Identifiers in Array
p = A is the same as p = &A[0]
An array can be passed in a function as either a A[] or as a pointer
Typedef
typedef - is used to declare a new type or can be used as an alias for a single type ( used for
recurring programming types)
E.g.
typedef double data_t
● Using typedef allows easy manipulation of multiple variables
E.g.
typedef int array_t[10];
array_t one_word[2];
● Using typedef allows the definition of an array for creation of 2D arrays.
Two Dimensional Arrays
E.g. (Define a 100 new variables)
Int A[10][10];
Arrays Initialization
E.g. (one dimensional)
Int month_days[13] = {0,31,28,...,31};
E.g. (two dimensional)
Downloaded by Sarry Bi ([email protected])
lOMoARcPSD|5554842
Int month_days[2][13] ={{0,31,28,...,31},{0,31,29,...,31}};
● Any remaining entries not defined are set to 0
● If number of elements is not specified that array will infer number of elements.
● A[size]={0} sets all entries to 0.
Array Pointers
● Pointers of arrays can be added and subtracted to find adjacent array values.
E.g.
*p = A[0]
Therefore p+1 is the element after p and p-1 is the element before p.
Likewise p[i] can be used to access the i’th value from p.
Strings
A valid string is c is stored as a null terminated array of chars. (have ‘\0’ stored as the last
character)
Strings can also be initialized as follows:
E.g.
s1[] = “Pluto”; # C automatically adds null byte to the end of the double quoted string
“%s” format descriptor prints characters until the null byte is encountered
stdlib.h header file includes string functions, the main ones are:
● int strcmp (char *s1, char *s2) #copies string
● int strlen(char *s) #returns length of string
● Int strcmp(char *s1, char *s2, n) #where n is the limit on characters and returns if string
is greater
● int atoi(char *s) returns integer value of string
● Int atof(char *s) returns double value of string
Structures
A structure is similar to a javascript object
E.g. (basic structure definition)
struct {
double distance;
double mass;
Downloaded by Sarry Bi ([email protected])
lOMoARcPSD|5554842
double radius;
} one_planet;
E.g. (defining a structure and assigning it to multiple variables)
Struct planet_s {
double distance;
double mass;
double radius;
};
struct planet_s big_planet, big_moon, …;
E.g. (defining a structure type and assigning it to multiple variables)
typedef struct {
double distance;
double mass;
double radius;
} planet_t;
planet_t big_planet = {...}
● Structures of the same type can be assigned but not compared
E.g.
another_planet = one_planet;
● In most cases functions should be passed as pointers in order for the function to
alternate the underlying variable instead of creating a local one.
● Arrays of structures are a valid and common practise.
Problem Solving Statergies
Generate and Test - is the proccess of testing each candidate for correctness and is
appropiate when there is ordering on candidate answers that allow exhausitive
enumeration.
Divide and conquer - Dividing the problem into a sub problem that can be used to
construct the solution of the original problem
Simulation - using randomly generated data to approxiamte a meaningful trend.
Multiple runs should be taken to verify the stability.
Downloaded by Sarry Bi ([email protected])
lOMoARcPSD|5554842
srand and rand generate a stream of apparently uncorrelated integers
E.g.
srand(SEED);
int x = rand();
Approximation Techniques - using a given step size to approximate values on function.
(step size cannot be to small as rounding errors with make approximation worse/ step
size cannot be to big as it will then not be a good approximation)
Physical Simulation - simulating the problem to find neccesary information
Solution by evolution - finding a similar solution that solves a similar problem and
evolving it to cope with the new situation.
Dyanmic Structures

Downloaded by Sarry Bi ([email protected])
lOMoARcPSD|5554842

欢迎咨询51作业君