C++ Data Structures and Algorithms Learn how to write efficient code to build scalable and robust applications in C++ (Wisnu Anggoro) (z-library.sk, 1lib.sk, z-lib.sk)

📄 File Format: PDF

💾 File Size: 4.8 MB

📖 Read Online ⬇️ Download

Registered users can read the full content for free

Register as a Gaohf Library member to read the complete e-book online for free and enjoy a better reading experience.

📄 Page 1

(This page has no text content)

📄 Page 2

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

📄 Page 3

Wisnu Anggoro BIRMINGHAM - MUMBAI

📄 Page 4

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

📄 Page 5

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.

📄 Page 6

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

📄 Page 7

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.PacktP ub.com and as a print book customer, you are entitled to a discount on the eBook copy. Get in touch with us at service@packtpub.com 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.

📄 Page 8

Contributors

📄 Page 9

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.

📄 Page 10

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.

📄 Page 11

Packt is searching for authors like you If you're interested in becoming an author for Packt, please visit authors.packtpub.c om 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.

📄 Page 12

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 1. 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

📄 Page 13

Recursive method Amortized analysis Summary QA section Further reading 2. 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 3. 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

📄 Page 14

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 4. 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 5. 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

📄 Page 15

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 6. 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 7. 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

📄 Page 16

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 8. 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 9. 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

📄 Page 17

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

📄 Page 18

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.

📄 Page 19

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.

📄 Page 20

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