Data Structures Using C Second Edition

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. It begins with a thorough overview of the concepts of C programming followed by introduction of different data structures and methods to analyse the complexity of different algorithms. It then connects these concepts and applies them to the study of various data structures such as arrays, strings, linked lists, stacks, queues, trees, heaps, and graphs. 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. Each chapter includes a variety of end-chapter exercises in the form of MCQs with answers, review questions, and programming exercises to help readers test their knowledge Content: 1. INTRODUCTION TO C 1.1 INTRODUCTION 1.2 IDENTIFIERS AND KEYWORDS 1.3 BASIC DATA TYPES 1.4 VARIABLES AND CONSTANTS 1.5 WRITING THE FIRST C PROGRAM 1.6 INPUT AND OUTPUT FUNCTIONS 1.7 OPERATORS AND EXPRESSIONS 1.8 TYPE CONVERSION AND TYPECASTING 1.9 CONTROL STATEMENTS 1.10 FUNCTIONS 1.11 POINTERS 2. INTRODUCTION TO DATA STRUCTURES AND ALGORITHMS 2.1 BASIC TERMINOLOGY 2.2 CLASSIFICATION OF DATA STRUCTURES 2.3 OPERATIONS ON DATA STRUCTURES 2.4 ABSTRACT DATA TYPE 2.5 ALGORITHMS 2.6 DIFFERENT APPROACHES TO DESIGNING AN ALGORITHM 2.7 CONTROL STRUCTURES USED IN ALGORITHMS 2.8 TIME AND SPACE COMPLEXITY 2.9 BIG O NOTATION 2.10 OMEGA NOTATION (?) 2.11 THETA NOTATION (Q) 2.12 OTHER USEFUL NOTATIONS 3. ARRAYS 3.1 INTRODUCTION 3.2 DECLARATION OF ARRAYS 3.3 ACCESSING THE ELEMENTS OF AN ARRAY 3.4 STORING VALUES IN ARRAYS 3.5 OPERATIONS ON ARRAYS 3.6 PASSING ARRAYS TO FUNCTIONS 3.7 POINTERS AND ARRAYS 3.8 ARRAYS OF POINTERS 3.9 TWO-DIMENSIONAL ARRAYS 3.10 OPERATIONS ON TWO-DIMENSIONAL ARRAYS 3.11 PASSING TWO-DIMENSIONAL ARRAYS TO FUNCTIONS 3.12 POINTERS AND TWO-DIMENSIONAL ARRAYS 3.13 MULTI-DIMENSIONAL ARRAYS 3.14 POINTERS AND THREE-DIMENSIONAL ARRAYS 3.15 SPARSE MATRICES 3.16 APPLICATIONS OF ARRAYS 4. STRINGS 4.1 INTRODUCTION 4.2 OPERATIONS ON STRINGS 4.3 ARRAYS OF STRINGS 4.4 POINTERS AND STRINGS 5. STRUCTURES AND UNIONS 5.1 INTRODUCTION 5.2 NESTED STRUCTURES 5.3 ARRAYS OF STRUCTURES 5.4 STRUCTURES AND FUNCTIONS 5.5 SELF-REFERENTIAL STRUCTURES 5.6 UNIONS 5.7 ARRAYS OF UNION VARIABLES 5.8 UNIONS INSIDE STRUCTURES 6. LINKED LISTS 6.1 INTRODUCTION 6.2 SINGLY LINKED LISTS 6.3 CIRCULAR LINKED LISTS 6.4 DOUBLY LINKED LISTS 6.5 CIRCULAR DOUBLY LINKED LISTS 6.6 HEADER LINKED LISTS 6.7 MULTI-LINKED LISTS 6.8 APPLICATIONS OF LINKED LISTS 7. STACKS 7.1 INTRODUCTION TO STACKS 7.2 ARRAY REPRESENTATION OF STACKS 7.3 OPERATIONS ON A STACK 7.4 LINKED REPRESENTATION OF STACKS 7.5 OPERATIONS ON A LINKED STACK 7.6 MULTIPLE STACKS 7.7 APPLICATIONS OF STACKS 8. QUEUES 8.1 INTRODUCTION TO QUEUES 8.2 ARRAY REPRESENTATION OF QUEUES 8.3 LINKED REPRESENTATION OF QUEUES 8.4 TYPES OF QUEUES 8.5 APPLICATIONS OF QUEUES 9. TREES 9.1 INTRODUCTION 9.2 TYPES OF TREES 9.3 CREATING A BINARY TREE FROM A GENERAL TREE 9.4 TRAVERSING A BINARY TREE 9.5 HUFFMAN'S TREE 9.6 APPLICATIONS OF TREES 10. EFFICIENT BINARY TREES 10.1 BINARY SEARCH TREES 10.2 OPERATIONS ON BINARY SEARCH TREES 10.3 THREADED BINARY TREES 10.4 AVL TREES 10.5 RED-BLACK TREES 10.6 SPLAY TREES 11. MULTI-WAY SEARCH TREES 11.1 INTRODUCTION TO M-WAY SEARCH TREES 11.2 B TREES 11.3 B+ TREES 11.4 2-3 TREES 11.5 TRIE 12. HEAPS 12.1 BINARY HEAPS 12.2 BINOMIAL HEAPS 12.3 FIBONACCI HEAPS 12.4 COMPARISON OF BINARY, BINOMIAL,AND FIBONACCI HEAPS 12.5 APPLICATIONS OF HEAPS 13. GRAPHS 13.1 INTRODUCTION 13.2 GRAPH TERMINOLOGY 13.3 DIRECTED GRAPHS 13.4 BI-CONNECTED COMPONENTS 13.5 REPRESENTATION OF GRAPHS 13.6 GRAPH TRAVERSAL ALGORITHMS 13.7 TOPOLOGICAL SORTING 13.8 SHORTEST PATH ALGORITHMS 13.9 APPLICATIONS OF GRAPHS 14. SEARCHING AND SORTING 14.1 INTRODUCTION TO SEARCHING 14.2 LINEAR SEARCH 14.3 BINARY SEARCH 14.4 INTERPOLATION SEARCH 14.5 JUMP SEARCH 14.6 INTRODUCTION TO SORTING 14.7 BUBBLE SORT 14.8 INSERTION SORT 14.9 SELECTION SORT 14.10 MERGE SORT 14.11 QUICK SORT 14.12 RADIX SORT 14.13 HEAP SORT 14.14 SHELL SORT 14.15 TREE SORT 14.16 COMPARISON OF SORTING ALGORITHMS 14.17 EXTERNAL SORTING 15. HASHING AND COLLISION 15.1 INTRODUCTION 15.2 HASH TABLES 15.3 HASH FUNCTIONS 15.4 DIFFERENT HASH FUNCTIONS 15.5 COLLISIONS 15.6 PROS AND CONS OF HASHING 15.7 APPLICATIONS OF HASHING 16. FILES AND THEIR ORGANIZATION 16.1 INTRODUCTION 16.2 DATA HIERARCHY 16.3 FILE ATTRIBUTES 16.4 TEXT AND BINARY FILES 16.5 BASIC FILE OPERATIONS 16.6 FILE ORGANIZATION 16.7 INDEXING The second edition of Data Structures Using C is designed to serve as a textbook for undergraduate engineering students of computer science as well as postgraduate students of computer applications. It provides a comprehensive coverage of the concepts of data structures and their implementation using C language.