DATA STRUCTURE USING ‘C’ Dr. Prabhakar Gupta D« WALL Vineet Agarwal SS ~ MEDIA Manish Varshney in ec at nai CCPublished by : FIREWALL MEDIA (An imprint of Laxmi Publications Pot. Ltd.) 118, Golden House, Daryaganj, New Delhi-110002 Phone : 011-43 53 25 00 Fox : 011-43 53 25 28 wwwlaxmipublications.com info@laxmipublications.com Copyright © 2007 by Firewall Media (An imprint of Laxmi Publications Pot. Ltd.) All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying. recording or otherwise without the prior written permission of the publisher. Price : Rs, 150.00 Only. First Edition : 2007 OFFICES India USA © Bangalore 080-26 61 15 61 Boston © Chennai 044-24 34 47 26 11, Leavitt Street, Hingham, © Cochin 0484-239 70 04 ‘MA 02043, USA © Guwahati 0361-254 36 69, 251 38 81 ® Hyderabad 040-24 65 23 33 © Jalandhar 0181-222 12 72 © Kolkata 033-22 27 87 73, 22275247 ® Lucknow 0522-220 95 78 © Mumbai 022-24 91 54 15, 24 92 78 69 © Ranchi 0651-230 77 64 FDA-2925-150-DATA STRUCTURE USING ‘C’ C—14069/07/04 ‘Typesetted at : Balaji Graphics, New Delhi. Printed at : Pack Printer, Delhi.CONTENTS Page No. Preface (x) Acknowledgement ... Qi) 1 | Polymorphic Data | De .5 Structure Operations 1.6 Program Development Life Cyc! 9 1.7_Program Design Tools 10 1.8 Introduction to Algorithms, ML 2. Arrays 17— 40 2.1 ‘Types of Array 17 22 Array Operations. 18 23 How to Represent the 19 24 Merging of Two Arrays 22 25 Two Dimensional Arrays 25 26 Applications of Array . 27 2.7 Sparse Matrix ........ 30 28 String... 32 2.9 Pattern Matching. 36 2.10 Array as Parameter 38 Stack Implementation al Al 82 Operations on Stacks Al 33_Stack Terminology 42 3.4_ Algoritluns for Push and Pop 42 ‘8.5__Implementing Stack using Pointers 45 3.6 Application of Stacks 47 3.7 Calculation of Postfix Expression .... 48 @)4, Recursion 3.8_Notation Conversion 3.9 Parenthesis Checker... 3.10 Quick Sort Algorithm eB bs 5._Queues .... 6._Linked List. 4.1 Introduction .. 42 Recursion in ‘C’ 43 Recursive Algorithm 4.4 The Tower of Hanoi... 4.5 Principles of Recursion .. 4.6 Disadvantages of Recursion .. 7 Dif 4.8 ‘Types of Recursion 48 Back Tracking... 4.10 Simulating Recursion 4.11 Removal of Recursion il Bisse 81— 100 5.1_Operations on a Queu 5.2 Algorithms for Insertion and Deletion in Queue . 5.3 Limitation of Simple Queues 5.4 Linked Queue 5.5 Circular Queue 5.6 Double Ended Queue (D-Quene) 5.7 Full and Emy 5.8 Priority Queue 5.8 Application of Queue.. 5.10 Multiple Queue... 6.11 Dynamic Memory Allocation 7. Tree... 6.1_Linked List 6.2_Advantages and Disadvantages of using Linked List... 104 6.3 Empty List. 104 6.4 Representation of Linear Linked List . 105 6.5 _‘C’ Programs on Various Operations of Linked List 106 6.6 Polynomial Representation... 137 6.7 Garbage Collection and Compactions. 138 21 ‘Tree... 141 7.2. Tree Terminology M2 7.3 Complete Binary Tree ua 74 Extended Binary Tree M437S. 344 7.6 Operations on Binary Tree. uz 7.7 Traversal of a Binary Tree. us 7.8 Conversion of an Expression into Binary Tree .. 164 7.9 Property of Binary Tree... 166 7.10 Huffman's Algorithm. 159 8. Searching .. 164 — 183 8.1 Sequential Search 164 8.2__Binary Search... 166, 8.3__Comparision of Sequential Search and Binary Search. 169 84__Anslysis of Sequential and Binary Searc! 169 8.5 Hash Table and Hashing 170 8.6 Hash Functions ... 172 87 Resolving Collisions 88 Rehashing.. 9. Sorting G1 Bubble Sort ssssssssssssnssemanssosnsssaassssenanssssssnnasassssssiessssmecssanioe dBA 2.2 Insertion SOFt tosses 185 $3 Quick Sort. 187 9.4 Merge Sort. 188 95 Heap Sort. 188 96 Sorting on Different Keys .. 194 9.7 Practical Consideration of Sorting 195 200 202 10. Binary Search Tree. . 207 — 238 10.1 Construction of Binary Search Tree 207 102 212 103 213 104 213 105 217 106 Height Balanced Tree or AVL Tre 227 10.7 B-Tree 234 108 236 1L._ Graph. . 239 — 265 11.1 _Konigsberg Bridge Problem 230 112 Graph 240 113. Types of Graph 241 114. Representation of Graph 245 11.5 Linked Representation .. 249124 ‘Text Mode v/s Binary Mode... 12.5 File Operations .. Organization of Records into Blocks ..PREFACE Efficiency of the program plays very important role in Computer Science. Efficient program can handle a large amount of data. Data structure plays a very important role in the efficiency of Computer Program. Also it is very important to decide which data structure must be used to store data items before writing the program. The objective of this book is to explain the fundamentals of the data structures that are available and to explain the different operations that can be applied on data structure. The study of data structure gives an idea for the selection of data structure in programming, We have tried to make this book different in many ways. This book gives the reader more number of programs with explanation. This book has been divided in twelve chapters. This book covers the entire syllabus of U.P. Technical University of data structure using ‘C’. This book is useful for the students of B.tech. Computer Science, Information Technology of III Semester, Electronics and Communication IV Semester and MCA II semester. This book is written in easy language. ‘The main focus of this book is to make the reader experience the real-life software development scenario as closely as possible. This book also explain the performance analysis of the various programs such as sorting and searching methods. —Authors (i)ACKNOWLEDGEMENT We extend our warm thanks to Sri Dev Murtiji, Chairman of SRMS-CET, Bareilly for giving us an opportunity to write the book. We are also thankful to our Director Dr. S.P. Gupta and Principal Prof. M.L. Sadana for their valuable suggestions for the quality improvement of this book. We also acknowledge the consistent support and cooperation received from our faculty members of various departments. ‘We also thankful to Dr. Ravindra Singh Prof. Computer Science Deptt. IET Campus MJPRU Bareilly for his valuable guidance. We are also thankful to Mr. Shantanu Sharma for his valuable support. Finally, we wish to express our grateful thanks to all friends and family members for their moral support. —Authors (Gai)1 | INTRODUCTION Data structure is created with the help of two words ie., Data and Structure, that means we have to store the data in the form of structure in the main memory. In order to represent and store data in main memory and/or secondary memory, we need an appropriate model. The different models used to organize data in the main memory are collectively referred to as, data structures, whereas the different models used to organize data in the secondary memory are collectively referred to as file structures. 1.1 BASIC TERMINOLOGY OF DATA ORGANIZATION The following are the basic terminology related to data organization : 1. Data : The term data simply refers to a value or set of values. These values may represent some observations from an experiment, some figures collected during some survey, marks obtained by a student in an examination ete. . Data item : A data item refers to a single unit of values. For example Roll No., Name, Date of Birth, Age, Address and Marks in each subject are data items. Data items that can be divided into sub-items are called group items whereas those item which cannot be divided into sub-items are called elementary items. For example an address is a group item as it is usually divided into sub-iteme such as house No, street No, locality. city, Pincode ete. On the other hand Roll No, Marks, City, Pincode are normally treated as elementary items, Entity : An entity is something that has certain attributes or properties which may be assigned values, The values assigned may be either numeric or non-numeric. For example : A student is an entity. The possible attributes for a student can be roll no., name, date of birth, sex and class. Each attribute of an entity has a defined set of values called Domain. Entity Set : An entity set is a collection of similar entities. For example : Student of a class, employees of an organization, products manufactured by a manufacturing unit ete. forms an entity set. . Record : A record is a collection of related data items. For example : 8. No. Name Age 1001 AA 23 [> Record . File : A file is a collection of related records. For example, a file containing records , of all students in a class, a file containing reeords of all employees of an organization. ,Data Structure Using 'C’ 7. Key :A key is a data item in a record that makes unique values and can be used to distinguish a record from other records. Various keys are there, primary key, foreign key, composite key, super key, alternate key. These topics are related with Data Base Management System. 8. Information : The terms data and information have been used to mean same thing. But actually information is more than just data. In simple terms, information is a processed data. Data is just a collection of values (raw data), from which no cunclusions can be drawn. Thus data as such is not useful for decision making. When the data is processed by applying certain rules, new generated data becomes information. 1.2 CONCEPT OF DATA TYPE A data type is a collection of values and a-set of operations that act on those values. Whether our program is dealing with predefined data types or user defined types. These two aspects must be considered : I. Set of values IL. Set of operations. For example : Consider an integer data type which consists of values {minint, ... - 3, - 2, - 1,0, 1, 2, 3, ... maxint}, where minint and maxint are the smallest and largest integers that can be represented by an integer type on a particular computer. Primitive data type : A primitive data type is a data type that is predefined. The predefined data type is also known as built in data type. These primitive data types may be different for different programming languages. For example C programing language provides built in support for integers (int, long), real (float, double) and char (characters). Abstract data type : An abstract data type is a data type that is organized in such a way that the specification of the values and the specification of the operation on those values are separated from the representation of the values and the implementation of the operations. For example, consider list abstract data type. A list is basically on collection of elements which can be ordered or unordered. The primitive operations on a list may include : I. Adding new elements II. Deleting elements III. Determining number of elements in the list IV. Applying a particular process to each element in the list Here we are not concerned with how a list is represented and how the above mentioned operation are implemented. We only need to know that it is a list whose element are of given type and what can be do with the list. 1.3 POLYMORPHIC DATA STRUCTURE If we use the concept of abstract data type for implementing a list, then we have to create different abstract data types for different types of lists with different types of elements, which means we have to create a separate abstract data type for list of integers, reals, strings and so on. This would require the list code to be dependent. On the specific data type used to represent the abstract data type. Moreover there would be no way to make a heterogenous list.Introduction EM A heterogenous list is one that contains data elements of variety of data types. Therefore, it is desirable to create a data type that is independent of the values stored in the list. This | kind of data type is known as polymorphic data type. | In OOPS we create the polymorphic data type with the help of template. | In order to create a polymorphic data type, it is necessary to understand a little more about data types in general. | Data typing is important because it supplies two essential pieces of information : (@® The amount of memory a data element uses. (ii) The manner in which the data is to be interpreted. Polymorphic data types, therefore, must be able to function independently of both the size and exact nature of data they store. ‘To achieve the first goal, polymorphic data structure never access data elements directly, they used pointer to access the data. In C, a pointer to void data type can be used to point a value of any kind. 1.4 DATA STRUCTURE DEFINITION A data structure is a logical model of a particular organization of data. The choice of a data structure depends on the following consideration : (It must be able to represent the inherent relationship of the data in the real world. (i) It must be simple enough so that it can processed efficiently as and when necessary. The study of data structure, includes : (® Logical description of the data structure (i) Implementation of the data structure (iii) Quantitative analysis of Data Structure. This analysis includes determining the amount of memory needed to store the data structure and the time required to process it. 1.4.1 Description of Various Data Structures Actually we divide the data structure into two categories : (@ Linear data structure (i) Non-linear data structure (i) Linear data structure : The elements of a linear structure form a sequences i.e., linear list. Examples of linear data structure are Arrays, Linked lists, Stacks and Queues. (ii) Non-linear data structure : The elements of a non-linear data structure do not form a sequence. Example of non-linear data structures are : Trees and Graphs. So we can say we will discuss the following Data Structure > Arrays > Stacks Queues > Linked lists -» Trees -» Graphs 1.4.2 General Overview of All Data Structures 1. Array : Array is the collection of similar data type and having a common name. We can access the elements in the array with the help of index. Array is classified into following categories :i | Data Structure Using ‘C’ (a) One dimensional array or linear array : The General syntax to define the one dimensional array is as follows : [size] It requires only one index to access an individual element of the array. For example : If we define int a[10]; the meaning of this line is that a is an array which holds 10 elements from [0] to a9). The first element is stored at the position of a [0] and 10th element is stored at the position of a [9]. Example : Consider a linear array r, consisting of roll numbers of 5 students of a particular class. This array can be pictured as follows : 1200 | 1201 | 1202 | 1203 | 1204 ° 1 2 3 4 (6) Two dimensional arrays : A two dimensional array is the collection of elements in the form of rows and columns. A 2D array is represented with the help of following syntax : [size of row] (size of column) If we define | int a[3)[3] ‘The meaning of this line is that a is an array which holds 3 rows and 3 columns and the first element is stored at the position of a[0][0] and the last element is stored at the position of a[2][2] a[O0] a[0}1] af0]{2) @(1J[0) @(1)0) @f1){2) a(2][0] a([2)(1) af2){2) ‘Total memory allocated for int a [3] [3] is 18 bytes. 2. Linked list : A linked list is a linear collection of data elements called nodes. The linear order is maintained by pointers. A linked list can be linear linked list (one way list) or doubly linked list (two way list), and circular linked list. (a) Linear linked list : In linear linked list, each node is divided in two parts : (i) First part contains the information of the element. (ii) The second part, called the link field or next pointer field contains the address of the next node in the list. ‘We can represent the linear linked list in C language as follows : struct node int info; struct node * next; }* start = NULL;Introduction | 5 | A linear linked list can be traversed only in one direction. The following figure shows a linear linked list with 4 nodes. head 1200] - —}—+f1202]_ =} +203 x J——+> nut a Information field Next Pointer field of Second Node of Second Node (6) Circular linked list ; A circular linked list is a linear linked list, except that the last element points to the first element. ‘The following figure shows a circular list with 4 nodes. [rai] i206] _—}——~+f zo] _—} —-+fia02[ _—}- fio] The limitation of linear linked list is that it can be traversed only in one direction. The circular linked list is represented as follows struct node ( int info; struct node * next; )* start = NULL; But the limitation is that when start goes to null then it goes to move to first node. We will discuss all the link lists in detaile later on. 8. Stack : A stack is also called a Last In Firs Out (LIFO) system, is a linear list in which insertion and deletions can take place only at one end, called the top. The following figure shows a stack with 6 elements : 8 }+——— Top Everything is inserted or 16 deleted with the help of top. 8 100 200aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.8. Introduction (i) The shape property states that heap is a complete or nearly binary tree. (ii) The order property states that : (a) Either the element at any node is smallest of all its children called min heap. (0) The element at any node is largest of all of its children, called max heap. A heap is represented in memory by sequential representation ie., using linear array. The most important application of a heap structure is to implement priority queues, ag well as implement the sorting technique that is known as heap sort. The following figure shows a min heap as well as max heap. (20) (50) (20) (28) (38) (40) ® © @®M ®© ® © @© ® Min Heap ‘Max Heap . Graph : A graph G is a ordered set (VjE) where V represent the set of elements, called nodes or vertices in graph terminology and E represents the edges between these elements. This data structure is used to represent relationship between pairs of elements which are not necessarily hierarchical in nature. For example : Graph may be used to show the sir map where the airline flies only between the cities connected by lines that is shown in the following figure. The following figure shows the cities for which there is a direct flight : Srinagar Kolkata Amritsar Chennai Mumbai Aiding Fights In the above figure V = (Srinagar, Amritsar, Delhi, Mumbai, Chennai, Kolkata} E = ((Srinagar, Amritsar), (Amritsar, Delhi), (Delhi, Kolkata), (Delhi, Chennai), (Delhi, Mumbai), (Chennai, Kolkata), (Mumbai, Chennai)} Hash table : There are many applications that require a dynamic structure, that supports only insert, search and delete operations. These operations are commonly known as dictionary operations. A hash table is an effective data structure for implementing dictionaries.EE Data Structure Using ‘C’ A hash table requires much less storage than direct access table. Specifically the storage requirement can be reduced to 0 (KI), even though, searching for an element in the hash table requires constant time. 1.4.3 Common Operations on Data Structures (i) Traversal : Accessing each element exactly once in order to process it. The operation is called visiting the element. (ii) Searching : Finding the location of a given element. (iii) Insertion : Adding a new element to the structure. (iv) Deletion ; Removing an existing element from the structure. (v) Sorting ; Arranging the elements in some logical order. This logical order may be ascending or descending in case of numeric key. In case of alphanumeric key, it can be dictionary order. (vi) Merging : Combining the elements of two similar stored structures into a single structure. 1.5 STRUCTURE OPERATIONS Structure plays a very important role in procedural language. In procedural language every thing is done with the help of structure and the statements are executed line by line. In C language we can define the structure, with the help of following syntax struct ( ; } ; For example : If we define struct student int sno; char name[25]; 1S; In the above structure s is a structure variable and sno and name are the data members of the structure student. We can directly access the data members of any particular structure, with the help of structure variable and dot operator. For example : If we want to access the sno and name then we can directly access S.sno S.name 1.5.1 Arrays of Structure If we want to store more than one record then we have to use the concept of array of structure. We can define the array of structure with the help of following syntax.Introduction EM struct { ; } [size]; For example : If we define struct student ints no; char name (25) }s(10}; This means that is a structure variable which holds 10 student records ie., this behaves just like array of structure. 1.5.2 Nested Structure Nested structure means structure within structure. We can define the nested structure as follows : struct ; struct ; | ; } ; If we want to access the data members of structure 1 then we can directly access with the help of - ; If we want to access the data members of structure 2 then we can directly access with the help of [__. - ; 1.6 PROGRAM DEVELOPMENT LIFE CYCLE Program development life cycle, is a systematic way of developing a quality software. It provides an organized plan for breaking down the task of program development into manageable chunks, each of which must be successfully completed before moving onto the next phase. The program development process is divided into following phases : (Defining the problem. (i) Designing the program. (iii) Coding the program.Data Structure Using 'C’ (iv) ‘Testing and debugging the program. (v) Documenting the program. (vi) Implementing and maintaining the program. (i) Defining the problem : The first step in developing a program is to define the problem. In major software projects, this is a job for system analyst, who provides the result of their work to programmers in the form of program specification. The program specification precisely defines the input data, the processing that should take place, the format of the output reports and the user interface. Depending on the size of the job, the program development might be handled by an individual or a team. (ii) Designing the program : Program design begins by focusing on the main goal that the program is trying to achieve and then breaking the program into manageable, components, each of which contributes to this goal. This approach of program design is called top-down, program design or modular programming. The first step involves main routine, which is the program’s major activity. From there, programmers try to break down the various components of the main routine into smaller units called modules. If an error appears in a program designed this way, it is relatively easy to identify the module that must be causing the error. For each module, the programmer draws a conceptual plan, using an appropriate program design tool to visualize how the module will do its assigned job. 1.7 PROGRAM DESIGN TOOLS The following are the various program design tools : (i) Structure charts : A structure chart, also called hierarchy chart, show the top down design of a program, Each box in the chart indicates a task that the program must accomplish. The top module, called the main module or control module. We can graphically represent this chart as follows : Main module <——_} —_—_, Enter a record Modify a record Delete a record A structure chatt for a data entry program (i) Algorithms : An algorithm is a step by step description of how to arrive at a solution. Algorithms are not restricted to computers. In fact we use them everyday. (iii) Flowcharts : A flowchart is a diagram that shows the logic of the program. Programmers create flowchart either by hand using a flowchart template or on the computer.Introduction The following are the symbols which we implement in flowchart. | Flow line Parallelogram —~/ / ——+> Input/Ontput © Connector Rectangle <—— ——> Processing — —> Decision Box ——+ One entry point and more than one exit point (iv) Decision tables : A decision table is a special kind of table, which is divided into four parts by a pair of horizontal and vertical lines. The left top-part called conditions stub, contains the different questions being asked for decision making. The right top part called condition entries, contains the answer to these questions. The left bottom part called action stub, contains the action, to be carried out and the right bottom part, called action entries, contains either X’ entry or ‘_’. The ‘X’ entry represents an action while —’ represents no action. The decision tables are usually used as supplementary to flowcharts. Pseudocodes : A pseudocode, is an another tool to describe, the way to arrive at a solution. tv In some sense, it is considered as a form of algorithms. 1.8 INTRODUCTION TO ALGORITHMS ‘An algorithm is a finite set of steps defining the solution of a particular problem. An algorithm can be expressed in English like language, called pseudocode, in a programming language or in the form of flowchart. Every algorithm must satisfy the following criteria : @ Input : There are zero or more values which are externally supplied. (ii) Output : At least one value is produced. (iii) Definiteness : Each step must be clear and unambiguous. (iv) Finiteness : If we trace the steps of an algorithm, then for all cases, the algorithm must terminate after a finite number of steps. Effectiveness : Each step must be sufficiently basic that it can in principle be carried out by a person using only paper and pencil. In addition, not only each step be definite, it must also be feasible. 1 Algorithm Complexity ‘There are basically two aspects of computer programming. One is the data organization ie. The data and structure to represent the data of the problem in hand, and is the subject of the present text. The other one involves choosing the appropriate algorithm to solve the problem in hand. Data structure and algorithm designing, both are involved with each other. WW) 44Data Structure Using ‘C’ As an algorithm is a sequence of steps to solve a problem, there may be more than one algorithm to solve a problem : The choice of a particular algorithm depends on the following considerations : (i) Performance requirement i.e,, time complexity (ii) Memory requirement ie., space complexity (iii) Programming requirements We can directly considered only time complexity and space complexity directly and programming requirements differ from language to language. 1. Space Complexity The space complexity of an algorithm, i.e., program, is the amount of memory, it needs to run to completion. Some of the reasons for studying space complexity are : () If the program, is to run on multi user system, it may be required to specify the amount of memory to be allocated to the program. (ii) We may be interested to know in advance that whether sufficient memory is available to run the program. (iii) There may be several possible solutions with different space requirements. ‘The space needed by a program consists of the following components : (é) Instruction space : Space needed to store the executable version of the program and it is fixed. (ii) Data space : Space needed to store all constants, variable values and has further following components : (a) Space needed by constants and simple variables. This space is fixed. (6) Space needed by fixed sized structured variables, such as arrays and structure. (©) Dynamically allocated space. This space usually vary. (iii) Environment stack space : Space needed to store the information needed to resume the suspended (partially completed) functions. Each time a function is involved, the following data is saved on the environmental stack : (c) Return address ie., from where it has to resume after completion of the called function. (8) Values of all local variables and the values of formal parameters in the funetion being involved. The amount of space needed by recursive functions is called the recursion stack space. For each recursive function, this space depends on the space needed by the local variables and the formal parameters. In addition, this space depends on the maximum depth of the recursion i.e, maximum number of nested recursive calls. In general the total space needed by a program can be divided in two parts: (®) A fixed part that is independent of particular problem, and includes instruction space, space for constants, simple variables and fixed size structured variables. (ié) A variable part that includes structured variables whose size depends on the particular problem being solved, dynamically allocated space and the yecursion stack space.Introduction 2. Time Complexity The time complexity of an algorithm, is the amount of time it needs to run to completion. ‘Some of the reasons for studying time complexity are : (@) We may be interested to know in advance that whether a program will provide a satisfactory real time response. For example : An interactive program, such as an editor, must provide such a response. If it takes even a few seconds to move the cursor one page up or down. It will not be acceptable to the user. (i) There may be several possible solutions with different time requirements. The time complexity of a program depends on all factors that the space complexity depends on. ‘To measure the time complexity accurately, we can count, the all sort of operations performed in an algorithm. If we know, the time for each one of the primitive operations performed on a given computer, we can easily compute the time taken by an algorithm to complete its execution. This time will vary from system to system. Our intention is to estimate the execution time of an algorithm irrespective of the computer on which it will be used. Hence, the more reasonable approach is to identify the key operation and count such operations performed till the program completes its execution. A key operation in our algorithm is an operation that takes maximum time among all possible operations in the algorithm. (iii) The time complexity can now be expressed as a function of number of key operations performed. 1.8.2 Time Space Trade Off The best algorithm, hence best program, to solve a given problem is one that requires less space in memory and takes less time to complete its execution. But in practice, it is not always possible to achieve both of these objective. As said earlier, there may be more than one approaches to solve a same problem. One such approach may require more space but takes less time to complete its execution, while the other approach requires less space but takes more time to complete its execution. Thus we may have to sacrifice one at the cost of the other. That is what we can say that there exists a time-space trade among algorithms. ‘Therefore, if space is our constraint, then we have to choose a program that requires less space at the cost of more execution time. On the other hand, if time is our constraint such as in real time systems, we have to choose a program that takes less time to complete its execution at the cost of more space. In the analysis of algorithms, we are interested in the average case, the amount of time a program might be expected to take on typical input data and in the worst case, the amount of time a program would take on the worst possible input configuration. 1.8.3 Expressing Space and Time Complexity ‘The space and/or time complexity is usually expressed in the form of the function fin) where n is the input size for a given instance of the problem being solved. Expressing space and/or time complexity as a function fin) is important because of following reasons : (@) We may be interested to predict the rate of growth of complexity as the size of problem increases.EL Data Structure Using ‘C” ~] (ii) To compare the complexities of two or more algorithms, solving the same problem in order to find which is more efficient. The most important notation used to express the function f(n) is Big oh notation, which provides the upper bound for the complexity. (iii) Since in modern computers, the memory is not a sence constraint, therefore, our analysis of algorithms will be on the basis of time complexity. 1.8.4 Big Oh Notation Big oh is a characterization scheme that allows to measure properties of algorithms such as performance and/or memory requirements in a general fashion. The algorithm complexity can be determined ignoring the implementation depending factors. This is done by eleminating constant factors in the analysis of the algorithms. Basically these are the constant factors that differ from computer to computer. Clearly the complexity function fin) of an algorithm increases as n increases. It is the rate of increase of fin) that we want to examine. Theorem : There is an important theorem. mT FO) = Gyn + Oy ph + oe gn? Fyn tag and dy, >O then F(n) = O(n") Solution : Fin) < Elajtn! fr) 1) algorithm (v) Exponential time 0 (") for k > 1 algorithm Many algorithms are 0 (nlog,) 1.8.6 Rate of Growth at Some Standard Functions f@)in | logyn n n? ns 2 ni log,n 5 3 5 25 125 32 15 10 4 10 100 10° ay? 40 100 7 100 104 10° aye 700 1000 10 10° 108 10° (2yi0? 10* From the above table, we observe that the logarithmic function, grows most slowly, whereas the exponential function (2)" grows most rapidly. 1.8.7 Limitations of Big Oh Notation Big oh notation, has two basic limitations : (i) It contains no consideration of programming effort. Gi) It hides potentially important constants. SUMMARY m Data structure can be used for live implementation of Complex Problems. Array is the collection of similar Data Type and having a Common Name. ‘The actual implementation of Data Structure is to hold the Data with in main memory in a very efficiont way. Stack is a Linear Data Structure which holds the Property (LIFO). Queue is a Linear Data Structure which holds the FIFO Property. Linked list is a Linear Data structure which is used for Dynamic Memory allocation. ‘Tree is a Non Linear Data Structure which holds the items in hierarchical order. Graph is a Non Linear Data Structure which holds the items in the graphical order. Algorithm is a way by which we can solve the problem in a very efficient way. ‘Time complexity and space complexity are two important concepts for representation of Algorithm. We want to develop an algorithms whose Time Complexity must be minimum.Ei Data Structure Using ‘C” PROBLEMS 1 Ses eae ey 10. . How to express the Time and Space Complexity Define with the help of example ? Define the following terms : (a) Data (6) Information (c) Entity (d) Entity Type (e) Record (p File Define Data ‘Types and classification of Data types in brief. Define Data Structure. Define the classification of Data Structure. Differentiate between Linear and Non Linear Data Structure. Define the Basic Overview of all the Data Structure. What do you mean by Time and Space Complexity and how to represent these complexities ? What do you mean by Time Space Trade Off ? Define with the help of example ? ‘What do you mean by Algorithm. Give example ? Define the various Program Design Tools. Where we use the concept of Data Structure ? Define the line example ?ARRAYS Array is the collection of similar data type. Array is our data structure that has been used (as well as abused) more than any other Arrays are simple yet reliable and are used in more situations than you can count. They are like old friends. You accept and live with their qualities — good as well as bad. Data structures are classified into two categories — linear and non-linear. A data structure is said to be linear if its elements form a sequence. Elements in a non-linear data structure do not form a sequence. There are two ways of representing linear data structures in memory. One way is the Static Memory Allocation and second way is the Dynamic Memory Allocation. Static Memory Allocation is maintained with the help of Array and Dynamic Memory Allocation is maintained with the help of Pointers and Malloc function. ‘We can represent this as graphically 34] 1] 5| 6} 9]12)6}7] 8] 9 0123456789 An array of 10 elements 34 > [56 + (70 +> (se_J Nuit) Allinked list contains 4 integers. Arrays are useful when the number of elements to be stored is fixed, They are easy to traverse, search and sort. On the other hand, linked lists are useful when the number of data items in the collection are likely to vary. Linked lists are difficult to maintain as compared to ‘an array. 2.1 TYPES OF ARRAY Array is the collection of similar data type and having a common name. Array is classified into two categories : ARRAY | Single Dimentional Array Multi Dimentional Array 2D, 3D, 4D...... ‘We will only discussed Single Dimentional Array and 2D Array. Single Dimentional Array : The general syntex for defining the single dimentional array is as follows : (size); anData Structure Using ‘C’ For example : if we define int a (5); The meaning of this line is that a is an array which holds 5 elements, the first element is stored at the position of a[0] and the 5" clement is stored at the position of a [4]. Two Dimensional Array : We can define the 2D array as follows : [size of row] [size of column); For example : If we define int a [3) (3); The meaning of this line is that a is an array which holds 3 rows and 3 columns. The memory is allocated i.e., 18 bytes because here 9 elements exists. ‘The representation of 2D Array is as follows : @[0}(0] af0}f1] af0)(2) eft) aftia) afta} ef2ifo} al2if2] @f2I12) Three Dimensional Array : [No. of 2D Array] [size of row] [size of columnl; If we define int @ [2] (5) (3); The meaning of this line is that we define two 2D array each of which is having 5 rows and 3 columns i.., total elements are — 30 elements i.e., 60 bytes memory is allocated for this purpose. 2.2 ARRAY OPERATIONS There are several operations that ean be performed on an array. The following are the operations : OPERATION DESCRIPTION ‘Traversal Processing each element in the array Search Finding the location of an element with a given value Insertion ‘Adding a new element to an array Deletion Removing an element from an array Merging Combining two arrays into a single array Reversing Reversing the elements at an array‘Arrays 2.3 HOW TO REPRESENT THE LINEAR ARRAY IN MEMORY We know that the memory of the microprocessor is simply a sequence of addressed locations as shown in the following figure. 1197 1198 1199 1200 1201 1202 1203 Let a be a linear array with n elements. As arrays are stored in consecutive memory location, the system need not keep track of the address of every element of a, but needs to keep track of the address of first element only, The address of the first element is also known as the base address of the array denoted by base(a). Using the base address, the computer computes the address of the K element with the help of the following formula. Computer Memory Map 1210 Joe (a{k}) = base(a) + w * K Where w is the number of bytes/storage location for one element of the array. Example : Consider that array a is declared as array of integers with size 10, and its first element is stored at memory address 1197, ie, its base address is 1197. loc (alk]) = base(a)+ w*K; loc (a[3]) = 1197 +2*3 loc (a[3]) = 1197 + 6 = 1203. Ans. Probl. 1 Insert the element in an array 2 Delete an element from an array 3 Reverse an array 4 Display the array 5 Search the element in the array 6 Exit ENTER your choice Solution: — #include #include Develop a Program whose Output is as follows :Data Structure Using ‘C’ #include #tdefine MAX 20; void insert (int *, int, int); void del (int *, int); void reverse ( int *); void display (int *); void search (int *, int); void main() int almax]; elrserO; int ch=1, pos, n; while (ch != 6) printf“\n 1 > Insert the Element in an array”); printf(“\n 2 -> Delete an Element from an array”); printf"\n 3 > Reverse An Array”); printf“\n 4 + Display the Array”); printf(“\n 5 -> Search the Element in the Array”); printf“\n 6 —> Exit”); printft“\n Enter your choice”); scanf(“%d",&ch); switch (ch) case 1: printft“\nEnter the position where u want to insert the Record”); scanf("%d”,&pos); printf(*\nEnter the No. which you want to insert”), scanf(“%d”,&n); insert(a, pos, n); break; case 2: printfi“\nEnter the position where you want to delete the No. scanf(“%d",&pos); del(a, pos); break, case 3: reverse (a); break; case 4: display (a); break; case 5: printft“\n Enter the Element which you want to search”); scanf(“%d",&n); search(a,n); break; case 6: exit(1); default : printf{“\n Incorrect choice please Enter 1 > 6");Arrays } getch0; void insert (int *a, int pos, int n) int i; for (i = Max — 1; i > = pos; i- -) void reverse (int *a) int i, t for(i=0; i < MAX/ 2; i++) Li); ali] = al MAX -1- i}; a[MAX ~ 1-i}=t; ! 1 void search (int *a, int n) { int i; forli=0; i < MAX ; i++) { if (ali) == n) ( printf(“\n\n The Element %d is present at %d™ position”, n, it); return; ! if (i == MAX) printi(“\n\n The Element %d is not present in the Array’, n);EZ Data Structure Using ‘C’ Void display (int *a) S int i; printf (“\n”); for(i=0; i < MAX; i++) printf(“\t%d", afi); } 2.4 MERGING OF TWO ARRAYS Merging of arrays involves two steps : Sorting the array that are to be merged ‘Adding the sorted elements of both the arrays to a new arrays in a sorted order. Problem : Program for merging of two arrays of different size. 1. Create first array 2. Create second array 3. Sort first array 4. Sort second array 5. Merge both the arrays 6. Display the merge array 7. Exit Solution: — finclude #include #include #ineludecalloc.h> define MAXI 5; #define MAX? 7; int ta; int *create(int); Void sort (int *, int); Void display (int *, int), int *merge (int *, int *); Void main() int a, *b, *e, ch; elrser(); ch= 1; while (ch !=7) printf(“\n 1 > Create first Array”), printf(“\n 2 -> Create Second Array”);Arrays printf“\n 3 > Sort first Array”); printf{“\n 4 > Sort second Array”); printf“\n 5 > Merge both the Arrays”); printf(“\n 6 -> Display the Merge Array”); printf(“\n 7 > Exit”); printf“\n Enter your choice”); scanf{“fod", &ch); switch (ch) case 1: a= create (MAXL); break; case 2: b = create (MAX2); break; case 3: sort(a, MAXL); printf(“\n First Array\n”); display(a, MAX); break; case 4: sort(h, MAK2); printf“\n Second Array”); display(b, MAX2); break; : printf(‘\n After merging”); c = merge(a, b); display (e, MAX] + MAX2); break; case 6: display(c, MAX] + MAX2); break; ° exit; printf(“\n Invalid choice Either press 1, 2, 8, 4, 5, 6 or 7”); 11 End of switch 1 End of while getch0); 1 //Bnd of Main. int *create (int size) i int *a, i; a = (int *) malloc (size * size of (int)); for(i=0; i < size; i++) printf(“\n Enter the Element No. %d”, i+ 1); scanf(“%d", &ali}); return a;Gi Data Structure Usiny 1 Void sort(int *a, int size) ( inti, tj; for(i=0; i < size; i++) { for(j=i+; j < size; j++) ( if (ali] > a) ( t= ali; afi] = aff]; afi] 1 } 1 1 Void display (int *a, int size) { int i; forti=0; i < size; i++) ( printit“\n%d”, afi); } ) int *merge (int *a, int *b) { int *e; int i, j, k, size; size = MAX1 + MAX2; int *) malloc (size + size of (int)); for(k=0, j=0, i=0; i <= size; i++) if (alk) < bfil) { if (K >= MAXI) { forti++; j < MAX2; j++, i++) efi] = bul; }Aves EAI efi] = bij]; jes if G >= MAX2) fortit+; K < MAX1; K++, i++) efi) = alk); }* End of if | /* End of else ) * End of for loop return ¢; } 2.5 TWO DIMENSIONAL ARRAYS A2D array is a collection of elements placed in m row, and n columns ie, if we want to store the elements in the form of MATRIX then definitely we have to use the concept of 2D Array, We can define the 2D Array as follows : (size of Row) [size of Column); If we define int a[3) [3], The representation of this Array is as follows : @(0}l0] af[0}f) a(0j{2) a(l}fo) @fJ0) a@fi)l2) a(2\0) a2) a(2)(2] The total number of elements in this array is 9, So 18 bytes memeory is allocated for this array. Row MAJOR and Column MAJOR Arrangement : Rows and columns of a MATRIX, are only a matter of imagination. When a MATRIX gets stored in memory, all elements of it are stored linearly since computer's memory can only be viewed as consecutive units of memory : ‘This leads to two possible arrangements : (@ Row major arrangement Gi) Column major arrangement ‘The following figure shows these two arrangements : int a{3] [4] = ( {12,11-9,23},, {14,7,11,21}, {6,78,15,34),Data Structure Using ‘C’ @ Row major arrangement + 0th row —>|+ Ithrow —>|< 2nd row >| 12] 1 |-9}23| 14] 7 | 11 [121] 6 | 78 | 15 | 34 502, 504, 506, 508, 24 (ti) Column major arrangement [+ Oth column —rl+- 1th column ~rle- 2th column ~+|¢- 3th column —>| wuts {1]7 | wf -s] iu] is | 2 Jia] 4 502, 504, : « Since the array elements are stored in adjacent memory location, we can access any element of the array, once we know the BASE ADDRESS (starting address) of the ARRAY and number of rows and columns present in the array. 2.5.1 Address Calculation in 2D Array In general for an ARRAY a[m][n] the address of element ali}{j] would be => Base address + number of bytes (i * n +j) For example : If we want to calculate the address of 121 number in the above example. 121 is stored at al1[3] i=, j=3 and the order of array is al3J[4). Son = 4 Base address — 502 80, => 5024 1* 443 = 502 number of bytes +7 = 509 Ans. => 510 Ans. Column MAJOR arrangements : In general for an array a{m][n] the address of element ali)[j] would be => (Base Address + j * m +1) © NOTE THAT - C language permits only a Row MAJOR arrangement, whereas Pascal uses a column MAJOR Arrangement. => 121is present at a[1][3] =» 502+ number of bites (3 * 3 +1) m=3,n=4 502 + 2(10) = 502 + 20 = 522. Common MATRIX Operations : © MATRIX Addition MATRIX Multiplication © Transpose of a MATRIX © Print the Diagonal elements © To calculate the determinant of a MATRIX ,j=32.6 APPLICATIONS OF ARRAY Arrays and Polynomials : Polynomials like 5x‘ + 2x° + 7x" + 10x-8 Arrays can be maintained using an ARRAY. Arithmetic operations like addition and multiplication of polynomials are common and often we need to write a program involving these operations. Problem : Write a program to add two polynomials using Arrays : Solution: — finclude #include #define MAX 10; struct poly struct term int coeff; int exp; int number of terms ) thax]; Pe; Void initpoly(struct poly*); Void polyappend(struct poly *, int, int); struct poly polyadd(struct poly, struct poly); Void display (struct poly); Void main() struct poly P;, Pay Psi initpoly(&p,); initpoly(&p,); initpoly(&p,); polyappend(&p,, 1, 7); polyappend(&p,, 2, 6); polyappend(&p,, 3, 6); polyappend(&p,, 4, 4); polyappend(&p,, 5, 2); polyappend(&p,, 1, 4); polyappend(&pp, 1, 8); polyappend(&p», 1, 2); polyappend(&pp, 1, 1); polyappend(&po, 2, 0); P3 = polyadd(p,, Pa);Data Structure Using ‘C’ printf(“\nfirst polynomial\n”); display(p,); printf(*\nsecond polynomial\n”); display(p,); printf(“\nResultant Polynomial\n"); display(ps); getch(); 1 Void initpoly (struct poly *p) inti; p ~ number of terms = 0 for(i=0; i < MAK ; i+) P > t [i]. coeff = 0; p> tli. exp = 0; 1 Void polyappend (struct poly “p, int c, int e) { Pp 7 t[p > no. of terms}. coeff = ¢; p> t[p > no. of terms]. exp (p > no of terms); ! Void display (struct poly P) int ¢; forli=0; i < p. no. of terms; i++) if (p.tli). exp != 0) printf("%edx %dA”, p.tlil.coeff, ptlil.exp); else { printit"%d” p tli] coeff); 1 } struct poly polyadd (struct poly p,, struct poly p,)int i,j, ¢; struct poly ps; initpoly(&p;); if(p,. no. of terms > p, no. of terms) ¢ = pj. no. of terms; else ¢ = Py, no. of terms; icee; py. no. of terms +4) if (p,.tlil.coeff = = 0 && petlil.coeff == 0) break; if (p,.tlil.exp >= pp-tfil.exp) if (p,.tlil.exp == pp tlil.exp) | Pa-tlpg. no. of term] coeff = p, tfilcoeff + p,-tli]. coeff; Ps-tipy. no. of terms].exp = p, tlil.exp; indy i \ else Ps-tlps. no. of terms].coeff = p,.t{i).coeff p3-tlps. no. of terms).exp = p,.tfil.exp; ints else P3-tlpg. no. of terms).coeff = pp.t{i].coeff; P3-t[ps. no. of terms].exp = pptlilexp; ins return pg} ) Multiplication at Polynomials : Now we will discuss the multiplication of two polynomials : (ax" + bx +c) * (ax? + bx + x +d) —» a's + abe’ + acx® + adx? + abx! + bx" + bex” + bdx + acx* + ox + edData Structure Using ‘C’ ax) + Qabr‘ + x°(2ac +87) + x(ab + be) + xbd + c*)+ed Ans. Now we will discuss the concept of string. Before we discuss the concept of string, we will discuss the concept of sparse matrices : 2.7 SPARSE MATRIX Am x n matrix A is said to be sparse, if many of its elements are ZERO. A MATRIX, that is not sparse is called dense matrix. The diagonal and Tridiagonal matrices fit into the category of sparse matrices, Now we will consider a sparse matrix which is as follows : coood conmoo coors cocoon noooo eoouns A (8% 6) Sparse Matix How to represent the sparse MATRIX in memory The following are the schemes by which we can represent the sparse matrix in memory : (a) ARRAY Representation : IN ARRAY REPRESENTATION An array of triplets of type col, element> Is used to store NON ZERO Elements. ie. first field of the triplet is used to record row position, second to record column position and third one to record the NON ZERO Element of the sparse matrix. In addition, we need to record the size of the matrix. How the memory is calculated. The ARRAY REPRESENTATION will use [2 * (n+1) * size of (int) + n * size of (T)] Bytes of memory, where n is the number of NON ZERO elements and T is the data type of the elements. Required MEMORY declarations for the ARRAY Representation will be : #define MAX 50; struct triplet int row, column; float element; 4 struct triplet sparsemat{max]; ¢ THE ARRAY representation very rarely used for practical purposes. The major limitation of array representation of a sparse MATRIX is that we need to know the number of NON ZERO terms in each of the sparse matrices, we plan to use when the array is created. (6) Linked Representation : If we want to represent the sparse matrix with the help of linked list then it is as follow :rr A (5 x 6) sparse matrices : soooed conco coos eooon sucooce econe The description of this is as follows : © It contains one starter node that has four fields. A. n row (number of rows), n col (number of columns), num (number of NON ZERO Elements), and start (a pointer to the first row containing at least one NON ZERO Element). B. A linked list of rows containing at least one NON ZERO term in the ascending order of their row values. Each node of this lists has three fields : Row (Row number for corresponding row list). NEXT (A pointer to next node in the row lit). First (a pointer to the first column in a row having NON ZERO item). C. A linked list of columns containing NON ZERO terms, in the ascending order of their column values. Each node of this lists has three fields : Col (Column number for corresponding row list). Term(ANON ZERO value in column col). ¢ Link (A Pointer to the next column having NON ZERO element). The linked list Representation of the above sparse matrix is as follows : 2 5} 6|5 vw |e—| a |e—] oo J-—| 32 | Data Structure Using 2.8 STRING A string is the collection of characters and it is terminated with the help of ‘\0’ character. How to represent a string : A string can be represented using an array or a linked list. A. STRING of characters having length n can be implemented by a one dimentional array of n elements where the i” element of the array stores the i” character of the string. The advantage of such a representation is that the array elements can be directly accessed and this could speed up several operations on strings. char (10) S = "Man" S(0)="M’ st='a m[a [wn [x01 ei 401 408. 408 [3] ="\0' [Null Character] 2.8.1 The LINKED Representation is as Follows Mt >a" + [ay [van] For operations on string we use the predefined header file 2.8.2 Functions on String 1. Strlen : Strlen is a predefined function which is used to calculate the length of any string. Problem : Write a program to input a string and calculate the length of that string. Solution : #include #include #includecstring h> Void main() char s(80); int n; elrser(); print{(“\n Enter the string”); acanf"%s",s); n= strlen(s); printf(“\nThe length of the given string is %d”, n); getchO; } 2. Streat() : Streat() is a predefined function in which is used to concatenate two strings. ‘The general syntex is Void streat(source string, destination string);“Arrays Bi With the help of this function, the source and the destination strings are concatenated and the final result is stored in source string. : Problme : Write a program to input two string and the concatenate them and then print the concatenate string. Solution : #includecstdio.h> #include #include Void main() char s{80], 51[40]; elrser(); printf(‘\n Enter first string”); seanf(“%s",s); printf{*\n Enter second string”); seanf("%es",s1); streat(s, el); printft*\n The concatening string is %s”, s); getch(); 1 8. Strepy() : strepy() is a predefined function in which is used to copy the source string into destination string. Problem : Write a program to input one string and then copy it to the destination string and then print the destination string. Solution : fincludecstdio.h> #include #includecstringh> Void main() char s{80], s1{80); elrser(); printft“\n Enter the source string”), scani("%s”, 8); strepy(sl,s); printf{"\n The copied string is %s”, 81); getch(); 1 4. Strrev() : strrev() is a predefined function which is used to reverse the string. Problem : Write a program to input a string and then reverse the string and print the reverse string. Solution ; #include #includeEL Data Structure Using ‘C’ ) #include Void main() char s{80], s1[80); printf(“\n Enter the string”); scanfl“%s”, 8); 81 = strrev(s); printf(“\n The reverse string is %s”, sl); getch(); 5. Stremp() : stremp() is a predefined function in , which is used to compare source string to destination string. Problem : Write a program to input two string and then compare both the string. Solution : ) #include #includecconio.h> #include Void main() char s{80], s1{80}; printf(“\n Enter the first string”); scanfi“%s”, printf(“\n Enter the second string”); seanft"%s”, s1); if (stremp(s, s1) == 0) printf(“\n both the strings are equal”); else printi(“\n both the strings are not equal”); getch(); Now we have to do these operations with the help of USER Defined functions : #includecstdio.h> #include #includecstring.h> int xstrlen(char *); void strepy(char *, char *); void streat(char *, char *); int xstremp(char *, char *); void main() char s1[ ] = “ SRMS College”;ros char s2{]="SRMS Medical college”; char 83[80); int]; elrser(); printf(“\n First string is %s”, 81); 1 = strlen (s1); printf{“\n The length of the string s1 %d", 1); printf(“\n The second string is %s", 2); xstrepy (88, 81); printf(“\n string 63 after copied is %0”, 03); xstreat (68, 82); printf(“\n string 63 after concatanation is %s”, #3); if (xstremp(s1,s2) == 0) printf(“\n The string s1 and s2 are similar”), else printf“\n The string s1 and s2 are not similar”); getch0); int xstrlen(char *s) ) return (1); } void xstrepy (char *t, char *s) while (*s) ata 3; t= NO} 4 void xstreat ( char *t, char *s) while (*t) tet; while (*s)Data Structure Using ‘C’ tot me Fett; t=O; ) int xstremp (char *s, char *t) { while (*s == *t) {if (Cs) return 0; return (+s, *t); } Pointers and strings : We can define the string as follows : char str{ ] = “Hello”; char *p = “Hello”; void main() char sf ] = “Hello”; char si{10]; char *s = “Good Morning”, char *g; P* Error */ q=5; works; 4 How to define two dimention array of string: char s{20] [20]; or char *qs[20); Ifyou want to store 20 names then you can write it as follows : forti=0; i < 10; i++): { printf(“\n Enter the string”); scani(“%s”, si); } 2.9 PATTERN MATCHING Pattern matching means we want to search sub-string into a string. 2.9.1 Brute Force Algorithm This is the simplest algorithm for the searching of a sub-string in a string. In this algorithm the string s in which the pattern string is to be searched is scanned character by character.ion EN « Beginning from the 0" character of the string 61 each character, is compared with each and every character of the pattern string P. This process continues till either there is no mismatch or the pattern string P is not exhausted. If a match is found then the index of characters of s from which the comparison bijon is returned as the position where the pattern string P is found. Program for Brute Force Algo : #includecstdio.h> finclude #include int xstreearch(char *, char*); void main() char a[80], 5180]; int pos; elrscr(); printf(“\n Enter the first string”); geta(s); printf(*\n Enter the second string”); gets (sl); pos = xstrsearch (s1, 92); printf(“\n The pattern string is found at position %d”, pos); getch(); , int xstrsearch(char *s1, char *s2) { int i, j,k; int ll = strlen(s1); int 12 = strlen(s2); for(i=0; i <= 11-12; i++) 2Li}) && (j < 12) ( kes deh 1 if G ==12) return 1; else return —1;Data Structure Using 2.10 ARRAY AS PARAMETER We can pass the array in the function with the help of Pointers. For example : If we define int max (int *) The meaning of this line is that max is a function which accepts an integer type of Pointer ie, an integer type of array and according to that array it returns an integer type of value. Problem : Write a program to input 10 numbers and calculate the maximum number, with the help of function. Solution : #includecstdio.h> #include #includecstd.h> int max (int *) // Function Prototype void main(); — int a[10}, i, g, m; clescr(); for (i= 0,1 < 10,i+j) printi(‘/n enter the No.”); scanfi“%d”, and ali m = mox (a); // calling of the function prinf(“/n the max. no. is %d”, m); getch(); int max (int «p) int m, i; m = pl0); for (i= 1,1 < 0;i +4) if (m < plil) m= phil; return (m); t 2.11 ORDERED LIST If the list ie, Array is ordered in either ascending or descending order than that is known as Ordered Lists.Arrays Problem : Write a program to input 10 numbers and then sort the number in ascending order with the help of function. Solution : #include #include void sort(); void main() clrser(); sort(); getch(); ) void sort(); int a[10}, i, j, ts for (i = 031 < 10;i +t) ( printft'/n enter the No.”); seanfl“%d", & ali); 1 for (i i < 10; i++) for j =i +1;j < 10, j++) if(ali] > ali) t=alil; afi) = aff]; afi) = t; 1 Print(“/n The elements in the Sorted order”); for (i = 0;i< 10; i++) prinft(“in %d”, alil); ' getch0);BL Data Structure Using ‘C’ SUMMARY Array is a linear Data Structure which holds the similar data. Array plays a very important role if we want to store more than one element of the same type. ‘The syntex for defining the 1D Array is ‘ (size); __— ed If we define int a{3}; the meaning of this line is that o is an array which holds 3 elements and the elements are stored from a[0] to a[2). ‘The syntex for defining the 2D Array is {size of row] (size of column); If we define this int @[3}[3], the meaning of this line is that @ is an array which holds 9 elements and the elements are stored from a{0}{0] to a{2)(2). ‘The syntex for defining the 3D Array is «data type> (No. of two dimensional Array] [size of row] {size of column] Prosiems Poe ep 10. ML 12. 13. 14. 15. 16. 17. 18. 19, What do you mean by Array ? Classify it ? Write a program to input 10 number and calculate the max. number between 10 numbers ? Write a program to input 10 numbers and calculate the min. number between 10 numbers ? Write a program to input 10 numbers and sort that numbers in ascending order ? Give an example to show the usefullness of an array ? Define static memory allocation and dynamic memory allocation ? Write an algo / function to merge two arrays stored in ascending order ? A.2D Array X{6I[4] is stored a row wise in the memory. The first clement of the array is stored at location 80. Find the memory location of X{3}2] if the each elements of array requires (4) memory locations ? Give an array X{6J[6] whose base address is 100. Calculate the location X(2][5] if each element occupies 4 bytes and array is stored row wise ? Define 3D Array with example ? Write a program to input two 3 x 8 matrices and print the addition of matrix ? Write a program to input two 3 x 3 matrices and print the multiplication of matrix ? Write a program to input a 3 x 3 matrix and calculate the transpose of that matrix ? Write a program to multiplication of two polynomials with the help of array ? Define Markov Algo for Pattern Matching ? ‘Write a program to input a string and check whether the given string is palindrome or not ? Write a program to generate the Fibonacci series using arrays ? Differentiate between static and dynamie memory allocation ? Calculate the address of X[4, 3] in a 2D Array X (1.5, 1..4] stored in row major order in the main memory. Assume the base address to be 1000 and that each element requires (4) words of storage ? Write a program to input. 10 number and print the aum and average of numbers ?STACKS A stack is a non-primitive Linear DATA structure. It is an ordered list in which addition of NEW data item and deletion of already existing data is done from only one end, known as TOP of the stack (TOS). As all the deletion and insertion in a stack is done from top of the stack, the last added element will be the first to be removed. That is the reason, why stack is also called Last In First Out. Example : A common model of a stack is plates in a marriage, a party or coin stucker. Fresh plates are “Pushed” onto the top and “popped” off the top. Graphically we can represent this as follows : 4) Te (3) go | RP) aay | PP] cao a3) (20) 20) (Empty Stack) “UInserting) (Inserting) “(Inserting) (Element 54) (Top) First Element” Second Element Third Element” Deleted 3.1 STACK IMPLEMENTATION Stack can be implemented in two ways : (a) Static Implementation (6) Dynamic Implementation (a) Static Implementation : Static implementation is done with the help of Array. In this type memory is waste and this is not efficient. (b) Dynamic Implementation : 1s also called linked list representation, and uses pointers to implement the stack type of Data structure. 3.2 OPERATIONS ON STACK The basic operations that can be performed on stack are as follows : 1. Push : The process of adding a new element to the top of stack is called push operation. Pushing an element in the stack invoke adding of element, as the new (41)Ez Data Structure Using ‘C” ] element will be inserted at the top after every push operation, the top is incremented by one. In case the array is full and no new element can be accommodated, it is called stack full condition. This condition is called stack overflow. Pop : The process of deleting an element from the top of stack is called pop operation. After every pop operation the stack is decremented by one. If there is no element on the stack and the pop is performed then this will result into stack underflow condition. 3.3 STACK TERMINOLOGY 1. CONTEXT : The environment in which a function executes, includes argument: values, local variables and global variables. All the context except the global variables is stored in a stack frame. . STACK frames : The data structures containing all the data (arguments, local variables, return address etc.) needed each time a procedure or function is called. . MAXSIZE : This term is not a standard one, we use this term to refer the maximum size of stack. . TOP : This term refers to the top of the stack (TOS). The stack top is used to check stack overflow or underflow conditions. Initializing TOP stores -1. . STACK : It is an array of size MAXSIZE. |. Stack empty or UNDERFLOW : This is the situation when the stack contains no element. At this point the top of stack is present at the bottom of the stack. . Stack overflow : This is the situation when the stack becomes full and no more elements can be pushed on to the stack. At this point the stack top is present at the highest location of the stack. 3.4 ALGORITHMS FOR PUSH AND POP Ll Push : Let stack {maxsize] is an array for implementing the stack. 1. [check for stack overflow 7] if top = maxsize — 1 then print overflow and exit. 2. set top = top + 1 [ increase the top by 1] 8. set stack [Top] = item (Inserts item in new top position] 4. Exit. Algorithm for deleting an element from the stack : This algorithm deletes the top element of the stack and assign it to a variable item. 1. [check for the stack UNDERFLOW] if top < 0 then print “stack UNDERFLOW’” and Exit. else [Remove the top element] set item = stack [top]; 2. Decrement the stack top set top = top — 1 3. Returned the deleted item from the stack. 4. Exit.Stacks | 43 | Problem : Write a program to demonstrate the following operations : Solution : 1. Push 2. Pop 3. Display Enter your choice #include #include #include #dofine MAX 10; Void push (); int pop); Void display(); int stack[maxsize]; int top = -1; Void main() int ch; char ch1; do " drser(); printf(‘\n 1 + Push”); printf{“\n 2 -> Pop”); printf(“\n 3 > Display”); printf(“\n Enter your choice”); scanit"%d’, &ch); switch (ch) { case 1: push(); break; case 2: printf (“\n The deleted item is %d”, Pop); break; case 3: display(); break; default : printf(*\n You entered wrong choice”); ! printf{“\n Do you want to continue (Y/N )"); filush(stdin); seani("%c",&ch1); while (ch == 'y’ | Ichl == ‘Y):Structure Using getch(); Void push) int item; ifftop == maxsize ~ 1) printf(“\n Overflow stack is full”); getch(); exit(0); else printf(“\n Enter the element which you want to insert”); scani(“%d", &item); top = top + 1; stackltop] = int pop() inti; if (top == -1) printf(“\n UNDERFLOW stack is empty”); getch0); exit(0); else i= stack{top); top = top ~ 1; 1 return(i); 1 Void display() t int i; if (top == - 1) printft“\n stack is empty”); getch; exitiO);else’ forli=top; i >= 0;i--) printf("\n The item is %d", stackli]); ' 3.5 IMPLEMENTING STACK USING POINTERS This is also known as linked list implementation of stack. #include #include struct stack int no; struct stack *next; ] *top = NULL; typedef struck stack st; void push(); int pop0; void display(); void main() int ch; char chl; int item; do elrser(); printf(‘\n 1 + Push”); printf(“\n 2 + Pop”); printf(“\n 3 + Display”); printf{‘\n 4 + Exit”); printf(‘\n Enter your choice”); scanft“%d", &ch); switch(ch) ease 1: push(); break; case 2: printf(“\n The deleted item is %d”, pop()); break; case 3: display(); break; StacksEL Data Structure Using ‘C” case 4: exit(1); default : printf(“\n Wrong choice”); printf(“\n Do you want to continue (Y/N)"); flush(stdin); scanf(“%ec", &ch1); while (chl == ‘y' I ch ==‘Y); getch(); void push() st *node; node = (st *) malloc (size of (st)); printf(“\n Enter the number “); scanf("%d", & node ~» number); node -> next = top; top = node; int pop() printf(“\n Stack is empty”); getch(); exit(); else top = top — next; free(temp); return(temp — number ); void display() st “temp; temp = top; while (temp — next != NULL) printf(“\n Number is %d", temp — number );Stacks Ea temp = temp — next; 1 printf("\n The number is %d”, temp —> number ); ' 3.6 APPLICATION OF STACKS The following are the application of stack : As mentioned earlier, stack is one of the most commonly used data structures, some of the applications are : 1, Stacks are used to pass parameters between functions, On a call to a function, the parameters and local variables are stored on a stack. 2. High level Programming languages, such as Pascal , C etc. that provides support for recursion use stack for book keeping. Remember, in each recursive call, there is need to save the current values of parameters, local variables and the return address (the address where the control has to return from the call). 3. Stack frames : Almost invariably, programs compiled from modern high level languages (Even c!) make use of a stack frame for the working memory of each procedure or function invocation, 4, When any procedure or functions is called, a number of words — The stack frames — is pushed onto a program stack. When the procedure or function returns, this frame of data is popped off the stack. 5. As a function calls another function, first its arguments, then the return address and finally space for local variables is pushed onto the stack. Since each function runs in its own environment or context, it becomes possible for a function to call itself — A technique is known as recursion. This capability is extremely useful and extensively used — because many problems are elegantly specified or solved in a recursive way. ° NOTE : The stack is a region of main memory within which programs temporarily store data as they execute. For example : When a program sends parameters to a function, the parameters are placed on the stack. When the function completes its execution, these parameters are popped off from the stack. 6. When a function calls other function the current contents (i.e. variables) of the caller function are pushed onto the stack with the address of instruction just next to the call instruction, this is done so that after execution of called function, the compiler ean track back (remember) the path frame where it is sent to the called function. 7. Reversing a String : As the characteristic of stack is reversing the order of execution. This fact can be exploited to reverse strings of line of characters. This can be simply thought of simply as pushing the individual characters, and when the complete line is pushed onto the stack, then individual characters of the line are popped off. Because the last inserted character pushed on stack would be the first character to be popped off, the line obviously be reversed.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.Stacks EE ‘The error in the above calculation occurs, as there are no braces to define the precedence of operators. Thus expression A + B * C is interpreted as A + (B * C). This is an alternative to convey the computer that multiplication has higher precedence over addition, as there is no other way to specify this. Operator Precedence : Exponential operator © Highest precedences Multiplication/division +,! Next precedence Addition/substraction +,- Least precedence 3.8.1 Rules for Converting Infix to Postfix Form 1. Parenthesize the expression starting from left to right. 2. During parenthesizing the expression, the operands associated with operator having higher precedence are first parenthesized. 3. The sub-expression (part of expression) which has been converted into postfix is to be treated as single operand. 4, Once the expression is converted to postfix form, remove the parenthesize. For example : 1 A+Bte (Convert this into postfix) A+(B*C) A+(BC*) (ABC *+) Ans. 2 A+((B+C)+(D+E)* FYG A+[{ (BC+) + (DE+) * F/G] A+[{ (BC+) + (DE + F * VG] A+[{ (BC+) (DE+ F* +)/G] A+(BC+DE+F*+G/) ABC +DE+F*+G/+ Ans. Example: A+B-C (A+B)-C (AB+)-C AB+C- Ans. Example: A*B+C/D (A*B) +(CD) (AB *) +(CD/) AB*CD/+ Ans. Example: A *B+C = (A*B)+C (AB +C = AB*C+ Ans. Example: A+B/C-D A+(BIC)-D A+(BO4)-D (ABC/+D-) Ans.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.stats EBM #includecstring.h> char stack(50], int top=-1; Void in_to_post (char{ }); or Void in_to_post (char *); Void push (char); char pop(); int preced (char); ‘Void main() char infix(50); printf(“\n Enter the infix expression”); gets(infix), in_to_post (infix); getch(); Void push(char symb) if (top >= 49) printf(“\n Stack overflow”); getch(); return(); else top = top +1; stack{top] = symb; } char pop() { char item; if (top == 1) printft“\n Stack is empty”); getch0); return(); } else item = stack{top];Data Structure Using ‘C’ top--; return(item), int preced (char ch) if (ch == 47) ~ { - oR return (5); else if (ch return (4); else if (ch == 43) return (3); else return (2); } void in_to_post (char infix{ ]) int length; static int index = 0, pos = 0; char symbol, temp; char postfix[50]; length = strlen(infix); while(index < length) symbol = infixtindex); switch(symbol) { case’: Push (symbol); break; case‘): temp = pop (); while(temp !="c') postfix(pos] = temp; pos +4; temp = pop(); if (ch ==‘,’) { return 5; } else if (ch == "*'! Ich =='7)case: case ‘7: while (preced (stack{top]) >= preced (symbol)) { temp = pop(); post fix [pos] = symbol; postfix (pos) = temp; post+ pos +4; } push (symbol); break; default: Postfix{pos++] = symbol;] break; post fix [pos] = temp; ) pos++ index +4; } while(top >= 0) { temp = pop0); postfixipos++] = temp; postfix{pos++] = ‘\0’; puts(postfix); return; ) 3.8.3 Converting Infix Expression to Prefix Expression This algorithm is bit tricky, in this we first reverse the input expression a + b*e will become c*b + a and then we do the conversion and then again we reverse to get the result. Doing this has an advantage that except for some miner modification algorithm for infix to prefix remains almost same as the one for infix to postfix. Example: A+B*C (C*B+A) (C*B)+A (CB*)+A C(B*A+) (+A*BC) Ans. Algorithm and program is same but only the difference is that firstly we reverse the given string and then evaluate it and then we again reverse it.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.EL Data Structure Using ‘C’ Problem : Evaluate the expression 562 + * 124 / — in tabular form showing stack after every step. Solution : | Srvevmiemens || rere q Push Push Push Pop @) elements Push result Pop 2 elements Push result 40 Push 12 Push Y Pop two elements Push result @) Pop two element Problem : Write a program to accepts a postfix expression, asks the values for variables of the expression, calculate the expression for that values. 231 Solution : #include #include float stack[{10]; int top =-1; Void push(float); float pop(); float level(char{ }, floatf ));Stacks [EZ void main() int i=0; char suffix(20]; float value[20], result; elrser(); printf(“\n Enter a valid postfix expression”); gets(suffix); while(suffix{i] != ‘\0") { iffisalpha (suffixfi)) { flush(stdin); printf(“\n Enter the value of %c”, suffix(i)); scanf(“%f", &valueli)); ies; result = eval (suffix, value); printf(“The result of %s = %f”, suffix, result); getch0); 1 float eval(char suffix[ ], float datal J) int i= 0; float op1, op2, res; char ch; while (suffix{i] != ‘\0°) ch & suffixfil; if (is alpha (suffix [i])) Push (data [i)); else 0p2 = pop); opt = pop); switch (ch) case‘+': push (op + op2); break; case‘: push (op] ~ op2); break;aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.Stacks #include #tdefine MAX 20; typedef struct node int info, struct node*next; 1 *stack; typedef enum{false, true} boolean; Void createstack(stack*); boolean is empty(stack ); Void push(stack *, int); int pop(stack *); Void disposestack(stack *); Void reduction (int *, int, int, int); Void quicksortiterative(int *, int); Void main() int i, n, afmax]; elrser(); printf(“\n Enter number of elements in Array”); scanf(“%d”, &n); iffn > max) printft“\n Input size of ARRAY greater than declared size”); exit(1); printf(“\n Enter %d elements”, n); for(i=0; i a} In the similar way, one can easily compute the negative (integer) exponential power of a number i.e, a”. The recursive definition is lifb=0 | power (a,b) = { a* power (a,—(b- 1)ifb< 0 Here we have taken mantissa = a and exponent = b. The power is negative so the inverse of the returned value of the function is taken as the exponential power of the number. Problem : The recursive program for calculating a’ or a” is illustrated as follows : Solution : #include #include double power(double, float); Void main() double mantissa; float exponent; printf(*\n Input the mantissa”); scanfi“% If”, & mantissa); printi“\n Input the exponent”); scanfi“% If", & exponent); if (exponent < 0) printf(“\n The mantissa * exponent : % If", power (mantissa, exponent)); else 42,3 printé(“\n Mantissa * exponent : % If, M1 2x power (2, 2) power (mantissa, exponent)); MH 2x 2 power (2, 1) getch(); i [Bxaxout]Recursion El double power(double m, float e) ifle== 0) retum 1, + dlseif(b <0) ( return (a * power(m, 1- 1)); ) else return (a* power (m, 1 - 1)); ) *Greatest Common Divisor : Another recursive example is to find the greatest common divisor of two positive integers with the help of Euclid’s algorithm. The definition of Euclid’s algorithm is as follows : GCD(n, m) = mifn>,m andn mod m=0 otherwise GCD (m, n mod m) Problem : The GCD Algorithm is implemented in the following program : Solution : #include #include int GCD (int, int); Void main() int m, n, result; elrser(); printf(“\n Enter the first integer number”); seanf(“%d”, &n); printf(“\n Enter the second integer number”); scanf(“%d”, &m); result = GCD(n,m); printf(“\n GCD of : %d and %d is = %d”, n, m, result); getch(); int GCD (int n, int m) if (n >= m) && (n%m = 0)) return m; else GCD (m, (n%m)); } | 4.4 THE TOWER OF HANOI! The tower of HANOI is a famous recursive problem, which is based on three pegs and a set of discs of sizes.EL Data Structure Using ‘C’ © Suppose three pegs labeled X, Y and Z are given and on peg X there are finite number of n discs in increasing size order i.e., biggest one at the bottom and the smallest one at the top. The problem is to more dises from neg X to peg Z using peg Y, whenever it is required. The rules which one has to take into account before moving a disc are : Only one disc may be moved at a time. Only the top disc on any peg may be moved to any other peg. A larger disc cannot be placed on a smaller one. In data structure like linked lists, stacks, trees, quicksort, recursion is more hardy. In certain problems like tower of Hanoi, recursion may be the only solution. © It is a game problem, there will be three different sized disks. Each disk has a hole in the centre. So that it can be stacked on any of the pegs. Call three pegs as X, Z and ¥. At the beginning of the games, the disks are stacked on the X peg, that is the largest sized disk on the bottom and the smallest sized disk on top, for n = 3 disks. Rules for the game : A. Translating the disks from the source peg to the destination path such that at any point of transformation no larger disk is placed on the smaller one. B. Only one disk may be moved at a time. C. Each disk must be stacked on any one of the pegs. Recursive definition : It is clear that the movement of disk is from X peg to the Y peg. And the Z peg is used for intermediate stacking assuming there is only one disk its movement is straight forward. ie.. Assuming that initially all disks are stored on the X peg and transferring all these to the y peg can be recursively defined as follows : ‘A. Move the top (n-1) disks from the X peg to the Z peg. B. Move the n' disk to the Z peg. C. Move the (n-1) disk stacked on the Z peg to the ¥ peg. Now if we have three disks and the initial three disks are on X peg and we want to transfer three disks from X to Z through Y then the graphical representations of these moves are as follows : eoeee a = Y z Y z Disk 1 x Disk 2 Disk 2 Disk 3 [Disk s [isk] (initial state) K+2)Recursion |71 | Step 2 x Y 2 [Disks] [Disk Disk] &-Y) Step 3 P x Y 2 | fo Disk 3 Disk 2 ay) Step 4 x 1 a Diskt [Disk 2 Dik3 | (X—»2) Step 5 x Y Zz Disk1 | Disk 2 l Disk 3 (¥-»X) Step 6 x y Z l Disk 2 Disk1 [disks (Y-+Z) x Zz Step7 vi I Disk1 Disk 2 Disk 3 (KZ)aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.5 lan A queue is logically a first in first out (FIFO) type of list. In our everyday life we come across many situations where we ought to wait for the desired service, there we have to get into a waiting line for our turn to get serviced. ¢ This waiting queue can be thought of a queue. @ Queue means a line. For example : At the railway reservation booth, we have to get into the reservation queue. Note the important feature of the queue — new customers got into the queue from the rear end, whereas the customers who get their seats reserved leave the queue from the front end. It means the customers are serviced in the order in which they arrive the service centre (i., first come first serve type FCFS). The same characteristics apply to our queue. Thus a queue is a non-primitive data structure. It is an homogeneous collection of elements in which new elements are added at one end called the rear end and the existing elements are deleted from other end called the front end. ie., for the implementation purpose we have to take two variables ie, first is rear for the insertion purpose and second is front for the deletion purpose. ‘The following figure show queue graphically during insertion operation Empty Queue R=0, F=0 20 #9 2 2 FH 8 tt One element queue FR F FR zB FeO, Re2 20 | 30 20 | 20 | 40 t ‘ ‘Two element queue t t ‘Three element queue It is clear from the above figure that whenever we insert an element in the queue, the value of rear is increment by 1. ie, Rear = Rear+1 Note that during the insertion of first element in the queue we always increment the front by 1 ie. Front = Front +1 (81)aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.void delete() int item; if (front < 0) printf(“\n Queue is empty”); break; ' else item = Queuelfront}; front = front + 1; printf("\n The deleted item is %d”, item); void display() int forli = front; i <= rear; i++) printf(“\n %d”, queueli)); 4 5.3 LIMITATIONS OF SIMPLE QUEUES * There are certain problems associated with a simple queue, when queue is implemented using array as we have just studied. Consider an example of simple queue Q{6] which initially empty. We analyse the problem with a series of insertion and deletion operations performed on the queue. This insertion and deletion processes are shown in the following figures a Rech Feat # R=0, Feo o] [| | o i 2 3 4 o 1 2 3 4 Initially empty queue) (One element queue)aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.Queues EI { struct queue *temp; int vah if (start == NULL) printf{*\n Queue is empty”); getch(); return; or exit(1); temp = start; value = temp > info; start = start — next; free(temp); return(value); void display() struct queue “temp; temp = start; while(temp — next != NULL) printf(“\n %d”, temp -» info); temp = temp —> next; ) printf(“\n %d”, temp -+ info); getch0; } Note that we don’t need to check overflow condition in dynamic implementation during addition operation. Though overflow can occur in this implementation (when we have no more RAM available), but it occurs almost never. Only the underflow condition is to be checked during deletion operation. 5.5 CIRCULAR QUEUE Accircular queue is one in which the insertion of a new element is done at the very first location of the queue if the last location of the queue is full. @ In other words if we have a queue Q of say n elements, then after inserting an element last (ée., in the (n-1)") location of the array the next element will be inserted at the very high first location (i.e., location with subscript 0) of the array. © It is possible to insert new elements, if and only if those locations (lots) are empty. We can say that a circular queue is one, in which the first element comes just after the last element.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.Queues El printf(“\n Do you want to continue”); fflush(stdin); scanft"%d”, &ch1); while(ch1 == 'y’ | ch] 2=‘Y); getch(); 1 void cqinsert() int n; if (front == (rear + 1) % max) printf(“\n Queue is full"); getch(); exit(1); else { printft“\n Enter the element to be inserted”); scanf(“%d", &n); if (front == —1) front = rear = 0; else rear = (rear + 1) % max; eqirear] = n; int eqdelete() int num; if (front == -1 || rear == front) printf{"\n Queue is empty’); getch(); exit(1); else num = cq[front];aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.6 | LinKeb List If the memory is allocated before the execution of a program it is fixed, and it cannot be changed. ‘We have to adapt an alternative strategy to allocated memory only when it is required. There is a special data structure called linked list that provides a more flexible storage system and it does not require the use of arrays. For stack and queues, we employed arrays to represent them in compute memory. When we choose arrays representation (also called sequential representation) it is necessary to declare in advance the amount of memory to be utilized. ‘The memory is very important resources, so we should handle it efficiently. - Key terms : As we know, linked list is the collection of nodes. These nodes are containing two fields : A. Data field B. Link field The data field contains an actual value to be stored and processed and the link field contains the address of the next data item in the linked list. The address used to access 2 particular node is known as a pointer. Therefore the elements in a linked list are ordered not by their physical placement in memory but their logical links stored as part of the data within the node itself. In other words the logical and physical ordering of data items in a linked list need not be the same, but in sequential representation these ordering are the same. Null pointer Note that the link (next) field of the last node contains Null rather than a valid address. It is a Null Pointer and indicates the end of the list. External pointer It is a pointer to the very first node in the linked list, it enables us to access the entire linked list. 6.1 LINKED LIST Linked list is collection of nodes and each node is divided into two parts : A. Information field B. Address of next field. The linked list is categorised into four categories 1, Linear or singly linked list (101)aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.This can be represented as follows : Start Data Link 1] os 1 2) L 5 2 3/ Q@ 1 3 4> M 2 4 5 P 3 5 6 —_ 6 * eal 7 s| oN — }\o Null] 8 The above example of linked list indicate that two nodes of a list need not occupy adjacent elements in the arrays data and link. However each list must have its own pointer variable giving the location of its first node. 6.4 REPRESENTATION OF LINEAR LINKED LIST Suppose we want to store list of integer numbers then the linear linked list can be represented in memory with the following declarations : struct node { int a; struct node *next; typedef struct node NODE; NODE * start; ‘The above declaration defines a new data type, whose each element is of type node-type and gives it a name NODE. 6.4.1 Operations on Linked List ‘The basic operations to be performed on the linked lists are as follows : 1. Creation 2. Insertion 3. Deletionaa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.ny case case 2: case 3 case 4 case 6 case 8 default Linked List EE) elrser(); do printi(“\n 1 > Insert element at begin”); printi(“\n 2 -» Insert element at last position”); printf(“\n 3 ~ Insert element at specified position”); printf(“\n 4 + Delete from the begin”); printf(“\n 5 — Delete from the end”); printf(“\n 6 -> Delete from the specified position”); print{(“\n 7 -> Display or inorder tranversing”); printf(“\n 8 -> Exit); printf(“\n Enter your choice”); seanf(“%d”, &ch), switch(ch); : inseratbegin(); break; insertatlast/); break; : insertatspecified(); break; : del_begin(); break; : dellast0; break; : del_specified(); break; : display; break; + exit(L); : printf(“\n Wrong choice”); printf“\n Do you want to continue”); fflush(stdin), scanf("%e", &ch1); while(ch1 == ‘y' 1 | chi getch0; Start void insertatbegin() | P struct node*temp, *p; P = (struct node*) malloc (size of (struet node); printf“\n Enter the information”);aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.{ Linked Ust RE] printf(“\n 1 -> Create first list”); printf{“\n 2 —> Create second list”), printf(“\n 3 > Concat both the list”); printi(“\n 4 —> Searching element’); printf(“\n 5 > Sorting list”); printf{"\n 6 —» Display”); printit“\n 7 > Exit"); printf(“\n Enter your choice”); seanfi“%d”, &ch); switch(ch) case 1: create(start); case 2: case 3: ease 4: break; create(start1); break; start3 = concat(start 1, start2), break; printft“\n Enter the list name where you want to search”); scanft%os",a); if (stremp(a, “first”) search(start); else if (stremp(a, “second” search(start1); 0) else search(start2); break; : printf(“\n Enter the name of the list which you want to sort”); scan(“%s", a); if (stremp(a, “first” == 0) sort(start); else if (stremp(a, “second”) sort(start1); 0) else sort(start2); break; printft"\n Enter the name of the list which you want to display”); scanf(“%s", 8); if (stremp(a, “first? display(start); else if (stremp(a, “second”) == 0) display(start1); 0) else display(start2); break;aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.FER Dota Structure Using "Cc" templ=temp1-+ next; forliz0, ie(pos +1); i++) temp2=temp2— next; temp1— next=temp2; temp2 pre=temp1; free(temp); ! void merg0 { struct node *temp1, *temp2; temp |sstart; temp2=start]; while(temp + next!=start) temp1=temp1— next; while(temp2— next!=start1) temp2=temp2— next; temp] > next=startl; startl— pre=temp1; temp2— nextestart; start > pre=temp2; sort); display(); } void sort() { struct node “temp, *temp1; int tempe; temp1=start; temp=start; for(temp=start; temp -next!=start;temp=temp ->next) { for(temp1=temp ->next;temp!!=start;temp1=temp1 —next) { ifftemp -» info > temp! — info) { tempe=temp — info; temp + info=tmep! — info; temp] — info=tempe; 1 1 display();aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.TREE Now we will discuss the concept of trees Trees are very flexible, versatile and powerful data-structures that can be used to represent data items processing hierarchical relationship between the grandfather and his descendents and in turn their descendants and so on. In this chapter we will discuss the following topics : « Tree (Definition), « Binary Trees, « Binary Tree Representation e Trees and their applications 7.1 TREE A tree is a non-linear data structure in which items are arranged in a sorted sequence. @ It is used to represent hierarchical relationship existing amongest several data items. Definition : It is a finite set of one or more data items (nodes) such that : A. There is a special data item called the root of the tree. B. And its remaining data items are partitioned into number of mutually exclusive (ie., disjoint) subsets, each of which is itself a tree. And they are called subtrees. The following structure shows a tree : Level 0 Level 1 Level 2 Level 3 ¢ Natural trees grow upwards from the ground into the air. But tree data structure grows downwards from top to bottom. @ It is an universally practical convention for trees. (141)aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.aa You have either reached a page that is unavailable for viewing or reached your viewing limit for this book.[126 fll Data Structure Using ‘C” The following steps are encountered : Pass 1 : a{1) is inserted either before or after a[0] so that a[0] and a[1] are sorted. Pass 2 : a[2] is inserted either before a[0] or between a[0] and af1] or after all) so that elements a[0}, a{1), a[2] are sorted. Pass 3 : a{3] is inserted either before a[0] or between a[0] and afl] or between afl] and a{2] or after a[2] so that the elements a[0], a[1], a[2] and a[3] are sorted. Pass k : a[k] is inserted in proper place in the sorted sub-array a(0], a[1], a[2) . a[k — 1] so that after insertion, the elements a[0], a[1], a[2] afk — 1) are sorted. Pass (n- 1): a{n— 1) is inserted in proper place in the sorted sub-array {0}, a{1J, a[2], a[n — 2] so that after insertion, the elements o[0}, a{1), a[2] ....... ala — 1] are sorted. Thus after (n — 1) passes, the array will be sorted in ascending order. e.g., sort the following array by insertion sort. Pass k : 1% 33, 44, i, 88, 22, 55 m kel: “77, 33, 44 WU, 88, 22, 55 ke2: 83, “a, ll, 88, 22,55 ka3: An ay 88, 22, 55 hed: 0,

You might also like

• Principle of Compiler Design

  

  100% (3)

  Principle of Compiler Design

  120 pages
• Advanced Computer Architecture

  

  88% (17)

  Advanced Computer Architecture

  170 pages
• Fundamentals of Data Structures in C by Ellis Horowitz Sartaj Sahni Susan Anderson Freed 0929306406 PDF

  

  No ratings yet

  Fundamentals of Data Structures in C by Ellis Horowitz Sartaj Sahni Susan Anderson Freed 0929306406 PDF

  5 pages
• Algorithms Design and Analysis by Udit Agarwal PDF

  

  67% (15)

  Algorithms Design and Analysis by Udit Agarwal PDF

  245 pages
• Horowitz and Sahani Fundamentals of Computer Algorithms 2nd Edition PDF

  

  No ratings yet

  Horowitz and Sahani Fundamentals of Computer Algorithms 2nd Edition PDF

  777 pages
• Dunham - Data Mining PDF

  

  83% (6)

  Dunham - Data Mining PDF

  156 pages
• (PDF) Fundamentals of Data Structure in C

  

  No ratings yet

  (PDF) Fundamentals of Data Structure in C

  202 pages
• Data Structures Using C Compress

  

  No ratings yet

  Data Structures Using C Compress

  323 pages
• Object Oriented Programming Through Java

  

  No ratings yet

  Object Oriented Programming Through Java

  130 pages
• Programming in C

  

  100% (1)

  Programming in C

  689 pages
• Research Paper On DSA

  

  No ratings yet

  Research Paper On DSA

  6 pages
• Introduction To C Programming Notes PDF

  

  100% (3)

  Introduction To C Programming Notes PDF

  425 pages
• CP Text Book

  

  No ratings yet

  CP Text Book

  546 pages
• Design and Analysis of Algorithm

  

  No ratings yet

  Design and Analysis of Algorithm

  116 pages
• Group Theory Discrete Mathematics Mukesh Bhardwaj

  

  100% (1)

  Group Theory Discrete Mathematics Mukesh Bhardwaj

  29 pages
• Data Structures by D. Samantha

  

  67% (9)

  Data Structures by D. Samantha

  167 pages
• 12 Computerscience Eng SM 2024

  

  No ratings yet

  12 Computerscience Eng SM 2024

  291 pages
• Unix Programming For BE VTU Cou - I. A. Dhotre

  

  No ratings yet

  Unix Programming For BE VTU Cou - I. A. Dhotre

  292 pages
• Unit 2: Classes, Objects and Class Diagrams

  

  No ratings yet

  Unit 2: Classes, Objects and Class Diagrams

  17 pages
• Important Que List (Chapterwise) (Chapters 1 To 11 ANSI C)

  

  50% (2)

  Important Que List (Chapterwise) (Chapters 1 To 11 ANSI C)

  9 pages
• Sample 55252

  

  No ratings yet

  Sample 55252

  16 pages
• Data Structures Using C and C++ - Y. Langsam, M. Augenstein and A. M. Tenenbaum

  

  No ratings yet

  Data Structures Using C and C++ - Y. Langsam, M. Augenstein and A. M. Tenenbaum

  99 pages
• Subject: Bcs-303 Data Structure & Algorithms Class: Sybsc (CS) - Semester Iii

  

  No ratings yet

  Subject: Bcs-303 Data Structure & Algorithms Class: Sybsc (CS) - Semester Iii

  12 pages
• Book - Computer Architecture (Ripped From Amazon Kindle Ebooks by Sai Seena)

  

  0% (1)

  Book - Computer Architecture (Ripped From Amazon Kindle Ebooks by Sai Seena)

  400 pages
• 27 Computer Programming CS100 Syllabus

  

  No ratings yet

  27 Computer Programming CS100 Syllabus

  2 pages
• Introduction To C++

  

  100% (1)

  Introduction To C++

  13 pages
• Sample Questions JTG Release

  

  No ratings yet

  Sample Questions JTG Release

  2 pages
• MCA Data Structures With Algorithms 01

  

  No ratings yet

  MCA Data Structures With Algorithms 01

  16 pages
• Vtu Lab Manuals Materials

  

  100% (1)

  Vtu Lab Manuals Materials

  3 pages
• Baadada Hoo - S Ananthanarayana

  

  No ratings yet

  Baadada Hoo - S Ananthanarayana

  71 pages
• Programming in C

  

  No ratings yet

  Programming in C

  127 pages
• 15MA302 Discrete Mathematics PDF

  

  100% (1)

  15MA302 Discrete Mathematics PDF

  3 pages
• Discrete Mathematical Structures With Application To Computer Science by J.P Tremblay & R. Manohar

  

  No ratings yet

  Discrete Mathematical Structures With Application To Computer Science by J.P Tremblay & R. Manohar

  308 pages
• Ashok N Kamthane Programming

  

  No ratings yet

  Ashok N Kamthane Programming

  2 pages
• Design and Analysis of Algorithms

  

  No ratings yet

  Design and Analysis of Algorithms

  2 pages
• Algorithms For Competitive Programming 2021

  

  No ratings yet

  Algorithms For Competitive Programming 2021

  371 pages
• GATE - CSE Made Easy 342 392

  

  100% (1)

  GATE - CSE Made Easy 342 392

  51 pages
• FULL DBMS Notes (All Units)

  

  100% (1)

  FULL DBMS Notes (All Units)

  78 pages
• 18CS744 Cryptography - Module 2 Notes

  

  No ratings yet

  18CS744 Cryptography - Module 2 Notes

  46 pages
• 22POP13

  

  No ratings yet

  22POP13

  6 pages
• MC - BCS402 Lab Manual

  

  No ratings yet

  MC - BCS402 Lab Manual

  21 pages
• Kleene's Theorem - Part 1: The Recursive Definition of Regular Language

  

  No ratings yet

  Kleene's Theorem - Part 1: The Recursive Definition of Regular Language

  9 pages
• Complete C Programming Guide Employment

  

  100% (1)

  Complete C Programming Guide Employment

  201 pages
• Data Structure

  

  100% (2)

  Data Structure

  72 pages
• Data Structures With C - by Schaum Series 2

  

  No ratings yet

  Data Structures With C - by Schaum Series 2

  554 pages
• Calcutta University Syllabus Masters of Computer Science

  

  No ratings yet

  Calcutta University Syllabus Masters of Computer Science

  20 pages
• 279 - DBMS Complete1

  

  No ratings yet

  279 - DBMS Complete1

  121 pages
• Data Structures

  

  100% (4)

  Data Structures

  275 pages
• Data Structures PDF

  

  100% (1)

  Data Structures PDF

  275 pages
• Dsa Get Set Go

  

  No ratings yet

  Dsa Get Set Go

  93 pages
• Unit1 DS PDF

  

  No ratings yet

  Unit1 DS PDF

  55 pages
• DSA Ch1 (Introduction) (Recovered)

  

  No ratings yet

  DSA Ch1 (Introduction) (Recovered)

  30 pages
• Files 4 2022 January NotesHubDocument 1642765885

  

  No ratings yet

  Files 4 2022 January NotesHubDocument 1642765885

  521 pages
• MDU BCA - Data Structures

  

  No ratings yet

  MDU BCA - Data Structures

  474 pages
• Data Structures Using C (Csit124) Lecture Notes: by Dr. Nancy Girdhar

  

  No ratings yet

  Data Structures Using C (Csit124) Lecture Notes: by Dr. Nancy Girdhar

  33 pages
• DS PPT - 29.03.2023

  

  No ratings yet

  DS PPT - 29.03.2023

  14 pages
• CS III Sem Compelte Material

  

  No ratings yet

  CS III Sem Compelte Material

  110 pages
• Jul 23 - Data Structure

  

  No ratings yet

  Jul 23 - Data Structure

  63 pages
• DSA Unit 1

  

  No ratings yet

  DSA Unit 1

  76 pages
• Unit Test 1

  

  No ratings yet

  Unit Test 1

  1 page
• Unit1 Class Diagram

  

  No ratings yet

  Unit1 Class Diagram

  83 pages
• ֌֡օ֧֟֗᳒֞֌֠ւ֏֒ֆ֠ᮧᳰᮓ֑֞׃ׁׂׄ List Of Applicant Shortlisted For Document Verification Round-IV

  

  No ratings yet

  ֌֡օ֧֟֗᳒֞֌֠ւ֏֒ֆ֠ᮧᳰᮓ֑֞׃ׁׂׄ List Of Applicant Shortlisted For Document Verification Round-IV

  1 page
• University of Pune Recruitment Process 2013

  

  No ratings yet

  University of Pune Recruitment Process 2013

  6 pages
• Hpds

  

  No ratings yet

  Hpds

  12 pages
• SQL Inference

  

  No ratings yet

  SQL Inference

  10 pages
• Structure BE

  

  No ratings yet

  Structure BE

  2 pages