Unit 1 introduction to data structure

Introduction to
Data Structures
Kalyani Neve
Asst.Prof.
GHRIBM,Jalgaon

 Data Concepts
 Data types, ADT (Abstract Data Type)
 Types of data structure
 Algorithm Analysis: Space complexity, Time complexity
 Asymptotic Notations (Big O, Omega, Theta), Linear
data structure
 Array as linear data structure
 Representation of array in memory, Strings, structure
and pointer in C/C++

Data Structure:
The logical or mathematical model of a particular organization
of data is called a data structure.
Data structure mainly specifies the following four things:
1. Organization of data
2. Accessing Methods
3. Degree of associativity
4. Processing alternatives for information

Types of Data Structure :
Data structure are normally divided into two categories
1. Primitive Data structure
2. Non-Primitive Data structure
Chart of Data structure is given on next slide.

Data Structure
Primitive DS Non-Primitive DS
int float pointer char Array Lists Files
Linear list
Non Linear
list
Stack Queues Graphs Trees

Data Structure Operations :
1. Traversing
2. Searching
3. Inserting
4. Deleting
5. Sorting
6. Merging

Algorithm Analysis:Algorithm Analysis:
Space complexitySpace complexity
Space complexity of a program is the amount of memory that it needs to run to
completion
Includes, Instruction space
Space for simple variables
Space for constants; etc.
Include, Dynamically created variables
Recursion stack space

Time complexityTime complexity
Time complexity of a program is the amount of computer time that it needs to
run to completion
 Dependent on
• Machine speed
• Compiler code generation
• Number of inputs
• Number of executed statements
 Count the number of operations the program perform
 Require to divide the program into distinct steps

Asymptotic Notation:Asymptotic Notation:
To choose the best algorithm, we need to check efficiency of
each
algorithm. The efficiency can be measured by computing time
complexity of each algorithm. Asymptotic notation is a shorthand
way to represent the time complexity.
There are three kinds of mathematical notation which are very
useful for this kind of analysis.
1. Big oh (O) Notation
2. Omega (Ω) Notation
3. Theta (Ө) Notation

Linear data structure :
Array as linear data structure
An array can be defined as an infinite collection of homogeneous
(similar type) elements.
Arrays are always stored in consecutive memory locations.
Datatype var_name [Expression];
E.g.. int num[10];
Algorithms for Insert, Delete and Display of elements in arrays
are given below :

INSERT(A, N, K, ITEM)
Here A is a array with N elements and k is a positive integer
such that k<=N. This algo. Inserts an elements ITEM into the
kth position in A.
1. [Initialize counter]
Set J := N
2. Repeat step 3 and 4 while J>=k
3. [Move Jth element downward]
Set A[j+1] := A[J]
2. [Decrease counter]
Set J := J-1
[End of step2 loop]
5. [Insert element]
Set A[k] := ITEM
6. [Reset N]
Set N := N+1
6. Exit

DELETE(A, N, k, ITEM)
Here A is a linear array with N elements and k is a positive
integer such that k<=N. This algorithm deleted the kth element
from A.
1. Set ITEM := A[k]
2. Repeat for J=k to N-1
[Move J + 1st
element upward]
Set A[J] := A[J+1]
[End of loop.]
3. [Reset the number N of elements in A]
Set N := N-1
4. Exit

DISPLAY(A, k, LB, UB)
Here A is a linear array with lower bound LB and upper
bound UB. This algorithm traverses A applying an operation
PROCESS to each element of A.
1. [Initialize counter]
Set k := LB
2. Repeat steps 3 and 4 while k<=UB
3. [Visit element]
Apply PROCESS to A[k]
4. [Increase counter]
Set k := k +1
[End of step2 loop]
5. Exit

Representation of array in memory:
Suppose name of linear array is arr and it has 5 elements. Then its
elements are represented as:
arr
0 1 2 3 4
arr[0] arr[1] arr[2] arr[3] arr[4].
Since array elements are stored in contiguous memory locations,
the computer needs to not to know the address of every element
but the address of only first element. The address of first element
is called base address of array.

Review of Strings
Definition of Strings
 Generally speaking, a string is a sequence of characters
 Examples: “hello”, “high school”, “H2O”.
 Typical desirable operations on strings are:
 Concatenation: “high”+“school”=“highschool”
 Comparisons: “high”<“school” // alphabetical
 Finding/retrieving/modifying/deleting/inserting substrings in a
given string

Declaration of strings
 The following instructions are all equivalent. They declare x
to be an object of type string, and assign the string “high
school” to it:
 string x(“high school”);
 string x= “high school”;
 string x; x=“high school”;

Operations on strings (Concatenation)
 Let x and y be two strings
 To concatenate x and y, write: x+y
string x= “high”;
string y= “school”;
string z;
z=x+y;
cout<<“z=“<<z<<endl;
z =z+“ was fun”;
cout<<“z=“<<z<<endl;
Output:
z=highschool
z= highschool was fun

Comparison Operators for string Objects
 We can compare two strings x and y using the following
operators: ==, !=, <, <=, >, >=
 The comparison is alphabetical
 The outcome of each comparison is: true or false

Correspondence between the C library and
the C++ string Class
C Library Functions C++ string operators/methods
strcpy = (the assignment operator)
strcat += (assign+concat operator)
strcmp = =, !=, <, >, <=, >=
strchr, strstr
strrchr
.find( ) method
.rfind( ) method
strlen .size( ) or .length( ) methods

Structures :
A structure is a collection of simple variables. The variables in a
structure can be different types: Some can be int, float and so on.
The data items in a structure are called the members of the
structure.
A structure is a collection of data, while class is a collection of
both data and functions.

Declaring the structure :
The structure declaration tells how the structure is organized. It
specifies what members the structure will have.
struct part
{
int no;
float cost;
};
The Structure declaration serves only as a blueprint for the
creation of variables of type part.

Consider, following statement,
part part1;
Defines a variable, called part1, of type structure part.
This definition reserves space in memory for part1. This
memory holds all the members of part1.
Once a structure variables has been defined, its members can be
asses using something called the dot operator.
part1. no = 2222;

Pointers :
A pointer is an entity that refers to the memory addresses. It
specifies the number that gives a location in a memory. Each
pointer variable can point to specific data type such as int, char,
float etc.
Pointers are used for…….
1. Accessing array elements.
2. Passing arguments to function by address when modification
of formal arguments are to be reflected on actual arguments.
3. Passing arrays and string to functions.
4. Creating data structure like Link List,Trees,Graphs etc.
5. Allocate a memory dynamically.

Pointer Defination
Syntax :
Datatype * ptrvar,………….
e.g
int * ptr;
char *msg=“Hello”;
Int marks;
Ptr=&marks;
Dereferencing of Pointers
Int * ptr;
Int I;
i=10;
Ptr=&I;
Cout<<*ptr<<endl;

Unit 1 introduction to data structure

Recommended

More Related Content

What's hot (20)

Similar to Unit 1 introduction to data structure (20)

More from kalyanineve (7)

Recently uploaded (20)

Unit 1 introduction to data structure