CU-BCA-SEM-III-DATA STRUCTURES- Second Draft-converted

BACHELOR OF COMPUTER APPLICATIONS SEMESTER III DATA STRUCTURES BCA131

CHANDIGARH UNIVERSITY Institute of Distance and Online Learning Course Development Committee Prof. (Dr.) R.S.Bawa Pro Chancellor, Chandigarh University, Gharuan, Punjab Advisors Prof. (Dr.) Bharat Bhushan, Director – IGNOU Prof. (Dr.) Majulika Srivastava, Director – CIQA, IGNOU Programme Coordinators & Editing Team Master of Business Administration (MBA) Bachelor of Business Administration (BBA) Coordinator – Dr. Rupali Arora Coordinator – Dr. Simran Jewandah Master of Computer Applications (MCA) Bachelor of Computer Applications (BCA) Coordinator – Dr. Raju Kumar Coordinator – Dr. Manisha Malhotra Master of Commerce (M.Com.) Bachelor of Commerce (B.Com.) Coordinator – Dr. Aman Jindal Coordinator – Dr. Minakshi Garg Master of Arts (Psychology) Bachelor of Science (Travel &Tourism Management) Coordinator – Dr. Samerjeet Kaur Coordinator – Dr. Shikha Sharma Master of Arts (English) Bachelor of Arts (General) Coordinator – Dr. Ashita Chadha Coordinator – Ms. Neeraj Gohlan Academic and Administrative Management Prof. (Dr.) R. M. Bhagat Prof. (Dr.) S.S. Sehgal Executive Director – Sciences Registrar Prof. (Dr.) Manaswini Acharya Prof. (Dr.) Gurpreet Singh Executive Director – Liberal Arts Director – IDOL © No part of this publication should be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording and/or otherwise without the prior written permission of the authors and the publisher. SLM SPECIALLY PREPARED FOR CU IDOL STUDENTS Printed and Published by: TeamLease Edtech Limited www.teamleaseedtech.com CONTACT NO:- 01133002345 For: CHANDIGARH UNIVERSITY 2 Institute of Distance and Online Learning CU IDOL SELF LEARNING MATERIAL (SLM)

First Published in 2021 All rights reserved. No Part of this book may be reproduced or transmitted, in any form or by any means, without permission in writing from Chandigarh University. Any person who does any unauthorized act in relation to this book may be liable to criminal prosecution and civil claims for damages. This book is meant for educational and learning purpose. The authors of the book has/have taken all reasonable care to ensure that the contents of the book do not violate any existing copyright or other intellectual property rights of any person in any manner whatsoever. In the event the Authors has/ have been unable to track any source and if any copyright has been inadvertently infringed, please notify the publisher in writing for corrective action. CONTENTS 3 CU IDOL SELF LEARNING MATERIAL (SLM)

Unit 1: Introduction To Data Structures ....................................................................................5 Unit 2: Arrays 1 .......................................................................................................................22 Unit 3: Arrays 2 .......................................................................................................................44 Unit 4: Structures .....................................................................................................................55 Unit 5: Stacks 1........................................................................................................................70 Unit 6: Stacks 2........................................................................................................................77 Unit 7: Applications Of Stacks ................................................................................................87 Unit 8: Queues .......................................................................................................................102 Unit 9: Memory Representation.............................................................................................109 Unit 10: Linked List...............................................................................................................125 Unit 11: Types Of Linked List...............................................................................................139 Unit 12: Tree ..........................................................................................................................154 Unit 13: Binary Search Tree ..................................................................................................175 Unit 14: Graph .......................................................................................................................205 Unit 15: Sorting......................................................................................................................222 4 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 1: INTRODUCTION TO DATA STRUCTURES Structure 1.0 Learning Objective 1.1 Characteristics and Operations 1.2 Types of Data Structures 1.3 Space Complexity 1.4 Time Complexity 1.5 Abstract Data Types 1.6 Summary 1.7 Keywords 1.8 Learning activity 1.9 Unit End Questions 1.10 References 1.0 LEARNING OBJECTIVE After studying this unit, the student will be able to: ▪ Learn data structure operations and their implementations. ▪ Become familiar with mathematical calculations of time complexity and space complexity. ▪ Describe abstract data type. 1.1 CHARACTERISTICS AND OPERATIONS Data Structures are the most a part of many computing algorithms as they allow the programmers to handle the info in an efficient way. It plays an important role in enhancing the performance of the software or a program because the main function of the software is to store and retrieve the user's data as fast as possible. the subsequent terms are the inspiration characteristics of a knowledge structure. 1. Correctness 2. Time Complexity 3. Space Complexity 5 CU IDOL SELF LEARNING MATERIAL (SLM)

Correctness − Data structure implementation should implement its interface correctly. Time Complexity − Running time or the execution time of operations of the data structure must be as small as possible. It is defined as the number of times a particular instruction set is executed rather than the total time is taken. It is because the entire time taken also depends on some external factors just like the compiler used, processor’s speed, etc. Time requirements are often denoted or defined as a numerical function ������(������),, where ������(������) are often measured because the number of steps, provided each step takes constant time. For example, within the case of the addition of two n-bit integers, N steps are taken. Consequently, the entire computational time is ������(������) = ������ ∗ ������ t(N) where c is that the time consumed for the addition of two bits. Here, we observe that ������(������) grows linearly as input size increases. Space Complexity - It is the entire memory space required by the program for its execution. Memory usage of a knowledge structure operation should be as little as possible. a hard and fast part may be a space required to store certain data and variables (i.e., simple variables and constants, program size etc.), that aren't hooked in to the dimensions of the matter. for instance, recursion stack space, dynamic memory allocation etc. Space complexity S(p) of any algorithm p is ������(������) = ������ + ������������(������) Where A is treated because the fixed part and ������������(������) is treated because the variable a part of the algorithm which depends on instance characteristic I. Operations on Data Structure: Different types of operations can be performed for the manipulation of data in every data structure. Some common operations are given below: 1. Traversing 2. Searching 3. Insertion 4. Deletion 5. Sorting 6. Merging 1. Traversing: Traversing a Data Structure means visiting the element stored in it. This can be done with any type of DS. Below is the program to illustrate traversal in an array: 6 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 1.1: Tree Traversing 2. Searching: Searching means finding a particular element in the given data-structure. It is considered successful when the required element is found. Searching is the operation that we can perform on data-structures like an array, linked-list, tree, graph, etc. 3. Insertion: It is the operation that we apply to all the data-structures. Insertion means to add an element in the given data structure. The operation of insertion is successful when the specified element is added to the specified data-structure. it's unsuccessful in some cases when the dimensions of the info structure are full and when there's no space within the data- structure to feature any additional element. The insertion has an equivalent name as an insertion within the data-structure as an array, linked-list, graph, tree. In stack, this operation is named Push. within the queue, this operation is named Enqueue. 4. Deletion: It is the operation that we apply to all the data-structures. Deletion means deleting an element in the given data structure. The operation of deletion is successful when the required element is deleted from the data structure. The deletion has the same name as a deletion in the data-structure as an array, linked-list, graph, tree, etc. In stack, this operation is called Pop. In Queue this operation is called Dequeue. 5. Sorting: The process of arranging the info structure during a specific order is understood as Sorting. Many algorithms are often wont to perform sorting, for instance, insertion sort, selection sort, bubble sort, etc. 6.Merging: When two lists List A and List B of size M and N respectively, of comparable sort of elements, clubbed or joined to supply the third list, List C of size (M+N), then this process is named merging. 7 CU IDOL SELF LEARNING MATERIAL (SLM)

1.2 TYPES OF DATA STRUCTURES Data structures are a very important programming concept. They provide us with a means to store, organize and retrieve data in an efficient manner. The data structures are used to make working with our data, easier. Many data structures help us with this. Types of Data Structures: data structures are mainly classified into the followings Figure 1.2: Types of Data Structure Primitive Data structures The primitive data structures are primitive data types. The int, char, float, double, and pointer are the primitive data structures that can hold a single value. The pointers, however, don’t hold a data value, instead, they hold memory addresses of the data values. These are also called reference data types. Non-Primitive Data structures The non-primitive data structures can be performed with the primitive data structures. Although, they too are provided by the system itself yet they have derived data structures and cannot be formed without using the primitive data structures. The Non-primitive data structures are further divided into the following categories: 1. Linear data structure 2. Non -Linear data structure Linear data structure In linear data structure elements are stored physically or logically next to each other in order. Ex Array is a linear data structure and List. 8 CU IDOL SELF LEARNING MATERIAL (SLM)

Static data structure: It is a kind of knowledge structure where the dimensions is allocated at the compile time. Therefore, the utmost size is fixed. Dynamic data structure: It is a kind of knowledge structure where the dimensions is allocated at the run time. Therefore, the utmost size is flexible Array: Arrays are a homogeneous and contiguous collection of the same data types. They have a static memory allocation technique, which means, if memory space is allocated for once, it cannot be changed during runtime. The arrays are wont to implement vectors, matrices and also other data structures. If we don't know the memory to be allocated beforehand then the array can cause wastage of memory. Also, insertions and deletions are complex in arrays since elements are stored in consecutive memory allocations. Figure 1.3: Linear Data Structure Static Representation Linked list: The lists support dynamic memory allocation. The memory space allocated can be changed at the run time also. The linked lists are those which have the elements stored in logically sequential order. The insertions and deletions are easier in the lists. Figure 1.4: Linear Data Structure Dynamic Representation 9 CU IDOL SELF LEARNING MATERIAL (SLM)

Stacks: The stack follows a Last in First Out technique for retrieving and storing the elements. The element which is stored at the end will be the first one to be retrieved from the stack. The stack has the following functions: 1. Push (int): To insert an element in the stack. 2. Pop (): To remove an element from the stack. Queues: The queues follow the First In First Out mechanism for storing and retrieving elements. The elements which are stored first into the queue will only be the primary elements to be removed out from the queue. The “ENQUEUE” operation is employed to insert a component into the queue whereas the “DEQUEUE” operation is employed to get rid of a component from the queue Non-Linear data structure In a non-linear arrangement, data elements are hierarchically connected and are present at various levels. Ex Graph and Trees are Non-linear arrangement. The non-linear lists don't have elements stored during a certain manner. Graphs: The Graph arrangement is employed to represent a network. It comprises vertices and edges (to connect the vertices). The graphs are very useful when it involves studying a network. Figure 1.5: Graph Representation Trees: Tree arrangement comprises nodes connected during a particular arrangement and that they (particularly binary trees) make search operations on the info items easy. The tree data structures contain a root node which is further divided into various child nodes then on. . Figure 1.6: Tree Representation 10 CU IDOL SELF LEARNING MATERIAL (SLM)

1.3 SPACE COMPLEXITY The space complexity of an algorithm represents the amount of memory space needed by the algorithm in its life cycle. Space needed by an algorithm is equal to the sum of the following two components A fixed part is a space required to store certain data and variables (i.e. simple variables and constants, program size etc.), that are not dependent on the size of the problem. A variable part is a space required by variables; whose size is dependent on the size of the problem. For example, recursion stack space, dynamic memory allocation etc. Space complexity S(p) of any algorithm p is ������(������) = ������ + ������������(������) Where A is treated as the fixed part and ������������(������) is treated as the variable part of the algorithm which depends on instance characteristic I. Following is a simple example that tries to explain the concept Algorithm int findSum(int P, int Q) { int sum; // creating the sum variable R = P + Q; // storing the sum of a and b return sum; // returning the sum variable } Here we have three variables P, Q and R and one constant. Hence ������(������) = 1 + 3. Now space is dependent on data types of given constant types and variables and it will be multiplied accordingly. 1.4 TIME COMPLEXITY Tree arrangement comprises nodes connected during a specific arrangement which they (particularly binary trees) make search operations on the data items easy. The tree data structures contain a root node which is further divided into various child nodes than on. 11 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 1.7: Time Complexity The most popular method for determining time complexity is to count the amount of elementary steps taken by every algorithm to finish execution. As within the previous example, the primary code will run the loop n times, leading to time complexity of a minimum of n, and because the value of n increases, the time taken also will increase. While for the second code, the time complexity is constant, because it'll never be hooked in to the worth of n, it'll always give the end in 1 step. Taking the previous algorithm forward, above we've a little logic of Quick Sort.Now in Quick Sort, we divide the list into halves whenever, but we repeat the iteration whenever, ere N is that the size of the list). Hence time complexity is going to be N*log (N). The time period consists of N loops (iterative or recursive) that are logarithmic, thus the algorithm may be a combination of linear and logarithmic. And since the algorithm's performance may vary with differing types of input file, hence for an algorithm we usually use the worst-case Time complexity of an algorithm because that's the utmost time taken for any input size. Table 1.1: Comparison of Time Complexity Data structure Access Search Insertion Deletion Array O(1) O(N) O(N) O(N) Stack O(N) O(N) O(1) O(1) Queue O(N) O(N) O(1) O(1) Singly Linked list O(N) O(N) O(1) O(1) 12 CU IDOL SELF LEARNING MATERIAL (SLM)

Doubly Linked List O(N) O(N) O(1) O(1) Hash Table O(1) O(1) O(1) O(1) O(log N) O(log N) O(log N) O(log N) Binary Search Tree O(log N) O(log N) O(log N) O(log N) AVL Tree O(log N) O(log N) O(log N) O(log N) B Tree O(log N) O(log N) O(log N) O(log N) Red Black Tree 1.5 ABSTRACT DATA TYPES Abstract Data Type (ADT) is a type (or class) for objects whose behaviour is defined by a set of value and a set of operations. The definition of ADT only mentions what operations are to be performed but not how these operations are going to be implemented. It doesn't specify how data are going to be organized in memory and what algorithms are going to be used for implementing the operations. it's called “abstract” because it gives an implementation-independent view. the method of providing only the essentials and hiding the small print is understood as abstraction. Figure 1.8: Abstract Data Type 13 CU IDOL SELF LEARNING MATERIAL (SLM)

1.List ADT: The data is usually stored during a key sequence during a list that features a head structure consisting of count, pointers and address of compare function needed to match the info within the list . Figure 1.9: List ADT The data node contains the pointer to a data structure and a self-referential pointer which points to the next node in the list. struct Node 14 { int data; struct node *link; } Node; typedef struct { int count; Node *pos; Node *head; Node *rear; int (*compare) (void *argument1, void *argument2) } LIST; List ADT Type Definitions: CU IDOL SELF LEARNING MATERIAL (SLM)

The List ADT Functions is given below: Figure 1.10: List ADT Function A list contains elements of the same type arranged in sequential order and the following operations can be performed on the list. 1. get() – Return an element from the list at any given position. 2. insert() – Insert an element at any position of the list. 3. remove() – Remove the first occurrence of any element from a non-empty list. 4. remove At () – Remove the element at a specified location from a non-empty list. 5. replace() – Replace an element at any position by another element. 6. size() – Return the number of elements in the list. 7. isEmpty() – Return true if the list is empty, otherwise return false. 8. isFull() – Return true if the list is full, otherwise return false. 2. Stack ADT In Stack ADT Implementation instead of data being stored in each node, the pointer to data is stored. The program allocates memory for the data and the address is passed to the stack ADT. The head node and the data nodes are encapsulated in the ADT. The calling function can only see the pointer to the stack. 15 CU IDOL SELF LEARNING MATERIAL (SLM)

The stack head structure also contains a pointer to the top and a count of the number of entries currently in the stack Figure 1.11: Stack Conceptual and Physical Structure typedef struct node { int *DataPtr; struct node *link; } StackNode; typedef struct { int count; StackNode *top; } STACK; Stack ADT Type Definitions : A Stack contains elements of the same type arranged in sequential order. All operations take place at a single end that is top of the stack and the following operations can be performed: 1. push() – Insert an element at one end of the stack called top. 2. pop() – Remove and return the element at the top of the stack, if it is not empty. 3. peek() – Return the element at the top of the stack without removing it, if the stack is not empty. 16 CU IDOL SELF LEARNING MATERIAL (SLM)

4. size() – its return the number of elements in the stack. 5. isEmpty() – Return true if the stack is empty, otherwise return false. 6. isFull() – Return true if the stack is full, otherwise return false. 3. Queue ADT The queue abstract data type (ADT) follows the basic design of the stack abstract data type. Figure 1.12: Queue Conceptual and Physical Structure Figure 1.13: Queue Physical Structure Each node contains a void pointer to the data and the link pointer to the next element in the queue. The program’s responsibility is to allocate memory for storing the data. Queue ADT Type Definitions : typedef struct node { int DataPtr; struct node *next; } QueueNode; 17 CU IDOL SELF LEARNING MATERIAL (SLM)

typedef struct { QueueNode *front; QueueNode *rear; int count; } QUEUE; A Queue contains elements of the same type arranged in sequential order. Operations take place at both ends, insertion is done at the end and deletion is done at the front. Following operations can be performed: 1. enqueue() – Insert an element at the end of the queue. 2. dequeue() – Remove and return the first element of the queue, if the queue is not empty. 3. peek() – Return the element of the queue without removing it, if the queue is not empty. 4. size() – Return the number of elements in the queue. 5. isEmpty() – Return true if the queue is empty, otherwise return false. 6. isFull() – Return true if the queue is full, otherwise return false. From these definitions, we can see that the definitions do not specify how these ADTs will be represented and how the operations will be carried out. There can be different ways to implement an ADT, for example, the List ADT can be implemented using arrays, or singly linked list or a doubly-linked list. Similarly, stack ADT and Queue ADT can be implemented using arrays or linked lists. 1.6 SUMMARY • This chapter gives some hints on how to define a data structure. A data structure is a particular way of organizing data in a computer so that it can be used effectively. The data structure name indicates itself that organizing the data in memory. • Some examples of Data Structures are arrays, Linked List, Stack, Queue, etc. Data Structures are widely used in almost every aspect of Computer Science i.e. Operating System, Compiler Design, Artificial intelligence, Graphics and many more. • Characteristics of a data structure: Correctness, Time Complexity, Space Complexity. 18 CU IDOL SELF LEARNING MATERIAL (SLM)

• Different types of operations can be performed for the manipulation of data in every data structure: Traversing, Searching, Insertion, Deletion. • Space complexity: An algorithm represents the amount of memory space needed by the algorithm in its life cycle. Space needed by an algorithm is equal to the sum of the following two components. • Time complexity: of an algorithm signifies the total time required by the program to run till its completion. The time complexity of algorithms is most commonly expressed using the big O notation. 1.7 KEYWORDS • Correctness − Data structure implementation should implement its interface correctly. • Time Complexity − Running time or the execution time of operations of the data structure must be as small as possible. • Space Complexity − Memory usage of a data structure operation should be as little as possible. • Operations: • Search − Algorithm to search an item in a data structure. • Sort − Algorithm to sort items in a certain order. • Insert − Algorithm to insert an item in a data structure. • Update − Algorithm to update an existing item in a data structure. • Delete − Algorithm to delete an existing item from a data structure. 1.8 LEARNING ACTIVITY The Josephus problem is the following game: N people, numbered to N, are sitting in a circle. Starting at person 1, a hot potato is passed. After M passes, the person holding the hot potato is eliminated, the circle closes ranks, and the game continues with the person who was sitting after the eliminated person picking up the hot potato the last remaining person wins. Thus , if M =0 and N5 , the order of eliminations is 2,4,1,5. What is the running time of your program? ___________________________________________________________________________ ____________________________________________________________________ 1.9 UNIT END QUESTIONS 19 CU IDOL SELF LEARNING MATERIAL (SLM)

A. Descriptive Questions Short Questions 1. Define ADT 2. List the characteristic of Data Structure. 3. What is space complexity and Time Complexity? 4. What is Linear Data Structure? 5. Difference between linear and Non-Linear Data Structure. Long Questions 1. Explain in details about Abstract Data Type 2. Give some example of Linear Data Structure and Non-Linear Data Structure 3. What are Data structures and Explain the types? 4. Explain in details Space Complexity. 5. Give an example of Time Complexity B. Multiple choice Questions 1. Which of the following is a non-liner data structure? a. Stacks b. List c. Strings d. Trees 2. Which of the following data structure is linear type? a. Graph b. Trees c. Binary tree d. Stack 3. Which of the following is true about the characteristics of abstract data types? 20 I. It exports a type. II. It exports a set of operations a. True, False b. False, True CU IDOL SELF LEARNING MATERIAL (SLM)

c. True, True d. False, False 4. The complexity of linear search algorithm is _________ a. O(n) b. O(log n) c. O(n2) d. O(n log n) 5. The complexity of Binary search algorithm is _________ a. O(n) b. O(log) c. O(n2) d. O(n log n) Answer 1. (d) 2. (d) 3. (c) 4. (a) 5. (b) 1.10 REFERENCES Reference Books: • R1 Trembley & Soreson, Introduction to Data Structures Applications, Second Edition, Pearson Education. • R2 A. Tannenbaum, Y. Lanhgsam and A.J. Augenstein, Data Structures Using C++, Prentice Hall of India. Text Books: • T1 Schaum's Outlines Series- Data Structures, Seymour Lipschutz, TMH. • T2 E. Balagarusamy, Data Structure using C/C++, Tata McGraw-Hill Education. Websites: • https://www.geeksforgeeks.org/ • https://www.tutorialspoint.com/ 21 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 2: ARRAYS 1 Structure 2.0 Learning Objective 2.1 Introduction 2.2 Operations on Arrays 2.3 Summary 2.4 Keywords 2.5 Learning activity 2.6 Unit End Questions 2.7 References 2.0 LEARNING OBJECTIVE After studying this unit, the student will be able to: ▪ Implement array structure and memory representation. ▪ Know how to declare and initialize an array. ▪ Implement an array of operations ▪ Elaborate advantage and disadvantages of array. 2.1 INTRODUCTION An array may be a quite arrangement which will store a fixed-size sequential collection of elements of an equivalent type. An array is employed to store a set of knowledge, but it's often more useful to consider an array as a set of variables of an equivalent type. Figure 2.1: Array Representation Instead of declaring individual variables, like number0, number1, ..., and number99, you declare one array variable like numbers and use numbers [0], numbers [1], and ..., numbers [99] to represent individual variables. a selected element in an array is accessed by an index (or) index. 22 CU IDOL SELF LEARNING MATERIAL (SLM)

All arrays consist of contiguous memory locations. The lowest address corresponds to the first element and the highest address to the last element. Declare an Array: To declare an array in C, a programmer specifies the type of the elements and the number of elements required by an array as follows. Syntax: dataType arrayName[arraySize]; Example: int marks[5]; This is called a single-dimensional array. The arraySize must be an integer constant greater than zero and the type can be any valid primitive data type. Here, we declared an array, mark, of integer type. And its size is 5. Meaning, it can hold 5 integer values. It's important to note that the size and type of an array cannot be changed once it is declared. Initializing Arrays: Initialize an array either one by one or using a single statement as follows. int marks[5] = { 19, 10, 18, 17, 9}; initialize an array like this: The number of values between braces { } cannot be larger than the number of elements that we declare for the array between square brackets [ ]. If you omit the size of the array, an array just big enough to hold the initialization is created. Therefore, if you write int marks[] = { 19, 10, 18, 17, 9}; Here, we haven't specified the size. However, the compiler knows its size is 5 as we are initializing it with 5 elements. Another way of assigning the array int marks[2] = 8; Here, Figure 2.2: Array Memory Representation CU IDOL SELF LEARNING MATERIAL (SLM) 23

marks[0] is equal to 19 marks[1] is equal to 10 marks[2] is equal to 8 marks[3] is equal to 17 marks[4] is equal to 9 Accessing Array Elements: You can access the array elements with the help of an array index. Suppose you declared an array mark as above. marks [0] is the first element of an array, marks [1] is the second element of an array and so on. Arrays have 0 as the first index, not 1. In this example, marks [0] is the first element. If the size of an array is n, to access the last element, the n-1 index is used. In this example, mark[4] Example: int stud_mark = marks[3]; The above statement will take the 4th element from the array and assign the value to stud_mark variable. Input and Output Array Elements: Here's how you can take input from the user and store it in an array element. take input and store it in the 3rd element scanf(\"%d\", &marks[2]); take input and store it in the ith element scanf(\"%d\", &marks[i-1]); Access elements out of their bound: Suppose you declared an array of 10 elements. int marks[5]; we can access the array elements from marks[0] to marks[4].Now let's say if you try to access marks[12]. The element is not available. This may cause unexpected output (undefined behavior). Sometimes you might get an error and some other time your program may run correctly. Hence, you should never access elements of an array outside of its bound. #include <stdio.h> int main () { int Element[ 5 ]; /* n is an array of 5 integers */ int i,j; /* initialize elements */ 24 CU IDOL SELF LEARNING MATERIAL (SLM)

for ( i = 0; i < 5; i++ ) { Element[ i ] = i + 100; } /* output of array element's value */ for (j = 0; j < 5; j++ ) { printf(\"Element[%d] = %d\\n\", j, Element[j] ); } return 0; } When the above code is compiled and executed, it produces the following result – Element[0] = 100 Element[1] = 101 Element[2] = 102 Element[3] = 103 Element[4] = 104 MULTI-DIMENSIONAL ARRAYS: In C programming, you can create an array of arrays. These arrays are known as multidimensional arrays. C programming language allows multidimensional arrays. Syntax: type name[size1][size2]...[sizeN]; Example: int three_dimensional[5][10][4]; Two-dimensional Arrays: The simplest sort of multidimensional array is that the two-dimensional array. A two- dimensional array is, in essence, an inventory of one-dimensional arrays. To declare a two- dimensional array of size [x][y] Syntax: type arrayName [ x ][ y ]; 25 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 2.3: Two-dimensional array Representation Initializing Two-Dimensional Arrays: Multidimensional arrays could also be initialized by specifying bracketed values for every row. Following is an array with 3 rows and every row has 4 columns. int a[3][4] = { {0, 1, 2, 3} , {4, 5, 6, 7} , {8, 9, 10, 11} }; The nested braces, which indicate the intended row, are optional. The following initialization is equivalent to the previous example: int a[3][4] = {0,1,2,3,4,5,6,7,8,9,10,11}; Accessing Two-Dimensional Array Elements: An element in a two-dimensional array is accessed by using the subscripts, i.e., row index and column index of the array. For example – int val = a[2][3]; The above statement will take the 4th element from the 3rd row of the array. You can verify it in the above figure. Let us check the following program where we have used a nested loop to handle a two-dimensional array. Three Dimensional Arrays: Three Dimensional arrays are initialised, accessed and processed similar to the two-dimensional arrays shown above. Exempting, two square braces will not be used in the code, rather there will be three square braces used in the code for the three-dimensional arrays. For example – int a[2][4][3]; 26 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 2.4: 1D,2D and 3D array Representation ARRAYS AND FUNCTIONS: single-dimension arrays can be passed as an argument in a function, you would have to declare a formal parameter in one of the following three ways and all three declaration methods produce similar results because each tells the compiler that an integer pointer is going to be received. Similarly, you can pass multi-dimensional arrays as formal parameters. Way-1 : Formal parameters as a pointer void Function(int *par) { //Statement 1 //Statement 2 } Way-2 : Formal parameters as a sized array void Function(int par[10]) { //Statement 1 //Statement 2 } Way-3 : Formal parameters as an unsized array void Function(int par[]) { //Statement 1 //Statement 2 } 27 CU IDOL SELF LEARNING MATERIAL (SLM)

Now, let us consider the following function, which takes an array as an argument along with another argument and based on the passed arguments, it returns the average of the numbers double getAvg(int arr[], int size) { // to calculate an average int i; double avg; double sum = 0; for (i = 0; i < size; ++i) { sum = sum + arr[i]; } avg = sum / size; return avg; } passed through the array as follows Now, let us call the above function as follows Output of the above program. Average value is: 214.400000 #include <stdio.h> /* function declaration */ double getAvg(int arr[], int size); int main () { /* an int array with 5 elements */ int balance[5] = {1000, 2, 3, 17, 50}; double avg; /* pass pointer to the array as an argument */ avg = getAvg( balance, 5 ) ; /* output the returned value */ printf( \"Average value is: %f \", avg ); return 0; 28 } CU IDOL SELF LEARNING MATERIAL (SLM)

ARRAY REPRESENTATION: Array is a container that can hold a fixed number of items and these items should be of the same type. Most of the data structures make use of arrays to implement their algorithms. Following are the important terms to understand the concept of Array. • Element − Each item stored in an array is called an element. • Index − Each location of an element in an array has a numerical index, which is used to identify the element. Arrays can be declared in various ways in different languages. For illustration, let's take the C array declaration. Figure 2.5: Array Initialization As per the above illustration, the following are the important points to be considered. • Index starts with 0. • Array length is 10 which means it can store 10 elements. • Each element can be accessed via its index. For example, we can fetch an element at index 6 as 9. 2.2 OPERATIONS ON ARRAYS 29 Following are the basic operations supported by an array. 1. Traverse − print all the array elements one by one. 2. Insertion − Adds an element at the given index. 3. Deletion − Deletes an element at the given index. CU IDOL SELF LEARNING MATERIAL (SLM)

4. Search − Searches an element using the given index or by the value. 5. Update − Updates an element at the given index. Traverse Operation: This operation is to traverse through the elements of an array. Figure 2.6: Array Traversing 30 #include <stdio.h> main() { int LA[] = {1,3,5,7,8}; int item = 10, k = 3, n = 5; int i = 0, j = n; printf(\"The original array elements are :\\n\"); for(i = 0; i<n; i++) { printf(\"LA[%d] = %d \\t\", i, LA[i]); } } Example Program: Output: The original array elements are : LA[0] = 1 LA[1] = 3 LA[2] = 5 LA[3] = 7 LA[4] = 8 Insertion Operation: CU IDOL SELF LEARNING MATERIAL (SLM)

Insert operation is to insert one or more data elements into an array. Based on the requirement, a new element can be added at the beginning, end, or any given index of an array. Here, we see a practical implementation of insertion operation, where we add data at the end of the array Figure 2.7: Array Insertion 31 CU IDOL SELF LEARNING MATERIAL (SLM)

#include <stdio.h> main() { int LA[] = {1,3,5,7,8}; int item = 10, k = 3, n = 5; int i = 0, j = n; printf(\"The original array elements are :\\n\"); for(i = 0; i<n; i++) { printf(\"LA[%d] = %d \\n\", i, LA[i]); } n = n + 1; while( j >= k) { LA[j+1] = LA[j]; j = j - 1; } Example Program: LA[k] = item; printf(\"The array elements after insertion :\\n\"); for(i = 0; i<n; i++) { printf(\"LA[%d] = %d \\n\", i, LA[i]); } } Output 32 The original array elements are : LA[0] = 1 LA[1] = 3 CU IDOL SELF LEARNING MATERIAL (SLM)

LA[2] = 5 LA[3] = 7 LA[4] = 8 The array elements after insertion : LA[0] = 1 LA[1] = 3 LA[2] = 5 LA[3] = 10 LA[4] = 7 LA[5] = 8 Deletion Operation: Deletion refers to removing an existing element from the array and re- organizing all elements of an array. Consider LA is a linear array with N elements and K is a positive integer such that K<=N. Following is the algorithm to delete an element available at the Kth position of LA. Figure 2.8: Array Deletion 33 CU IDOL SELF LEARNING MATERIAL (SLM)

Algorithm: 34 Begin deletion() Set J = K Repeat steps 4 and 5 while J < N Set LA[J] = LA[J + 1] Set J = J+1 Set N = N-1 end Example Program: #include <stdio.h> int main () { int array[] = {1,3,5,7,8}; int k = 3, n = 5; int i, j; printf(\"The original array elements are :\\n\"); for(i = 0; i<n; i++) { printf(\"array [%d] = %d \\n\", i, array [i]); } j = k; while( j < n) { array[j-1] = array[j]; j = j + 1; } n = n -1; printf(\"The array elements after deletion :\\n\"); for(i = 0; i<n; i++) { CU IDOL SELF LEARNING MATERIAL (SLM)

printf(\"array [%d] = %d \\n\", i, array[i]); } return 0; } Output The original array elements are : ARRAY[0] = 1 ARRAY[1] = 3 ARRAY[2] = 5 ARRAY[3] = 7 ARRAY[4] = 8 The array elements after deletion : ARRAY[0] = 1 ARRAY[1] = 3 ARRAY[2] = 7 ARRAY[3] = 8 Search Operation: You can perform a search for an array element based on its value or its index. Consider ARRAY is a linear array with N elements and K is a positive integer such that K<=N. Following is the algorithm to find an element with a value of ITEM using sequential search. Figure 2.9: Array Search 35 CU IDOL SELF LEARNING MATERIAL (SLM)

Algorithm: 36 begin search() Set J = 0 Repeat steps 4 and 5 while J < N IF LA[J] is equal ITEM THEN GOTO STEP 6 Set J = J +1 PRINT J, ITEM end Example: Program: #include <stdio.h> int main() { int array[] = {1,3,5,7,8}; int item = 5, n = 5; int i = 0, j = 0; printf(\"The original array elements are :\\n\"); for(i = 0; i<n; i++) { printf(\"array[%d] = %d \\n\", i, array[i]); } while( j < n) { if( array[j] == item ) { break; } j = j + 1; } CU IDOL SELF LEARNING MATERIAL (SLM)

printf(\"Found element %d at position %d\\n\", item, j+1); return 0; } Output: The original array elements are : ARRAY[0] = 1 ARRAY[1] = 3 ARRAY[2] = 5 ARRAY[3] = 7 ARRAY[4] = 8 Found element 5 at position 3 Update Operation: Update operation refers to updating an existing element from the array at a given index. Consider ARRAY is a linear array with N elements and K is a positive integer such that K<=N. Following is the algorithm to update an element available at the Kth position of ARRAY. Algorithm: begin update() Set ARRAY[K-1] = ITEM end 37 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 2.10: Array Update 38 Example Program: #include <stdio.h> int main() { int ARRAY[] = {1,3,5,7,8}; int k = 3, n = 5, item = 10; int i, j; printf(\"The original array elements are :\\n\"); for(i = 0; i<n; i++) { printf(\"ARRAY[%d] = %d \\n\", i, ARRAY[i]); } ARRAY[k-1] = item; printf(\"The array elements after updation :\\n\"); for(i = 0; i<n; i++) { printf(\"ARRAY[%d] = %d \\n\", i, ARRAY[i]); CU IDOL SELF LEARNING MATERIAL (SLM)

} return 0; } Output: The original array elements are : ARRAY[0] = 1 ARRAY[1] = 3 ARRAY[2] = 5 ARRAY[3] = 7 ARRAY[4] = 8 The array elements after updation : ARRAY[0] = 1 ARRAY[1] = 3 ARRAY[2] = 10 ARRAY[3] = 7 ARRAY[4] = 8 2.3 SUMMARY • Arrays are a kind of data structure that can store a fixed-size sequential collection of elements of the same type. An array is used to store a collection of data, but it is often more useful to think of an array as a collection of variables of the same type. • The number of values between braces { } cannot be larger than the number of elements that we declare for the array between square brackets [ ]. You can access elements of an array by indices. • Make an array of arrays is called multidimensional arrays. The simplest form of the multi-dimensional array is the two-dimensional array. • arrays can be passed as an argument into a function. • Traverse, Insertion, Deletion, Search and Update are the basic operations of an array. 2.4 KEYWORDS • Array - Arrays a kind of data structure that can store a fixed-size sequential collection of elements of the same type 39 CU IDOL SELF LEARNING MATERIAL (SLM)

• Array Size - Integer constant greater than zero indicating the size of the array • Type - Any valid C data type indicating the type of the array • Element - Each item stored in an array is called an element. • Index or Indices – The location of the element in the particular array • Multi-dimensional Arrays – Arrays having columns, rows and depth. Providing a table/cube-like interface to the array respectively. • Traverse − print all the array elements one by one. • Insertion − Adds an element at the given index. • Deletion − Deletes an element at the given index. • Search − Searches an element using the given index or by the value. • Update − Updates an element at the given index. 2.5 LEARNING ACTIVITY Suppose we have an array-based list ������[0 … ������ − 1] and we want to delete all duplicates. Lastposition is initially ������ − 1, but gets smaller as elements are deleted. Consider the following program. for(i=0;i<lastPosition;i++) { j = i+ 1; while( j < lastPosition) if(A[i] == A[j]) delete(j); else j++; } The program Delete deletes the element in position j and collapses the list. a. Explain how this procedure works. ___________________________________________________________________________ ____________________________________________________________________ b. Rewrite this procedure using general list operations. 40 CU IDOL SELF LEARNING MATERIAL (SLM)

___________________________________________________________________________ ____________________________________________________________________ 2.6 UNIT END QUESTIONS A. Descriptive Questions Short Questions 1. What is an array? 2. How to declare a two-dimensional array? 3. List out the array operation 4. How to access the array with suitable example 5. What are the ways to create an array? Long Questions 1. Explain in details about array 2. What are the operations of an array? 3. Write a program in C to store elements in an array and print it 4. Write a program in C to copy the elements of one array into another array 5. Write a program in C to merge two arrays of the same size sorted in descending order B. Multiple choice Questions 1. Which of the following statements are correct about an array? I. The array int num[26]; can store 26 elements. II. The expression num[1] designates the very first element in the array. III. It is necessary to initialize the array at the time of declaration. IV. The declaration num[SIZE] is allowed if SIZE is a macro. a. I, II b. I, IV c. I, III d. II, III 2. What is an Array in C language.? 41 a. A group of elements of same data type. b. An array contains more than one element c. Array elements are stored in memory in continuous or contiguous locations. CU IDOL SELF LEARNING MATERIAL (SLM)

d. All of these 3. An array Index starts with? a. -1 b. 0 c. 1 d. 2 4. Choose a correct statement about C language arrays. a. An array size can not changed once it is created. b. Array element value can be changed any number of times c. To access Nth element of an array students, use students[n-1] as the starting index is 0. d. All of these 5. What is the output of C Program.? int main() { int a[] = {1,2,3,4}; int b[4] = {5,6,7,8}; printf(\"%d,%d\", a[0], b[0]); return 0; } a. 1,5 b. 2,6 c. 0 0 d. Compiler error Answer 42 1. (b) 2. (d) 3. (b) 4. (d) 5. (a) CU IDOL SELF LEARNING MATERIAL (SLM)

2.7 REFERENCES Reference Books: • R1 Trembley & Soreson, Introduction to Data Structures Applications, Second Edition, Pearson Education. • R2 A. Tannenbaum, Y. Lanhgsam and A.J. Augenstein, Data Structures Using C++, Prentice Hall of India. Text Books: • T1 Schaum's Outlines Series- Data Structures, Seymour Lipschutz, TMH. • T2 E. Balagarusamy, Data Structure using C/C++, Tata McGraw-Hill Education. Websites: • https://www.geeksforgeeks.org/ • https://www.tutorialspoint.com/ 43 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 3: ARRAYS 2 Structure 3.0 Learning Objective 3.1 Linear Search 3.2 Binary Search 3.3 Polynomial Representation and its Operations 3.4 Summary 3.5 Keywords 3.6 Learning activity 3.7 Unit End Questions 3.8 References 3.0 LEARNING OBJECTIVE After studying this unit, the student will be able to: ▪ Describe the two types of searching algorithm like linear search and binary search. ▪ State the how to declare polynomial and operations. 3.1 LINEAR SEARCH Searching is the process of finding some particular element in the list. If the element is present in the list, then the process is called successful and the process returns the location of that element, otherwise, the search is called unsuccessful. Two popular search methods are widely used to search some item into the list. However, the choice of the algorithm depends upon the arrangement of the list. 1. Linear Search 2. Binary Search Linear Search Linear search is the simplest search algorithm and often called a sequential search. In this type of searching, we simply traverse the list completely and match each element of the list with the item whose location is to be found. If the match found then the location of the item is returned otherwise the algorithm return NULL. Linear search is implemented using the following steps 44 CU IDOL SELF LEARNING MATERIAL (SLM)

1. Read the search element from the user. 2. Compare the search element with the first element in the list. 3. If both are matched, then display \"Given element is found!!!\" and terminate the function 4. If both are not matched, then compare the search element with the next element in the list. 5. Repeat steps 3 and 4 until the search element is compared with the last element in the list. 6. If the last element in the list also doesn't match, then display \"Element is not found!!!\" and terminate the function. Figure 3.1: Linear Search Linear Search Algorithm: begin LinearSearch(array, key) for each item in the array if item == value return its index end Example Program: int search(int array[], int n, int x) { // Going through array sequencially for (int i = 0; i < n; i++) if (array[i] == x) return i; return -1; } 45 CU IDOL SELF LEARNING MATERIAL (SLM)

3.2 BINARY SEARCH Divide the search time in half repeatedly to search a sorted list. Start by constructing an interval that covers the entire array. If the search key's value is less than the object in the interval's centre, the interval can be narrowed to the lower half. Otherwise, hold it to the upper half of the page. Check the value before it is found or the interval is zero. Figure 3.2: Binary Search Binary search is implemented using the following steps Step 1 - Read the search element from the user. Step 2 - Find the middle element in the sorted list. Step 3 - Compare the search element with the middle element in the sorted list. Step 4 - If both are matched, then display \"Given element is found!!!\" and terminate the function. Step 5 - If both are not matched, then check whether the search element is smaller or larger than the middle element. Step 6 - If the search element is smaller than the middle element, repeat steps 2, 3, 4 and 5 for the left sublist of the middle element. Step 7 - If the search element is larger than the middle element, repeat steps 2, 3, 4 and 5 for the right sublist of the middle element. Step 8 - Repeat the same process until we find the search element in the list or until the sublist contains only one element. Step 9 - If that element also doesn't match with the search element, then display \"Element is not found in the list!!!\" and terminate the function. 46 CU IDOL SELF LEARNING MATERIAL (SLM)

Algorithm: begin binary_search A ← sorted array n ← size of array x ← value to be searched Set lowerBound = 1 Set upperBound = n while x not found if upperBound < lowerBound EXIT: x does not exists. set midPoint = lowerBound + ( upperBound - lowerBound)/2 if A[midPoint] < x set lowerBound = midPoint + 1 if A[midPoint] > x set upperBound = midPoint - 1 if A[midPoint] = x EXIT: x found at location midPoint end while end Example Program: int binarySearch(int arr[], int l, int r, int x) { if (r >= l) { int mid = l + (r - l) / 2; // If the element is present at the middle if (arr[mid] == x) return mid; 47 CU IDOL SELF LEARNING MATERIAL (SLM)

// If element is smaller than mid, then // it can only be present in left subarray if (arr[mid] > x) return binarySearch(arr, l, mid - 1, x); // Else the element can only be present // in right subarray return binarySearch(arr, mid + 1, r, x); } // We reach here when element is not present in array return -1; } 3.3 POLYNOMIAL REPRESENTATION AND ITS OPERATIONS A polynomial p(x) is the expression in variable x which is in the form������������������ + ������������������−1 + ⋯ ������������ + ������ where a, b, c …., k fall in the category of real numbers and 'n' is a non-negative integer, which is called the degree of a polynomial. An essential characteristic of the polynomial is that each term in the polynomial expression consists of two parts: 1. one is the coefficient 2. other is the exponent Array representation assumes that the exponents of the given expression are arranged from 0 to the very best value (degree), which is represented by the subscript of the array beginning with 0. The coefficients of the respective exponent are placed at an appropriate index within the array. The array representation for the below polynomial expression is given below: ������(������) = 4������6 − 2������ + 5 That is 0 123456 +----+-----+----+----+----+----+----+ | 5 | -2 | 0 | 0 | 0 | 0 | 4 | 48 +----+-----+----+----+----+----+----+ Figure 3.3: Polynomial Representation Using Array CU IDOL SELF LEARNING MATERIAL (SLM)

1. the coefficient 5 is in slot 0 of the array (representing 5x^0) 2. the coefficient -2 is in slot 1 of the array (representing -2x^1) 3. the coefficient 4 is in slot 6 of the array (representing 4x^6) Polynomial operation: 1. Addition 2. Subtraction 3. Multiplication 4. Differentiation Typedef struct { int CoeffArray[MaxDegree + 1]; int Power; }*Polynomial; Type declarations for array implementation of the polynomial ADT: Procedure to initialize a polynomial to zero: void ZeroPolynomial(Polynomial poly) { int i; for(i = 0; I <= MaxDegree; i++) Poly-> CoeffArray[i] =0; Poly->Power = 0; } Procedure to add two polynomials: void AddPolynomial ( Const Polynomial Poly1, Const Polynomial Poly2, Const Polynomial Sum) { int i; ZeroPolynomial(Sum); Sum->Power = Max(Poly1->Power, Poly2- 49 CU IDOL SELF LEARNING MATERIAL (SLM)

>Power ); for(i=Sum->Power; i >= 0; i--) { Sum->CoeffArray[i] = Poly1->CoeffArray[i] + Poly2->CoeffArray[i]; } } Procedure to subtract two polynomials: void SubPolynomial ( Const Polynomial Poly1, Const Polynomial Poly2, Const Polynomial Sub) { int i; ZeroPolynomial(Sub); PolySub->Power = Max(Poly1->Power, Poly2- >Power ); for(i=PolySub->Power; i >= 0; i--) { PolySub->CoeffArray[i] = Poly1->CoeffArray[i] - Poly2->CoeffArray[i]; } } Procedure to multiply two polynomials: void MultPolynomial(Const Polynomial Poly1, Const Polynomial Poly2, Const Polynomial Prod) { int i,j; ZeroPolynomial(Prod); Prod->Power=Poly1->Power+Poly2->Power; 50 CU IDOL SELF LEARNING MATERIAL (SLM)