Introduction to datastructures presentation

Data Structures • Data Structure is a method of collecting and organizing large amount of data more efficiently so that any operation on that data becomes easy. • Any data structure is designed to organize data to suit a specific purpose so that it can be accessed and worked with in appropiate ways • Ex: Vijay Age String datatype Integer datatypes

Important terms of a data structure: • Interface:Each data structure has an interface.Interface represents the set of operations that a data structure supports.An interface only provides list of supported operations,type of parameters they can accept and return type of these operations • Implementation:It provides internal representation of a data structure,definition of algorithms used in operations of DS.

Characteristics of a Data Structure: • Correctness:DS implementation should implement its interface correctly • Time complexity:Running time or execution time of operations of DS must be as small as possible. • Space complexity:Memory usage of DS operation should be as little as possible

Applications of DS: • Data Search • Processor speed • Multiple requests

Uses of DS: • DS is almost used in almost every program • It helps to write efficient code,structures the code and solve problems • Data can be maintained more easily by encouraging a better design or implementation • Used to store,manipulate and arrange data • It can be processed using some algorithm

Primitive DS: • These are the basic DS that directly operate upon the machine instructions • These are used to represent single value and have different representations on different computers • It is basic DS which is available in most of programming language • It includes integer,float,character and boolean DS

int: • Description: Represents integer numbers. • Example: int x = 10; float: • Description: Represents floating-point numbers (real numbers with a fractional part). • Example: float y = 3.14;

• Description: Represents double-precision floating-point numbers with more precision than float. • Example: double z = 2.71828; char: • Description: Represents a single character. • Example: char ch = 'A'; double:

boolean: • Description: Represents boolean values (true or false). • Example: bool isTrue = true; Pointers: • Description: Stores the memory address of another variable. • Example: int* ptr = &x;

Non-primitive DS: • These are more complicated data structures and are derived from primitive data structures • They emphasize on grouping of same or different data items with relationship between each item Non-Primitive Linear DS Non-Linear DS

Linear data structures: • Linear data structures are fundamental data structures where data elements are organized in a sequential manner, with each element connected to its previous and next elements. • The main characteristic of linear data structures is that they can be traversed in a single sequential manner from the beginning to the end or vice versa. • It includes arrays,linked list,stack and queue data structures

Arrays: • Arrays are collections of elements stored at contiguous memory locations. • Elements in an array are accessed using their indices. Arrays have a fixed size and allow random access to elements. Linked Lists: • Linked lists are collections of nodes where each node contains a data element and a reference (or pointer) to the next node in the sequence. • Linked lists come in various forms such as singly linked lists, doubly linked lists, and circular linked lists.

Stacks: • Stacks are abstract data types that follow the Last In, First Out (LIFO) principle. • Elements are added and removed from the top of the stack. • Common stack operations include push (adding an element to the top of the stack) and pop (removing the top element from the stack). Queues: • Queues are abstract data types that follow the First In, First Out (FIFO) principle. • Elements are added to the rear (enqueue) and removed from the front (dequeue) of the queue. • Other common operations include peek (viewing the front element without removing it) and isEmpty (checking if the queue is empty).

Non-Linear data structure: • Non-linear data structures are those in which the elements are not arranged in a sequential manner. • Unlike linear data structures, non-linear data structures allow elements to be connected in a hierarchical or non-sequential manner. • It includes trees and graphs

Trees: • Trees are hierarchical data structures consisting of nodes connected by edges. • Each node has a parent-child relationship, where a node can have zero or more child nodes. • Trees are widely used for representing hierarchical data such as directory structures, organization charts, and XML/HTML documents.

Graphs: • Graphs are data structures consisting of vertices (nodes) and edges (connections) between them. • Unlike trees, graphs do not have a strict hierarchical structure and can have cycles. • Graphs can represent various relationships and connections between objects, making them suitable for modeling networks, social connections, transportation systems, and more.

Datatypes • A data type refers to a set of values and the operations that can be performed on those values in a programming language. • It defines how a particular type of data is represented in memory and what operations can be performed on that data. • Data types in programming languages include primitive types (e.g., integers, floating-point numbers, characters) and composite types (e.g., arrays, structures, classes). Abstract datatypes • An abstract data type refers to a mathematical model for a data type, which specifies a set of operations without specifying their implementation. • It defines a set of operations that can be performed on the data without specifying how those operations are implemented. • ADTs encapsulate data with a set of operations, hiding the implementation details from the user. Users interact with ADTs through a well-defined interface. • Examples of ADTs include stacks, queues, lists, trees, and graphs. These ADTs specify operations like insertion, deletion, traversal, and searching, but do not dictate how these operations are implemented.

Abstract Data Types • ADT is a set of data values and associated operations that are independent of implementation • The strength of ADT is its implementation and is hidden from the user • An ADT consists of two parts 1. Declaration of Data 2. Declaration of Operation Commonly used ADTs are Linked lists,stacks,queues,trees

Operations on linear data structures: • Traversal:Visit every part of data structure • Search:Traversal through the data structure for a given element • Insertion:Adding new elements to data structure • Deletion:Removing an element from data structure • Sorting:Rearranging elements in some type of order(increasing or decreasing) • Merging:Combining two structures into one.

C++ classes: • In C++, classes are a fundamental building block of object-oriented programming (OOP). • They serve as a blueprint for creating objects, which are instances of those classes

• Syntax: class class-name { datatype var1; datatype var2; ----------------- datatype varN; method1(); method2(); ---------------------- methodN(); }

#include <iostream> using namespace std; // Define a class called 'Car' class Car { // Access specifier 'private' private: // Private member variables string brand; string model; int year; -------------- }

Arrays • It is linear datastructure to store homogeneous elements at contiguous locations and provides direct access to any of its elements • Size of an array should be provided before storing data • Most of data structures use arrays to implement their algorithms • Element:Each item stored in an array is called an element • Index:Each location of an element in an array has a numerical index,which is used to identify element

Syntax: datatype Arrayname[sizeofArray]; Example: int scores[10]={79,80,81,87,90,74,85,65,76,82}; Refer program

Advantages of 1D Arrays • Efficient Data Storage • Random Access • Ease of Use • Memory Efficiency

Disadvantages of 1D Arrays • Fixed Size • Linear Search • Contiguous Memory Requirement • Limited Functionality

2-D Arrays and N-D Arrays • A two-dimensional array is a list of one-dimensional arrays • A multi-dimensional array is an array of arrays • 2-D are mostly used to store data in tabular manner Syntax: data_type array_name[rows][columns];

Example: int matrix[3][4] = { {1, 2, 3, 4}, // Row 0 {5, 6, 7, 8}, // Row 1 {9, 10, 11, 12} // Row 2 }; If you initialize only some elements of the array, the remaining elements will be initialized to zero Refer program

Advantages Disadvantages • Structured Data Storage • Efficient Access • Memory contiguity • Fixed Size • Memory Overhead • Rectangular Structure • Complexity in Insertion/Deletion

N-dimensional arrays: • In C++, you can declare arrays with more than two dimensions, commonly referred to as N-dimensional arrays. • The syntax for declaring an N-dimensional array is an extension of the syntax for 2-D arrays. • Syntax: data_type array_name[dim1_size][dim2_size]...[dimN_size]; Total number of elements=No.of rows*No.of columns

Special matrices: • Square matrix:No. of rows=No. of columns • Identity matrix:All the elements of the diagonal are one and remaining zero • Diagonal matrix:All the elements of the diagonal are numbers and remaining zero • Symmetric matrix:Matrix which is equal to its transpose(R↔C) • Triangular matrix: 1. Lower Triangular matrix - A matrix is called so when if all entries above the main diagonal are zero 2. Upper Traiangular matrix-A matrix is called so when if all entries below the main diagonal are zero

Linked List representation • A linked list is a combination of interconnected rows joined in a linear manner • In linked list representation,each node consists of four components 1. Rows:It stores index of row 2. Column:It stores index of column 3. Value:This variable consists of actual non-zero value being stored 4. Next node:It is a pointer to store the address of next connected node

Introduction to datastructures presentation

Introduction to datastructures presentation

More Related Content

Similar to Introduction to datastructures presentation

More from krishkiran2408

Recently uploaded

Introduction to datastructures presentation