AITutor

Computer Science Books/Sem3/Ds

intermediate

Computer Science Books/Sem3/Ds

Assistant Professor Department of Computer Science Shyama Prasad Mukherjee College for Women University of Delhi Reema Thareja Second Edition Data Structures Using c

– 1 of 557 –

3 Oxford University Press is a department of the University of Oxford. It furthers the University’s objective of excellence in research, scholarship, and education by publishing worldwide. Oxford is a registered trade mark of Oxford University Press in the UK and in certain other countries. Published in India by Oxford University Press YMCA Library Building, 1 Jai Singh Road, New Delhi 110001, India © Oxford University Press 2011, 2014 The moral rights of the author/s have been asserted. First Edition published in 2011 Second Edition published in 2014 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, without the prior permission in writing of Oxford University Press, or as expressly permitted by law, by licence, or under terms agreed with the appropriate reprographics rights organization. Enquiries concerning reproduction outside the scope of the above should be sent to the Rights Department, Oxford University Press, at the address above. You must not circulate this work in any other form and you must impose this same condition on any acquirer. ISBN-13: 978-0-19-809930-7 ISBN-10: 0-19-809930-4 Typeset in Times New Roman by Pee-Gee Graphics, New Delhi Printed in India by Radha Press, New Delhi 110031

– 2 of 557 –

I dedicate this book to my family and my uncle Mr B.L. Thareja

– 3 of 557 –

A data structure is defined as a group of data elements used for organizing and storing data. In order to be effective, data has to be organized in a manner that adds to the efficiency of an algorithm, and data structures such as stacks, queues, linked lists, heaps, and trees provide different capabilities to organize data. While developing a program or an application, many developers find themselves more interested in the type of algorithm used rather than the type of data structure implemented. However, the choice of data structure used for a particular algorithm is always of the utmost importance. Each data structure has its own unique properties and is constructed to suit various kinds of applications. Some of them are highly specialized to carry out specific tasks. For example, B-trees with their unique ability to organize indexes are well-suited for the implementation of databases. Similarly, stack, a linear data structure which provides ‘last-in-first-out’ access, is used to store and track the sequence of web pages while we browse the Internet. Specific data structures are essential components of many efficient algorithms, and make possible the management of large amounts of data, such as large databases and Internet indexing services. C, as we all know, is the most popular programming language and is widespread among all the computer architectures. Therefore, it is not only logical but also fundamentally essential to start the introduction and implementation of various data structures through C. The course data structures is typically taught in the second or third semester of most engineering colleges and across most engineering disciplines in India. The aim of this course is to help students master the design and applications of various data structures and use them in writing effective programs. About the Book This book is aimed at serving as a textbook for undergraduate engineering students of computer science and postgraduate level courses of computer applications. The objective of this book is to introduce the concepts of data structures and apply these concepts in problem solving. The book provides a thorough and comprehensive coverage of the fundamentals of data structures and the principles of algorithm analysis. The main focus has been to explain the principles required to select or design the data structure that will best solve the problem. A structured approach is followed to explain the process of problem solving. A theoretical description of the problem is followed by the underlying technique. These are then ably supported by an example followed by an algorithm, and finally the corresponding program in C language. The salient features of the book include: ∑ Explanation of the concepts using diagrams ∑ Numerous solved examples within the chapters ∑ Glossary of important terms at the end of each chapter ∑ Comprehensive exercises at the end of each chapter ∑ Practical implementation of the algorithms using tested C programs ∑ Objective type questions to enhance the analytical ability of the students Preface to the First Edition

– 4 of 557 –

Preface to the First Edition ix ∑ Annexures to provide supplementary information to help generate further interest in the subject The book is also useful as a reference and resource to young researchers working on efficient data storage and related applications, who will find it to be a helpful guide to the newly established techniques of a rapidly growing research field. Acknowledgements The writing of this textbook was a mammoth task for which a lot of help was required from many people. Fortunately, I have had the fine support of my family, friends, and fellow members of the teaching staff at the Institute of Information Technology and Management (IITM). My special thanks would always go to my father Mr Janak Raj Thareja and mother Mrs Usha Thareja, my brother Pallav and sisters Kimi and Rashi who were a source of abiding inspiration and divine blessings for me. I am especially thankful to my son Goransh who has been very patient and cooperative in letting me realize my dreams. My sincere thanks go to my uncle Mr B.L. Thareja for his inspiration and guidance in writing this book. I would also like to thank my students and colleagues at IITM who had always been there to extend help while designing and testing the algorithms. Finally, I would like to thank the editorial team at Oxford University Press for their help and support. Comments and suggestions for the improvement of the book are welcome. Please send them to me at reemathareja@gmail.com Reema Thareja

– 5 of 557 –

A data structure is the logical or mathematical arrangement of data in memory. It considers not only the physical layout of the data items in the memory but also the relationships between these data items and the operations that can be performed on these items. The choice of appropriate data structures and algorithms forms the fundamental step in the design of an efficient program. Thus, a thorough understanding of data structure concepts is essential for students who wish to work in the design and implementation of software systems. C, a general-purpose programming language, having gained popularity in both academia and industry serves as an excellent choice for learning data structures. This second edition of Data Structures Using C has been developed to provide a comprehensive and consistent coverage of both the abstract concepts of data structures as well as the implementation of these concepts using C language. The book utilizes a systematic approach wherein the design of each of the data structures is followed by algorithms of different operations that can be performed on them, and the analysis of these algorithms in terms of their running times. New to the Second Edition Based on the suggestions from students and faculty members, this edition has been updated and revised to increase the clarity of presentation where required. Some of the prominent changes are as follows: • New sections on omega and theta notations, multi-linked lists, forests, conversion of general trees into binary trees, 2-3 trees, binary heap implementation of priority queues, interpolation search, jump search, tree sort, bucket hashing, cylinder surface indexing • Additional C programs on header linked lists, parentheses checking, evaluation of prefix expressions, priority queues, multiple queues, tree sort, file handling , address calculation sort • New appendices on dynamic memory allocation, garbage collection, backtracking, Johnson’s problem • Stacks and queues and multi-way search trees are now covered in separate chapters with a more comprehensive explanation of concepts and applications Extended Material Chapter 1—This chapter has been completely restructured and reorganized so that it now provides a brief recapitulation of C constructs and syntax. Functions and pointers which were included as independent chapters in the first edition have now been jointly included in this chapter. Chapter 2—New sections on primitive and non-primitive data structures, different approaches to designing algorithms, omega, theta, and little notations have been included. A number of new examples have also been added which show how to find the complexity of different functions. Chapter 5—This chapter now includes brief sections on unions, a data type similar to structures. Chapter 6—This chapter has been expanded to include topics on multi-linked lists, multi-linked list implementation of sparse matrices, and a C program on header linked lists. Preface to the Second Edition

– 6 of 557 –

vi Preface to the Second Edition Chapter 7—New C programs on parenthesis checking and evaluation of prefix expressions have been added. Recursion, which is one of the most common applications of stacks, has been moved to this chapter. Chapter 8—New C programs on priority queues and multiple queues have been included. Chapter 9—This chapter now includes sections on general trees, forests, conversion of general trees into binary trees, and constructing a binary tree from traversal results. Chapter 10—An algorithm for in-order traversal of a threaded binary tree has been added. Chapter 11—A table summarizing the differences between B and B+ trees and a section on 2-3 trees have been included. Chapter 12—A brief section on how binary heaps can be used to implement priority queues has been added. Chapter 13—This chapter now includes a section which shows the adjacency multi-list representation of graphs. Chapter 14—As a result of organization, the sections on linear and binary search have been moved from Chapter 3 to this chapter. New search techniques such as interpolation search, jump search, and Fibonacci search have also been included. The chapter also extends the concept of sorting by including sections on practical considerations for internal sorting, sorting on multiple keys, and tree sort. Chapter 15—New sections on bucket hashing and rehashing have been included. Chapter 16—This chapter now includes a section on cylinder surface indexing which is one of the widely used indexing structures for files stored in hard disks. Content and Coverage This book is organized into 16 chapters. Chapter 1, Introduction to C provides a review of basic C constructs which helps readers to familiarize themselves with basic C syntax and concepts that will be used to write programs in this book. Chapter 2, Introduction to Data Strctures and Algorithms introduces data structures and algorithms which serve as building blocks for creating efficient programs. The chapter explains how to calculate the time complexity which is a key concept for evaluating the performance of algorithms. From Chapter 3 onwards, every chapter discusses individual data structures in detail. Chapter 3, Arrays provides a detailed explanation of arrays that includes one-dimensional, two- dimensional, and multi-dimensional arrays. The operations that can be performed on such arrays are also explained. Chapter 4, Strings discusses the concept of strings which are also known as character arrays. The chapter not only focuses on reading and writing strings but also explains various operations that can be used to manipulate the character arrays. Chapter 5, Structures and Unions deals with structures and unions. A structure is a collection of related data items of different types which is used for implementing other data structures such as linked lists, trees, graphs, etc. We will also read about unions which is also a collection of variables of different data types, except that in case of unions, we can only store information in one field at any one time. Chapter 6, Linked Lists discusses different types of linked lists such as singly linked lists, doubly linked lists, circular linked lists, doubly circular linked lists, header linked lists, and multi-linked lists. Linked list is a preferred data structure when it is required to allocate memory dynamically.

– 7 of 557 –

Preface to the Second Edition vii Chapter 7, Stacks focuses on the concept of last-in, first-out (LIFO) data structure called stacks. The chapter also shows the practical implementation of these data structures using arrays as well as linked lists. It also shows how stacks can be used for the evaluation of arithmetic expressions. Chapter 8, Queues deals with the concept of first-in, first-out (FIFO) data structure called queues. The chapter also provides the real-world applications of queues. Chapter 9, Trees focuses on binary trees, their traversal schemes and representation in memory. The chapter also discusses expression trees, tournament trees, and Huffman trees, all of which are variants of simple binary trees. Chapter 10,Efficient Binary Trees broadens the discussion on trees taken up in Chapter 9 by going one step ahead and discussing efficient binary trees. The chapter discusses binary search trees, threaded binary trees, AVL trees, red-black trees, and splay trees. Chapter 11, Multi-way Search Trees explores trees which can have more than one key value in a single node, such as M-way search trees, B trees, B+ trees, tries, and 2-3 trees. Chapter 12, Heaps discusses three types of heaps—binary heaps, binomial heaps, and Fibonacci heaps. The chapter not only explains the operations on these data structures but also makes a comparison, thereby highlighting the key features of each structure. Chapter 13, Graphs contains a detailed explanation of non-linear data structure called graphs. It discusses the memory representation, traversal schemes, and applications of graphs in the real world. Chapter 14, Searching and Sorting covers two of the most common operations in computer science, i.e. searching and sorting a list of values. It gives the technique, complexity, and program for different searching and sorting techniques. Chapter 15, Hashing and Collision deals with different methods of hashing and techniques to resolve collisions. Chapter 16, the last chapter of the book, Files and Their Organization, discusses the concept related to file organization. It explains the different ways in which files can be organized on the hard disk and the indexing techniques that can be used for fast retrieval of data. The book also provides a set of seven appendices. Appendix A introduces the concept of dynamic memory allocation in C programs. Appendix B provides a brief discussion of garbage collection technique which is used for automatic memory management. Appendix C explains backtracking which is a recursive algorithm that uses stacks. Appendix D discusses Johnson’s algorithm which is used in applications where an optimal order of execution of different activities has to be determined. Appendix E includes two C programs which show how to read and write binary files. Appendix F includes a C program which shows how to sort a list of numbers using address calculation sort. Appendix G provides chapter-wise answers to all the objective questions. Reema Thareja

– 8 of 557 –

Preface to the Second Edition v Preface to the First Edition viii

  1. Introduction to C 1
  2. Introduction to Data Structures and Algorithms 43
  3. Arrays 66
  4. Strings 115
  5. Structures and Unions 138
  6. Linked Lists 162
  7. Stacks 219
  8. Queues 253
  9. Trees 279
  10. Efficient Binary Trees 298
  11. Multi-way Search Trees 344
  12. Heaps 361
  13. Graphs 383
  14. Searching and Sorting 424
  15. Hashing and Collision 464
  16. Files and Their Organization 489 Appendix A: Memory Allocation in C Programs 505 Appendix B: Garbage Collection 512 Appendix C: Backtracking 514 Appendix D: Josephus Problem 516 Appendix E: File Handling in C 518 Appendix F: Address Calculation Sort 520 Appendix G: Answers 522 Index 528 Brief Contents

– 9 of 557 –

xii Detailed Contents

  1. Introduction to C 1 1.1 Introduction 1 1.2 Identifiers and Keywords 2 1.3 Basic Data Types 2 1.4 Variables and Constants 3 1.5 Writing the First C Program 5 1.6 Input and Output Functions 6 1.7 Operators and Expressions 9 1.8 Type Conversion and Typecasting 16 1.9 Control Statements 17 1.9.1 Decision Control Statements 17 1.9.2 Iterative Statements 22 1.9.3 Break and Continue Statements 27 1.10 Functions 28 1.10.1 Why are Functions Needed? 29 1.10.2 Using Functions 29 1.10.3 Passing Parameters to Functions 31 1.11 Pointers 34 1.11.1 Declaring Pointer Variables 35 1.11.2 Pointer Expressions and Pointer Arithmetic 36 1.11.3 Null Pointers 36 1.11.4 Generic Pointers 36 1.11.5 Pointer to Pointers 37 1.11.6 Drawback of Pointers 38
  2. Introduction to Data Structures and Algorithms 43 2.1 Basic Terminology 43 2.1.1 Elementary Data Structure Organization 45 2.2 Classification of Data Structures 45 2.3 Operations on Data Structures 49 2.4 Abstract Data Type 50 2.5 Algorithms 50 2.6 Different Approaches to Designing an Algorithm 51 2.7 Control Structures Used in Algorithms 52 2.8 Time and Space Complexity 54 2.8.1 Worst-case, Average-case, Best-case, and Amortized Time Complexity 54 2.8.2 Time–Space Trade-off 55 2.8.3 Expressing Time and Space Complexity 55 2.8.4 Algorithm Efficiency 55 2.9 Big O Notation 57 2.10 Omega Notation (Ω) 60 2.11 Theta Notation (Q) 61 2.12 Other Useful Notations 62
  3. Arrays 66 3.1 Introduction 66 3.2 Declaration of Arrays 67 3.3 Accessing the Elements of an Array 68 3.3.1 Calculating the Address of Array Elements 68 3.3.2 Calculating the Length of an Array 69 3.4 Storing Values in Arrays 69 3.5 Operations on Arrays 71 3.5.1 Traversing an Array 71 Detailed Contents Preface to the Second Edition v Preface to the First Edition viii

– 10 of 557 –

Detailed Contents xiii 3.5.2 Inserting an Element in an Array 76 3.5.3 Deleting an Element from an Array 79 3.5.4 Merging Two Arrays 82 3.6 Passing Arrays to Functions 86 3.6.1 Passing Individual Elements 86 3.6.2 Passing the Entire Array 87 3.7 Pointers and Arrays 90 3.8 Arrays of Pointers 92 3.9 Two-dimensional Arrays 93 3.9.1 Declaring Two-dimensional Arrays 93 3.9.2 Initializing Two-dimensional Arrays 95 3.9.3 Accessing the Elements of Two-dimensional Arrays 96 3.10 Operations on Two-Dimensional Arrays 99 3.11 Passing Two-dimensional Arrays to Functions 103 3.12 Pointers and Two-dimensional Arrays 105 3.13 Multi-dimensional Arrays 107 3.14 Pointers and Three-dimensional Arrays 109 3.15 Sparse Matrices 110 3.16 Applications of Arrays 111 4. Strings 115 4.1 Introduction 115 4.1.1 Reading Strings 117 4.1.2 Writing Strings 118 4.2 Operations on Strings 118 4.3 Arrays of Strings 129 4.4 Pointers and Strings 132 5. Structures and Unions 138 5.1 Introduction 138 5.1.1 Structure Declaration 138 5.1.2 Typedef Declarations 139 5.1.3 Initialization of Structures 140 5.1.4 Accessing the Members of a Structure 141 5.1.5 Copying and Comparing Structures 142 5.2 Nested Structures 144 5.3 Arrays of Structures 146 5.4 Structures and Functions 148 5.4.1 Passing Individual Members 149 5.4.2 Passing the Entire Structure 149 5.4.3 Passing Structures through Pointers 152 5.5 Self-referential Structures 155 5.6 Unions 155 5.6.1 Declaring a Union 156 5.6.2 Accessing a Member of a Union 156 5.6.3 Initializing Unions 156 5.7 Arrays of Union Variables 157 5.8 Unions Inside Structures 158 6. Linked Lists 162 6.1 Introduction 162 6.1.1 Basic Terminologies 162 6.1.2 Linked Lists versus Arrays 164 6.1.3 Memory Allocation and De-allocation for a Linked List 165 6.2 Singly Linked Lists 167 6.2.1 Traversing a Linked List 167 6.2.2 Searching for a Value in a Linked List 167 6.2.3 Inserting a New Node in a Linked List 168 6.2.4 Deleting a Node from a Linked List 172 6.3 Circular Linked Lists 180 6.3.1 Inserting a New Node in a Circular Linked List 181 6.3.2 Deleting a Node from a Circular Linked List 182 6.4 Doubly Linked Lists 188 6.4.1 Inserting a New Node in a Doubly Linked List 188

– 11 of 557 –

xiv Detailed Contents 6.4.2 Deleting a Node from a Doubly Linked List 191 6.5 Circular Doubly Linked Lists 199 6.5.1 Inserting a New Node in a Circular Doubly Linked List 200 6.5.2 Deleting a Node from a Circular Doubly Linked List 201 6.6 Header Linked Lists 207 6.7 Multi-linked Lists 210 6.8 Applications of Linked Lists 211 6.8.1 Polynomial Representation 211 7. Stacks 219 7.1 Introduction to Stacks 219 7.2 Array Representation of Stacks 220 7.3 Operations on a Stack 221 7.3.1 Push Operation 221 7.3.2 Pop Operation 221 7.3.3 Peek Operation 222 7.4 Linked Representation of Stacks 224 7.5 Operations on a Linked Stack 224 7.5.1 Push Operation 224 7.5.2 Pop Operation 225 7.6 Multiple Stacks 227 7.7 Applications of Stacks 230 7.7.1 Reversing a List 230 7.7.2 Implementing Parentheses Checker 231 7.7.3 Evaluation of Arithmetic Expressions 232 7.7.4 Recursion 243 8. Queues 253 8.1 Introduction to Queues 253 8.2 Array Representation of Queues 254 8.3 Linked Representation of Queues 256 8.4 Types of Queues 260 8.4.1 Circular Queues 260 8.4.2 Deques 264 8.4.3 Priority Queues 268 8.4.4 Multiple Queues 272 8.5 Applications of Queues 275 9. Trees 279 9.1 Introduction 279 9.1.1 Basic Terminology 279 9.2 Types of Trees 280 9.2.1 General Trees 280 9.2.2 Forests 280 9.2.3 Binary Trees 281 9.2.4 Binary Search Trees 285 9.2.5 Expression Trees 285 9.2.6 Tournament Trees 286 9.3 Creating a Binary Tree from a General Tree 286 9.4 Traversing a Binary Tree 287 9.4.1 Pre-order Traversal 287 9.4.2 In-order Traversal 288 9.4.3 Post-order Traversal 289 9.4.4 Level-order Traversal 289 9.4.5 Constructing a Binary Tree from Traversal Results 290 9.5 Huffman’s Tree 290 9.6 Applications of Trees 294 10. Efficient Binary Trees 298 10.1 Binary Search Trees 298 10.2 Operations on Binary Search Trees 300 10.2.1 Searching for a Node in a Binary Search Tree 300 10.2.2 Inserting a New Node in a Binary Search Tree 301 10.2.3 Deleting a Node from a Binary Search Tree 301 10.2.4 Determining the Height of a Binary Search Tree 303 10.2.5 Determining the Number of Nodes 303 10.2.6 Finding the Mirror Image of a Binary Search Tree 305 10.2.8 Finding the Smallest Node in a Binary Search Tree 305 10.2.9 Finding the Largest Node in a Binary Search Tree 306 10.3 Threaded Binary Trees 311 10.3.1 Traversing a Threaded Binary Tree 314

– 12 of 557 –

Detailed Contents xv 10.4 AVL Trees 316 10.4.1 Operations on AVL Trees 317 Searching for a Node in an AVL Tree 317 10.5 Red-Black Trees 327 10.5.1 Properties of Red-Black Trees 328 10.5.2 Operations on Red-Black Trees 330 10.5.3 Applications of Red-Black Trees 337 10.6 Splay Trees 337 10.6.1 Operations on Splay Trees 338 10.6.2 Advantages and Disadvantages of Splay Trees 340 11. Multi-way Search Trees 344 11.1 Introduction to M-Way Search Trees 344 11.2 B Trees 345 11.2.1 Searching for an Element in a B Tree 346 11.2.2 Inserting a New Element in a B Tree 346 11.2.3 Deleting an Element from a B Tree 347 11.2.4 Applications of B Trees 350 11.3 B+ Trees 351 11.3.1 Inserting a New Element in a B+ Tree 352 11.3.2 Deleting an Element from a B+ Tree 352 11.4 2-3 Trees 353 11.4.1 Searching for an Element in a 2-3 Tree 354 11.4.2 Inserting a New Element in a 2-3 Tree 354 11.4.3 Deleting an Element from a 2-3 Tree 356 11.5 Trie 358 12. Heaps 361 12.1 Binary Heaps 361 12.1.1 Inserting a New Element in a Binary Heap 362 12.1.2 Deleting an Element from a Binary Heap 364 12.1.3 Applications of Binary Heaps 364 12.2 Binomial Heaps 365 12.2.1 Linked Representation of Binomial Heaps 366 12.2.2 Operations on Binomial Heaps 366 12.3 Fibonacci Heaps 373 12.3.1 Structure of Fibonacci Heaps 373 12.3.2 Operations on Fibonacci Heaps 374 12.4 Comparison of Binary, Binomial, and Fibonacci Heaps 379 12.5 Applications of Heaps 379 13. Graphs 383 13.1 Introduction 383 13.2 Graph Terminology 384 13.3 Directed Graphs 385 13.3.1 Terminology of a Directed Graph 385 13.3.2 Transitive Closure of a Directed Graph 386 13.4 Bi-connected Components 387 13.5 Representation of Graphs 388 13.5.1 Adjacency Matrix Representation 388 13.5.2 Adjacency List Representation 390 13.5.3 Adjacency Multi-List Representation 391 13.6 Graph Traversal Algorithms 393 13.6.1 Breadth-First Search Algorithm 394 13.6.2 Depth-first Search Algorithm 397 13.7 Topological Sorting 400 13.8 Shortest Path Algorithms 405 13.8.1 Minimum Spanning Trees 405 13.8.2 Prim’s Algorithm 407 13.8.3 Kruskal’s Algorithm 409 13.8.4 Dijkstra’s Algorithm 413 13.8.5 Warshall’s Algorithm 414

– 13 of 557 –

xvi Detailed Contents 13.8.6 Modified Warshall’s Algorithm 417 13.9 Applications of Graphs 419 14. Searching and Sorting 424 14.1 Introduction to Searching 424 14.2 Linear Search 424 14.3 Binary Search 426 14.4 Interpolation Search 428 14.5 Jump Search 430 14.6 Introduction to Sorting 433 14.6.1 Sorting on Multiple Keys 433 14.6.2 Practical Considerations for Internal Sorting 434 14.7 Bubble Sort 434 14.8 Insertion Sort 438 14.9 Selection Sort 440 14.10 Merge Sort 443 14.11 Quick Sort 446 14.12 Radix Sort 450 14.13 Heap Sort 454 14.14 Shell Sort 456 14.15 Tree Sort 458 14.16 Comparison of Sorting Algorithms 460 14.17 External Sorting 460 15. Hashing and Collision 464 15.1 Introduction 464 15.2 Hash Tables 465 15.3 Hash Functions 466 15.4 Different Hash Functions 467 15.4.1 Division Method 467 15.4.2 Multiplication Method 467 15.4.3 Mid-Square Method 468 15.4.4 Folding Method 468 15.5 Collisions 469 15.5.1 Collision Resolution by Open Addressing 469 15.5.2 Collision Resolution By Chaining 481 15.6 Pros and Cons of Hashing 485 15.7 Applications of Hashing 485 Real World Applications of Hashing 486 16. Files and Their Organization 489 16.1 Introduction 489 16.2 Data Hierarchy 489 16.3 File Attributes 490 16.4 Text and Binary Files 491 16.5 Basic File Operations 492 16.6 File Organization 493 16.6.1 Sequential Organization 493 16.6.2 Relative File Organization 494 16.6.3 Indexed Sequential File Organization 495 16.7 Indexing 496 16.7.1 Ordered Indices 496 16.7.2 Dense and Sparse Indices 497 16.7.3 Cylinder Surface Indexing 497 16.7.4 Multi-level Indices 498 16.7.5 Inverted Indices 499 16.7.6 B-Tree Indices 500 16.7.7 Hashed Indices 501 Appendix A: Memory Allocation in C Programs 505 Appendix B: Garbage Collection 512 Appendix C: Backtracking 514 Appendix D: Josephus Problem 516 Appendix E: File Handling in C 518 Appendix F: Address Calculation Sort 520 Appendix G: Answers 522 Index 528

– 14 of 557 –

1.1 INTRODUCTION The programming language ‘C’ was developed in the early 1970s by Dennis Ritchie at Bell Laboratories. Although C was initially developed for writing system software, today it has become such a popular language that a variety of software programs are written using this language. The greatest advantage of using C for programming is that it can be easily used on different types of computers. Many other programming languages such as C++ and Java are also based on C which means that you will be able to learn them easily in the future. Today, C is widely used with the UNIX operating system. Structure of a C program A C program contains one or more functions, where a function is defined as a group of statements that perform a well-defined task. Figure 1.1 shows the structure of a C program. The statements in a function are written in a logical sequence to perform a specific task. The main() function is the most important function and is a part of every C program. Rather, the execution of a C program begins with this function. From the structure given in Fig. 1.1, we can conclude that a C program can have any number of functions depending on the tasks that have to be performed, and each function can have any number LeaRNINg ObjeCTIve This book deals with the study of data structures through C. Before going into a detailed analysis of data structures, it would be useful to familiarize ourselves with the basic knowledge of programming in C. Therefore, in this chapter we will learn about the various constructs of C such as identifiers and keywords, data types, constants, variables, input and output functions, operators, control statements, functions, and pointers. Introduction to C Chapter 1

– 15 of 557 –

2 Data Structures Using C of statements arranged according to specific meaningful sequence. Note that programmers can choose any name for functions. It is not mandatory to write Function1, Function2, etc., with an exception that every program must contain one function that has its name as main(). 1.2 IDeNTIFIeRS aND KeYWORDS Every word in a C program is either an identifier or a keyword. Identifiers Identifiers are basically names given to program elements such as variables, arrays, and functions. They are formed by using a sequence of letters (both uppercase and lowercase), numerals, and underscores. Following are the rules for forming identifier names: ∑ Identifiers cannot include any special characters or punctuation marks (like #, $, ^, ?, ., etc.) except the underscore “_”. ∑ There cannot be two successive underscores. ∑ Keywords cannot be used as identifiers. ∑ The case of alphabetic characters that form the identifier name is significant. For example, ‘FIRST’ is different from ‘first’ and ‘First’. ∑ Identifiers must begin with a letter or an underscore. However, use of underscore as the first character must be avoided because several complier-defined identifiers in the standard C library have underscore as their first character. So, inadvertently duplicated names may cause definition conflicts. ∑ Identifiers can be of any reasonable length. They should not contain more than 31 characters. (They can actually be longer than 31, but the compiler looks at only the first 31 characters of the name.) Keywords Like every computer language, C has a set of reserved words often known as keywords that cannot be used as an identifier. All keywords are basically a sequence of characters that have a fixed meaning. By convention, all keywords must be written in lower case letters. Table 1.1 contains the list of keywords in C. Table 1.1 Keywords in C language auto break case char const continue default do double else enum extern float for goto if int long register return short signed sizeof static struct switch typedef union unsigned void volatile while 1.3 baSIC DaTa TYPeS Data type determines the set of values that a data item can take and the operations that can be performed on the item. C language provides four basic data types. Table 1.2 lists the data types, their size, range, and usage for a C programmer. The char data type is of one byte and is used to store single characters. Note that C does not provide any data type for storing text. This is because text is made up of individual characters.You

main()
{
Statement 1;
Statement 2;
............
Statement N;
}
Function1()
{
Statement 1;
Statement 2;
Statement N;
}
Function2()
{
Statement 1;
Statement 2;
Statement N;
}
FunctionN()
{
Statement 1;
Statement 2;
Statement N;
}

………… ………… ………… ………… ………… ……………… ……………… ………… ………… Figure 1.1 Structure of a C program

– 16 of 557 –

Introduction to C 3 might have been surprised to see that the range of char is given as –128 to 127. char is supposed to store characters not numbers, so why this range? The answer is that in the memory, characters are stored in their ASCII codes. For example, the character ‘A’ has the ASCII code of 65. In memory we will not store ‘A’ but 65 (in binary number format). Table 1.2 Basic data types in C Data Type Size in Bytes Range Use char 1 –128 to 127 To store characters int 2 –32768 to 32767 To store integer numbers float 4 3.4E–38 to 3.4E+38 To store floating point numbers double 8 1.7E–308 to 1.7E+308 To store big floating point numbers In addition, C also supports four modifiers—two sign specifiers (signed and unsigned) and two size specifiers (short and long). Table 1.3 shows the variants of basic data types. Table 1.3 Basic data types and their variants Data Type Size in Bytes Range char 1 –128 to 127 unsigned char 1 0 to 255 signed char 1 –128 to 127 int 2 –32768 to 32767 unsigned int 2 0 to 65535 signed int 2 –32768 to 32767 short int 2 –32768 to 32767 unsigned short int 2 0 to 65535 signed short int 2 –32768 to 32767 long int 4 –2147483648 to 2147483647 unsigned long int 4 0 to 4294967295 signed long int 4 –2147483648 to 2147483647 float 4 3.4E–38 to 3.4E+38 double 8 1.7E–308 to 1.7E+308 long double 10 3.4E–4932 to 1.1E+4932 Note When the basic data type is omitted from a declaration, then automatically type int is assumed. For example, long var; //int is implied While the smaller data types take less memory, the larger data types incur a performance penalty. Although the data type we use for our variables does not have a big impact on the speed or memory usage of the application, we should always try to use int unless there is a need to use any other data type. 1.4 vaRIabLeS aND CONSTaNTS A variable is defined as a meaningful name given to a data storage location in the computer memory. When using a variable, we actually refer to the address of the memory where the data is stored. C language supports two basic kinds of variables.

– 17 of 557 –

4 Data Structures Using C Numeric Variables Numeric variables can be used to store either integer values or floating point values. Modifiers like short, long, signed, and unsigned can also be used with numeric variables. The difference between signed and unsigned numeric variables is that signed variables can be either negative or positive but unsigned variables can only be positive. Therefore, by using an unsigned variable we can increase the maximum positive range. When we omit the signed/unsigned modifier, C language automatically makes it a signed variable. To declare an unsigned variable, the unsigned modifier must be explicitly added during the declaration of the variable. Character Variables Character variables are just single characters enclosed within single quotes. These characters could be any character from the ASCII character set—letters (‘a’, ‘A’), numerals (‘2’), or special characters (‘&’). Declaring Variables To declare a variable, specify the data type of the variable followed by its name. The data type indicates the kind of values that the variable can store. Variable names should always be meaningful and must reflect the purpose of their usage in the program. In C, variable declaration always ends with a semi-colon. For example, int emp_num; float salary; char grade; double balance_amount; unsigned short int acc_no; In C, variables can be declared at any place in the program but two things must be kept in mind. First, variables should be declared before using them. Second, variables should be declared closest to their first point of use so that the source code is easier to maintain. Initializing Variables While declaring the variables, we can also initialize them with some value. For example, int emp_num = 7; float salary = 9800.99 char grade = ‘A’; double balance_amount = 100000000; Constants Constants are identifiers whose values do not change. While values of variables can be changed at any time, values of constants can never be changed. Constants are used to define fixed values like pi or the charge on an electron so that their value does not get changed in the program even by mistake. Declaring Constants To declare a constant, precede the normal variable declaration with const keyword and assign it a value. const float pi = 3.14;

– 18 of 557 –

Introduction to C 5 1.5 WRITINg THe FIRST C PROgRaM To write a C program, we first need to write the code. For that, open a text editor. If you are a Windows user, you may use Notepad and if you prefer working on UNIX/Linux, you can use emac or vi. Once the text editor is opened on your screen, type the following statements:

#include <stdio.h>
int main()
{
printf("\n Welcome to the world of C ");// prints the message on the screen
return 0;// returns a value 0 to the operating system
}

After writing the code, select the directory of your choice and save the file as first.c. #include <stdio.h> This is the first statement in our code that includes a file called stdio.h. This file has some in-built functions. By simply including this file in our code, we can use these functions directly. stdio basically stands for Standard Input/Output, which means it has functions for input and output of data like reading values from the keyboard and printing the results on the screen. int main() Every C program contains a main() function which is the starting point of the program. int is the return value of the main function. After all the statements in the program have been executed, the last statement of the program will return an integer value to the operating system. The concepts will be clear to us when we read this chapter in toto. So even if you do not understand certain things, do not worry. { } The two curly brackets are used to group all the related statements of the main function. printf(“\n Welcome to the world of C “); The printf function is defined in the stdio.h file and is used to print text on the screen. The message that has to be displayed on the screen is enclosed within double quotes and put inside brackets. \n is an escape sequence and represents a newline character. It is used to print the message on a new line on the screen. Other escape sequences supported by C language are shown in Table 1.4. return 0; This is a return command that is used to return value 0 to the operating system to give an indication that there were no errors during the execution of the program. Note Every statement in the main function ends with a semi-colon (;). first.c. If you are a Windows user, then open the command prompt by clicking StartÆRun and typing “command” and clicking Ok. Using the command prompt, change to the directory in which you saved your file and then type: C:\>tc first.c In case you are working on UNIX/Linux operating system, then exit the text editor and type $cc first.c –ofirst The –o is for the output file name. If you leave out the –o, then the file name a.out is used. Table 1.4 Escape sequences Escape Sequence Purpose \a Audible signal \b Backspace \t Tab \n New line \v Vertical tab \f New page\Clear screen \r Carriage return

– 19 of 557 –

6 Data Structures Using C This command is used to compile your C program. If there are any mistakes in the program, then the compiler will tell you what mistake(s) you have made and on which line the error has occurred. In case of errors, you need to re-open your .c file and correct the mistakes. However, if everything is right, then no error(s) will be reported and the compiler will create an .exe file for your program. This .exe file can be directly run by typing “first.exe” for Windows and “./first” for UNIX/Linux operating system When you run the .exe file, the output of the program will be displayed on screen. That is, Welcome to the world of C Note The printf and return statements have been indented or moved away from the left side. This is done to make the code more readable. Using Comments Comments are a way of explaining what a program does. C supports two types of comments. ∑ // is used to comment a single statement. ∑ /* is used to comment multiple statements. A /* is ended with */ and all statements that lie between these characters are commented. Note that comment statements are not executed by the compiler. Rather, they are ignored by the compiler as they are simply added in programs to make the code understandable by programmers as well as other users. It is a good habit to always put a comment at the top of a program that tells you what the program does. This helps in defining the usage of the program the moment you open it. Standard Header Files Till now we have used printf() function, which is defined in the stdio.h header file. Even in other programs that we will be writing, we will use many functions that are not written by us. For example, to use the strcmp() function that compares two strings, we will pass string arguments and retrieve the result. We do not know the details of how these functions work. Such functions that are provided by all C compilers are included in standard header files. Examples of these standard header files include: ∑ string.h : for string handling functions ∑ stdlib.h : for some miscellaneous functions ∑ stdio.h : for standardized input and output functions ∑ math.h : for mathematical functions ∑ alloc.h : for dynamic memory allocation ∑ conio.h : for clearing the screen All the header files are referenced at the start of the source code file that uses one or more functions from these files. 1.6 INPUT aND OUTPUT FUNCTIONS The most fundamental operation in a C program is to accept input values from a standard input device and output the data produced by the program to a standard output device. As shown in Section 1.4, we can assign values to variables using the assignment operator ‘=’. For example, int a = 3; What if we want to assign value to variable a that is inputted from the user at run-time? This is done by using the scanf function that reads data from the keyboard. Similarly, for outputting results of

– 20 of 557 –

Introduction to C 7 the program, printf function is used that sends results to a terminal. Like printf and scanf, there are different functions in C that can carry out the input–output operations. These functions are collectively known as Standard Input/Output Library. A program that uses standard input/output functions must contain the following statement at the beginning of the program: #include <stdio.h> scanf() The scanf()function is used to read formatted data from the keyboard. The syntax of the scanf() function can be given as, scanf (“control string”, arg1, arg2, arg3 …argn); The control string specifies the type and format of the data that has to be obtained from the keyboard and stored in the memory locations pointed by the arguments, arg1, arg2, …,argn. The prototype of the control string can be given as, %[*][width][modifier]type

– 21 of 557 –

8 Data Structures Using C Note In case of reading strings, we do not use the & sign in the scanf function. printf() The printf function is used to display information required by the user and also prints the values of the variables. Its syntax can be given as: printf (“control string”, arg1,arg2,arg3,…,argn); After the control string, the function can have as many arguments as specified in the control string. The control string contains format specifiers which are arranged in the order so that they correspond with the arguments in the variable list. It may also contain text to be printed such as instructions to the user, identifier names, or any other text to make the text readable. Note that there must be enough arguments because if there are not enough arguments, then the result will be completely unpredictable. However, if by mistake you specify more number of arguments, the excess arguments will simply be ignored. The prototype of the control string can be given as below: %[flags][width][.precision][modifier]type Each control string must begin with a % sign. flags is an optional argument, which specifies output justification like decimal point, numerical sign, trailing zeros or octadecimal or hexadecimal prefixes. Table 1.6 shows different types of flags with their descriptions. Table 1.6 Flags in printf() Flags Description – Left–justify within the given field width

Used to provide additional specifiers like o, x, X, 0, 0x, or 0X for

octal and hexadecimal values respectively for values different than zero 0 The number is left–padded with zeroes (0) instead of spaces width is an optional argument which specifies the minimum number of positions that the output characters will occupy. If the number of output characters is smaller than the specified width, then the output would be right justified with blank spaces to the left. However, if the number of characters is greater than the specified width, then all the characters would be printed. precision is an optional argument which specifies the number of digits to print after the decimal point or the number of characters to print from a string. modifier field is same as given for scanf() function. type is used to define the type and the interpretation of the value of the corresponding argument. The type specifiers for printf function are given in Table 1.5. The most simple printf statement is printf (“Welcome to the world of C language”); The function when executed prompts the message enclosed in the quotation to be displayed on the screen. For float x = 8900.768, the following examples show output under different format specifications: printf (“%f”, x) 8 9 0 0 . 7 6 8 printf(“%10f”, x); 8 9 0 0 . 7 6 8

– 22 of 557 –

Introduction to C 9 printf(“%9.2f”, x); 8 9 0 0 . 7 7 printf(“%6f”, x); 8 9 0 0 . 7 6 8 1.7 OPeRaTORS aND eXPReSSIONS C language supports different types of operators, which can be used with variables and constants to form expressions. These operators can be categorized into the following major groups: ∑ Arithmetic operators ∑ Relational operators ∑ Equality operators ∑ Logical operators ∑ Unary operators ∑ Conditional operator ∑ Bitwise operators ∑ Assignment operators ∑ Comma operator ∑ Sizeof operator We will now discuss all these operators. Arithmetic Operators Consider three variables declared as, int a=9, b=3, result; We will use these variables to explain arithmetic operators. Table 1.7 shows the arithmetic operators, their syntax, and usage in C language. Table 1.7 Arithmetic operators Operation Operator Syntax Comment Result Multiply * a * b result = a * b 27 Divide / a / b result = a / b 3 Addition + a + b result = a + b 12 Subtraction – a – b result = a – b 6 Modulus % a % b result = a % b 0 In Table 1.7, a and b (on which the operator is applied) are called operands. Arithmetic operators can be applied to any integer or floating point number. The addition, subtraction, multiplication, and division (+, –, *, and /) operators are the usual arithmetic operators, so you are already familiar with these operators. However, the operator % might be new to you. The modulus operator (%) finds the remainder of an integer division. This operator can be applied only on integer operands and cannot be used on float or double operands. While performing modulo division, the sign of the result is always the sign of the first operand (the dividend). Therefore, 16 % 3 = 1 –16 % 3 = –1 16 % –3 = 1 –16 % –3 = –1 When both operands of the division operator (/) are integers, the division is performed as an integer division. Integer division always results in an integer result. So, the result is always rounded-off by ignoring the remainder. Therefore, 9/4 = 2 and –9/4 = –3

– 23 of 557 –

10 Data Structures Using C tw Note It is not possible to divide any number by zero. This is an illegal operation that results in a run-time division-by-zero exception thereby terminating the program. Except for modulus operator, all other arithmetic operators can accept a mix of integer and floating point numbers. If both operands are integers, the result will be an integer; if one or both operands are floating point numbers then the result would be a floating point number. All the arithmetic operators bind from left to right. Multiplication, division, and modulus operators have higher precedence over addition and subtraction operators. Thus, if an arithmetic expression consists of a mix of operators, then multiplication, division, and modulus will be carried out first in a left to right order, before any addition and subtraction can be performed. For example, 3 + 4 * 7 = 3 + 28 = 31 Relational Operators A relational operator, also known as a comparison operator, is an operator that compares two values or expressions. Relational operators return true or false value, depending on whether the conditional relationship between the two operands holds or not. For example, to test if x is less than y, relational operator < is used as x < y. This expression will return true value if x is less than y; otherwise the value of the expression will be false. C provides four relational operators which are illustrated in Table 1.8. These operators are evaluated from left to right. Equality Operators C language also supports two equality operators to compare operands for strict equality or inequality. They are equal to (==) and not equal to (!=) operators. The equality operators have lower precedence than the relational operators. The equal-to operator (==) returns true (1) if operands on both sides of the operator have the same value; otherwise, it returns false (0). On the contrary, the not- equal-to operator (!=) returns true (1) if the operands do not have the same value; else it returns false (0). Table 1.9 summarizes equality operators. Logical Operators C language supports three logical operators. They are logical AND (&&), logical OR (||), and logical NOT (!). As in case of arithmetic expressions, logical expressions are evaluated from left to right. Logical AND (&&) Logical AND is a binary operator, which simultaneously evaluates two values or relational expressions. If both the operands are true, then the whole expression is true. If both or one of the operands is false, then the whole expression evaluates to false. The truth table of logical AND operator is given in Table 1.10. Table 1.8 Relational operators Operator Meaning Example < Less than 3 < 5 gives 1 > Greater than 7 > 9 gives 0 <= Less than or equal to 100 <= 100 gives 1 >= Greater than equal to 50 >= 100 gives 0 Table 1.9 Equality operators Operator Meaning == Returns 1 if both operands are equal, 0 otherwise != Returns 1 if operands do not have the same value, 0 otherwise Table 1.10 Truth table of logical AND A B A && B 0 0 0 0 1 0 1 0 0 1 1 1

– 24 of 557 –

Introduction to C 11 For example, (a < b) && (b > c) The whole expression is true only if both expressions are true, i.e., if b is greater than a and c. Logical OR (||) Logical OR returns a false value if both the operands are false. Otherwise it returns a true value. The truth table of logical OR operator is given in Table 1.11. For example, (a < b) || (b > c) The whole expression is true if either b is greater than a or b is greater than c or b is greater than both a and c. Logical NOT (!) The logical NOT operator takes a single expression and produces a zero if the expression evaluates to a non-zero value and produces a 1 if the expression produces a zero. The truth table of logical NOT operator is given in Table 1.12. For example, int a = 10, b; b = !a; Now the value of b = 0. This is because value of a = 10. !a = 0. The value of !a is assigned to b, hence the result. Unary Operators Unary operators act on single operands. C language supports three unary operators. They are unary minus, increment, and decrement operators. Unary Minus (–) Unary minus operator negates the value of its operand. For example, if a number is positive then it becomes negative when preceded with a unary minus operator. Similarly, if the number is negative, it becomes positive after applying the unary minus operator. For example, int a, b = 10; a = –(b); The result of this expression is a = –10, because variable b has a positive value. After applying unary minus operator (–) on the operand b, the value becomes –10, which indicates it has a negative value. Increment Operator (++) and Decrement Operator (– –) The increment operator is a unary operator that increases the value of its operand by 1. Similarly, the decrement operator decreases the value of its operand by 1. For example, – –x is equivalent to writing x = x – 1. The increment/decrement operators have two variants: prefix and postfix. In a prefix expression (++x or – –x), the operator is applied before the operand while in a postfix expression (x++ or x––), the operator is applied after the operand. An important point to note about unary increment and decrement operators is that ++x is not same as x++. Similarly, – –x is not the same as x– –. Although, x++ and ++x both increment the value of x by 1, in the former case, the value of x is returned before it is incremented. Whereas in the latter case, the value of x is returned after it is incremented. For example, Table 1.11 Truth table of logical OR A B A || B 0 0 0 0 1 1 1 0 1 1 1 1 Table 1.12 Truth table of logical NOT A ! A 0 1 1 0

– 25 of 557 –

12 Data Structures Using C int x = 10, y; y = x++; is equivalent to writing y = x; x = x + 1; Whereas y = ++x; is equivalent to writing x = x + 1; y = x; The same principle applies to unary decrement operators. Note that unary operators have a higher precedence than the binary operators. And if in an expression we have more than one unary operator then they are evaluated from right to left. Conditional Operator The syntax of the conditional operator is exp1 ? exp2 : exp3 exp1 is evaluated first. If it is true, then exp2 is evaluated and becomes the result of the expression, otherwise exp3 is evaluated and becomes the result of the expression. For example, large = (a > b) ? a : b The conditional operator is used to find the larger of two given numbers. First exp1, that is a > b, is evaluated. If a is greater than b, then large = a, else large = b. Hence, large is equal to either a or b, but not both. Conditional operators make the program code more compact, more readable, and safer to use as it is easier to both check and guarantee the arguments that are used for evaluation. Conditional operator is also known as ternary operator as it takes three operands. Bitwise Operators As the name suggests, bitwise operators perform operations at the bit level. These operators include: bitwise AND, bitwise OR, bitwise XOR, and shift operators. Bitwise AND Like boolean AND (&&), bitwise AND operator (&) performs operation on bits instead of bytes, chars, integers, etc. When we use the bitwise AND operator, the bit in the first operand is ANDed with the corresponding bit in the second operand. The truth table is the same as we had seen in logical AND operation. The bitwise AND operator compares each bit of its first operand with the corresponding bit of its second operand. If both bits are 1, the corresponding bit in the result is 1 and 0 otherwise. For example, 10101010 & 01010101 = 00000000 Bitwise OR When we use the bitwise OR operator (|), the bit in the first operand is ORed with the corresponding bit in the second operand. The truth table is the same as we had seen in logical OR operation. The bitwise OR operator compares each bit of its first operand with the corresponding bit of its second operand. If one or both bits are 1, the corresponding bit in the result is 1 and 0 otherwise. For example, 10101010 | 01010101 = 11111111 Bitwise XOR When we use the bitwise XOR operator, the bit in the first operand is XORed with the corresponding

– 26 of 557 –

Introduction to C 13 bit in the second operand. The truth table of bitwise XOR operator is shown in Table 1.13. The bitwise XOR operator compares each bit of its first operand with the corresponding bit of its second operand. If one of the bits is 1, the corresponding bit in the result is 1 and 0 otherwise. For example, 10101010 ^ 01010101 = 11111111 Bitwise NOT (~) The bitwise NOT or complement is a unary operator that performs logical negation on each bit of the operand. By performing negation of each bit, it actually produces the one’s complement of the given binary value. Bitwise NOT operator sets the bit to 1 if it was initially 0 and sets it to 0 if it was initially 1. For example, ~10101011 = 01010100 Shift Operators C supports two bitwise shift operators. They are shift left (<<) and shift right (>>). The syntax for a shift operation can be given as operand op num where the bits in the operand are shifted left or right depending on the operator (left, if the operator is << and right, if the operator is >>) by number of places denoted by num. For example, if we have x = 0001 1101 then x << 1 produces 0011 1010 When we apply a left shift, every bit in x is shifted to the left by one place. So, the MSB (most significant bit) of x is lost, the LSB (least significant bit) of x is set to 0. Therefore, if we have x = 0001 1101, then x << 3 gives result = 1110 1000 On the contrary, when we apply a right shift, every bit in x is shifted to the right by one place. So, the LSB of x is lost, the MSB of x is set to 0. For example, if we have x = 0001 1101, then x >> 1 gives result = 0000 1110 Similarly, if we have x = 0001 1101, then x >> 4 gives result = 0000 0001 Note The expression x << y is equivalent to multiplication of x by 2 y. And the expression x >> y is equivalent to division of x by 2 y if x is unsigned or has a non-negative value. Assignment Operators In C language, the assignment operator is responsible for assigning values to the variables. While the equal sign (=) is the fundamental assignment operator, C also supports other assignment operators that provide shorthand ways to represent common variable assignments. When an equal sign is encountered in an expression, the compiler processes the statement on the right side of the sign and assigns the result to the variable on the left side. For example, int x; x = 10; assigns the value 10 to variable x. The assignment operator has right-to-left associativity, so the expression Table 1.13 Truth table of bitwise XOR A B A ^ B 0 0 0 0 1 1 1 0 1 1 1 0

– 27 of 557 –

14 Data Structures Using C a = b = c = 10; is evaluated as (a = (b = (c = 10))); First 10 is assigned to c, then the value of c is assigned to b. Finally, the value of b is assigned to a. Table 1.14 contains a list of other assignment operators that are supported by C. Comma Operator The comma operator, which is also called the sequential-evaluation operator, takes two operands. It works by evaluating the first expression and discarding its value, and then evaluates the second expression and returns the value as the result of the expression. Comma-separated expressions when chained together are evaluated in left-to-right sequence with the right-most value yielding the result of the expression. Among all the operators, the comma operator has the lowest precedence. Therefore, when a comma operator is used, the entire expression evaluates to the value of the right expression. For example, the following statement first increments a, then increments b, and then assigns the value of b to x. int a=2, b=3, x=0; x = (++a, b+=a); Now, the value of x = 6. sizeof Operator sizeof is a unary operator used to calculate the size of data types. This operator can be applied to all data types. When using this operator, the keyword sizeof is followed by a type name, variable, or expression. The operator returns the size of the data type, variable, or expression in bytes. That is, the sizeof operator is used to determine the amount of memory space that the data type/variable/expression will take. When a type name is used, it is enclosed in parentheses, but in case of variable names and expressions, they can be specified with or without parentheses. A sizeof expression returns an unsigned value that specifies the size of the space in bytes required by the data type, variable, or expression. For example, sizeof(char) returns 1, that is the size of a character data type. If we have, int a = 10; unsigned int result; result = sizeof(a); then result = 2, that is, space required to store the variable a in memory. Since a is an integer, it requires 2 bytes of storage space. Operator precedence Chart Table 1.15 lists the operators that C language supports in the order of their precedence (highest to lowest). The associativity indicates the order in which the operators of equal precedence in an expression are evaluated. Table 1.14 Assignment operators Operator Example /= float a=9.0; float b=3.0; a /= b; = int a= 9; int b = 3; a = b; *= int a= 9; int b = 3; a *= b; += int a= 9; int b = 3; a += b; –= int a= 9; int b = 3; a –= b; &= int a = 10; int b = 20; a &= b; ^= int a = 10; int b = 20; a ^= b; <<= int a= 9; int b = 3; a <<= b; >>= int a= 9; int b = 3; a >>= b;

– 28 of 557 –

Introduction to C 15 Examples of Expressions Using the Precedence Chart If we have the following variable declarations: int a = 0, b = 1, c = –1; float x = 2.5, y = 0.0; then, (a) a && b = 0 (b) a < b && c < b = 1 (c) b + c || ! a = ( b + c) || (!a) = 0 ||1 = 1 (d) x * 5 && 5 || ( b / c) = ((x * 5) && 5) || (b / c) = (12.5 && 5) || (1/–1) = 1 (e) a <= 10 && x >= 1 && b = ((a <= 10) && (x >= 1)) && b = (1 && 1) && 1 = 1 (f) !x || !c || b + c = ((!x) || (!c)) || (b + c) = (0 || 0) || 0 = 0 (g) x * y < a + b || c = ((x * y) < (a + b)) || c = (0 < 1) || –1 = 1 (h) (x > y) + !a || c++ = ((x > y) + (!a)) || (c++) = (1 + 1) || 0 = 1 P rogramming ExamPlE

  1. Write a program to calculate the area of a circle.
#include <stdio.h>
#include <conio.h>
int main()
{
float radius;
double area;
clrscr();
printf("\n Enter the radius of the circle : ");
scanf("%f", &radius);
area = 3.14 * radius * radius;
printf(" \n Area = %.2lf", area);
return 0;
}

Output Enter the radius of the circle : 7 Area = 153.86 Table 1.15 Operators precedence chart Operator Associativity () [] . —> left–to–right ++(postfix) ––(postfix) right–to–left ++(prefix) ––(prefix) +(unary) – (unary) ! ~ (type) *(indirection) &(address) sizeof right–to–left

– 29 of 557 –

16 Data Structures Using C 1.8 TYPe CONveRSION aND TYPeCaSTINg Type conversion or typecasting of variables refers to changing a variable of one data type into another. While type conversion is done implicitly, casting has to be done explicitly by the programmer. We will discuss both these concepts here. Type Conversion Type conversion is done when the expression has variables of different data types. So to evaluate the expression, the data type is promoted from lower to higher level where the hierarchy of data types can be given as: double, float, long, int, short, and char. For example, type conversion is automatically done when we assign an integer value to a floating point variable. Consider the following code: float x; int y = 3; x = y; Now, x = 3.0, as integer value is automatically converted into its equivalent floating point representation. Typecasting Typecasting is also known as forced conversion. It is done when the value of one data type has to be converted into the value of another data type. The code to perform typecasting can be given as: float salary = 10000.00; int sal; sal = (int) salary; When floating point numbers are converted to integers, the digits after the decimal are truncated. Therefore, data is lost when floating point representations are converted to integral representations. As we can see in the code, typecasting can be done by placing the destination data type in parentheses followed by the variable name that has to be converted. Hence, we conclude that typecasting is done to make a variable of one data type to act like a variable of another type. P rogramming ExamPlE 2. Write a program to convert an integer into the corresponding floating point number.

#include <stdio.h>
#include <conio.h>
int main()
{
float f_num;
int i_num;
clrscr();
printf("\n Enter any integer: ");
scanf("%d", &i_num);
f_num = (float)i_num;
printf("\n The floating point variant of %d is = %f", i_num, f_num);
return 0;
}

Output Enter any integer: 56 The floating point variant of 56 is = 56.000000

– 30 of 557 –

Introduction to C 17 1.9 CONTROL STaTeMeNTS Till now we know that the code in the C program is executed sequentially from the first line of the program to its last line. That is, the second statement is executed after the first, the third statement is executed after the second, so on and so forth. Although this is true, in some cases we want only selected statements to be executed. Control flow statements enable programmers to conditionally execute a particular block of code. There are three types of control statements: decision control (branching), iterative (looping), and jump statements. While branching means deciding what actions have to be taken, looping, on the other hand, decides how many times the action has to be taken. Jump statements transfer control from one point to another point. 1.9.1 Decision Control Statements C supports decision control statements that can alter the flow of a sequence of instructions. These statements help to jump from one part of the program to another depending on whether a particular condition is satisfied or not. These decision control statements include: (a) if statement, (b) if–else statement, (c) if–else–if statement, and (d) switch–case statement. if Statement if statement is the simplest decision control statement that is frequently used in decision making. The general form of a simple if statement is shown in Fig. 1.2. Test Expression Statement Block 1 Statement x FALSE TRUE Syntax of if Statement

if (test expression)
{
statement 1;
............
statement n;
}
statement x;

Figure 1.2 if statement construct The if block may include 1 statement or n statements enclosed within curly brackets. First the test expression is evaluated. If the test expression is true, the statements of the if block are executed, otherwise these statements will be skipped and the execution will jump to statement x. The statement in an if block is any valid C language statement, and the test expression is any valid C language expression that evaluates to either true or false. In addition to simple relational expressions, we can also use compound expressions formed using logical operators. Note that there is no semi-colon after the test expression. This is because the condition and statement should be put together as a single statement.

– 31 of 557 –

18 Data Structures Using C

#include <stdio.h>
int main()
{
int x=10;
if (x>0) x++;
printf("\n x = %d", x);
return 0;
}

In the above code, we take a variable x and initialize it to 10. In the test expression, we check if the value of x is greater than 0. As 10 > 0, the test expression evaluates to true, and the value of x is incremented. After that, the value of x is printed on the screen. The output of this program is x = 11 Observe that the printf statement will be executed even if the test expression is false. Note In case the statement block contains only one statement, putting curly brackets becomes optional. If there are more than one statement in the statement block, putting curly brackets becomes mandatory. if–else Statement We have studied that using if statement plays a vital role in conditional branching. Its usage is very simple. The test expression is evaluated, if the result is true, the statement(s) followed by the expression is executed, else if the expression is false, the statement is skipped by the compiler. What if you want a separate set of statements to be executed if the expression returns a false value? In such cases, we can use an if–else statement rather than using a simple if statement. The general form of simple if–else statement is shown in Fig. 1.3. Test Expression Statement Block 2 Statement Block 1 Statement x FALSE TRUE Syntax of if-else Statement

if (test expression)
{
statement block 1;
}
else
{
statement block 2;
}
statement x;

Figure 1.3 if–else statement construct In the if–else construct, first the test expression is evaluated. If the expression is true, statement block 1 is executed and statement block 2 is skipped. Otherwise, if the expression is false, statement block 2 is executed and statement block 1 is ignored. In any case after the statement block 1 or 2 gets executed, the control will pass to statement x. Therefore, statement x is executed in every case.

– 32 of 557 –

Introduction to C 19 P rogramming ExamPlE 3. Write a program to find whether a number is even or odd.

#include <stdio.h>
int main()
{
int a;
printf("\n Enter the value of a : ");
scanf("%d", &a);
if(a%2==0)
printf("\n %d is even", a);
else
printf("\n %d is odd", a);
return 0;
}

Output Enter the value of a : 6 6 is even if–else–if Statement C language supports if–else–if statements to test additional conditions apart from the initial test expression. The if–else–if construct works in the same way as a normal if statement. Its construct is given in Fig. 1.4. Syntax of if-else-if Statement

if (test expression 1)
{
statement block 1;
}
else if (test expression 2)
{
statement block 2;
}
...........................
else
{
statement block x;
}
statement y;

Test Expression 1 Statement Block 1 FALSE TRUE Test Expression 2 Statement Block 2 Statement Block x Statement y TRUE FALSE Figure 1.4 if–else–if statement construct Note that it is not necessary that every if statement should have an else block as C supports simple if statements. After the first test expression or the first if branch, the programmer can have as many else–if branches as he wants depending on the expressions that have to be tested. For example, the following code tests whether a number entered by the user is negative, positive, or equal to zero.

– 33 of 557 –

20 Data Structures Using C

#include <stdio.h>
int main()
{
int num;
printf("\n Enter any number : ");
scanf("%d", &num);
if(num==0)
printf("\n The value is equal to zero");
else if(num>0)
printf("\n The number is positive");
else
printf("\n The number is negative");
return 0;
}

Note that if the first test expression evaluates to a true value, i.e., num=0, then the rest of the statements in the code will be ignored and after executing the printf statement that displays ‘The value is equal to zero’, the control will jump to return 0 statement. switch–case Statement A switch-case statement is a multi-way decision statement that is a simplified version of an if– else–if block. The general form of a switch statement is shown in Fig. 1.5. Value 1 Value 2 Value N Statement Block D Statement X Statement Block 1 Statement Block 2 Statement Block N FALSE FALSE FALSE FALSE TRUE TRUE TRUE Syntax of Switch Statement

switch (variable)
{
case value 1:
statement block 1;
break;
case value 2:
statement block 2;
break;
.....................
case value N:
statement block N;
break;
default:
statement block D;
break;
}
statement X;

Figure 1.5 switch–case statement construct The power of nested if–else–if statements lies in the fact that it can evaluate more than one expression in a single logical structure. switch statements are mostly used in two situations: ∑ When there is only one variable to evaluate in the expression ∑ When many conditions are being tested for

– 34 of 557 –

Introduction to C 21 When there are many conditions to test, using the if and else–if constructs becomes complicated and confusing. Therefore, switch case statements are often used as an alternative to long if statements that compare a variable to several ‘integral’ values (integral values are those values that can be expressed as an integer, such as the value of a char). Switch statements are also used to handle the input given by the user. We have already seen the syntax of the switch statement. The switch case statement compares the value of the variable given in the switch statement with the value of each case statement that follows. When the value of the switch and the case statement matches, the statement block of that particular case is executed. Did you notice the keyword default in the syntax of the switch case statement? Default is the case that is executed when the value of the variable does not match with any of the values of the case statements. That is, default case is executed when no match is found between the values of switch and case statements and thus there are no statements to be executed. Although the default case is optional, it is always recommended to include it as it handles any unexpected case. In the syntax of the switch–case statement, we have used another keyword break. The break statement must be used at the end of each case because if it is not used, then the case that matched and all the following cases will be executed. For example, if the value of switch statement matched with that of case 2, then all the statements in case 2 as well as the rest of the cases including default will be executed. The break statement tells the compiler to jump out of the switch case statement and execute the statement following the switch–case construct. Thus, the keyword break is used to break out of the case statements. Advantages of Using a switch–case Statement Switch–case statement is preferred by programmers due to the following reasons: ∑ Easy to debug ∑ Easy to read and understand ∑ Ease of maintenance as compared to its equivalent if–else statements ∑ Like if–else statements, switch statements can also be nested ∑ Executes faster than its equivalent if–else construct P rogramming ExamPlE 4. Write a program to determine whether the entered character is a vowel or not.

– 35 of 557 –

22 Data Structures Using C

#include <stdio.h>
int main()
{
char ch;
printf("\n Enter any character : ");
scanf("%c", &ch);
switch(ch)
{
case 'A':
case 'a':
printf("\n %c is VOWEL", ch);
break;
case 'E':
case 'e':
printf("\n %c is VOWEL", ch);
break;
case 'I':
case 'i':
printf("\n %c is VOWEL", ch);
break;
case 'O':
case 'o':
printf("\n %c is VOWEL", ch);
break;
case 'U':
case 'u':
printf("\n %c is VOWEL", ch);
break;
default: printf("\n %c is not a vowel", ch);
}
return 0;
}

Output Enter any character : j j is not a vowel Note that there is no break statement after case A, so if the character A is entered then control will execute the statements given in case a. 1.9.2 Iterative Statements Iterative statements are used to repeat the execution of a sequence of statements until the specified expression becomes false. C supports three types of iterative statements also known as looping statements. They are ∑ while loop ∑ do–while loop ∑ for loop In this section, we will discuss all these statements. while Loop The while loop provides a mechanism to repeat one or more statements while a particular condition is true. Figure 1.6 shows the syntax and general form of a while loop. Condition Statement x Statement y Statement Block Update the Condition Expression FALSE TRUE Syntax of While Loop

statement x;
while (condition)
{
statement block;
}
statement y;

Figure 1.6 While loop construct

– 36 of 557 –

Introduction to C 23 Note that in the while loop, the condition is tested before any of the statements in the statement block is executed. If the condition is true, only then the statements will be executed, otherwise if the condition is false, the control will jump to statement y, that is the immediate statement outside the while loop block. In the flow diagram of Fig. 1.6, it is clear that we need to constantly update the condition of the while loop. It is this condition which determines when the loop will end. The while loop will execute as long as the condition is true. Note that if the condition is never updated and the condition never becomes false, then the computer will run into an infinite loop which is never desirable. For example, the following code prints the first 10 numbers using a while loop.

#include <stdio.h>
int main()
{
int i = 1;
while(i<=10)
{
printf("\n %d", i);
i = i + 1; 	// condition updated
}
return 0;
}

Note that initially i = 1 and is less than 10, i.e., the condition is true, so in the while loop the value of i is printed and its value is incremented by 1. When i=11, the condition becomes false and the loop ends. P rogramming ExamPlE 5. Write a program to calculate the sum of numbers from m to n.

#include <stdio.h>
int main()
{
int n, m, i, sum =0;
printf("\n Enter the value of m : ");
scanf("%d", &m);
i=m;
printf("\n Enter the value of n : ");
scanf("%d", &n);
while(i<=n)
{
sum = sum + i;
i = i + 1;
}
printf("\n The sum of numbers from %d to %d = %d", m, n, sum);
return 0;
}

Output Enter the value of m : 2 Enter the value of n : 10 The sum of numbers from 2 to 10 = 54 do–while Loop The do–while loop is similar to the while loop. The only difference is that in a do–while loop, the test condition is tested at the end of the loop. As the test condition is evaluated at the end, this means that the body of the loop gets executed at least one time (even if the condition is false). Figure 1.7 shows the syntax and the general form of a do–while loop.

– 37 of 557 –

24 Data Structures Using C Figure 1.7 Do–while construct Note that the test condition is enclosed in parentheses and followed by a semi-colon. The statements in the statement block are enclosed within curly brackets. The curly brackets are optional if there is

[…content truncated for processing]