DATA STRUCTURE
NOTES
, 2
DATA STRUCTURE
Introduction
Algorithm:
An algorithm may be defined as a finite sequence of instructions each of which has a
clear meaning and can be performed with a finite amount of effort in a finite length
of time.
The algorithm word originated from the Arabic word “Algorism” which is linked to
the name of the Arabic mathematician AI Khwarizmi. He is considered to be the first
algorithm designer for adding numbers.
Structure and Properties of Algorithm:
An algorithm has the following structure
Input Step
Assignment Step
Decision Step
Repetitive Step
Output Step
An algorithm will be good with the following properties:
Finiteness: An algorithm must terminate after a finite number of steps.
Definiteness: The steps of the algorithm must be precisely defined or unambiguously
specified.
Generality: An algorithm must be generic enough to solve all problems of a particular
class.
Effectiveness: the operations of the algorithm must be basic enough to be put down
on pencil and paper. They should not be too complex to warrant writing another
algorithm for the operation.
Input-Output: The algorithm must have certain initial and precise inputs, and outputs
that may be generated both at its intermediate and final steps.
An algorithm does not enforce a language or mode for its expression but only
demands adherence to its properties.
Practical Algorithm Design Issues:
, 3
DATA STRUCTURE
To save time (Time Complexity): A program that runs faster is a better program.
To save space (Space Complexity): A program that saves space over a competing
program is considerable desirable.
Introduction to Data structures
In computer terms, a data structure is a Specific way to store and organize data in a
computer's memory so that these data can be used efficiently later. Data may be
arranged in many different ways such as the logical or mathematical model for a
particular organization of data is termed as a data structure. The variety of a
particular data model depends on the two factors –
Firstly, it must be loaded enough in structure to reflect the actual relationships of
the data with the real world object.
Secondly, the formation should be simple enough so that anyone can efficiently
process the data each time it is necessary.
Categories of Data Structure:
The data structure can be sub divided into major types:
Linear Data Structure
Non-linear Data Structure
Linear Data Structure:
A data structure is said to be linear if its elements combine to form any specific
order. There are basically two techniques of representing such linear structure within
memory.
First way is to provide the linear relationships among all the elements represented
by means of linear memory location. These linear structures are termed as arrays
. The second technique is to provide the linear relationship among all the elements
represented by using the concept of pointers or links. These linear structures are
termed as linked lists. The common examples of linear data structure are:
Arrays
Queues
Stacks
, 4
DATA STRUCTURE
Linked lists
Nonlinear Data Structure:
This structure is mostly used for representing data that contains a hierarchical
relationship among various elements. Examples of Non Linear Data Structures are
listed below:
Graphs
Family of trees and
Table of contents Tree:
In this case, data often contain a hierarchical relationship among various elements.
The data structure that reflects this relationship is termed as rooted tree graph or a
tree.
Graph: In this case, data sometimes hold a relationship between the pairs of
elements which is not necessarily following the hierarchical structure. Such data
structure is termed as a Graph.
Operations on Data Structures
The basic operations that are performed on data structures are as follows:
Insertion: Insertion means addition of a new data element in a data structure.
Deletion: Deletion means removal of a data element from a data structure if it is
found.
Searching: Searching involves searching for the specified data element in a data
structure.
Traversal: Traversal of a data structure means processing all the data elements
present in it.
Sorting: Arranging data elements of a data structure in a specified order is called
sorting.
Merging: Combining elements of two similar data structures to form a new data
structure of the same type, is called merging.
NOTES
, 2
DATA STRUCTURE
Introduction
Algorithm:
An algorithm may be defined as a finite sequence of instructions each of which has a
clear meaning and can be performed with a finite amount of effort in a finite length
of time.
The algorithm word originated from the Arabic word “Algorism” which is linked to
the name of the Arabic mathematician AI Khwarizmi. He is considered to be the first
algorithm designer for adding numbers.
Structure and Properties of Algorithm:
An algorithm has the following structure
Input Step
Assignment Step
Decision Step
Repetitive Step
Output Step
An algorithm will be good with the following properties:
Finiteness: An algorithm must terminate after a finite number of steps.
Definiteness: The steps of the algorithm must be precisely defined or unambiguously
specified.
Generality: An algorithm must be generic enough to solve all problems of a particular
class.
Effectiveness: the operations of the algorithm must be basic enough to be put down
on pencil and paper. They should not be too complex to warrant writing another
algorithm for the operation.
Input-Output: The algorithm must have certain initial and precise inputs, and outputs
that may be generated both at its intermediate and final steps.
An algorithm does not enforce a language or mode for its expression but only
demands adherence to its properties.
Practical Algorithm Design Issues:
, 3
DATA STRUCTURE
To save time (Time Complexity): A program that runs faster is a better program.
To save space (Space Complexity): A program that saves space over a competing
program is considerable desirable.
Introduction to Data structures
In computer terms, a data structure is a Specific way to store and organize data in a
computer's memory so that these data can be used efficiently later. Data may be
arranged in many different ways such as the logical or mathematical model for a
particular organization of data is termed as a data structure. The variety of a
particular data model depends on the two factors –
Firstly, it must be loaded enough in structure to reflect the actual relationships of
the data with the real world object.
Secondly, the formation should be simple enough so that anyone can efficiently
process the data each time it is necessary.
Categories of Data Structure:
The data structure can be sub divided into major types:
Linear Data Structure
Non-linear Data Structure
Linear Data Structure:
A data structure is said to be linear if its elements combine to form any specific
order. There are basically two techniques of representing such linear structure within
memory.
First way is to provide the linear relationships among all the elements represented
by means of linear memory location. These linear structures are termed as arrays
. The second technique is to provide the linear relationship among all the elements
represented by using the concept of pointers or links. These linear structures are
termed as linked lists. The common examples of linear data structure are:
Arrays
Queues
Stacks
, 4
DATA STRUCTURE
Linked lists
Nonlinear Data Structure:
This structure is mostly used for representing data that contains a hierarchical
relationship among various elements. Examples of Non Linear Data Structures are
listed below:
Graphs
Family of trees and
Table of contents Tree:
In this case, data often contain a hierarchical relationship among various elements.
The data structure that reflects this relationship is termed as rooted tree graph or a
tree.
Graph: In this case, data sometimes hold a relationship between the pairs of
elements which is not necessarily following the hierarchical structure. Such data
structure is termed as a Graph.
Operations on Data Structures
The basic operations that are performed on data structures are as follows:
Insertion: Insertion means addition of a new data element in a data structure.
Deletion: Deletion means removal of a data element from a data structure if it is
found.
Searching: Searching involves searching for the specified data element in a data
structure.
Traversal: Traversal of a data structure means processing all the data elements
present in it.
Sorting: Arranging data elements of a data structure in a specified order is called
sorting.
Merging: Combining elements of two similar data structures to form a new data
structure of the same type, is called merging.
