CPP253 Data Structures - Introduction PDF

CPP253 Data Structures Introduction to Data Structures Öğr. Gör. İhsan Can İÇİUYAN  2 CPP253 – Data Structures Contents  Basic Terminology  Data Structure Organization  Classification of Data Structures ...

CPP253 Data Structures Introduction to Data Structures Öğr. Gör. İhsan Can İÇİUYAN  2 CPP253 – Data Structures Contents  Basic Terminology  Data Structure Organization  Classification of Data Structures  Arrays  Linked Lists  Stacks  Queues  Trees  Graphs  Operations on Data Structures  Abstract Data Type (ADT)  3 CPP253 – Data Structures Basic Terminology  A good program is defined as a program that  runs correctly  is easy to read and understand  is easy to debug  is easy to modify  Program → correct results + efficient run-time  In order to write efficient programs we need to apply certain data management concepts.  4 CPP253 – Data Structures Basic Terminology  The concept of data management is a complex task that includes activities like  data collection  organization of data into appropriate structures  developing and maintaining routines for quality assurance  A data structure is basically a group of data elements that are put together under one name, and which defines a particular way of storing and organizing data in a computer so that it can be used efficiently.  5 CPP253 – Data Structures Basic Terminology  Data structures are widely applied in the following areas:  Compiler design  Operating system  Statistical analysis package  DBMS  Numerical analysis  Simulation  Artificial intelligence  Graphics  The primary goal of a program or software is not to perform calculations or operations but to store and retrieve information as fast as possible.  6 CPP253 – Data Structures Basic Terminology  When selecting a data structure to solve a problem, the following steps must be performed: 1. Analysis of the problem to determine the basic operations that must be supported. For example, basic operation may include inserting/deleting/searching a data item from the data structure. 2. Quantify the resource constraints for each operation. 3. Select the data structure that best meets these requirements. Data-centred view of the design process  7 CPP253 – Data Structures Basic Terminology  3 step process 1. Data + Operations on them 2. Representation of the data 3. Implementation  Adding new data items → Only at the beginning? Any position?  Accessing data items → Sequentially? Randomly?  Selection of an appropriate data structure for the problem is a crucial decision and may have a major impact on the performance of the program.  8 CPP253 – Data Structures Data Structure Organization  Data → a value or set of values  value of a variable or constant  marks of students, name of an employee, address of a customer, value of pi, etc.  Record → collection of data items  name + address + course + marks  File → collection of related records  A file of all students in a class, employees in an organization, all the customers of a company, etc.  Primary key, K → unique data item for each record in a file  student number, employee id, etc.  9 CPP253 – Data Structures Classification of Data Structures  10 CPP253 – Data Structures Classification of Data Structures  Primitive data structures → fundamental data types supported by the programming language  integer, float, character, boolean  data type, basic data type, primitive data type  Non-primitive data structures → created using primitive data structures  arrays, linked lists, stacks, trees, graphs, etc.  two categories: linear and non-linear  11 CPP253 – Data Structures Classification of Data Structures  Linear data structure → elements are stored in a linear or sequential order  arrays, linked lists, stacks, queues  two different representation in memory:  sequential memory locations  links  Non-linear data structure → elements are not stored in a sequential order  trees, graphs  12 CPP253 – Data Structures Arrays  Array → collection of similar data elements  Elements  have the same data type.  are stored in consecutive memory locations.  are referenced by an index.  In C, arrays are declared using the following syntax: type name[size];  13 CPP253 – Data Structures Arrays  For example int marks;  An array named marks containing 10 elements.  The array index starts from zero.  In the memory, the array will be stored as below:  14 CPP253 – Data Structures Arrays  Arrays are generally used when we want to store large amount of similar type of data.  They have some limitations:  Arrays are of fixed size.  Data elements are stored in consecutive memory locations which may not be always available.  Insertion and deletion of elements can be problematic because of shifting of elements from their positions.  Possible solutions: dynamic arrays (using pointers), linked lists  15 CPP253 – Data Structures Linked Lists  Linked list → very flexible, dynamic data structure in which elements (called nodes) form a sequential list  No fixed size like arrays.  Each node is allocated space as it is added to the list.  Every node in the list points to the next node in the list.  Every node contains the following two types of data:  The value of the node  A pointer or link to the next node in the list  16 CPP253 – Data Structures Linked Lists  The last node in the list contains a NULL pointer (end or tail of the lists)  An example of linked list of seven nodes:  Advantage: Easier to insert or delete data elements.  Disadvantage: Slow search operation and requires more memory space  17 CPP253 – Data Structures Stacks  Stack → linear data structure in which insertion and deletion of elements are done at only one end (top of the stack)  Last-in, first-out (LIFO) structure  Can be implemented using arrays or linked lists  An array implementation of a stack (top = 4):  18 CPP253 – Data Structures Stacks  top → the address of the topmost element of the stack. Elements will be added at or deleted from this position.  MAX → the maximum number of elements that the stack can store.  top = NULL or -1 → Stack is empty  top = MAX – 1 → Stack is full  19 CPP253 – Data Structures Stacks  Supports three operations:  push → adds an element to the top of the stack  pop → removes the element from the top of the stack  peek → returns the value of the topmost element of the stack (without deleting it)  Before inserting an element → check for overflow (full stack)  Before deleting an element → check for underflow (empty stack)  20 CPP253 – Data Structures Queues  Queue → linear data structure in which the element that is inserted first is the first one to be taken out  First-in, first-out (FIFO) structure  Can be implemented using arrays or linked lists  An array implementation of a queue (front = 0, rear = 5):  21 CPP253 – Data Structures Queues  front → the position from where deletions can be done  rear → the position from where insertions can be done  MAX → the maximum number of elements in the queue  rear = MAX – 1 → Queue is full  front = NULL and rear = NULL → Queue is empty  22 CPP253 – Data Structures Queues  Adding an element to the queue (front = 0, rear = 6):  Deleting an element from the queue (front = 1, rear = 6):  Before inserting an element → check for overflow (full queue)  Before deleting an element → check for underflow (empty queue)  23 CPP253 – Data Structures Trees  Tree → non-linear data structure which consists of a collection of nodes arranged in a hierarchical order  One of the nodes is designated as the root node.  The remaining nodes can be partitioned into disjoint sets such that each set is a sub-tree of the root.  24 CPP253 – Data Structures Trees  The simplest form of a tree → binary tree  A binary tree consists of a root node and left and right sub-trees, where both sub-trees are also binary trees.  Each node contains:  a data element  a left pointer which points to the left sub-tree  a right pointer which points to the right sub-tree  root element → topmost node which is pointed by a root pointer  root = NULL → Tree is empty  25 CPP253 – Data Structures Trees  An example of a binary tree:  R → root, T1 → left sub-tree, T2 → right sub-tree  Node 2 → left child of root, node 3 → right child of root  Advantage: Provides quick search, insert, and delete operations  Disadvantage: Complicated deletion algorithm  26 CPP253 – Data Structures Graphs  Graph → non-linear data structure which is a collection of vertices (also called nodes) and edges that connect these vertices  Graph → generalization of the tree structure  Tree → parent-child relationship  Graph → complex relationships  An example of a graph with five nodes:  27 CPP253 – Data Structures Graphs  Examples:  Cities as nodes, roads as edges  Workstations as nodes, network connections as edges  No root node!  Two nodes connected via an edge → neighbours  Advantage: Best models real-world situations  Disadvantage: Some algorithms are slow and very complex  28 CPP253 – Data Structures Data Structures  29 CPP253 – Data Structures Operations on Data Structures  Traversing → to access each data item exactly once so that it can be processed  printing the names of all the students in a class  Searching → to find the location of one or more data items that satisfy the given constraint  finding the names of all the students who secured 100 marks in mathematics  Inserting → to add new data items to the given list of data items  adding the details of a new student who has recently joined the course  Deleting → to remove (delete) a particular data item from the given collection of data items  deleting the name of a student who has left the course  30 CPP253 – Data Structures Operations on Data Structures  Sorting → to arrange in some order like ascending order or descending order  arranging the names of students in a class in an alphabetical order  Merging → to combine lists of two sorted data to form a single list of sorted data items  31 CPP253 – Data Structures Abstract Data Type  Abstract Data Type (ADT) → the way we look at a data structure  focusing on what it does  ignoring how it does its job  Mathematical description of an object with set of operations on the object  The end-user is not concerned about the details of how the methods carry out their tasks.  They are only aware of the methods that are available to them.  Stack → push() and pop() functions, but can be implemented using arrays or linked lists  32 CPP253 – Data Structures Data Structures  33 CPP253 – Data Structures References  https://en.wikipedia.org/wiki/Data_structure  https://www.geeksforgeeks.org/data-structures/  https://www.tutorialspoint.com/data_structures_algorithms/index.ht m  https://www.programiz.com/dsa/data-structure-types  https://levelup.gitconnected.com/data-structures-overview- 13ac8a02a880  https://youtu.be/DuDz6B4cqVc  34 CPP253 – Data Structures That’s all for today!  CPP253 Data Structures Arrays - Part I Öğr. Gör. İhsan Can İÇİUYAN  2 CPP253 – Data Structures Contents  Arrays  Declaration of Arrays  Accessing the Elements of an Array  Address of Array Elements  Length of an Array  Storing Values in Arrays  Operations on Arrays  Traversing an Array  Inserting an Element  Deleting an Element  Merging Two Arrays  3 CPP253 – Data Structures Arrays  Assume: 20 students in a class  Aim: to read and print the marks of all students  Create: 20 integer variables with different names  4 CPP253 – Data Structures Arrays  20 read + 20 write statements  Read and print the marks of students  in the entire course (100 students)  in the entire college (500 students)  in the entire university (10.000 students)  To process a large amount of data, we need a data structure known as array.  Array → collection of similar data elements  Elements  have the same data type.  are stored in consecutive memory locations.  are referenced by an index.  5 CPP253 – Data Structures Declaration of Arrays  An array must be declared before being used.  Arrays are declared using the following syntax: type name[size];  Data type: the kind of values it can store, for example, int, char, float, double  Name: to identify the array  Size: the maximum number of values that the array can hold  6 CPP253 – Data Structures Declaration of Arrays  If we write int marks; then the statement declares marks to be an array containing 10 elements. In C, the array index starts from zero.  The last element (10th element) will be stored in marks.  In the memory, the array will be stored as below:  7 CPP253 – Data Structures Declaration of Arrays  Declaring arrays of different data types and sizes  8 CPP253 – Data Structures Accessing the Elements of an Array  We can access all the elements of an array by varying the value of the index into the array (marks, marks, marks, etc.)  To access all the elements of an array, we must use a loop.  The code accesses every element of the array and sets its value to –1.  9 CPP253 – Data Structures Address of Array Elements  Array name → symbolic reference to the address of the first byte of the array  When we use the array name, we are actually referring to the first byte of the array.  The index represents the offset from the beginning of the array to the element being referenced.  The formula to calculate the address of data elements is: Address of data element, A[k] = BA(A) + w(k - lower_bound)  A → the array; k → index of the element of which we have to calculate the address; BA → base address of the array A; w → size of one element in memory  10 CPP253 – Data Structures Address of Array Elements  EX: Given an array int marks[]={99,67,78,56,88,90,34,85}, calculate the address of marks if the base address = 1000. 1000 1004 1008 1012 1016 1020 1024 1028  We know that storing an integer value requires 4 bytes, therefore, its size is 4 bytes. marks = 1000 + 4(4 - 0) = 1000 + 4(4) = 1016  NOTE: sizeof(int) is 4 bytes on 64-bit machines!  11 CPP253 – Data Structures Length of an Array  The length of an array → the number of elements stored in it  The formula to calculate the length of an array is Length = upper_bound - lower_bound + 1  upper_bound → index of the last element lower_bound → index of the first element  EX: Let Age be an array of integers such that Age = 2, Age = 5, Age = 3, Age = 1, Age = 7 Show the memory representation of the array and calculate its length. length = 4 - 0 + 1 = 5  12 CPP253 – Data Structures Storing Values in Arrays  Declaring an array → allocating space for its elements, no values are stored!  There are three ways to store values in an array:  13 CPP253 – Data Structures Storing Values in Arrays  The elements of an array can be initialized at the time of declaration.  Arrays are initialized by writing, type array_name[size] = {list of values};  Every value is separated by a comma. int marks = {90, 82, 78, 95, 88};  While initializing the array at the time of declaration, we may omit the size of the array. int marks[] = {98, 97, 90};  14 CPP253 – Data Structures Storing Values in Arrays  Initialization of array elements  15 CPP253 – Data Structures Storing Values in Arrays  16 CPP253 – Data Structures Storing Values in Arrays  An array can be initialized by inputting values from the keyboard.  In this method, a while/do–while or a for loop is executed to input the value for each element of the array.  17 CPP253 – Data Structures Storing Values in Arrays  We can also assign values to individual elements of the array by using the assignment operator.  A simple assignment statement can be written as marks = 100; We cannot assign one array to another array! (even if they have the same type and size)  To copy an array, you must copy the value of every element of the first array into the elements of the second array.  18 CPP253 – Data Structures Operations on Arrays  Operations that can be performed on arrays:  Traversing an array  Inserting an element in an array  Deleting an element from an array  Merging two arrays  Searching an element in an array  Sorting an array in ascending or descending order  19 CPP253 – Data Structures Traversing an Array  Traversing an array → accessing each and every element of the array for a specific purpose, e.g:  Printing every element  Counting the total number of elements  Performing any process on the elements  The algorithm for array traversal is given below:  20 CPP253 – Data Structures Traversing an Array  EX: Write a program to read and display n numbers using an array.  Code: 01_traverse1.c Output: Enter the number of elements in the array: 5 arr = 1 arr = 2 arr = 3 arr = 4 arr = 5 The array elements are 1 2 3 4 5  21 CPP253 – Data Structures Traversing an Array  EX: Write a program to find the mean of n numbers using an array.  Code: 02_traverse2.c Output: Enter the number of elements in the array: 5 arr = 1 arr = 2 arr = 3 arr = 4 arr = 5 The sum of the array elements = 15 The mean of the array elements = 3.00  22 CPP253 – Data Structures Traversing an Array  EX: Write a program to print the position of the smallest number of n numbers using arrays.  Code: 03_traverse3.c Output: Enter the number of elements in the array: 5 Enter the elements: 36 45 68 27 83 The smallest element is: 27 The position of the smallest element in the array is: 3  23 CPP253 – Data Structures Traversing an Array  EX: Write a program to find the second largest of n numbers using an array.  Code: 04_traverse4.c Output: Enter the number of elements in the array: 5 Enter the elements: 36 45 68 27 83 The numbers you entered are: 36 45 68 27 83 The largest of these numbers is: 83 The second largest of these numbers is: 68  24 CPP253 – Data Structures Traversing an Array  EX: Write a program to enter n number of digits. Form a number using these digits.  Code: 05_traverse5.c Output: Enter the number of digits: 4 Enter the digit at position 1: 2 Enter the digit at position 2: 3 Enter the digit at position 3: 0 Enter the digit at position 4: 9 The number is: 9032  25 CPP253 – Data Structures Traversing an Array  EX: Write a program to find whether the array of integers contains a duplicate number.  Code: 06_traverse6.c Output: Enter the number of elements in the array: 5 arr = 1 arr = 2 arr = 3 arr = 2 arr = 5 Duplicate numbers found at locations 1 and 3  26 CPP253 – Data Structures Inserting an Element  Insert element at the end → add 1 to the upper_bound and assign the value  The array should still have empty elements!!!  Algorithm to insert a new element to the end of an array:  Assume an array has been declared as int marks;  We have 55 students, a new students comes and takes the test: marks = 68;  27 CPP253 – Data Structures Inserting an Element  Insert element in the middle → move the elements from their positions to accommodate space for the new element  Insert an element to an array which is arranged in ascending order  Not a trivial task!  Algorithm INSERT will be declared as INSERT(A, N, POS, VAL). The arguments are  A → the array in which the element has to be inserted  N → the number of elements in the array  POS → the position at which the element has to be inserted  VAL → the value that has to be inserted  28 CPP253 – Data Structures Inserting an Element  Algorithm to insert an element in the middle of an array:  In Step 2, a while loop is executed which will move all the elements having an index greater than POS one position towards right to create space for the new element.  29 CPP253 – Data Structures Inserting an Element  Initial Data[] is given as below  Calling INSERT(Data, 6, 3, 100) will lead to the following processing in the array:  30 CPP253 – Data Structures Inserting an Element  EX: Write a program to insert a number at a given location in an array.  Code: 07_insert1.c Output: Enter the number of elements in the array: 5 arr = 1 arr = 2 arr = 3 arr = 4 arr = 5 Enter the number to be inserted: 0 Enter the position at which the number has to be added: 3 The array after insertion of 0 is: arr = 1 arr = 2 arr = 3 arr = 0 arr = 4 arr = 5  31 CPP253 – Data Structures Inserting an Element  EX: Write a program to insert a number in an array that is already sorted in ascending order.  Code: 08_insert2.c Output: Enter the number of elements in the array: 5 arr = 1 arr = 2 arr = 4 arr = 5 arr = 6 Enter the number to be inserted: 3 The array after insertion of 3 is: arr = 1 arr = 2 arr = 3 arr = 4 arr = 5 arr = 6  32 CPP253 – Data Structures Deleting an Element  Delete element from the end → subtract 1 from the upper_bound  Algorithm to delete an element from the end of an array:  Assume an array has been declared as int marks;  We have 54 students, student 54 leaves the course. We just have to decrement the upper_bound. So, upper_bound = 52.  33 CPP253 – Data Structures Deleting an Element  Delete element from the middle → move the elements from their positions to occupy the space of the deleted element  Delete an element from an array which is arranged in ascending order  Not a trivial task!  Algorithm DELETE will be declared as DELETE(A, N, POS). The arguments are  A → the array from which the element has to be deleted  N → the number of elements in the array  POS → the position from which the element has to be deleted  34 CPP253 – Data Structures Deleting an Element  Algorithm to delete an element from the middle of an array <  In Step 2, a while loop is executed which will move all the elements having an index greater than POS one space towards left to occupy the space vacated by the deleted element.  35 CPP253 – Data Structures Deleting an Element  Initial Data[] is given as below  Calling DELETE(Data, 6, 2) will lead to the following processing in the array:  36 CPP253 – Data Structures Deleting an Element  EX: Write a program to delete a number from a given location in an array.  Code: 09_delete1.c Output: Enter the number of elements in the array: 5 arr = 1 arr = 2 arr = 3 arr = 4 arr = 5 Enter the position from which the number has to be deleted: 3 The array after deletion is: arr = 1 arr = 2 arr = 3 arr = 5  37 CPP253 – Data Structures Deleting an Element  EX: Write a program to delete a number from an array that is already sorted in ascending order.  Code: 10_delete2.c Output: Enter the number of elements in the array: 5 arr = 1 arr = 2 arr = 3 arr = 4 arr = 5 Enter the number to be deleted: 3 The array after deletion is: arr = 1 arr = 2 arr = 4 arr = 5  38 CPP253 – Data Structures Merging Two Arrays  Merging arrays → first copy the contents of the first array into the third array and then copy the contents of the second array into the third array  Merging of two unsorted arrays:  39 CPP253 – Data Structures Merging Two Arrays  EX: Write a program to merge two unsorted arrays.  Code: 11_merge1.c Output: Enter the number of elements in the first array: 3 Enter the elements of the first array arr1 = 1 arr1 = 3 arr1 = 5 Enter the number of elements in the second array: 3 Enter the elements of the second array arr2 = 2 arr2 = 4 arr2 = 6 The merged array is arr = 1 arr = 3 arr = 5 arr = 2 arr = 4 arr = 6  40 CPP253 – Data Structures Merging Two Arrays  Merging two sorted arrays into a third sorted array is not a trivial task.  The task of merging can be explained as below:  41 CPP253 – Data Structures Merging Two Arrays  EX: Write a program to merge two sorted arrays.  Code: 12_merge2.c Output: Enter the number of elements in the first array: 3 Enter the elements of the first array arr1 = 1 arr1 = 3 arr1 = 5 Enter the number of elements in the second array: 3 Enter the elements of the second array arr2 = 2 arr2 = 4 arr2 = 6 The merged array is arr = 1 arr = 2 arr = 3 arr = 4 arr = 5 arr = 6  42 CPP253 – Data Structures References  Introduction to Arrays, https://www.geeksforgeeks.org/introduction-to- arrays/  Jenny's Lectures | Arrays, https://www.youtube.com/playlist?list=PLdo5W4Nhv31bbKJzrsKfMpo_grxuLl8 LU  Arrays in Data Structure | Declaration, Initialization, Memory representation, https://youtu.be/AT14lCXuMKI  Array Operations | Traversal, Insertion, https://youtu.be/Bnjbun-hiBk  Array Operations | Deletion from array, https://youtu.be/CMbpZK_xqoc  43 CPP253 – Data Structures That’s all for today!  CPP253 Data Structures Arrays - Part II Öğr. Gör. İhsan Can İÇİUYAN  2 CPP253 – Data Structures Contents  Passing Arrays to Functions  Passing Data Values  Passing Addresses  Passing the Entire Array  Pointers and Arrays  Arrays of Pointers  3 CPP253 – Data Structures Passing Arrays to Functions  We can pass an array to a function.  You may want to pass  individual elements of the array  the entire array  4 CPP253 – Data Structures Passing Data Values  Individual elements can be passed in the same manner as we pass variables of any other data type.  Here, arr evaluates to a single integer value.  The called function hardly bothers whether a normal integer variable is passed to it or an array value is passed.  5 CPP253 – Data Structures Passing Addresses  We can pass the address of an individual array element by preceding the indexed array element with the address operator.  To pass the address of the fourth element of the array to the called function, we will write &arr.  In the called function, the value of the array element must be accessed using the indirection (*) operator.  6 CPP253 – Data Structures Passing the Entire Array  In C, the array name refers to the first byte of the array in the memory.  To pass an entire array to a function → pass the name of the array  A function that accepts an array can declare the parameter in either of the two following ways: func(int arr[]); or func(int *arr);  7 CPP253 – Data Structures Passing the Entire Array  When we pass the name of an array to a function, the address of the first element of the array is copied to the local pointer variable in the function.  When a parameter is declared in a function header as an array, it is interpreted as a pointer to a variable and not as an array.  With this pointer variable you can access all the elements of the array by using the expression: array_name + index  You can also pass the size of the array as another parameter to the function: func(int arr[], int n); or func(int *arr, int n);  8 CPP253 – Data Structures Passing the Entire Array  We can also pass a part of the array known as a sub-array.  If there are 10 elements in the array, and we want to pass the array starting from the third element, then only eight elements would be part of the sub-array.  So the function call can be written as func(&arr, 8);  When you make changes on the array inside called function, those changes will be reflected to the original array.  9 CPP253 – Data Structures Passing the Entire Array  EX: Write a program to read an array of n numbers and then find the smallest number.  Code: 13_pass_array1.c Output: Enter the size of the array: 5 arr = 23 arr = 95 arr = 66 arr = 17 arr = 42 The smallest number in the array is = 17  10 CPP253 – Data Structures Passing the Entire Array  EX: Write a program to interchange the largest and the smallest number in an array.  Code: 14_pass_array2.c Output: Enter the size of the array: 5 arr = 23 arr = 95 arr = 66 arr = 17 arr = 42 The new array is: arr = 23 arr = 17 arr = 66 arr = 95 arr = 42  11 CPP253 – Data Structures Pointers and Arrays  If we have an array declared as int arr[] = {1, 2, 3, 4, 5}; then in memory it would be stored as below: 1000 1004 1008 1012 1016  Array notation is a form of pointer notation.  Name of the array → starting address of the array in memory  Base address → address of arr  12 CPP253 – Data Structures Pointers and Arrays  Let us use a pointer variable as given in the statement below: int *ptr; ptr = &arr;  Here, ptr is made to point to the first element of the array.  Examine the following code: main() { int arr[] = {1, 2, 3, 4, 5}; printf("Address of array = %p %p %p", arr, &arr, &arr); } The name of an array is actually a reference that points to the first element of the array.  13 CPP253 – Data Structures Pointers and Arrays  If pointer variable ptr holds the address of the first element in the array, then the address of successive elements can be calculated by writing ptr++. int *ptr = &arr; ptr++; printf("The value of the second element of the array is %d", *ptr);  If x is an integer variable, then x++; adds 1 to the value of x.  But ptr is a pointer variable, so when we write ptr+i, then adding i gives a pointer that points i elements further along an array than the original pointer.  14 CPP253 – Data Structures Pointers and Arrays  Incrementing a pointer using the unary ++ operator, increments the address it stores by the amount given by sizeof(type) where type is the data type of the variable it points to.  If ptr originally points to arr, then ptr++ will make it to point to the next element, i.e., arr.  Had this been a character array, ptr++ would then add only 1 byte to the address of ptr.  15 CPP253 – Data Structures Pointers and Arrays  An expression like arr[i] is equivalent to writing *(arr+i).  Don't confuse the array name as a pointer. For example, while we can write ptr = arr; // ptr = &arr  we cannot write arr = ptr;  This is because while ptr is a variable, arr is a constant.  The location at which the first element of arr will be stored cannot be changed once arr[] has been declared.  arr[i], i[arr], *(arr+i), *(i+arr) give the same value.  16 CPP253 – Data Structures Pointers and Arrays  EX: Following code modifies the contents of an array using a pointer to an array. int main(void) { int arr[] = {1, 2, 3, 4, 5}; int *ptr, i; ptr = &arr; *ptr = -1; *(ptr + 1) = 0; *(ptr - 1) = 1; printf("\n Array is: "); for(i = 0; i < 5; i++) printf("%d ", *(arr + i)); return 0; } Output: Array is: 1 1 -1 0 5  17 CPP253 – Data Structures Pointers and Arrays  C also permits addition and subtraction of two pointer variables.  Look at the code given below: int main(void) { int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}; int *ptr1, *ptr2; ptr1 = arr; ptr2 = arr + 2; printf("%d", ptr2 - ptr1); return 0; }  The output of this code will be 2. We may subtract two pointers as long as they point to the same array.  C also allows pointer variables to be compared with each other.  18 CPP253 – Data Structures Pointers and Arrays  EX: Following code displays an array of given numbers. int main(void) { int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}; int *ptr1, *ptr2; ptr1 = arr; ptr2 = &arr; while(ptr1 c)  25 CPP253 – Data Structures Logical Operators  Logical OR (||): Logical OR returns a false value if both the operands are false. Otherwise it returns a true value.  EX: The whole expression is true if either b is greater than a or b is greater than c or b is greater than both a and c. (a < b) || (b > c)  26 CPP253 – Data Structures Logical Operators  Logical NOT (!): The logical NOT operator takes a single expression and produces a 0 if the expression evaluates to a non-zero value and produces a 1 if the expression produces a zero.  EX: int a = 10, b; b = !a; Now the value of b = 0. This is because value of a = 10. !a = 0. The value of !a is assigned to b, hence the result.  27 CPP253 – Data Structures Unary Operators  Unary operators act on single operands. C language supports three unary operators. They are unary minus, increment, and decrement operators.  Unary minus (-) operator negates the value of its operand.  EX: int a, b = 10; a = -(b); The result of this expression is a = -10, because variable b has a positive value. After applying unary minus operator (–) on the operand b, the value becomes –10, which indicates it has a negative value.  28 CPP253 – Data Structures Unary Operators  The increment operator (++) is a unary operator that increases the value of its operand by 1.  The decrement operator (--) is a unary operator that decreases the value of its operand by 1.  For example, --x is equivalent to writing x = x – 1.  The increment/decrement operators have two variants: prefix and postfix. In a prefix expression (++x or --x), the operator is applied before the operand while in a postfix expression (x++ or x--), the operator is applied after the operand.  29 CPP253 – Data Structures Unary Operators ++x is not same as x++ --x is not same as x--  For example, int x = 10, y; y = x; y = x++; x = x + 1; x = x + 1; y = ++x; y = x;  30 CPP253 – Data Structures Conditional Operator  The syntax of the conditional operator is exp1 ? exp2 : exp3  exp1 is evaluated first. If it is true, then exp2 is evaluated and becomes the result of the expression, otherwise exp3 is evaluated and becomes the result of the expression.  EX: large = (a > b) ? a : b; The conditional operator is used to find the larger of two given numbers. First exp1, that is a > b, is evaluated. If a is greater than b, then large = a, else large = b. Hence, large is equal to either a or b, but not both.  31 CPP253 – Data Structures Bitwise Operators  Bitwise operators perform operations at the bit level. These operators include: bitwise AND, bitwise OR, bitwise XOR, bitwise NOT and shift operators.  The bitwise AND operator compares each bit of its first operand with the corresponding bit of its second operand. If both bits are 1, the corresponding bit in the result is 1 and 0 otherwise. 10101010 & 01010101 = 00000000  The bitwise OR operator compares each bit of its first operand with the corresponding bit of its second operand. If one or both bits are 1, the corresponding bit in the result is 1 and 0 otherwise. 10101010 | 01010101 = 11111111  32 CPP253 – Data Structures Bitwise Operators  The bitwise XOR operator compares each bit of its first operand with the corresponding bit of its second operand. If one of the bits is 1, the corresponding bit in the result is 1 and 0 otherwise. 10101010 ^ 01010101 = 11111111  The bitwise NOT operator is a unary operator that performs logical negation on each bit of the operand. Bitwise NOT operator sets the bit to 1 if it was initially 0 and sets it to 0 if it was initially 1. ~10101011 = 01010100  33 CPP253 – Data Structures Bitwise Operators  C supports two bitwise shift operators. They are shift left (). The syntax for a shift operation can be given as operand op num where the bits in the operand are shifted left or right depending on the operator (left, if the operator is >) by number of places denoted by num. x = 0001 1101 x 1 result = 0000 1110 x >> 4 result = 0000 0001 The expression x > y is equivalent to division of x by 2^y if x is unsigned or has a non-negative value.  34 CPP253 – Data Structures Assignment Operators  In C language, the assignment operator is responsible for assigning values to the variables.  While the equal sign (=) is the fundamental assignment operator, C also supports other assignment operators that provide shorthand ways to represent common variable assignments. int x; x = 10; a = b = c = 10; (a = (b = (c = 10)));  35 CPP253 – Data Structures Comma Operator  The comma operator takes two operands. It works by evaluating the first expression and discarding its value, and then evaluates the second expression and returns the value as the result of the expression.  Comma-separated expressions when chained together are evaluated in left-to-right sequence with the right-most value yielding the result of the expression.  EX: int a = 2, b = 3, x = 0; x = (++a, b+=a); Now, the value of x = 6.  36 CPP253 – Data Structures sizeof Operator  sizeof is a unary operator used to calculate the size of data types. This operator can be applied to all data types.  When using this operator, the keyword sizeof is followed by a type name, variable, or expression. The operator returns the size of the data type, variable, or expression in bytes.  For example, sizeof(char) returns 1, that is the size of a character data type.  EX: int a = 10; unsigned int result; result = sizeof(a); then result = 4, that is, space required to store the variable a in memory. Since a is an integer, it requires 4 bytes of storage space.  37 CPP253 – Data Structures Operator Precedence Chart  Following table lists the operators that C language supports in the order of their precedence (highest to lowest). The associativity indicates the order in which the operators of equal precedence in an expression are evaluated.  38 CPP253 – Data Structures Operator Precedence Chart  If we have the following variable declarations: then  39 CPP253 – Data Structures Operators and Expressions  EX: Write a program to calculate the area of a circle. #include int main(void) { float radius; double area; printf("\n Enter the radius of the circle: "); scanf("%f", &radius); area = 3.14 * radius * radius; printf("\n Area = %.2lf", area); return 0; } Output: Enter the radius of the circle: 7 Area = 153.86  40 CPP253 – Data Structures Type Conversion and Type Casting  Type conversion or typecasting of variables refers to changing a variable of one data type into another.  Type conversion → implicitly Typecasting → explicitly  Type conversion is done when the expression has variables of different data types. So to evaluate the expression, the data type is promoted from lower to higher level where the hierarchy of data types can be given as: double, float, long, int, short, and char float x;  EX: int y = 3; x = y; Now, x = 3.0, as integer value is automatically converted into its equivalent floating point representation.  41 CPP253 – Data Structures Type Conversion and Type Casting  42 CPP253 – Data Structures Type Conversion and Type Casting  Typecasting is also known as forced conversion. It is done when the value of one data type has to be converted into the value of another data type.  EX: The code to perform typecasting can be given as: float salary = 9875.63; int sal = (int) salary;  When floating point numbers are converted to integers, the digits after decimal are truncated. Therefore, data is lost when floating point representations are converted to integral representations.  Typecasting can be done by placing the destination data type in parentheses followed by the variable name that has to be converted.  43 CPP253 – Data Structures Type Conversion and Type Casting  44 CPP253 – Data Structures Type Conversion and Type Casting  EX: Write a program to convert an integer into the corresponding floating point number. #include int main(void) { float f_num; int i_num; printf("\n Enter any integer: "); scanf("%d", &i_num); f_num = (float)i_num; printf("\n The floating point variant of %d is = %f", i_num, f_num); return 0; } Output: Enter any integer: 56 The floating point variant of 56 is = 56.000000  45 CPP253 – Data Structures References  Course Description Page, https://ebs.aydin.edu.tr/index.iau?Page=DersTanitimFormu2&Action =DersTanitimFormuView&bolum_kodu=54&DersID=12532&innerPage =tumu&ln=en  Dev-C++ 5.11, http://orwelldevcpp.blogspot.com  https://www.cprogramming.com/  https://www.tutorialspoint.com/cprogramming/index.htm  https://www.learn-c.org/  46 CPP253 – Data Structures That’s all for today!  CPP253 Data Structures C Programming - Part II Öğr. Gör. İhsan Can İÇİUYAN  2 CPP253 – Data Structures Contents  Control Statements  Decision Control Statements  if Statement  if-else Statement  if-else-if Statement  switch-case Statement  Iterative Statements  while Loop  do-while Loop  for Loop  Jump Statements  break Statement  continue Statement  3 CPP253 – Data Structures Control Statements  Control flow statements enable programmers to conditionally execute a particular block of code.  There are three types of control statements:  Decision control (branching)  Iterative (looping)  Jump statements  Branching means deciding what actions have to be taken.  Looping decides how many times the action has to be taken.  Jump statements transfer control from one point to another point.  4 CPP253 – Data Structures Decision Control Statements  C supports decision control statements that can alter the flow of a sequence of instructions.  These statements help to jump from one part of the program to another depending on whether a particular condition is satisfied or not.  These decision control statements include:  if statement  if–else statement  if–else–if statement  switch–case statement  5 CPP253 – Data Structures if Statement  if statement is the simplest decision control statement that is frequently used in decision making.  The general form of a simple if statement is shown below:  6 CPP253 – Data Structures if Statement  First the test expression is evaluated. If the test expression is true, the statements of the if block are executed, otherwise these statements will be skipped and execution will jump to statement x.  EX: #include int main(void) { int x = 10; if(x > 0) x++; printf("\n x = %d", x); return 0; } The output of this program is x = 11. NB: Observe that the printf statement will be executed even if the test expression is false.  7 CPP253 – Data Structures if-else Statement  What if you want a separate set of statements to be executed if the expression returns a false value? In such cases, we can use an if– else statement rather than using a simple if statement. The general form of simple if–else statement is shown below:  8 CPP253 – Data Structures if-else Statement  EX: Write a program to find whether a number is even or odd. #include int main(void) { int a; printf("\n Enter the value of a: "); scanf("%d", &a); if(a % 2 == 0) printf("\n %d is even.", a); else printf("\n %d is odd.", a); return 0; } Output: Enter the value of a: 6 6 is even.  9 CPP253 – Data Structures if-else-if Statement  C language supports if–else–if statements to test additional conditions apart from the initial test expression. The if–else–if construct works in the same way as a normal if statement. Its construct is given below:  10 CPP253 – Data Structures if-else-if Statement  EX: The following code tests whether a number entered by the user is negative, positive, or equal to zero. #include int main(void) { int num; printf("\n Enter any number: "); scanf("%d", &num); if(num == 0) printf("\n The number is equal to zero."); else if(num > 0) printf("\n The number is positive."); else printf("\n The number is negative."); return 0; }  11 CPP253 – Data Structures switch-case Statement  A switch-case statement is a multi-way decision statement that is a simplified version of an if–else–if block. The general form of a switch statement is shown below:  12 CPP253 – Data Structures switch-case Statement  switch statements are mostly used in two situations:  When there is only one variable to evaluate in the expression  When many conditions are being tested for  switch-case statements are often used as an alternative to long if statements that compare a variable to several ‘integral’ values (integral values are those values that can be expressed as an integer, such as the value of a char).  default is the case that is executed when the value of the variable does not match with any of the values of the case statements.  The break statement must be used at the end of each case because if it is not used, then the case that matched and all the following cases will be executed.  13 CPP253 – Data Structures switch-case Statement  switch–case statement is preferred by programmers due to the following reasons:  Easy to debug  Easy to read and understand  Ease of maintenance as compared to its equivalent if–else statements  Like if–else statements, switch statements can also be nested  Executes faster than its equivalent if–else construct  14 CPP253 – Data Structures switch-case Statement  EX: Write a program to determine whether the entered character is a vowel or not. #include int main(void) { char ch; printf("\n Enter any character: "); scanf("%c", &ch); switch(ch) { case 'A': case 'a': printf("\n %c is vowel.", ch); break; case 'E': case 'e': printf("\n %c is vowel.", ch); break; case 'I': case 'i':  15 CPP253 – Data Structures switch-case Statement  EX (cont.): Write a program to determine whether the entered character is a vowel or not. printf("\n %c is vowel.", ch); break; case 'O': case 'o': printf("\n %c is vowel.", ch); break; case 'U': case 'u': printf("\n %c is vowel.", ch); break; default: printf("\n %c is not a vowel.", ch); } return 0; } Output: Enter any character: j j is not a vowel.  16 CPP253 – Data Structures Iterative Statements  Iterative statements are used to repeat the execution of a sequence of statements until the specified expression becomes false.  C supports three types of iterative statements also known as looping statements. They are:  while loop  do–while loop  for loop  17 CPP253 – Data Structures while Loop  The while loop provides a mechanism to repeat one or more statements while a particular condition is true. Following figure shows the syntax and general form of a while loop.  18 CPP253 – Data Structures while Loop  In the while loop, the condition is tested before any of the statements in the statement block is executed.  If the condition is true, only then the statements will be executed, otherwise if the condition is false, control will jump to statement y.  We need to constantly update the condition of the while loop. It is this condition which determines when the loop will end.  If the condition is never updated and the condition never becomes false, then the computer will run into an infinite loop.  19 CPP253 – Data Structures while Loop  EX: The following code prints the first 10 numbers using a while loop. #include int main(void) { int i = 1; while(i