Data structures and algorithms are a must-learn for all programmers and software developers. Learning data structures and algorithms can help us solve problems, not only in programming but also in real life. Many people have found algorithms that solve specific problems. When we have a different problem, we can take advantage of the algorithm to solve it by ourselves.
In this book, we will begin by giving you a basic introduction to data structures and algorithms in C++. We will then move on to learn how to store data in linked lists, arrays, stacks, and so on. We will look at some interesting sorting algorithms such as insertion sort, heap sort, merge sort, which are algorithms every developer should be familiar with. We will also dive into searching algorithms, such as linear search, binary search, interpolation and much more.
By the end of this book, you'll be proficient in the use of data structures and algorithms.
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:
- Desktop PC or Notebook with Windows, Linux, or macOS
- GNU GCC v5.4.0 or above
- Code Block IDE v17.12 (for Windows and Linux OS) or Code Block IDE v13.12 (for macOS)
You can download the example code files for this book from your account at www.packtpub.com. If you purchased this book elsewhere, you can visit www.packtpub.com/support and register to have the files emailed directly to you.
You can download the code files by following these steps:
- Log in or register at www.packtpub.com.
- Select the
SUPPORTtab. - Click on
Code Downloads & Errata. - Enter the name of the book in the
Searchbox and follow the onscreen instructions.
Once the file is downloaded, please make sure that you unzip or extract the folder using the latest version of:
- WinRAR/7-Zip for Windows
- Zipeg/iZip/UnRarX for Mac
- 7-Zip/PeaZip for Linux
The code bundle for the book is also hosted on GitHub athttps://github.com/PacktPublishing/CPP-Data-Structures-and-Algorithms. We also have other code bundles from our rich catalog of books and videos available athttps://github.com/PacktPublishing/. Check them out!
We also provide a PDF file that has color images of the screenshots/diagrams used in this book. You can download it here: https://www.packtpub.com/sites/default/files/downloads/CPPDataStructuresandAlgorithms_ColorImages.
There are a number of text conventions used throughout this book.
CodeInText: Indicates code words in text, database table names, folder names, filenames, file extensions, pathnames, dummy URLs, user input, and Twitter handles. Here is an example: "After finishing the wizard, we will have a new project with a main.cpp file."
A block of code is set as follows:
// 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;
}When we wish to draw your attention to a particular part of a code block, the relevant lines or items are set in bold:
class Node
{
public:
T Value;
Node<T> * Next;
Node(T value) : Value(value), Next(NULL) {}
};Any command-line input or output is written as follows:
g++ simple.cppBold: Indicates a new term, an important word, or words that you see onscreen. For example, words in menus or dialog boxes appear in the text like this. Here is an example: "We can create a new project by clicking on the File menu, then clicking New, and then selecting Project."
Feedback from our readers is always welcome.
General feedback: Email feedback@packtpub.com 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 questions@packtpub.com.
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 copyright@packtpub.com 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.
Please leave a review. Once you have read and used this book, why not leave a review on the site that you purchased it from? Potential readers can then see and use your unbiased opinion to make purchase decisions, we at Packt can understand what you think about our products, and our authors can see your feedback on their book. Thank you!
For more information about Packt, please visit packtpub.com.
