This book is for developers who would like to learn data structures and algorithms in C++. Basic C++ programming knowledge is recommended but not necessary.

Chapter 1, Learning Data Structures and Algorithms in C++, introduces basic C++ programming, including fundamental and advanced data types, controlling code flow, the use of an Integrated Development Environment (IDE), and abstract data types, which will be used in developing data structures. We will also analyze an algorithm using asymptotic analysis, including worst-average-best cases and an explanation of Big Theta, Big-O, Big Omega.

Chapter 2, Storing Data in Lists and Linked Lists, explains how to build a linear data type to store data, that is, a list. It also will explain how to use the list data type we built earlier to create another data type, which is a linked list. However, before we build a data type in this chapter, we will be introduced to Node, the fundamental data type required to build a list and linked list.

Chapter 3, Constructing Stacks and Queues, covers how to create stack, queue, and deque data types, which are also linear data types. We also explain how to use these three types and when we need to use them.

Chapter 4, Arranging Data Elements Using a Sorting Algorithm, talks about sorting elements in a data structure. Here, we will learn how to arrange the order of elements using several sorting algorithms; they are bubble sort, selection sort, insertion sort, merge sort, quick sort, counting sort, and radix sort.

Chapter 5, Finding out an Element Using Searching Algorithm, walks us through the process of finding an element in a data structure. By giving a value to the algorithm, we can find out whether or not the value is in the data structure. There are seven sorting algorithms we are going to discuss; they are linear, binary, ternary, interpolation, jump, exponential, and sublist search.

Chapter 6, Dealing with the String Data Types, discusses how to construct a string data type in C++ programming. Using a string data type, we can construct several words and then do some fun stuff such as anagrams and palindromes. Also, we will learn about binary string, which contains binary digits only, and subsequent string, which is derived from another string. At last in this chapter, we'll discuss using pattern searching to find out a specific short string in a large string.

Chapter 7, Building a Hierarchical Tree Structure, introduces the tree data structure, using which we can construct a tree-like data type. Using the tree data structure, we can develop a binary search tree; we can easily search any element in the tree using binary search algorithm. The binary search tree we have built can be also balanced to prevent a skewed tree. Also, in this chapter, we are going to implement a priority queue using a binary heap. 

Chapter 8, Associating a Value to a Key in Hash Table, explains how to design a hash table, which is a data structure that stores an element based on the hash function. A collision might happen in a hash table data structure, so we also discuss how to handle the collision using separate chaining and open addressing techniques.

Chapter 9, Implementation of Algorithms in Real Life, elaborates some algorithm paradigms and implements them in the real world. There are six algorithm paradigms to discuss in this chapter; they are greedy algorithms, Divide and Conquer algorithms, dynamic programming, Brute-force algorithms, randomized algorithms, and backtracking algorithms.

To get through this book and successfully complete all the source code examples, you will need the following specifications:

    // in_out.cpp
    #include <iostream>

    int main ()
    {
      int i;
      std::cout << "Please enter an integer value: ";
      std::cin >> i;
      std::cout << "The value you entered is " << i;
      std::cout << "\n";
      return 0;
    }

class Node
{
public:
    T Value;
    Node<T> * Next;

    Node(T value) : Value(value), Next(NULL) {}
};

g++ simple.cpp

Feedback from our readers is always welcome.

General feedback: Email [email protected] and mention the book title in the subject of your message. If you have questions about any aspect of this book, please email us at [email protected].

Errata: Although we have taken every care to ensure the accuracy of our content, mistakes do happen. If you have found a mistake in this book, we would be grateful if you would report this to us. Please visit www.packtpub.com/submit-errata, selecting your book, clicking on the Errata Submission Form link, and entering the details.

Piracy: If you come across any illegal copies of our works in any form on the Internet, we would be grateful if you would provide us with the location address or website name. Please contact us at [email protected] with a link to the material.

If you are interested in becoming an author: If there is a topic that you have expertise in and you are interested in either writing or contributing to a book, please visit authors.packtpub.com.