An introduction to Data Structures
Concept of Data & Data Items :
Data are raw values, happenings, observations, both numeric & non-numeric, capable of being processed by a computer into useful piece of information.
Data Types:
Data type refers to a set of data values having homogenous characteristics. Data is classified into mainly two types
Fundamental or basic
Derived or Composite
All constants, variable, functions & expressions belong to some data type. They are indicated at the time of declaration.
The Derived Data Types
Arrays
Structures
Unions
Funtions
Pointers
Files
All these data types are derived from the fundamental types
Data Organization:
Data in C language are organized into hierarchical structures. The individual data items are also called fields.
Related fields which may not necessarily be of homogenous type are called record.
Related records stored together are called file.
Fields at the bottom level and files at the top level represent the hierarchy.
A record is represented in terms of a Structure.
Records/Structures are generally identified through an unique field called primary key
Records are of fixed length
Data Structures : Is nothing but an organized collection of variables related to each other in various ways.
The relation between data items may be of 4 types
Sequence : In this type of relationship a definite set of components are included in the data structure. For example record of an employee.
Selection : This type of relationship is based on either/or yes/no. A selection has to be made from among two or more items.
Iteration : This relationship is based on repetition. For example in a choice among various courses offered by an university data like contents, class, section etc. can be repeated.
Optional : Relationship signifies inclusion/exclusion based on need. For example late fee, parking fee etc.
Data Structure Operations:
Creation
Insertion
Modification
Traversal
Searching
Sorting
Deletion
Merging
Coping
Concatenating
Splitting
Complexity of Data Structure Algorithms
An algorithm is nothing but a finite sequence of instructions each of which has a clear meaning and can be carried out with a finite amount of effort within a finite length of time.
The main aim of each type of algorithm is to find suitable trade-off between time and memory space.
Time & Space Trade-off : The problem of balancing arises as time and memory space are costly and there use has to be optimized. If sufficient storage space is available then optimum result can be obtained using an algorithm which uses more space and less time.
On the other hand if processing of a program requires huge memory, it would be economical to use an algorithm involving more time and less space.
Selecting the best Algorithm (Big ‘O’ Notation)
Generally the performance of an algorithm is divided into three categories.
Best-case Performance under an ideal condition
If an item to be searched is the first item in list
Worst-case Performance under the most unfavorable condition.
Item to be searched is either the last item or not present in the list
Average-case performance under the most portable conditions.
If an item has an equal chance to be found anywhere in the list
The Big ‘O’ Notation
It is a measure of efficiency of an algorithm. The number of steps required to carry out an operation, searching or sorting or merging depends on the number of elements in a list.
So the big ‘O’ for such an array will be
Number of elements (n) applied to any of the three methods mentioned in the previous slide.
Concept of Data & Data Items :
Data are raw values, happenings, observations, both numeric & non-numeric, capable of being processed by a computer into useful piece of information.
Data Types:
Data type refers to a set of data values having homogenous characteristics. Data is classified into mainly two types
Fundamental or basic
Derived or Composite
All constants, variable, functions & expressions belong to some data type. They are indicated at the time of declaration.
The Derived Data Types
Arrays
Structures
Unions
Funtions
Pointers
Files
All these data types are derived from the fundamental types
Data Organization:
Data in C language are organized into hierarchical structures. The individual data items are also called fields.
Related fields which may not necessarily be of homogenous type are called record.
Related records stored together are called file.
Fields at the bottom level and files at the top level represent the hierarchy.
A record is represented in terms of a Structure.
Records/Structures are generally identified through an unique field called primary key
Records are of fixed length
Data Structures : Is nothing but an organized collection of variables related to each other in various ways.
The relation between data items may be of 4 types
Sequence : In this type of relationship a definite set of components are included in the data structure. For example record of an employee.
Selection : This type of relationship is based on either/or yes/no. A selection has to be made from among two or more items.
Iteration : This relationship is based on repetition. For example in a choice among various courses offered by an university data like contents, class, section etc. can be repeated.
Optional : Relationship signifies inclusion/exclusion based on need. For example late fee, parking fee etc.
Data Structure Operations:
Creation
Insertion
Modification
Traversal
Searching
Sorting
Deletion
Merging
Coping
Concatenating
Splitting
Complexity of Data Structure Algorithms
An algorithm is nothing but a finite sequence of instructions each of which has a clear meaning and can be carried out with a finite amount of effort within a finite length of time.
The main aim of each type of algorithm is to find suitable trade-off between time and memory space.
Time & Space Trade-off : The problem of balancing arises as time and memory space are costly and there use has to be optimized. If sufficient storage space is available then optimum result can be obtained using an algorithm which uses more space and less time.
On the other hand if processing of a program requires huge memory, it would be economical to use an algorithm involving more time and less space.
Selecting the best Algorithm (Big ‘O’ Notation)
Generally the performance of an algorithm is divided into three categories.
Best-case Performance under an ideal condition
If an item to be searched is the first item in list
Worst-case Performance under the most unfavorable condition.
Item to be searched is either the last item or not present in the list
Average-case performance under the most portable conditions.
If an item has an equal chance to be found anywhere in the list
The Big ‘O’ Notation
It is a measure of efficiency of an algorithm. The number of steps required to carry out an operation, searching or sorting or merging depends on the number of elements in a list.
So the big ‘O’ for such an array will be
Number of elements (n) applied to any of the three methods mentioned in the previous slide.