Preface – Introduction to Data Structures in C

Preface

This book is an introduction to all popular data structures, and their implementation with the C language. It is planned for beginners who would like to learn the subject through programs. We have therefore included a large number of programs along with their theories. It is hoped that the book will be of immense help to graduate and postgraduate students of engineering, science, and computer application. It can be used as a text-cum-reference book by students of BE, MCA, BCA, M.Sc. and B.Sc. courses, and also by students pursuing courses such as O, A, B, and C levels conducted by the DOEACC Society.

This book covers abstract concepts of data structures and describes how these theories are useful in problem-solving. Chapter 1 introduces the reader to the fundamentals of C language. It covers data types, structures, unions, algorithms, iterations and concepts of data structures.

Chapter 2 deals with arrays. It covers one-, two- and multidimensional arrays and contains numerous examples. It also covers row major and column major arrays. Pointers and arrays are also described at the end of the chapter.

Chapter 3 deals with recursion, which is a powerful and important concept in programming. Recursion plays a pivotal role in implementation of algorithmic solutions with minimum code. Direct and indirect recursive are explained through programs, and popular examples such as the Tower of Hanoi are also covered in the chapter.

Another building block of data structures is stack, which is described in Chapter 4. Terminologies of stack, pictorial representation of stack, push and pop operations and applications are discussed in the chapter. In addition, operations such as insertion and deletion of elements in a stack are explained with the help of examples. Evaluation of postfix expression and infix to postfix expressions are also given at the end of the chapter.

Queue, another linear data structure, is explained in Chapter 5. Representation of queue, insertion and deletion of an element in a queue, its static and dynamic implementation, and its applications are covered in the chapter. In addition, circular, deque and priority queues are explained. Ascending and descending priority queues are also discussed at the end of the chapter.

Chapter 6 discusses linked list, another significant element of data structures. Operations such as traversing a list, searching and retrieving an element from a list are described in this chapter. Types of linked lists, single, double and circular linked list are also described.

The most important topic presented on storage of data is memory. Chapter 7 discusses all the fundamental concepts of memory: how efficiently memory is managed by an operating system, how space is allocated by the operating system to the different programs and how storage allocation and de-allocation of memory are done. Buddy, binary buddy and compaction techniques are illustrated in this chapter.

One of the non-linear data structures, tree, is explained in Chapter 8. Basic terms used in binary tree are described at the beginning of the chapter. Topics such as binary tree, complete binary tree, extended binary tree, traversal in tree, threshold binary tree, balanced tree and B+ are all covered in this chapter.

Chapter 9 is devoted to graph. It deals with the basic terminologies of graph, representation of graph, traversals in graph, spanning tree, etc.

Chapter 10 discusses various searching techniques such as linear, binary, hashing, middivision, mid-square, folding and length-dependent methods. Attention has also been paid on establishing the efficiency of some searching methods.

Chapter 11 is devoted to sorting methods. Various sorting techniques such as selection insertion, bubble, tree, merge, heap sot methods have been elaborated with programs. Partition exchange and radix sort methods have been discussed and supported with programming examples.

Utmost care has been taken in bringing out this book, and it is hoped that the book will serve the requirements of those for whom it is intended. However, it is possible that a few errors might have managed to evade the watchful eye. The author will be grateful to the readers for bringing these errors to his notice and also for their valuable suggestions for improving the quality of the book. The author can be reached at kamthanean@yahoo.com

 

ASHOK N. KAMTHANE