midterm-reviewer-CP2.pdf

lOMoARcPSD|21504907 Midterm Reviewer Bachelor of Science in Computer Science (Polytechnic University of the Philippines) Scan to open on Studocu Studocu is not sponsored or endorsed by any college or university Downloaded by Melvin Delen ([email protected]) lOMoARcPSD|21504907 COMP 003 - Compu...

lOMoARcPSD|21504907 Midterm Reviewer Bachelor of Science in Computer Science (Polytechnic University of the Philippines) Scan to open on Studocu Studocu is not sponsored or endorsed by any college or university Downloaded by Melvin Delen ([email protected]) lOMoARcPSD|21504907 COMP 003 - Computer Programming 2 Midterm Reviewer UNIT 1 - Array Array - a fixed-size, sequenced collection of elements of the same data type. - a sequence of data items that are of the same type, that are indexible, and that are stored contiguously. - another approach in data structures. Elements refer to a list of variables of the same data type that can be grouped into an array. Size - how many elements are in the array. Example: int a, b, c, d, e, f, g, h, i, j; float a, b, c, d, e; Syntax: storage_class data_type arrayname[size]; Example: int ccmit; char bscs; *char - every character has a null character at the end. Overflow - too many elements (sobra). Underflow - too few elements (kulang). Underflow overflow. is acceptable, but not the Note: The first element begins at index and the last element is always size - 1. int X = { 3, 1,7,2,6,9,4,8,5,10}; (declaration with initialization) Accessing Elements in Arrays for(i=0; i 27 so the target value must be in the upper portion i = 0 - initialization i < 0 - sentinel i++ - iteration 2 Major Operations in Array Searching Sorting Formula: low = mid + 1 4+1= 5 mid = 5 + (9 – 5) / 2 = 7 Downloaded by Melvin Delen ([email protected]) lOMoARcPSD|21504907 35 ≠ 31 31 < 35 so the target value must be in the lower part. high = mid - 1 =7-1=6 mid = low + (high – low)/2 mid = 5 + (6 – 5) /2 = 5 31 = 31 Other formula: MID = (R + L)/2 Sorting - a process of putting data in order either numerically or alphabetically. - numerical order from highest to lowest values (descending order) or vice versa (ascending order). Types of Sorting Insertion Selection Bubble Merge Shell Quick Insertion Sort - a simple sorting algorithm that builds the final sorted array (or list) one item at a time. Selection Sort - an in-place comparison-based algorithm in which the list is divided into two parts, the sorted part at the left end and the unsorted part at the right end. Bubble Sort - a comparison-based algorithm in which each pair of adjacent elements is compared and the elements are swapped if they are not in order. Merge Sort - a sorting technique based on the divide and conquer technique. Shell Sort - a highly efficient sorting algorithm and is based on the insertion sort algorithm. - this algorithm avoids large shifts as in case of insertion sort, if the smaller value is to the far right and has to be moved to the far left. - this algorithm uses insertion sort on a widely spread elements, first to sort them and then sorts the less widely spaced elements. - This spacing is termed as interval. This interval is calculated based on Knuth's formula as: h=h*3+1 where − h is interval with initial value 1 Quick Sort - a highly efficient sorting algorithm and is based on partitioning of array of data into smaller arrays. - a large array is partitioned into two arrays one of which holds values smaller than the specified value, say pivot, based on which the partition is made and another array holds values greater than the pivot value. - Quick sort partitions an array and then calls itself recursively twice to sort the two resulting subarrays. Multidimensional Arrays - are defined in much the same manner as one-dimensional. - a two-dimensional array requires two pairs of square brackets. - two-dimensional arrays are also called array of arrays. Example: float IT; int CS; int ccmit ={1,2,3,4,5,6,7,8,9}; Size = row x column Subsets = row/value of each subset Example: declarations int x={{2,4,6,8},{10,12,1,3},{5,7,9,11}}; int x={{2,4,6,},{10,12,1,3},{5,7}}; error: int x={{2,4,6,8},{10,12,1,3,14},{5,7,9,11}}; int x={{2,4,6,8},{10,12,1,3},{8,1,3,4},{5,7,9,11}}; UNIT 2 - Function Variables - a storage are that our programs can manipulate. - each variable in C has a specific type, which determines the size and layout of the variable’s memory. How to characterize a variable? Downloaded by Melvin Delen ([email protected]) lOMoARcPSD|21504907 By data type - refers to the the type of information represented by a variable. By storage class - refers to the permanence of a variable and its scope within the program, that is, the portion of the program over which the variable is recognized. Storage Class - determines the part of the memory where the variable would be stored. - also determines the initial value of the variable. - use to define the scope and lifetime of variable. There are two storage location computer: CPU Registers Memory There are four storage-class specifications in C: Automatic storage class or Auto (local) Register storage class Static storage class External storage class or Extern (global) Two types of Function 1. Pre-defined function Example: main function () 2. User-defined function Example: int x (parameter) Three Elements of Functions 1. Function prototype - declared before the int main function. Also known as the function declaration. Syntax: return_type function_name(formal parameters); 2. Function definition - body of the function Syntax: return_type function_name(formal parameters) { body of a function } 3. Function call - They are "saved for later use", and will be executed when they are called. To call a function, write the function's name followed by two parentheses () and a semicolon ; Syntax: function_name(actual parameters); Example: Summary: static - last value will be retain. global/extern - last value will be retain when the program exits. the difference is that in global you can access it anywhere. auto - equivalent sa local variables register - same with auto and difference is it stores the variables in the register of the microprocessor. If notfree register,it stores in the memory. Function - a section of a program which performs a specific task. - The task assigned to a function is performed whenever C encounters the function name. #include void name(int a,int b); //prototype or declaration int main() {int a,b; //function definition func(a,b) //call a function - actual parameters } int func(int a,b) //formal parameters { } Two types of Parameters 1. Actual Parameters - variables in the int main function or the one inside the function call. 2. Formal Parameters - variables passed in user-defined functions. Two types of passing a variable 1. Pass by value - kung binago mo value sa user-defined function hindi siya magr-reflect sa main function. 2. Pass by reference - pwede mo mabago yung value. Gumagamit pointer(*) and address(&). Downloaded by Melvin Delen ([email protected]) lOMoARcPSD|21504907 Recursion - is a technique of making a function call itself. - This technique provides a way to break complicated problems down into simple problems which are easier to solve. - is the process of repeating items in a self-similar way a function to call itself. any type of pointer can point to anywhere in the memory. is used to declare a pointer and also to deference a pointer. Base case - in a recursion base case is important since it will stop the function to call itself. Address of the operator (&) - (&) a unary operator that returns the memory address. - it is used to reference the memory address of a variable. Example: int sum(int k); int main() { int result = sum(10); printf("%d", result); return 0; } int sum(int k) { if (k > 0) //base case { return k + sum(k - 1); } else { return 0; } When you write int *; the compiler assumes that any address that it holds points to an integer type. When we declare a variable, 3 things happen: 1. computer memory is set aside for the variable. 2. variable name is linked to that location in memory. 3. value of a variable is placed into the memory that was set aside. Example: m=&count; q=*m; } //it will result into 55 //return 10+9+8+7+6+5+4+3+2+1=55 UNIT 3 - Pointers Pointer - a variable that holds a memory address. - this address is the location of another object being pointed at in the memory. - pointer as an address indicates where to find an object. - not all pointers actually contain an address, example NULL pointer. - value of NULL pointer is 0. Declaring Pointer Syntax: Data type *name Example: int *p; float *p; (*) is a unary operator, also called an indirection operator. Indirection operator - you are able to access the value, you can also manipulate the pointer variable. Also called a reference. a data type is the type of object to which the pointer is pointing. Value of address operator(*) Pointer Conversion - also known as type casting. - one type of pointer can be converted to another type of pointer. Example: #include int main() { double x=100.1,y; int *p; //explicit conversion p=(int *)&x; //may asterisk since address tinuturo y=*p; } Generic Pointer - void *pointer is called as generic Downloaded by Melvin Delen ([email protected]) lOMoARcPSD|21504907 pointer. - can’t convert void *pointer to another pointer and vice-versa unless you perform another type casting. - void *pointer can be assigned to any other type of pointer - void * is used to specify whose base type is unknown. - it is capable of receiving any type of pointer argument without reporting any mismatch. Pointer Arithmetic - in pointer two operator: addition & subtraction - To understand this concept, let p1 be an integer value with value 2000 address int is 2 bytes. After expression p1++; p1 will be 2002, not 2001 - you will add how many bytes. Arithmetic Rules you cannot multiply or divide pointers. you cannot add or subtract two pointers. you cannot apply bitwise operators to them. you cannot add or subtract type of float or double to or from pointers. Pointer Comparison You can compare two pointers in a relational, example: if( p < q) printf(“p points to lower memory than 1 \n”); Pointer comparison are useful only when two pointers point to a common object such as an array. Benefits of Pointer Pointers are used in situations when passing actual values are difficult or not desired To return more that one value from a function They increase the execution speed The pointer are more efficient in handling the data types Pointers reduce the length and complexity of a program The use of a pointer array to character string results in saving of data To allocate memory and access it( Dynamic Memory Allocation) Implementing graphs and structure. linked many lists, trees other data Uses of pointer to function - Pointers are certainly awkward and off-putting and thus this feature of the pointer is used for invoking a function. Pointers and One-Dimensional Arrays - how you moved the address forward or backward. - array name always contain the base address or the first element of an array. &x == x. - Moreover, the address of the second array element can be written as either &x or as (x + 1), and so on. - it would seem reasonable that x[i] and *(x + i) both represent the contents of that address. Array Version Note: There is an index and ampersand. Example 1: Example 2: Pointer Version Note: There is an ampersand. Example: Downloaded by Melvin Delen ([email protected]) lOMoARcPSD|21504907 each time p1 is incremented, it will point to next integer. The same is true for decrement. ○ for p1- -; ○ causes value of p1 to be 1998; each time a pointer is incremented, then it points to previous element location. p1=p1+12; Dynamic Memory Allocation - the use of a pointer variable to represent an array requires some sort of initial memory assignment before the array elements are processed. - such initial memory allocations are accompanied by using the malloc library function, #include Explanation: int main function() How many numbers will be entered? n=5 Syntax: variableName=(data_type*) malloc(size(sizeof(data_type)); Note: reason why we need malloc — kapag hindi nagdeclare ng array at ginamit mo lang is pointer. If si pointer is walang na receive na size hindi malalaman ni compiler kung anong bytes ang gagamitin mo. Example: Downloaded by Melvin Delen ([email protected])