Data Structures
An introduction to C:
Dennis Ritchie at AT & T Bell laboratory, Murray Hill , New Jersey
How to run C program:
1. From the Ms Dos prompt start C by typing ‘tc’.
2. Open a file by selecting File | Open | File name from the IDE menu. Or press
F3 Key
3. Run the program by selecting Run | Run, Or press
Ctrl+F9 Key
4. To see the program’s output select Window | User screen or press
Alt+F5 Key.
We may compile and run the programs from the Dos command
Line like tcc Filename <Enter>.
After the program is compiled, we may run it and view the output by typing
Filename <Enter>
Problem solving using computer:
To solve a problem using a computer, the following steps are required :
Ø A program is developed using a high level programming language (program development)
Ø The developed program is entered into a commuter (Program editing).
Ø The edited program is translated and is produced as an executable machine code.
Ø The Executable machine code is run in the computer to carry out the actual task (execution).
To implement the above steps, the programmer develops a program and the developed program is entered and edited with the help of an editor. Normally the editor is provided along with the compiler. After editing the program, the compilation commands us used for the translation process. Then the execution command is used to run the program to get the desired output.
Compilation:
High-level languages allow some English –like words and mathematical expressions that facilitate the better understanding of the logic involved in a program. High-level languages are machine independent. Since a computer system cannot follow programs written in a high language, high language programs are translated into low-level language programs and then executed.
Translation of a high-level language program to allow level language program is done by software known as Compiler. Object code is an intermediate code between the source code and the executable code.
Linking:
Linker performs the linking of libraries with the object code, to make the generated object code into an executable machine code. Thus the object code becomes an input to the linker, which produces an executable machine code. Sometimes programs are www.allvupastpapers.blogspot.com
divided into modules and these modules are compiled separately and then linked by the linker and executed.
When running a program, the following files will be created automatically.
Þ OBJ (Object file)
Þ EXE (Executable file)
Þ Bak (Backup file)
Þ SWP (Swap file)
Data Structures Definition
Data Structure is a specialized format for storing data so that the data’s can be organized in an efficient way.
Classification
 | |||
 | |||
Primitive Non – Primitive
Example: - · Integer
· Real
· Character Linear Non – Linear
· Pointer Example: - Example: -
· Logical ·Linear List · Graph
· Stack ·Tree
· Queue
Array
An array is a finite collection of similar elements stored in contiguous location. The operations done on an array are: -
· Insertion
· Deletion
· Changing a particular element
Linked List
There are three types of linked lists. They are: -
v Single Linked List
v Doubly Linked List
v Singly Circular Linked List
v Doubly Circular Linked List
Single Linked List
Node structure
 |
The data field contains the data elements that have to be stored in the list. The pointer will point the next node in the list.
The operations done on a list are: -
ä Insertion
ä Deletion
Insertion
ä Insertion in the head node
To insert a node in the head node, just change the pointer field of the new node to point to the head node. Let the new node be ‘Temp’ and the head node be ‘Head’, then the insertion is
Temp ® data = X;
Head ® next = head
ä Insertion in the middle node
To insert in the middle node we need to change two pointers. Let the new node be ‘Temp’ and the present node is ‘Present’ and, the next node to the present node is ‘future’. The pointers used are ‘data’ for the data field, ‘next’ to the pointer field, the data to be inserted is ‘X ’then the insertion is
Temp ® data = X
Present ® next = temp
Temp ® next = future
ä Insertion in the last node
To insert an element in the last position just change the pointer field of the present last node to point to the new node, then set the pointer field of the new node to NULL. Let the new node be ‘Temp’ and the present node is ‘Present’. The pointers used are ‘data’ for the data field, ‘next’ to the pointer field, the data to be inserted is ‘X ’then the insertion is
Present ® next =Temp
Temp ® next =null
Temp ® data = X
Deletion
Ø Deletion in the head node
To delete a node in the head node, just point the head node as the second node. Let the head node be ‘Head’, and then the deletion is
Head ® next = head
Ø Deletion in the middle node
To delete a node in the middle we need to change two pointers. Let the node to be deleted is ‘Temp’ and the node previous to the node to be deleted is www.allvupastpapers.blogspot.com
‘Present’ and, the next node to the present node is ‘future’. The pointers used are ‘data’ for the data field, ‘next’ to the pointer field, the data to be inserted is ‘X ’then the insertion is
Present ® next = future
Ø Deletion in the last node
To delete an element in the last position just change the pointer field of the previous node to the last to null. Let the last node be ‘Temp’ and the previous node is ‘Present’. The pointers used are ‘data’ for the data field, ‘next’ to the pointer field, the data to be inserted is ‘X ’then the insertion is
Previous ® next =NULL
Singly Circular Linked List
The advantage of using Circular Linked List is the last null pointer is replaced and the pointer field of the last node points to the first node, due to this circular arrangement the traversing become quite easier. The insertion and deletion in the first and middle are same as singly linked list except the last node.
Insertion
· Insertion in the last node
To insert a node in the last position, insert the new node after the current last node, and then change the pointer field of the new node to point to the first node. Let the last node be last, the new node to be inserted to be new, the first node in the list to be first. The pointers used are ‘data’ for the data field, ‘next’ to the pointer field, the data to be inserted is ‘X ’then the insertion is
Last ® next = new
New ® next =first
Deletion
· Deletion in the last node
To delete a node in the last position, change the pointer field of the previous node to the current last to point the first node. Let the last node be last, the previous node to the current last node to be pre, the first node in the list to be first. The pointers used are ‘data’ for the data field, ‘next’ to the pointer field, the data to be inserted is ‘X ’then the deletion is
Prev ® next = first
Stack
An important subclass of lists permits the insertion and deletion of an element to occur only at one end. A linear list of this type is known as ‘stack’. The insertion is referred to as ‘push’. The deletion is referred to as ‘pop’. The two pointers used for accessing is top & bottom pointer.
|
PUSH – Storing the element into the stack.
Check top<= allowed size if yes increment the top position and store the value in the top position.
POP - Deleting the element from the stack. If top<= we can not delete.
Otherwise decrement the top by one and return the top+1 element.
Queue
The information in this list is processed in the same order as it was received, that is first in first out order (FIFO) or a first – come first – served (FCFS) basis. This type of frequently used list is known as queue. We have two pointers to access the queue. They are
1. Front (used for deletion)
2. Rear (Used for insertion)
Insertion :
if rear>n queue overflow
else
increment the rear pointer and insert the value in the rear position.
Deletion :
Else
Increment the front pointer and return the front-1 value
Tree
An important class of digraph, which involves for the description of hierarchy. A directed tree is an acyclic digraph which has one node called root with in degree 0, while other nodes have in degree 1. Every directed tree must have at least one node. An isolated node is also called as directed tree. The node with out degree as 0 is called as leaf. The length of the path from root to particular node level of the node. If the ordering of the node at each level is prescribed then the tree is called as ordered tree.
Binary Tree
If a tree has at most of two children, then such tree is called as Binary tree. If the elements in the binary tree are arranged in the following order
Left element is lesser than the root
Right element is greater then the root
No duplication of elements
Then such binary tree is called as Binary Search Tree
Operations performed in a binary tree are:
- Inserting a node
- Deleting a node
- Traversing the tree
Traversing Methods
1. Pre – order method
2. In – order method
3. Post – order method
4. Converse Pre – order method
5. Converse In – order method
6. Converse post – order method
Pre – order method
This method gives the tree key value in the following manner: -
1. Process the root
2. Traverse the left sub tree
3. Traverse the right Sub tree
In – order method
This method gives the tree key value in the following manner: -
1. Traverse the left sub tree
2. Process the root
3. Traverse the right Sub tree
Post – order method
This method gives the tree key value in the following manner: -
1. Traverse the left sub tree
2. Traverse the right Sub tree
3. Process the root
Sorting Sorting is, without doubt, the most fundamental algorithmic problem
- Supposedly, 25% of all CPU cycles are spent sorting
- Sorting is fundamental to most other algorithmic problems, for example binary search.
- Many different approaches lead to useful sorting algorithms, and these ideas can be used to solve many other problems.
What is sorting? It is the problem of taking an arbitrary permutation of n items and rearranging them into the total order,
Issues in Sorting
Increasing or Decreasing Order? - The same algorithm can be used by both all we need do is change
to 
in the comparison function as we desire. What about equal keys? – May be we need to sort on secondary keys, or leave in the same order as the original permutations.
What about non-numerical data? - Alphabetizing is sorting text strings, and libraries have very complicated rules concerning punctuation, etc. Is Brown-Williams before or after Brown America before or after Brown, John?
We can ignore all three of these issues by assuming a comparison function which depends on the application. Compare (a,b) should return ``<'', ``>'', or ''=''.
Applications of Sorting
One reason why sorting is so important is that once a set of items is sorted, many other problems become easy.
Heaps
A heap is a complete binary tree with values stored in its nodes such that no child has a value bigger than the value of the parent. Below is a heap.
9 / \ 8 2 / \ 6 4A heap provides a representation for a priority queue. Example: messages processed by priority at a server - messages given priority weighting, higher numbers give better service
- highly dynamic, messages coming and going frequently
- need efficient insert new message and remove highest priority message
9 / \ 8 2 / \ 6 4then we reheapify by copying rightmost leaf to root (4 becomes the root)
4 / \ 8 2 / 6and then we recursively reestablish the heap property as follows: if the parent is greater than a child, swap the www.allvupastpapers.blogspot.com
parent with the highest priority child. Keep swapping until no more swaps are possible. So in the above tree, first we would swamp 4 with 8.
8 / \ 4 2 / 6Then we would swap 4 with 6.
8 / \ 6 2 / 4The final swap yields a heap!
The cost of removing an item (reheapifiying after removing the item) is O(log n). The algorithm just traverses one path in the tree, which is O(log n) in length. For each node on that path it performs at most two comparisons and one swap (3 operations -> constant time). So overall the algorithm has a worst case time complexity of O(log n). Space complexity is O(n) since a sequential array representation can be used.
Quick sort
is a very efficient sorting algorithm invented by C.A.R. Hoarer. It has two phases:
- The partition phase and
- The sort phase.
As we will see, most of the work is done in the partition phase - it works out where to divide the work. The sort phase simply sorts the two smaller problems that are generated in the partition phase.
This makes Quick sort a good example of the divide and conquers strategy for solving problems. (You've already seen an example of this approach in the binary search procedure.) In quick sort, we divide the array of items to be sorted into two partitions and then call the quick sort procedure recursively to sort the two partitions, i.e. we divide the problem into two smaller ones and conquer by solving the smaller ones. Thus the conquer part of the quick sort routine looks like this: quicksort( void *a, int low, int high ) { int pivot; /* Termination condition! */ if ( high > low ) { pivot = partition( a, low, high ); quicksort( a, low, pivot-1 ); quicksort( a, pivot+1, high ); } } |  Initial Step - First Partition |
 Sort Left Partition in the same way |
To do this, we choose a pivot element and arrange that all the items in the lower part are less than the pivot and all those in the upper part greater than it. In the most general case, we don't know anything about the items to be sorted, so that any choice of the pivot element will do - the first element is a convenient one.
Dijkstra's AlgorithmDjikstra's algorithm (named after its discover, E.W. Dijkstra) solves the problem of finding the shortest path from a point in a graph (the source) to a destination. It turns out that one can find the shortest paths from a given source to all points in a graph in the same time, hence this problem is sometimes called the single-source shortest paths problem.
Graph Traversal
Systematic traversals of graph are similar to preorder and post order traversal for trees. There are two graph traversals, depth-first and breadth-first search. Frequently the graph searches start at an arbitrary vertex. The searches are efficient if they are done in O(n + m), where n is the number of vertices and m the number of edges.
Graph traversal can be used to determine the general characteristic of the graph, or to solve a specific problem on a particular graph, for example:
Graph traversal can be used to determine the general characteristic of the graph, or to solve a specific problem on a particular graph, for example:
- Routing phone calls, or packets
- Planning a car trip
- Locate particular vertices, for example a win position in a game.
Depth-first Search
We start the graph traversal at arbitrary vertices, and go down a particular branch until we reach a dead end. Then we back up and go as deep possible. In this way we visit all vertices, and all edges.
Breath-First Search
Breadth-first search visit all adjacent vertices before going deeper. Then we go deeper in one of the adjacent vertices.
Sparse Matrix :
A matrix consists of more number of zeros is called sparse matrix. Once the matrix is stored as it is then there is wastage of memory. For an efficient memory utilization the sparse matrix can be stored in a linear form. The linear form can be of array type or linked list type.
DATA STRUCTURES
Definition:
Data structure is collection of data elements organized in a specified manner and accessing functions are defined to store and retrieve individual data elements. Data structures are sometimes called Data types.
Classification of Data Structure:
A data type may be defined as a set and the elements of the set are called the values of the type. There are four basic or atomic or primitive data types in C. They are int, float, char and double. The Simple data types built from primitives are arrays , pointers, strings and records with which we can build new types called structured or composite types such as stacks, queues, and trees etc. The structured data types can be categorized as linear and non-linear. The linear data structures are stacks, queues and linked lists. The non-linear data structures are trees and graphs.
Stacks
Definition:
A stack is an ordered collection of items into which new items may be inserted and from which items may be deleted at one end, called the top of the stack. The first example of stack, which permits the selection of only its end element , is a pile of coins.
Second example could be a pile of trays or a books lying one above the other.
Let us draw a stack containing integers as in the following figure.
 5 |
| 9 |
| 1 |
| 3 |
| 7 |
top
Here, 5 is the current of the stack. If we add any element in the stack, it will be placed on top of 5 , and if we delete an element , it will be 5, which is on top of the stack.
Operations on Stacks:
Associated with the stack , there are several primitives operations. We can define the following necessary operations on stack.
a) create(s) - To create s as an empty stack.
b) push(s,i) - To insert the element I on top of the stack s.
c) pop(s) - To remove the top element of the stack and to return the removed
element as a function value.
d) top(s) - To return the top element of stack(s).
e) empty(s) - To check whether the stack is empty or not. It returns true if stack is empty and returns false otherwise.
If a stack is empty and it contains no element, it is not possible to pop the stack. Therefore, before popping an element, we must ensure that the stack is not empty.
PUSH & POP OPERATIONS:
When we add an element to a stack, we stay that we push it on the stack and if we delete an element from a stack, we say that we pop it from the stack. Let us see how stack shrinks or grows when we pop or push an element in the following figures.
Push (8) on the stack
 8 |
| 5 |
| 9 |
| 1 |
| 3 |
| 7 |
top
Push (4) on to stack
 4 |
| 8 |
| 5 |
| 9 |
| 1 |
| 3 |
| 7 |
top
Pop an element from the stack
| |
| 8 |
| 5 |
| 9 |
| 1 |
| 3 |
| 7 |
Top Popped element = 4Pop an element from the stack
| |
| |
| 5 |
| 9 |
| 1 |
| 3 |
| 7 |
Top Popped element = 8 We may notice that the last item pushed onto a stack is always the first that will be popped from the stack. That is why stack is called last in, first out or LIFO in short.
By : ADEEL ABBAS
www.allvupastpapers.blogspot.com
AdeelAbbasbk@gmail.com
No comments:
Post a Comment
PLEASE COMMENT ABOUT YOUR VISIT AND MY SITE
Note: Only a member of this blog may post a comment.