
Data Structure and Algorithms Using C++
Description
Alles über E-Books | Antworten auf Fragen rund um E-Books, Kopierschutz und Dateiformate finden Sie in unserem Info- & Hilfebereich.
More details
Other editions
Additional editions


Persons
Sachi Nandan Mohanty received his PhD from IIT Kharagpur in 2015. He has recently joined as an associate professor in the Department of Computer Science & Engineering at ICFAI Foundation for Higher Education Hyderabad. His research areas include data mining, big data analysis, cognitive science, fuzzy decision-making, brain-computer interface, and computational intelligence. He has published 20 SCI journal articles and has authored 3 as well as edited 4 books.
Pabitra Kumar Tripathy has completed his MTech in computer science at Berhampur University. He is currently pursuing his PhD in computer science and engineering at Biju Patnaik University of Technology. He has been teaching for 15 years and is currently working as the Head of Department Computer Science in KALAM Institute of Technology, Odisha. He has also published 3 programming books for technical students.
Content
Preface xt
1 Introduction to Data Structure 1
2 Review of Concepts of 'C++' 15
3 Sparse Matrix 49
4 Concepts of Class 59
5 Stack 91
6 Queue 129
7 Linked List 167
8 TREE 249
9 Graph 295
10 Searching and Sorting 349
11 Hashing 391
Index 397
1
Introduction to Data Structure
1.1 Definition and Use of Data Structure
Data structure is the representation of the logical relationship existing between individual elements of data. In other words the data structure is a way of organizing all data items that considers not only the elements stored but also their relationship to each other.
Data structure specifies
- Organization of data
- Accessing methods
- Degree of associativity
- Processing alternatives for information
The data structures are the building blocks of a program and hence the selection of a particular data structure stresses on
- The data structures must be rich enough in structure to reflect the relationship existing between the data, and
- The structure should be simple so that we can process data effectively whenever required.
In mathematically Algorithm + Data Structure = Program
Finally we can also define the data structure as the "Logical and mathematical model of a particular organization of data"
1.2 Types of Data Structure
Data structure can be broadly classified into two categories as Linear and Non-Linear
Linear Data Structures
In linear data structures, values are arranged in linear fashion. Arrays, linked lists, stacks, and queues are the examples of linear data structures in which values are stored in a sequence.
Non-Linear Data Structure
This type is opposite to linear. The data values in this structure are not arranged in order. Tree, graph, table, and sets are the examples of nonlinear data structure.
Operations Performed in Data Structure
In data structure we can perform the operations like
- Traversing
- Insertion
- Deletion
- Merging
- Sorting
- Searching
1.3 Algorithm
The step by step procedure to solve a problem is known as the ALGORITHM. An algorithm is a well-organized, pre-arranged, and defined computational module that receives some values or set of values as input and provides a single or set of values as out put. These well-defined computational steps are arranged in sequence, which processes the given input into output.
An algorithm is said to be accurate and truthful only when it provides the exact wanted output.
The efficiency of an algorithm depends on the time and space complexities. The complexity of an algorithm is the function which gives the running time and/or space in terms of the input size.
Steps Required to Develop an Algorithm
- Finding a method for solving a problem. Every step of an algorithm should be defined in a precise and in a clear manner. Pseudo code is also used to describe an algorithm.
- The next step is to validate the algorithm. This step includes all the steps in our algorithm and should be done manually by giving the required input, perform the required steps including in our algorithm and should get the required amount of output in a finite amount of time.
- Finally implement the algorithm in terms of programming language.
Mathematical Notations and Functions
- ? Floor and Ceiling Functions
- Floor function returns the greatest integer that does not exceed the number.
- Ceiling function returns the least integer that is not less than the number.
- ? Remainder Function
To find the remainder "mod" function is being used as
- ? To find the Integer and Absolute value of a number
INT(5.34) = 5 This statement returns the integer part of the number
INT(- 6.45) = 6 This statement returns the absolute as well as the integer portion of the number
- ? Summation Symbol
To add a series of number as a1+ a2 + a3 +............+ an the symbol S is used
- ? Factorial of a Number
The product of the positive integers from 1 to n is known as the factorial of n and it is denoted as n!.
Algorithemic Notations
While writing the algorithm the comments are provided with in [ ].
The assignment should use the symbol ": =" instead of "="
For Input use Read : variable name
For output use write : message/variable name
The control structures can also be allowed to use inside an algorithm but their way of approaching will be some what different as
Simple If
If condition, then: Statements [end of if structure] If...else
If condition, then: Statements Else : Statements [end of if structure] If...else ladder
If condition1, then: Statements Else If condition2, then: Statements Else If condition3, then: Statements ................ ................ ................ Else If conditionN, then: Statements Else: Statements [end of if structure] LOOPING CONSTRUCT
Repeat for var = start_value to end_value by step_value Statements [end of loop] Repeat while condition: Statements [end of loop] Ex : repeat for I = 1 to 10 by 2 Write: i [end of loop] OUTPUT
1 3 5 7 9 1.4 Complexity of an Algorithm
The complexity of programs can be judged by criteria such as whether it satisfies the original specification task, whether the code is readable. These factors affect the computing time and storage requirement of the program.
Space Complexity
The space complexity of a program is the amount of memory it needs to run to completion. The space needed by a program is the sum of the following components:
- A fixed part that includes space for the code, space for simple variables and fixed size component variables, space for constants, etc.
- A variable part that consists of the space needed by component variables whose size is dependent on the particular problem instance being solved, and the stack space used by recursive procedures.
Time Complexity
The time complexity of a program is the amount of computer time it needs to run to completion. The time complexity is of two types such as
- Compilation time
- Runtime
The amount of time taken by the compiler to compile an algorithm is known as compilation time. During compilation time it does not calculate for the executable statements, it calculates only the declaration statements and checks for any syntax and semantic errors.
The run time depends on the size of an algorithm. If the number of instructions in an algorithm is large, then the run time is also large, and if the number of instructions in an algorithm is small, then the time for executing the program is also small. The runtime is calculated for executable statements and not for declaration statements.
Suppose space is fixed for one algorithm then only run time will be considered for obtaining the complexity of algorithm, these are
- Best case
- Worst case
- Average case
Best Case
Generally, most of the algorithms behave sometimes in best case. In this case, algorithm searches the element for the first time by itself.
For example: In linear search, if it finds the element for the first time by itself, then it behaves as the best case. Best case takes shortest time to execute, as it causes the algorithms to do the least amount of work.
Worst Case
In worst case, we find the element at the end or when searching of elements fails. This could involve comparing the key to each list value for a total of N comparisons.
For example in linear search suppose the element for which algorithm is searching is the last element of array or it is not available in array then algorithm behaves as worst case.
Average Case
Analyzing the average case behavior algorithm is a little bit complex than the best case and worst case. Here, we take the probability with a list of data. Average case of algorithm should be the average number of steps but since data can be at any place, so finding exact behavior of algorithm is difficult. As the volume of data increases, the average case of algorithm behaves like the worst case of algorithm.
1.5 Efficiency of an Algorithm
Efficiency of an algorithm can be determined by measuring the time, space, and amount of resources it uses for executing the program. The amount of time taken by an algorithm can be calculated by finding the number of steps the algorithm executes, while the space refers to the number of units it requires for memory storage.
1.6 Asymptotic Notations
The asymptotic notations are the symbols which are used to solve the different algorithms and the notations are
- Big Oh Notation (O)
- Little Oh Notation (o)
- Omega Notation (O)
- Theta Notation (?)
Big Oh (O) Notation
This Notation gives the upper bound for a function to within a constant factor. We write f(n) = O(g(n)) if there are +ve constants n0 and C such that to the right of n0, the value of f(n) always lies on or below Cg(n)
Omega Notation (O)
This notation gives a lower bound for a function to with in a constant factor. We write f(n) = Og(n) if there are positive constants n0 and C such that to the right of n0 the value of f(n) always lies on or above...
System requirements
File format: ePUB
Copy protection: Adobe-DRM (Digital Rights Management)
System requirements:
- Computer (Windows; MacOS X; Linux): Install the free reader Adobe Digital Editions prior to download (see eBook Help).
- Tablet/smartphone (Android; iOS): Install the free app Adobe Digital Editions or the app PocketBook before downloading (see eBook Help).
- E-reader: Bookeen, Kobo, Pocketbook, Sony, Tolino and many more (not Kindle).
The file format ePub works well for novels and non-fiction books – i.e., „flowing” text without complex layout. On an e-reader or smartphone, line and page breaks automatically adjust to fit the small displays.
This eBook uses Adobe-DRM, a „hard” copy protection. If the necessary requirements are not met, unfortunately you will not be able to open the eBook. You will therefore need to prepare your reading hardware before downloading.
Please note: We strongly recommend that you authorise using your personal Adobe ID after installation of any reading software.
For more information, see our ebook Help page.