[ Home Page ] [ Back ] [ Content of Contributions ] [ Movement: Green Leaf World ]
------------------------------------------------------------------------------------------------------------------
Prerequisites
Before starting data structure, we must have a little bit knowledge regarding follows:
- Value: A value can be again classified as,
- Numerical Value
- Integer
- Unsigned : your age, weight are the example of unsigned values.
- Signed : Temperature is an example of signed value.
- Real : Average weight of a set of students.
- Character Value: Often we use M/F, to identify the sense of "Male"/ "female"
- Text Value : Your name is a text, i.e. set of characters.
- etc.
- Data: A set of meaningful values is called data. It is very interesting to realize the term "meaningful". Meaning means sense. When a sense(meaning) is associated with a value / set of values, it becomes data. What do you mean by 20? possibly nothing. What do you mean by 20kilogram? possibly nothing. What do mean by the statement "Bring 20kilogram rice"? Now you will understand that, 20kilogram is the measure of the rice. Thus, the value 20 is a data in the last statement but it is not a data in the first two statements.
- Variable: It is an identifier of the value, where the value may be changed over the time/ space.
- Constant : It is an identifier of the value, where the value should not change over the time/ space.
- Domain: A set of values that defines the boundary of a variable. Consider the example, S= { t; t is an integer with 0<t<10 }, here Domain of S is the set { 1, 2, 3, 4, 5, 6, 7, 8, 9 }, often expressed as D(S).
- Operation: An expression with single operator, e.g. 10+20.
- Function: An expression with one/ more operators, e.g. 10+20, 4+9+5, (2*t) + 5. You must remember, every operation is a function but every function is not an operation.
- Memory: Simply, a set of electronic cells, where we can represent ( read store for simplicity ) our values. But, as a person of computer science we must differentiate between the terms store and represent. Firstly, take a packet of milk and keep(store) it in a refrigerator. Secondly, consider your birthday celebration moment. Can you keep(store) it for future use like the milk? No it is not possible, but we can keep the moment in the form of a photo. Is there any difference between this two kind of keeping? Certainly yes. In the first one (milk), we do not need to transform the milk, but in latter, we need to transform the real bodies into something else. Camera can not store you as like milk in the refrigerator. Camera can represent you as an image, that can be viewed along with imagination power of your brain to realize what was happened on your birthday. So, in capturing time a transformation (encoding) is required. Similarly, when you will view the picture reverse transformation(decoding) is also required. We need to perform Write(Store or represent) & Read(Retrieve) from memory.
- Pointer: An unsigned integer used to identify a memory cell is referred as the address of the memory cell. A variable that can store an address is called pointer variable or simply pointer.
- Structure: In C programming, it is often used to represent a data with heterogeneous values, like date, as date contains three values {Day, Month, Year}. This trio together may be called structure of date.
- Algorithm
Definition of Data Structure
Data structure can be defined as, a mathematical model to represent data in the memory such that, it can be accessed efficiently whenever required it.
In this subject, we must concentrate on,
- Data & its behavior: Behavior of the data defines a set of functions applicable on it.
- Structure of data (or format of data): Structure specifies how to represent data.
- Access method (or algorithm): There are two views, low level view & programmers(high level) view. In low level view(or memory view), it can be treated as the mapping function from data model to the memory and vice versa. In high level view(or logical view), it can be treated as set of applicable methods or algorithms.
Characteristic of Data Structures
- Linear/ Non-Linear: It defines the correlation among the data. It can be expressed linearly or non linearly.
- Static/ Dynamic: It defines the allocation of the memory over the time. In static allocation, the size of the allocated memory cannot be altered after allocation(whatever in predefined or run time) but in the dynamic allocation memory can be allocated/ de-allocated/ re-allocated as per the requirement over the time. New data requires allocation, but deletion of a data requires de-allocation(release) of the memory cell(s).
- Contiguous/ Non-Contiguous: In static allocation a continuous block of memory is allocated but in dynamic allocation it is not possible, so, memory is allocated as cluster, where each cluster is a small block of continuous memory.
List of Data Structures
- Primitive Data Structures
- Array
- Linked List
- Others
- Stack
- Queue
- Tree
