Datastructure through C++

Data structure is the science of storing data in a computer so that it can be used efficiently. Often a carefully chosen data structure will allow a more efficient algorithm to be used. The choice of the data structure often begins from the choice of an abstract data structure. A well-designed data structure allows a variety of critical operations to be performed on using as little resources, both execution time and memory space, as possible.

Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to certain tasks. For example, B-trees are particularly well-suited for implementation of databases, while routing tables rely on networks of machines to function.

In the design of many types of programs, the choice of data structures is a primary design consideration, as experience in building large systems has shown that the difficulty of implementation and the quality and performance of the final result depends heavily on choosing the best data structure. After the data structures are chosen, the algorithms to be used often become relatively obvious. Sometimes things work in the opposite direction – data structures are chosen because certain key tasks have algorithms that work best with particular data structures. In either case, the choice of appropriate data structures is crucial.

This insight has given rise to many formalized design methods and programming languages in which data structures, rather than algorithms, are the key organizing factor. Most languages feature some sort of module system, allowing data structures to be safely reused in different applications by hiding their verified implementation details behind controlled interfaces. Object-oriented programming languages such as C++ and Java in particular use objects for this purpose.

Since data structures are so crucial to professional programs, many of them enjoy extensive support in standard libraries of modern programming languages and environments, such as C++’s Standard Template Library, the Java API, and the Microsoft .NET framework.

The above discussion aims at only making you understand how critical the proper understanding of data structures is. The implementation and demonstration of various data structures has been done by either C or C++.

Data Structure Through C++

Module – 1: Preliminaries

Programming in C++

  • Functions and Parameters
  • Templates
  • References
  • Const. References
  • Recursion
  • Dynamic Memory Allocation
  • Classes
  • Exception handling
  • Testing and debugging

Programming Performance

  • Space complexity
  • Time Complexity
  • Asymptotic Notations
  • Big Oh – O
  • Omega – W
  • Theta – Q
  • Little Oh – o
  • Performance measurement
Top
Module – 2: Data Structures

Data Representation

  • Introduction
  • Linear Lists
  • Formula-Based Representation
  • Linked Representation
  • Indirect Addressing
  • Simulating Pointers
  • Application

Arrays and Matrices

  • Arrays
  • Matrices
  • Special Matrices
  • Diagonal Matrices
  • Tridiagonal Matrix
  • Triangular Matrices
  • Symmetric Matrices
  • Spars Matrices

Stacks

  • The Abstract Data Type
  • Derived Classes and Inheritance
  • Formula-Based Representation
  • Linked Representation
  • Applications

Queues

  • The Abstract Data Type
  • Formula-Based Representation
  • Linked Representation
  • Applications

Skip Lists and Hashing

  • Dictionaries
  • Linear List Representation
  • Skip List Representation
  • Hash Table Representation
  • An Application – Text Compression

Binary and Other Trees

  • Tree
  • Binary Trees
  • Properties of Binary Trees
  • Common binary-tree Operations
  • Binary Tree traversal
  • The ADT BinaryTree
  • The Class BinaryTree
  • ADT and class Extensions
  • Applications

Priority Queues

  • Linear Lists
  • Heaps
  • Leftist Trees
  • Applications

Tournament Trees

  • The ADT WinnerTree
  • The Class WinnerTree
  • Loser Trees
  • Application

Search Trees

  • Binary Search Trees
  • AVL Trees
  • Red-Black Tree
  • B-Trees
  • Applications

Graphs

  • Definitions
  • Applications
  • Properties
  • The ADTs Graph and Diagraph
  • Representation of Networks
  • Class Definitions
  • Graph Iterators
  • Language Features
  • Graphical Search Methods
  • Advanced Applications
Top

Comments are closed.