AN INTRODUCTION TO DATA STRUCTURE #1
(by Md Farrukh Asif)
As we know, the Data Structure is the structural representation of logical relationships between data elements.
In other words, “A Data Structure is a
way of organizing data items by considering its relationship to each other”.
Data structure mainly specifies the
structured organization of data, by providing accessing methods with correct
degree of associativity.
Data structure affects the design of both the structural and functional aspects
of a program.
Algorithm + Data
Structure = Program
The representation of a particular data structure in a computer's memory is called a storage structure. It’s mean
that a data structure should be represented in such a way that it utilizes
maximum efficiency. The data structure can be shown in both main and auxiliary
memory of the computer. A storage structure representation in auxiliary memory
is often called a file structure.
Data Structure can be shown as below:
Data
Structure = Organized data + Operations.
Data structures are the building blocks of a program; here the selection of a particular data structure will help the programmer to design more efficient programs as the complexity and volume of the problems solved by the computer is steadily increasing day by day. The programmers have to strive hard to solve these problems. If the problem is analyzed and divided into subproblems, the task will be much easier i.e., divide, conquer, and combine.
A complex problem usually cannot be divided and programmed by a set of modules
unless its solution is structured or organized. This is because when we divide
the big problems into sub-problems, these sub-problems will be programmed by
different programmers or groups of programmers. But all the programmers should
follow a standard structural method so as to make easy and efficient
integration of these modules.
Such type of hierarchical structuring of
program modules and sub modules should not only reduce the complexity and
control the flow of program statements but also promote the proper structuring
of information. By choosing a particular structure (or data structure) for the
data items, certain data items become friends while others loses its relations.
PROGRAMMING
METHODOLOGIES
In the first stage, modeling, we try to
represent the problem using an appropriate mathematical model such as a graph,
tree etc. At this stage, the solution to the problem is an algorithm expressed
very informally.
At the next stage, the algorithm is written in
pseudo-language (or formal algorithm) that is, a mixture of any programming
language constructs and less formal English statements. The operations to be
performed on the various types of data become fixed.
In the final stage we choose an implementation
for each abstract data type and write the procedures for the various operations
on that type. The remaining in-formal statements in the pseudo-language
algorithm are replaced by (or any programming language) C/C++ code. Following
sections will discuss different programming methodologies to design a program.
ALGORITHM
Algorithm is a step-by-step finite sequence
of instruction to solve a well-defined computational program or problem.
In practice to solve any complex real
life problems, first we have to define the problems second step is to design
algorithm to solve.
Stepwise Refinement Techniques:
The initial version of the algorithm
will general statements (informal instructions).
Then we convert this informal algorithm into formal algorithm.
Refinement means is to convert an informal algorithm to a program. We must go through several stages of formalization until we arrive at a program --- whose meaning is formally defined by programming language manual --- is called stepwise refinement techniques.
ALGORITHM DESIGN
There are two ways to approach dynamic
programming problems, and that is bottom-up algorithms and top-down algorithms.
The easiest way to remember them is that bottom-up is
iterative and top-down is recursive.
The bottom-up approach is often
preferred because you don't have the risk of a stack overflow from recursion or
incur the space complexity from the call stack. However, if your language
implements tail-call optimization, then the recursive approach uses constant
space and its downsides no longer matter, and you can use either top-down or
bottom-up equally.
Top-Down Approach
Bottom-up takes the simplest/smallest
value(s) and builds up from these to reach the solution. This is often the most
intuitive way for people to solve problems when they are newer to programming.
To calculate a large fibonacci(n),
we start at the bottom which is 0 and 1 for the first two items in the
sequence. Then we repeatedly sum them together and build up to the solution.
Each iteration of the loop is solving a subproblem to calculate a given
Fibonacci number.
function fibonacci(n) {
let first = 0;
let second = 1;
for (let i = 2; i < n; i++) {
let temp = first + second;
first = second;
second = temp;
}
return first + second;
}
Bottom-Up Approach
For the top-down approach, we start by
considering the final solution and describe it as a combination of the results
of a series of subproblems. This is our recursive approach.
We start at the top (final state we
want) and express it as a recursive function. The recursive function then calls
itself with smaller input values until it reaches the base case. Once we reach
the base case, the results are returned through the functions calls, and we
combine the answers to build the final solution.
Since a Fibonacci number is just the sum
of the two Fibonacci numbers before it, if we solve this as a combination of
subproblems with the same logic for every Fibonacci number, we can then use
their results to calculate any fibonacci(n).
function fibonacci(n) {
// Base case
if (n < 2) {
return n
}
// Sum the two previous numbers to get the current value
return fibonacci(n - 1) + fibonacci(n - 2)
}
Optimization
In dynamic programming, we use
memorization to store the result of a subproblem so we don't repeat work when
they overlap. We incur additional space complexity to store the result of each
step so we can look up a result later without performing the computation again.
Memorization can be used for both bottom-up and top-down approaches.
STRUCTURED PROGRAMMING
STRUCTURED PROGRAMMING is a programming
style and this style of programming is known by several names:
Procedural
decomposition, Structured programming, etc. Structured
programming is not programming with structures but by using the following types of
code structures to write programs:
PROGRAMMING
METHODOLOGIES
1. Sequence of sequentially executed
statements
2. Conditional execution of statements
(i.e., “if” statements)
3. Looping or iteration (i.e., “for,
do...while, and while” statements)
4. Structured subroutine calls (i.e.,
functions) In particular, the following language usage is forbidden:
• “GoTo” statements
• “Break” or “continue” out of the
middle of loops
• Multiple exit points to a
function/procedure/subroutine (i.e., multiple “return” statements)
• Multiple entry points to a
function/procedure/subroutine/method
5 In this style of programming there is
a great risk that implementation details of many data structures have to be
shared between functions, and thus globally exposed. This in turn tempts other
functions to use these implementation details; thereby creating unwanted
dependencies between different parts of the program. The main disadvantage is
that all decisions made from the start of the project de-pends directly or
indirectly on the high-level specification of the application. It is a
well-known fact that this specification tends to change over a time. When that
happens, there is a great risk that large parts of the application need to be
rewritten.
CLASSIFICATION OF DATA STRUCTURE
Data structures are broadly divided into
two :
1.
Primitive data structures:
These
are the basic data structures and are directly operated upon by the machine
instructions, which is in a primitive level. They are integers, floating point
numbers, characters, string constants, pointers etc. These primitive data
structures are the basis for the discussion of more sophis-ticated
(non-primitive) data structures in this book. 10 PRINCIPLES OF DATA STRUCTURES
USING C AND C++
Non-primitive data structures: It is a more sophisticated data structure emphasis sizing on structuring of a group of homogeneous (same type) or heterogeneous (different type) data items. Array, list, files, linked list, trees and graphs fall in this category.
Basic operations on data structure are to create a (non-primitive) data structure; which is considered to be the first step of writing a program.
For example, in Pascal, C and C++, variables are created by using-declaration statements. int Variable; In C/C++, memory space is allocated for
the variable “Int Variable” when the above declaration statement executes. That
is a data structure is created.
*** See You Again ***
Share, Like and Comment
*********************
No comments:
Post a Comment