Unit -1
BASIC CONCEPTS OF DATA REPRESENTATION
Abstracting data types: Fundamental and derived data types
Primitive data structures.
First of all we will see that what data structure is.
Q. What is data structure?
1. A data structure is a particular way of storing and organizing data inside computer memory (RAM).
2. In computer science a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.
3. E.g. arrays, linked-list, queues, stack, binary tree, and hash tables
4. Data structures are used in almost every program and software.
5. Data structures mainly specifies the four things:-
a. Organization of data
b. Accessing methods
c. Degree of Associativity &
d. Processing alternative for information.
Operation on data structure:
These data structure operation are given below :
1. Insertion : Adding a new data in data structure is known as insertion.
2. Deletion : removing the data from Data Structure is known as deletion.
3. Shorting : arranging the element in increasing or decreasing order is known as sorting.
4. Merging : combining the data of two different sorted files into a single sorted files is known as merging.
5. Searching : finding the location of data in data structure is known as searching.
6. Traversing : accessing each data elements exactly once in the data structure is known as traversing .
1. Insertion : Adding a new data in data structure is known as insertion.
2. Deletion : removing the data from Data Structure is known as deletion.
3. Shorting : arranging the element in increasing or decreasing order is known as sorting.
4. Merging : combining the data of two different sorted files into a single sorted files is known as merging.
5. Searching : finding the location of data in data structure is known as searching.
6. Traversing : accessing each data elements exactly once in the data structure is known as traversing .
Q. What are the areas where we can use data structure?
1. Compiler design
2. Simulation
3. Operating system
4. Data base application (DBMS)
5. Graphics
6. Statistical Analysis and package
7. Numerical Analysis
Abstracting data types: Fundamental and derived data types
1. The abstract data type is a kind of data type, whose behaviour is defined by a set of operations and set of values.
2. Like data type we can also use the “abstract” keyword, and we can also perform different operations.
3. The Abstract data type is made up of primitive data-types, but its logical operations are hidden.
4. Abstract data-type doesn’t specify, in memory how data will be organized and while performing operations what algorithms will be used.
5. Due to its implementation and independent view it is called as “abstract”. Abstraction is the process of providing only the essentials and hiding the details.
6. Examples of Abstract data-types are Stack, Queue, and List etc.
Some operations of those above mentioned ADT are: -
Stack: -
a. To check whether stack is full or notisFull()is used.
b. To check whether stack is empty or notisEmpty()is used.
c. To push x into the stack push(x) is used.
d. To delete one element from top of the stack pop()is used.
e. To get the top most element of the stackpeek() is used.
f. To get number of elements present into the stack size() is used.
Queue: -
a. To check whether queue is full or notisFull() is used.
b. To check whether queue is empty or notisEmpty() is used.
c. To add x into the queue at the rear endinsert(x) is used.
d. To delete one element from the front end of the queue delete() is used.
e. To get number of elements present into the queue size() is used.
List: -
a. To get number of elements present into the list size() is used.
b. To insert one element into the listinsert(x) is used.
c. To remove given element from the listremove (x) is used.
d. To get element at position i get(i) is used.
e. To replace x with y value replace(x, y) is used.
.What is array and types of array ?
Array definition :
- Array is a collection of same data type elements.
- Array are always stored in consecutive memory location.
- Array can be stored multiple value which can be refferenced by a single name .
- The size of an array is fixed .
- In array , random access is posible .
- It takes less searching time and more wastage memory .
- TYPES OF AN ARRAY :
- It is also known as one dimmentional array.
- It has only one subscript [ ] value .
(¡¡) Multidimentional array
- It is also known as two dimentional array.
- It has two subscript [ ] value .
Syntax : data_type array_name[10] ;
INITIALIZATION OF AN ARRAY :
There are two ways to initialize an array
(¡) Compile time initialization :
Syntax : data_type array_name[size] ={list of value} ;
For example : -
data_type array_name[10] ={3,5,2,7,9,1,8} ;
For example : -
data_type array_name[10] ={3,5,2,7,9,1,8} ;
(¡¡) Run time initialization :
Syntax : data_type array_name[size]=value;
For example : data_type array_name[]=10 ;
For example : data_type array_name[]=10 ;
What is linked list and it's type ?
Definition :
- Linked list is a linear data structure in which contiguous memory location is not required.
- The size of linked list is not fixed .
- It takes more searching time and more memory space .
There are mainly three types of linked list : -
(¡) Singly linked list :
- In singly linked list , each nodes are divided into two parts first part is known as info and second part is known as address part .
- Each nodes are connected to each other .
- Address part of the first node is connected to the info part in the second nodes .
- The last node has a reference to null. The entry point into a linked list is known as head of the list .
(¡¡) Doubly linked list :
- doubly linked list is a type of linked list in which , each nodes are divided into three parts : prev , info and next .
- The info part contains the data ,the prev part contains the address of the previous nodes and the next part contains next node .
- doubly linked list can be used in navigation systems where both front and back nevigation is required .
- It is also used in various application to implement undo and redo functionality .
- Circular linked list is similar to the singly linked list except that the last node points to the first node in the list .
- Circular linked list is a types of linked list in which the first elements points to the last elements and the last element points to the first elements.
- The circular linked list is used in round robin scheduling algorithms, multiplayer games repeats the songs in playlist to implement undo function .
What is stack and operation on stack ?
Definition :
- Stack is a linear data structure in which insertion and deletion is easy .
- Stack follows the principle of last in first out (LIFO) .
- It is also known as LIFO because the last added element will be the first to be removed from the stack .
- In stack , TOP is a variable which contains the position of top most element.
- If stack is empty then TOP == -1 .
- If stack is full then TOP ==N-1 .
OPERATION ON STACK : -
Stack performs two operation they are : -
(¡) . PUSH OPERATION :
- It is a process of adding new element to the top of the stack .
- Every push operation, TOP is incremented by one .
- If stack is full then you want to adding an element ,this condition is known as stack overflow .
(¡¡). POP OPERATION :
- It is a process of deleting an element to the top of the stack .
- Every pop operation, TOP is decremented by one .
- If stack is empty then you want to delete an element ,this condition is known as stack underflow .
What is queue and operation on queue ?
Wha is stack notation ?
There are mainly three stack notation :
(¡). Prefix notation :
- In this notation , operator is written before the operators .
- It is also known as polish notation .
- For example : +AB
(¡¡). Infix notation :
- In this notation , the operator is written in between the operands.
- For example :. A+B.
(¡¡¡). Postfix notation :
- It is also known as suffix notation .
- In this notation , operator is written after the operands .
primitiv vs non primitive data structure
PRIMITIVE DATA STRUCTURE : -
NON-PRIMITIVE DATA STRUCTURE : -
Differenc between stack and queue ?
* STACK : -
(¡¡). Pop operation : -
* QUEUE : -
(¡¡). De queue operation. : -
- It is a linear data structure.
- Stack follows the principle of last in first out (LIFO) .
- Stack perform two operation : -
- It is used to insert an element.
(¡¡). Pop operation : -
- It is used to delete an element.
* QUEUE : -
- It is also a linear data structure.
- Queue follows the principle of first in first out (FIFO) .
- Stack perform two operation : -
(¡¡). De queue operation. : -
- It is used to delete the element
.
Q. What is Fundamental Data-types and Derived Data-types?
Fundamental Data-types: -
1. The Data-type which are used by the programmer directly to store only one value as per requirement, and they are predefined known as Fundamental Data-types.
2. Integer type, Character type, and Float type data are used by programmer directly to store values.
3. Examples of Fundamental Data-types are int, char and float, etc.
Derived Data-types: -
1. The Data-types which are derived using built-in Data-type known as Derived Data-types.
2. Derived Data-type are designed by the programmer to stire multiple values of same type as per their requirement.
3. Examples of derived Data-types are Array, Pointer, Function, list, etc.
User-defined Data-type: -
1. The Data-types which are derived using built-in Data-type known as User defined Data-types.
2. These types of data are wrapped into a single data-type to store multiple values of either same type or different type to store multiple values of either same type of different type or both as per the requirement.
3. Examples of user-defined Data-types are class, structures, etc.
Q. Difference between Fundamental and Derived Data-types.
Primitive data structures. We will discuss about primitive data type in classification of data structure.
Classification of Data structure:
Generally categorized into two classes:
1. Primitive Data structure
2. Non-primitive Data structure
Primitive Data structure: -
1. Primitive Data structure are the fundamental data structure which are supported by a programming language.
2. Primitive data structures are basic structure and are directly operated by the machine instructions.
3. Some basic data types which fall in these categories are char, int, float, and double.
Non-primitive Data structure: -
1. Non-primitive data structures are those data structure which are created using primitive data structure.
2. Non-primitive data structure is a group of homogeneous (same type) or heterogeneous (different type) data item.
3. Non-primitive data structure are derived into two types: -
a. Linear non-primitive data structure (e.g. arrays, stacks, queue, linked list)
. Non-linear non-primitive data structure (e.g. tress and graphs).
Linear Data-structure: -
A data structure that maintains a linear relationship between its elements called linear data structure. Example array, stack, queue, and linked list (list)
Non-Line Data-structure: -
A data structure that does not maintains any linear relationship between its elements. They maintain hierarchical relationship between the elements. Example tree and graph.
No comments:
Post a Comment