Advanced Programming and Problem-Solving Strategies in C. Part II: Algorithms and Data Structures.

This book presents computing technologies for university students enrolled in advanced programming classes such as "Algorithms and programming", and software development professionals. It will give the reader an informative, challenging ad entertaining introduction to use C language to solve complex problems. Those problems will include advance algorithms and complex data structures. The book will concentrate on complete working programs, somehow presenting and contrasting several possible solutions. This work assumes a general-purpose knowledge of the C language such as the one usually learned during basic programming courses delivered at the first year of the curricula in computer engineering and computer science. The book main highlights are the following: . Extended coverage of pointers, dynamic arrays and matrices, linked-lists, and other basic data structures. . Abstract data types (ADTs). . Recursions and recursive algorithms. Each topic is covered by a rich collection of partial and complete examples, and about 100 fully implemented and debugged programs. The focus is on good software engineering, and on program clarity, such that the reader is guided to learn properties of algorithms and data structures as fast as possible. The content of each chapter is the following: . Chapter 1 presents a revising set of exercise to recall basic C construct and problem solving strategies. This is essentially a very brief summary of Volume I by the Nocco et al. [1] (written in Italian). Code and programming style follow the same book. . Chapter 2 introduces pointers and how to use them to refer to and to manipulate objects. . Chapter 3 covers dynamic memory allocation. Pointers, operators on pointers, dynamic arrays, and dynamic matrices are covered into details. . Chapter 4 presents dynamically allocated lists. Simple, ordered, bi-linked, circular, and list-of-lists are described with several gures and code segments. . Chapter 5 describes basic concepts for recursion and it presents simple recursive programs. . Chapter 6 includes standard recursive problems such as merge-sort, quick-sort, the eight queen problems, etc. It also describes combinatorics problems, such as: The multiplication principle, simple arrangements, arrangements with repetitions, simple permutation, permutation with repetitions, simple combination, combinations with repetitions, and the power-set. . Chapter 7 describe how to apply recursion to some hard-to-solve problems. . Chapter 8 describes all required concepts to write programs "in the large", i.e., multi-file programs, with personalized header les. It also illustrates the main concepts of Abstract Data Type (ADTs) and their use in C programming. . Chapter 9 illustrates several ADT-based problems, such as the stack (based on an array or a dynamic list), queues, etc. The book is also covered by online material, as all source codes are available on the editor web page. Among the main source references let us remind the following. As far as algorithms and data structure are concerned, the reader may refer to [2, 3, 4, 5, 6, 7]. For the C language and language syntax a few references are the following [1, 8, 9, 10, 11, 12, 13]. We would sincerely appreciate any comments, criticisms, corrections and suggestions for improving the text. Please address all correspondence to: stefano.quer@polito.it or visits the following web page: http://fmgroup.polito.it/quer/ Changes for the second edition The book changed a lot from the first edition. A summary of the most significant changes for the second edition is the following: . We completely reorganized Chapter 1, interleaving language hints with revising exercises. . We divided Chapter 3 in two separate chapters, reorganizing part of the material presented in both of them. . We went through the entire book and rewrote sentences, paragraphs, and sections to make the writing clearer and more active. When necessary, we added new examples. . We deeply revised all C solutions and their congruency with the specication. Particular care is been placed on the key ones, introducing core details for the remaining part of the book. We also revised many comments inserted into our code. . We corrected several errors and discrepancies. Most of these errors were discovered using the previous edition in class during lectures and practice tests.