PREFACE

This book aims to cater to beginners who look to learning C and data structure under the same umbrella. While teaching C and data structure, we felt the need for a balanced book on the subject. In fact, this is the main impetus for writing such a book.

The book is designed for a one-semester course or a one-year course. It is suitable for courses based on algorithms and data structures. The prerequisite for using this text is elementary to middle level knowledge of C programming.

Algorithms in the book are presented in a way that readers can easily understand the method of solving problems. Concepts are illustrated through examples. All programs in the text are tested. Each chapter ends with exercises containing questions of varied difficulty levels.

Chapter 1 deals with basic data representation techniques. Chapter 2 concentrates on abstract data types and structures together with the concepts of implementing a data structure. Chapter 3 covers array data structures, the simplest and one of the best-known linear data structures, and their implementation details. As applications of array data structures, Chapter 4 deals with string processing and data matching techniques. Chapter 5 introduces the concept of pointers in C. Why pointers play a key role in algorithm implementation, and how and when to use them are discussed in detail. Stacks and queues are covered in Chapter 6. Though they are special type of lists, this chapter deals only with their array implementation. Expression evaluation is discussed as an application of stack. A rudimentary program for skill testing in multiplication is presented as an application to queue.

Chapter 7 covers recursion, a problem-solving technique. Lists are defined in Chapter 8. This chapter elaborates on the concepts of linked lists, their implementation techniques using both arrays and pointers. Linked list manipulation and list searching is also covered in the chapter. A word indexing program is explained and presented as an application through both array and linked version. Chapter 9 brings forth different variants of linked lists. Linked implementation of stacks and queues are presented in this chapter. It also focuses on major application areas of linked lists. Chapter 10 discusses details of internal sorting as well as some external sorting algorithms. Given a large number of internal sorting techniques, one must choose the best alternative for a particular problem.

Chapter 11 deals with various searching methodologies. The concept of trees is introduced in Chapter 12. It starts with the general tree and then concentrates on binary trees, tree traversal techniques, binary search trees, AVL trees, and B-trees. Chapter 13 describes graphs. The coverage of graph algorithms completes the basic understanding of data structure. The chapter discusses only fundamental graph algorithms.

It is possible that C language will be replaced by a better language in the near future. However, we think our techniques will remain with our readers.

We acknowledge the help of Dr. S. SenSarma, Reader of the Department of Computer Science and Engineering, University of Calcutta, for taking an active interest in different ways. We also thank our colleagues, students, and other members of the Department of Computer Science and Engineering, University of Calcutta, for providing the right environment during the preparation of the manuscript.

We thank the members of our family without whose help this book could not be written.

Samir Kumar Bandyopadhyay
Kashi Nath Dey