Data Structures Using C (Reema Thareja) (Z-Library)

📄 File Format: PDF

💾 File Size: 16.6 MB

📖 Read Online ⬇️ Download

Registered users can read the full content for free

Register as a Gaohf Library member to read the complete e-book online for free and enjoy a better reading experience.

📄 Page 1

(This page has no text content)

📄 Page 2

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

📄 Page 3

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

📄 Page 4

I dedicate this book to my family and my uncle Mr B.L. Thareja 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

📄 Page 5

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

📄 Page 6

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

📄 Page 7

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

📄 Page 8

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.

📄 Page 9

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

📄 Page 10

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

📄 Page 11

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

📄 Page 12

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

📄 Page 13

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

📄 Page 14

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

📄 Page 15

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

📄 Page 16

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

📄 Page 17

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

📄 Page 18

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.

📄 Page 19

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;

📄 Page 20

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