C++ Data Structures and Algorithms: Learn how to write efficient code to build scalable and robust applications in C++

C++ Data Structures and Algorithms

Learn how to write efficient code to build scalable and robust applications in C++

Wisnu Anggoro

BIRMINGHAM - MUMBAI

C++ Data Structures and Algorithms

Copyright © 2018 Packt Publishing

All rights reserved. No part of this book may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, without the prior written permission of the publisher, except in the case of brief quotations embedded in critical articles or reviews.

Every effort has been made in the preparation of this book to ensure the accuracy of the information presented. However, the information contained in this book is sold without warranty, either express or implied. Neither the author, nor Packt Publishing or its dealers and distributors, will be held liable for any damages caused or alleged to have been caused directly or indirectly by this book.

Packt Publishing has endeavored to provide trademark information about all of the companies and products mentioned in this book by the appropriate use of capitals. However, Packt Publishing cannot guarantee the accuracy of this information.

Commissioning Editor: Richa Tripathi

Acquisition Editor: Chaitanya Nair

Content Development Editor: Lawrence Veigas

Technical Editor: Supriya Thabe

Copy Editor: Safis Editing

Project Coordinator: Prajakta Naik

Proofreader: Safis Editing

Indexer: Aishwarya Gangawane

Graphics: Jisha Chirayil

Production Coordinator: Arvindkumar Gupta

First published: April 2018

Production reference: 1240418

Published by Packt Publishing Ltd.

Livery Place

35 Livery Street

Birmingham

B3 2PB, UK.

ISBN 978-1-78883-521-3

www.packtpub.com

mapt.io

Mapt is an online digital library that gives you full access to over 5,000 books and videos, as well as industry leading tools to help you plan your personal development and advance your career. For more information, please visit our website.

Why subscribe?

Spend less time learning and more time coding with practical eBooks and Videos from over 4,000 industry professionals

Improve your learning with Skill Plans built especially for you

Get a free eBook or video every month

Mapt is fully searchable

Copy and paste, print, and bookmark content

PacktPub.com

Did you know that Packt offers eBook versions of every book published, with PDF and ePub files available? You can upgrade to the eBook version at www.PacktPub.com and as a print book customer, you are entitled to a discount on the eBook copy. Get in touch with us at [email protected] for more details.

At www.PacktPub.com, you can also read a collection of free technical articles, sign up for a range of free newsletters, and receive exclusive discounts and offers on Packt books and eBooks.

Contributors

About the author

Wisnu Anggoro is a Microsoft Certified Professional in C# programming and an experienced C/C++ developer. He has been programming since junior high school (about 20 years ago) and started developing computer applications using the BASIC language in MS-DOS. He has a lot of experience with smart card, desktop, and web application programming.

He is currently a senior smart card software engineer at CIPTA, an Indonesian company

that specializes in the innovation and technology of smart cards.

I would like to thank God, whose blessings have made me who I am today. My wife, Vivin, who has supported me to achieve all my dreams. To my beloved sons, Olav and Oliver, who are very naughty sometimes but never fail to make me happy every day. To my parents for their inspiration.

Also, I would like to show my gratitude to Benediktus Dwi Desiyanto, my mentor and superior at CIPTA, who always helped me develop my skillsets.

About the reviewer

Mark Elston is a software engineer at an automated test equipment firm working primarily in IC and mobile device testing. His 30 years of experience include developing aircraft and missile simulations for the Air Force and Navy, hardware control systems for NASA, and tester operating systems for commercial products. He has also developed several Android applications for fun. His latest passion is delving into the world of functional programming and design.

I would like to thank my wife for her understanding when I had a chapter to finish reviewing. I would also like to thank the Packt team for giving me the opportunity to work with them on this project. It has been enlightening and entertaining. Finally, I would like to thank the author for taking my comments into account. It is a pleasure to be part of a project where your inputs are valued.

Packt is searching for authors like you

If you're interested in becoming an author for Packt, please visit authors.packtpub.com and apply today. We have worked with thousands of developers and tech professionals, just like you, to help them share their insight with the global tech community. You can make a general application, apply for a specific hot topic that we are recruiting an author for, or submit your own idea.

Table of Contents

Title Page

Copyright and Credits

C++ Data Structures and Algorithms

Packt Upsell

Why subscribe?

PacktPub.com

Contributors

About the author

About the reviewer

Packt is searching for authors like you

Preface

Who this book is for

What this book covers

To get the most out of this book

Download the example code files

Download the color images

Conventions used

Get in touch

Reviews

Learning Data Structures and Algorithms in C++

Technical requirements

Introduction to basic C++

Creating your first code in C++

Enhancing code development experience with IDE

Defining the variables using fundamental data types

Controlling the flow of the code

Conditional statement

Loop statement

Leveraging the variable capability using advanced data types

Developing abstract data types

Applying C++ classes to build user-defined ADTs

Playing with templates

Function templates

Class templates

Standard Template Library

Analyzing the algorithm

Asymptotic analysis

Worst, average, and best cases

Big Theta, Big-O, and Big Omega

Recursive method

Amortized analysis

Summary

QA section

Further reading

Storing Data in Lists and Linked Lists

Technical requirements

Getting closer to an array

Building a List ADT

Fetching an item in the List

Inserting an item into the List ADT

Finding out the index of a selected item in the List ADT

Removing an item from the List ADT

Consuming a List ADT

Introduction to node

Building a Singly Linked List ADT

Fetching an item in the LinkedList class

Inserting an item in the LinkedList class

Getting the index of the selected item in the LinkedList

Removing an item from the LinkedList ADT

Consuming the LinkedList ADT

Building the Doubly Linked List ADT

Refactoring the Node<T> data type

Refactoring several operations in the LinkedList ADT

Removing an element

Inserting an element

Consuming the DoublyLinkedList ADT

Applying List and LinkedList using STL

std::vector

std::list

Summary

QA section

Further reading

Constructing Stacks and Queues

Technical requirements

Building a Stack ADT

Fetching the item's value in the Stack ADT

Pushing the items of the Stack ADT

Popping the items from the Stack ADT

Consuming a Stack ADT

Another example of Stack ADT implementation

Building a Queue ADT

Getting a value from Queue ADT

Inserting an element into the Queue ADT

Removing an element from the Queue ADT

Consuming the Queue ADT

Building a Deque ADT

Fetching a value from a Deque

Enqueueing an element into the Deque ADT

Dequeuing an element from the Deque ADT

Consuming the Deque ADT

Summary

QA section

Further reading

Arranging Data Elements Using a Sorting Algorithm

Technical requirements

Bubble sort

Selection sort

Insertion sort

Merge sort

Quick sort

Counting sort

Radix sort

Summary

QA section

Further reading

Finding out an Element Using Searching Algorithms

Technical requirements

Linear search

Developing a linear search algorithm

Implementing the linear search algorithm

Binary search

Developing binary search algorithm

Implementing binary search algorithm 

Ternary search

Developing ternary search algorithm

Applying the ternary search algorithm

Interpolation search

Developing interpolation search algorithm

Applying interpolation search algorithm

Jump search

Developing jump search algorithm

Applying jump search algorithm

Exponential search

Developing exponential search algorithm

Invoking the ExponentialSearch() function

Sublist search

Designing sublist search algorithm

Performing sublist search algorithm

Summary

QA section

Further reading

Dealing with the String Data Type

Technical requirement

String in C++

Constructing a string using character array

Using std::string for more flexibility features

Playing with words

Rearranging a word to create an anagram

Detecting whether a word is a palindrome

Constructing a string from binary digits

Converting decimal to binary string

Converting binary string to decimal

Subsequence string

Generating subsequences from a string

Checking whether a string is a subsequence of another string

Pattern searching

Summary

QA section

Further reading

Building a Hierarchical Tree Structure

Technical requirements

Building a binary tree ADT

Building a binary search tree ADT

Inserting a new key into a BST

Traversing a BST in order

Finding out whether a key exists in a BST

Retrieving the minimum and maximum key values

Finding out the successor of a key in a BST

Finding out the predecessor of a key in a BST

Removing a node based on a given key

Implementing the BST ADT

Building a balanced BST (AVL) ADT

Rotating nodes

Inserting a new key

Removing a given key

Implementing AVL ADT

Building a binary heap ADT

Checking if the heap is empty

Inserting a new element into the heap

Fetching the element's maximum value

Removing the maximum element

Implementing a binary heap as a priority queue

Summary

QA section

Further reading

Associating a Value to a Key in a Hash Table

Technical requirement

Getting acquainted with hash tables

Big data in small cells

Storing data in a hash table

Collision handling

Implementing a separate chaining technique

Generating a hash key

Developing an Insert() operation

Developing a Search() operation

Developing a Remove() operation

Developing an IsEmpty() operation

Applying a HashTable ADT using a separate chaining technique in the code

Implementing the open addressing technique

Developing the Insert() operation

Developing a Search() operation

Developing the Remove() operation

Developing an IsEmpty() operation

Developing a PrintHashTable() operation

Applying an HashTable ADT using a linear probing technique in the code

Summary

QA section

Further reading

Implementation of Algorithms in Real Life

Technical requirements

Greedy algorithms

Solving the coin-changing problem

Applying the Huffman coding algorithm

Divide and conquer algorithms

Solving selection problems

Solving matrix multiplication calculations

Dynamic programming

Fibonacci numbers

Dynamic programming and the coin-change problem

Brute-force algorithms

Brute-force search and sort

Strengths and weaknesses of brute-force algorithms

Randomized algorithms

Rаndоm algorіthm classification

Random number generators

Applications of randomized algorithms

Backtracking algorithms

Arranging furniture in a new house

Playing tic-tac-toe

Summary

QA section

Further reading

Other Books You May Enjoy

Leave a review - let other readers know what you think

Preface

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. 

Who this book is for

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.

What this book covers

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 the most out of this book

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)

Download the example code files

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 SUPPORT tab.

Click on Code Downloads & Errata.

Enter the name of the book in the Search box 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 at https://github.com/PacktPublishing/CPP-Data-Structures-and-Algorithms. We also have other code bundles from our rich catalog of books and videos available at https://github.com/PacktPublishing/. Check them out!

Download the color images

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.

Conventions used

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

    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 * Next;

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

};

Any command-line input or output is written as follows:

g++ simple.cpp

Bold: 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.

Warnings or important notes appear like this.

Tips and tricks appear like this.

Get in touch

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.

Reviews

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.

Learning Data Structures and Algorithms in C++

In this first chapter, we are going to build the solid foundations so we can go through the following chapters easily. The topics we are going to discuss in this chapter are:

Creating, building, and running a simple C++ program

Constructing an abstract data type to make a user-defined data type

Leveraging the code with C++ templates and the Standard Template Library (STL)

Analyzing the complexity of algorithms to measure the performance of the code

Technical requirements

To follow along with this chapter including the source code, we require the following:

A 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 will find the code files on GitHub—https://github.com/PacktPublishing/CPP-Data-Structures-and-Algorithms

Introduction to basic C++

Before we go through the data structures and algorithms in C++, we need to have a strong, fundamental understanding of the language itself. In this section, we are going to build a simple program, build it, and then run it. We are also going to discuss the fundamental and advanced data types, and before we move on to algorithm analysis, we are going to discuss control flow in this section.

Creating your first code in C++

In C++, the code is executed from the main() function first. The function itself is a collection of statements to perform a specific task. As a result of this, a program in C++ has to contain at least one function named main(). The following code is the simplest program in C++ that will be successfully compiled and run:

    int main()

    {

      return 0;

    }

Suppose the preceding code is saved as a simple.cpp file. We can compile the code using the g++ compiler by running the following compiling command on the console from the active directory where the simple.cpp file is placed:

g++ simple.cpp

If no error message appears, the output file will be generated automatically. If we run the preceding compiling command on a Windows console, we will get a file named a.exe. However, if we run the command on Bash shells, such as Linux or macOS, we will get a file named a.out.

We can specify the output file name using the -o option followed by the desired filename. For instance, the following compiling command will produce the output file named simple.out:

g++ simple.cpp -o simple.out

Indeed, when we run the output file (by typing a and then pressing Enter on a Windows console or by typing ./a.out and then pressing Enter on Bash shell), we won't see anything on the console window. This is because we don't print anything to the console yet. To make our simple.cpp file meaningful, let's refactor the code so that it can receive the input data from the user and then print the data back to the user. The refactored code should look as follows:

    // in_out.cpp

    #include

    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;

  }

As we can see in the preceding code, we appended several lines of code so that the program can print to the console and the user can give an input to the program. Initially, the