Data Structures short notes on some of the important topics
(a) Priority Queues : Priority queue is an ordered list of homogeneous elements. In a normal queue, service is provided on the basis of First-in-first-out. In priority queue, service is not provided on the basis of "first-come-first-served" basis but rather than each element has a priority based on the urgency of need.
- An element with higher priority is processed before other elements with lower priority.
- Elements with the same priority are processed on "first-come-first served" basis.
An example of priority queue is found in long term scheduling of jobs processed in a computer. In practice, short processes are given a priority over long processed as it improves the average response of the system.
Implementation of Priority Queues : Priority queue can be implemented using a circular array. As the service must be provided to an element having highest priority, there could be a choice between :
- List is always maintained sorted on priority of elements with the highest priority element at the front. Here, deletion is trivial but insertion is complicated as the element must be inserted at the correct place depending on its priority.
- List is maintained in the "FIFO" form but the service is provided by selecting the element with highest priority. Deletion is difficult as the entire queue must be traversed to locate the element with highest priority. Here, insertion is trivial (at rear end).
Applications of Priority Queues : Priority Queues are used in following areas :
- Operating System : Priority queue is used for job scheduling and interrupt handling in operating system.
- Graph Searching : It is used for shortest path graph searching.
- Event-driven simulation : It is used for customers in a line.
- Data Compression : It is used for Huffman codes.
- Numerical Computation : It is used for reducing round off error.
- Computational number theory : It is used to find the sum of powers.
- Artificial Intelligence : It is used of A* search.
(b) Dynamic Allocation : The process of allocating memory at the time of execution is called dynamic memory allocation. The allocation and release of this memory space can be done with the help of some built-in-functions whose prototypes are found in alloch.h and stdlib.h header files. These functions tame memory from a memory area called heap and release this memory whenever not required, so that it can be used again for some other purpose.
Pointers play an important role in dynamic memory allocation for some other purpose. The dynamically allocated memory only through pointers.
malloc()
Declaration : void * malloc (size_t size)
calloc()
Declaration : void * calloc (size_t n, size_t size)
realloc()
Declaration : void * realloc (void*ptr, size_t size)
Free()
Declaration : void free(void *P)
Example for allocating dynamic memory for storing 100 numbers using malloc() :
int *P;
P = (int*)malloc (100*sizeof(int));
On successful execution of the above statement, a memory space of the size 100* size of an integer in byte is reversed and the address of the first byte of the memory allocated is assigned to the pointer P.
Example for allocating dynamic memory for storing 100 integer numbers using calloc().
int *P;
P = (int*) calloc (100, sizeof(int));
The above statement allocates contiguous space for 100 blocks, each of size 'sizeof(int)'. All bytes are initialized to zero and pointer to the first byte of allocated memory is assigned to pointer P.
(c) Tree Reversal : Most of the tree operation require traversing tree in particular order. Traversing a tree is a process of visiting every node of the tree and exactly once. Since, a binary tree is defined in a recursive manner, tree traversal too could be defined recursively. For example, to traverse a tree, one may visit the root first, then the left subtree and finally traverse the right subtree. If we impose the restriction than left subtree is visited before the right subtree then free different combination of visiting the root, traversing left subtree, traversing right sub-tree is possible.
- Visit the root, traverse, left sub-tree, traverse right sub-tree.
- Traverse left subtree, visit the root, traverse right subtree.
- Traverse left subtree, traverse right subtree, visit the root.
These three techniques of traversal are known as Preorder, inorder and postorder traversal of a binary tree.
Preorder Traversal (Recursive) : The functioning of preorder traversal of a non-empty binary tree is as follows :
- Firstly, visit the root mode.
- Next, traverse the left subtree in pre-order.
- At last, traverse the right-subtree in preorder.
Inorder Traversal (Recursive) : The functioning of inorder traversal of non-empty binary tree is as follows :
- Firstly, traverse the left sub-tree in-order.
- Next, visit the root node.
- At last, traverse the right subtree in in-order.
Postorder Traversal (Recursive) : The functioning of postorder traversal of nonempty binary tree is as follow :
- Firstly, traverse the left subtree in postorder.
- Next, traverse the right subtree in postorder.
- At last, visit the root node.
(d). File organization : A file is a collection of records where each record consists of one or more fields. File organization can be defined as the method of storing data records in a file. The primary objective of file organization is to provide means for record retrieval and update. The factors involved in selecting a particular file organization for uses are :
- Economy of storage
- Ease of retrieval
- Convenience of updates
- Realiability
- Security
- Integrity
- Volume of transcation
Commonly, used file organization are :
- Sequential files
- relative files
- Direct files
- Indexed Sequential files
- Index files
In a sequential file, data records are stored in specific sequence. Records are physically ordered on the value of one the fields called the ordering fields. Records could also be stored in the order of arrival.
In a relative file, each record is stored at a fixed place in a file. Each record is associated with a integer key value, which is mapped to fixed slot in a file.
Direct file is similar to relative file. Direct file popularly known as a hashed file. Here the key value need not be an integer.
In an indexed sequential file an index is added to a sequential file to provide random access. An overflow are should be maintained to allow insertions.
In an index file, data records need not be sequenced. An index is maintained to improve access.
Posts
