Linked Implementation of Queues

Linked Implementation of Queues

The items are deleted from the front of a queue and inserted at the rear. A pointer to the first element of a list represent the front of the queue. Another pointer to the last element of the list represent the rear of the queue.

If (empty(q))

{

Printf(“Queue underflow”);

Exit(1);

}

P=q.front;

X=info(p);

q.front=next(p) ;

if(q.front == null)

q.rear = null;

freenode(p);

return(x);

The operation insert(q,x) is implemented by

P = getnode();

Info(p) = x;

Next(p) = null;

If (q.rear == null)

q.front = p;

else

next(q.rear) = p;

q.rear = p;

Array implementation of lists

Array implementation of lists

A list is simply a collection of nodes, the nodes cannot be ordered by the array ordering; each contain within itself a pointer to its successor. Thus a group of 500 nodes might be declared as an array node as follows.

#define NUMNODES 500

Struct nodetype

{

Int info, next;

};

Struct nodetype node[NUMNODES];

Limitations of the Array Implementation

Under the array implementation, a fixed set of nodes represented by an array is established at the start of execution.

The number of nodes that are needed often cannot be predicted when a program is written.

The number of nodes are declared must remain allocated to the program throughout its execution.

The solution to this problem is to allow nodes that are dynamic rather than static.

Allocating and Freeing Dynamic Variables

Allocating and Freeing Dynamic Variables

If X is any object, &X is a pointers to help implement dynamic linked lists.
In C a pointer variable to an integer can be created by the declaration

Int *p;

Once a variable p has been declared as a pointer to a specific type of object, it must be possible to dynamically create an object of that specific type and assign its address to p.

Malloc dynamically allocates a portion of memory and returns a pointer to an item.

Pi = (int *) malloc(sizeof(int));

Pr = (float *)malloc(sizeof(float));



Linked list using Dynamic variables

The capability of dynamically allocating and freeing a variable.

Struct node
{
Int info;
Struct node * next;
};


Tydedef struct node *NODEPTR;

NODEPTR p;

P=getnode();

NODEPTR getnode()
{
NODEPTR p;
P = (NODEPTR) malloc(sizeof(struct node));
Return(p);
}


Freenode(p);

Circular List

Circular List

The stack as a Circular List

Empty(pstack)

NODEPTR 8pstack;
{
Return((*pstack == NULL) ? TRUE : FALSE);
}




Push(pstack, x)

NODEPTR *pstack;
Int x;
{
NODEPTR P;
P = getnode();
p->info = x;
if (empty(pstack) == TRUE)
*pstack = p;
Else
p->next = (*pstack)->next;
(*pstack) -> next = p;
}



Pop(pstack)

NODEPTR *pstack;
{
Int x;
NODEPTR p;
If (empty(pstack) == TRUE)
{
Printf(“stack underflow”);
Exit(1);
}
P=(*pstack) -> next;
X=p->info;
If ( p == *pstack)
*pstack = NULL;
Else
(*pstack) - > next = p->next;
Freenode(p);
Return(x);
}

Data Structures Lab Manual

Lab Manual Algorithms

Program List


1. Stack using Arrays

2. STACK using Linked List

3. Queues using Arrays

4. Queue using Linked List

5. Tree Traversal

6. Merge sort

7. Graph using DFS

8. Graph Traversal using BFS

9. Warshall’s Algorithm

10. Dijkstra’s Algorithm

11. Huffman Algorithm

12. Insertion sort

Stack using Arrays

Representation of Stack using Arrays

Algorithm:

Step 1: Create a push operation with one argument, the element to be added

Step 2: Create a POP function with one argument, the address of the element to store the popped operation

Step 3: Create a function PEEK with one argument, the address of the element of store the top value

Step 4: Create a function ISEMPTY with no argument for stack empty condition

Step 5: Create a function ISFULL for checking for stack full.

Step 6: Sop the program execution

STACK using Linked List

Representation of STACK using Linked List

Algorithm:


Step 1: Create a structure with data and Link field

Step 2: Allocate the memory for the new node

Step 3: Insert the value into the new node using PUSH operation

Step 4: Release the allocated memory for deleting the item from the structure

Step 5: Create a function to retrieve the contents from the Top of the Stack

Step 6: Create a function for display the items from the stack.

Step 7: Create a function for Is Empty condition

Step 8: Create a function for Is Full condition.

Step 9: Create a function to count the number of nodes in the stack.

Step 10 : Stop the execution.

Queues using Arrays

Queues using Arrays

Algorithm


Step 1: Create a function Enqueue() with two arguments

Step 2: Assign the new element in the array by increasing the Rear variable.

Step 3: Create a function Dequeue with two arguments

Step 4: Increment the Front variable by 1.

Step 5: Create a function Isempty with no arguments

Step 6: Check whether the front pointer and rear is equal to zero.

Step 7: If true, the queue is empty otherwise not empty.

Step 8: Create a function Isfull to check whether the queue is full or not.

Step 10 : Stop the execution.

Queue using Linked List

Representation of Queue using Linked List

Algorithm:

Step 1: Create a structure with data and link field.

Step 2: Allocate a memory for the new node using a getnode().

Step 3: Insert the item into the queue

Step 4: Delete the node by releasing the memory of the node.

Step 5: create a function to retrieve the contents from the top of the queue.

Step 6: Display the contents of the queue by traversing through the queue.

Step 7: Stop the execution.

Tree Traversal

Binary Search Tree Traversal

Aim : To create a binary search tree and do the following traversal

Algorithm :

Preorder Traversal

preorder(node)
print node.value
if node.left ≠ null then preorder(node.left)

if node.right ≠ null then preorder(node.right)

Inorder Traversal

inorder(node)
if node.left ≠ null then inorder(node.left)
print node.value
if node.right ≠ null then inorder(node.right)

Post Order Traversal

postorder(node)
if node.left ≠ null then postorder(node.left)
if node.right ≠ null then postorder(node.right)
print node.value

Merge sort

Merge sort

Aim : To sort the given elements using Merge Sort

Algorithm:

function merge_sort(m)
var list left, right, result
if length(m) < = 1
return m
var middle = length(m) / 2 - 1
for each x in m up to middle
add x to left
for each x in m after middle
add x to right

left = merge_sort(left)
right = merge_sort(right)
if left.last_item > right.first_item
result = merge(left, right)
else
result = append(left, right)
return result

function merge(left,right)
var list result
while length(left) > 0 and length(right) > 0
if first(left) < = first(right)
append first(left) to result
left = rest(left)
else
append first(right) to result
right = rest(right)
end while
if length(left) > 0
append left to result
else
append right to result
return result

Graph using DFS

Depth-first search

Aim : Program to traverse a graph using DFS

Algorithm:

Step 1: consider that the DFS is beginning from the starting vertex A. Process the vertex A and mark it as visited.

Step 2: Using the adjacency matrix of the graph find the vertex along the path which begins vertex A, that has not been visited yet. Process the vertex and consider this as the new vertex and mark the vertex as visited.

Step 3: Repeat Step 2 using the new search vertex. If no vertices back track to the previous node and continue the search from there.

Step 4: When backtracking to the previous search node in step 3 is impossible, the search from the originally chosen search node is complete.

Step 5: If the graph still contains unvisited nodes, choose any vertex that has not been visited and repeat step 1 to 4.

Graph Traversal using BFS

Breadth-first search

Aim : Program to demonstrate Graph Traversal using BFS

Algorithm:

Step 1: Consider any vertex in the graph. Process the vertex A and mark it as visited.

Step 2: Using the adjacency matrix of the graph proceed to the next vertex which has an edge connection wise the vertex considered in step 1.

Step 3: Backtrack to the vertex considered in step 1 descend along an edge towards an unvisited vertex and mark the new vertex as visited

Step 4: Repeat step3 until all vertices adjacent to the node in step 1 have been marked as visited.

Step 5: Stop the execution

Warshall’s Algorithm

Aim : To create a program to find the shortest path in a given graph using Warshall’s Algorithm.

Algorithm :

for(i=0; i < MAXNODES; ++i)
for(j=0; j < MAXNODES; ++j)
path[i][j]=path k-1[i][j] (path k-1[i][k] && path k-1[k][j]);


for(i=0; i < MAXNODES; ++i)
for(j=0; j < MAXNODES; ++j)
path k[i][j] = path k-1[i][j];
for(i=0;i < MAXNODES; ++i)
if(path k-1[i][k] == TRUE)
for(j=0;j < MAXNODES; ++j)
path k[i][j] = path k-1[i][j] path k-1[k][j];

Dijkstra’s Algorithm

Aim: To create a program to find the shortest path in a given graph using Dijkstra’s Algorithm.

Algorithm :

function Dijkstra(Graph, source):
for each vertex v in Graph:
dist[v] := infinity
previous[v] := undefined
dist[source] := 0
Q := the set of all nodes in Graph
while Q is not empty: // The main loop
u := vertex in Q with smallest dist[]
if dist[u] = infinity:
break
remove u from Q
for each neighbor v of u:
alt := dist[u] + dist_between(u, v)
if alt < dist[v]:
dist[v] := alt
previous[v] := u
return previous[]

Huffman Algorithm

Aim : Program for performing the Huffman Algorithm

Algorithm:


For(i=0;i < n; i++)
{
P=maketree(frequency[i]);
Position[i] = p;
Pqinsert(rootnodes, p);
}
While (root nodes contain more than one item)
{
P1=pqmindelete(rootnodes);
P2=pqmindelete(rootnodes);
P=maketree ( info (p1) + info (p2));
Setleft(p, p1);
Setright (p, p2);
Pqinsert(rootnodes, p);}

Root= pqmindelete(rootnodes);
For(i=0;i < n;i++)
{
P=position[i];
Code[i]=the null bit string;
While (p!= root)
{
If(isleft (P))
Code[i]= 0 followed by code[i];
Else
Code[i] = 1 followed by code[i];
P=father(p);
}
}

Insertion sort

Aim: Program to sort the given numbers using Insertion sort.

Algorithm:

insertionSort(array A)

begin
for i := 1 to length[A] - 1 do
begin
value := A[i];
j := i - 1;
while j >= 0 and A[j] > value do
begin
A[j + 1] := A[j];
j := j - 1;
end;
A[j + 1] := value;
end;
end;

INFIX, POSTFIX, AND PREFIX

INFIX
POSTFIX
PREFIX

A major application that illustrates the different types of stacks and the various operations and functions defined upon them.

A + B à Infix
+ AB à prefix
AB+ à postfix

A + (B * C)
A + (BC*)
A(BC*)+
ABC * +

The following is the order of precedence (highest to lowest)

Exponentiation

Multiplication / division
Addition / subtraction

Infix

A+B
A + B – C
(A+B) * (C – D)
A $ B * C – D + E / F / (G + H)

postfix

AB+
AB + C –
AB+ CD- *
AB$C*D-EF / GH + / +

Prefix

+AB
- + ABC
* + AB – CD
+ - * $ ABCD / / EF + GH


Evaluating a postfix Expression

Algorithm:

Opndstk = the empty stack;
While ( not end of input)
{
Symb = next input character;
If ( symb is an operator)
Push(opndstk, symb);
Else
{
Opnd2 = pop(opndstk);
Opnd1 = pop(opndstk);
Value = result of applying symb to opnd1 and opnd2;
Push(opndstk, value);
}
}
Return(pop(opndstk));


Example:

6 2 3 + - 3 8 2 / + * 2 $ 3 +

Garbage Collection

Routine for Garbage Collection

# include"stdio.h"
# include"conio.h"
# include"iostrem.h"
struct cell
{
int mark:1;
struct cell *c[2];}
struct cell *free;
struct cell heap[HEAPSIZE];
struct cell *roots[ROOTS];

/* Initially all cells are on free list. Use c[0] to link members of free list. */
void init_heap()
{
for (i=0; i < HEAPSIZE-1; i++)
heap[i].c[0] = &(heap[i+1]);
heap[HEAPSIZE-1].c[0] = 0;
free = &(heap[0]);
}

struct cell *allocate()
{
struct cell *a;
if (!free) { /* no more room => */
gc(); /* try gc */
if (!free) /* still no more room */
die();
};
a = free;
free = free->c[0];
return a;


void gc()
{
for (i = 0; i < ROOTS; i++)
mark(roots[i]);
sweep();
}

void mark(struct cell *cell)
{
if (!cell->mark)
{
cell->mark = 1;
mark(cell->c[0]);
mark(cell->c[1]);
}
}

void sweep()
{
for (i = 0; i < HEAPSIZE; i++)
if (heap[i].mark)
heap[i].mark = 0;
else
{
heap[i].c[0] = free;
free = &(heap[i]);
}
}

Copying Collection

Suitable routine for copying collection

struct cell
{
struct cell *c[2];
}

struct cell space[2][HALFSIZE];
struct cell *roots[ROOTS];
struct cell *free = &(space[0][0]);
struct cell *end = &(space[0][HALFSIZE]);
int from_space = 0;
int to_space = 1;
struct cell *allocate()
{
if (free == end) { /* no room */
gc();
if (free == end) /* still no room */
die();
};
return free++;
}

gc()
{
int i;
struct cell *scan = &(space[to_space][0]);
free = scan;
for (i = 0 ; i < ROOTS; i++)
roots[i] = forward(roots[i]);

while (scan < free)
{
scan->c[0] = forward(scan->c[0]);
scan->c[1] = forward(scan->c[1]);
scan++;
};
from_space = 1-from_space;
to_space = 1-to_space;
end = *(space[from_space][HALFSIZE]);
}

struct cell *forward(struct cell *p)
{
if (p >=&(space[from_space][0]) && p < &(space[from_space][HALFSIZE]))
if (p->c[0] >= &(space[to_space][0]) && p->c[0] < &(space[to_space][HALFSIZE]))
return p->c[0];

else
{
*free = *p;
p->c[0] = free++;
return p->c[0];
}
else return p;
}

ALGORITHM Mark and sweep

5.7.2.4.1 ALGORITHM : Mark and sweep

// The first tracing garbage collection algorithm.
// The mark-sweep algorithm is invoked when the mutator requests memory but there is
// insufficient free space.
// The mutator is stopped while the mark-sweep is executed.
// Mark phase: Identifies all reachable objects by setting a mark
// Sweep phase: Reclaims garbage objects

function DFS(x) {
if (x is a heap pointer)
if (x is not marked)
{
mark x
for(i = 1; i <= │x│; i++)
DFS(x,f1)
}
}

function Mark() {
for each (v in a stack frame)
DFS(V)
}
function Sweep() {
p = first address in heap
while (p < last address in heap)
{
if (p is marked)
unmark p;
else
{
p. f1 = freelist
freelist = p
}

p = p + sizeof(p)
}
}

Collections And Compaction

5.8 Collections And Compaction

Once the memory locations of a given system have been marked appropriately, the collection phase may begin. The purpose of the phase is to return to available memory all those locations that were previously garbage. (Not used by any program but unavailable to any user) It is easy to pass through memory sequentially, examine each node in turn, and return unmarked nodes to available storage.

5.8.1 Stop And Copy Algorithm

Garbage collection approach that collects garbage and defragments the heap is called stop and copy. In stop and copy garbage collection algorithm, the heap is divided into two separate regions/spaces. At any point in time, all dynamically allocated object instances reside in only one of the two regions the active region. The other, inactive region is unoccupied.

Copying garbage collection does not really “collect” garbage. Rather, it moves all the live objects into one area, and the rest of the heap is available which is only garbage. Garbage collection in these systems is only implicit. While mark and compact collectors 3 use a separate marking phase that traverses the live data, copying collectors integrate the traversal of the data and the copying process, so that most objects need only be traversed once. Objects are moved to the contiguous destination area as they are reached by the traversal. The work needed is proportional to the amount of live data.

18a. A simple semi region garbage collector before garbage collection

When running program demands an allocation that will not fit in the unused area of the current region (semi space) or if the memory in the active region is exhausted, the program is suspended or stopped and the garbage collection algorithm is invoked to reclaim space. The stop and copy algorithm copies all of the live objects from the active region to the inactive region. As each object is copied, all references contained in that object are updated to reflect the new locations of the referenced objects.

Stop and Copy garbage collection

Before and after Stop and copy garbage collection

For convenience, we can view each region as a separate heap and we shall refer to them as activeHeap and inactiveHeap. When the stop-and-copy algorithm is invoked, it copies all live objects from the activeHeap to the inactiveHeap. It does so by invoking the copy method given below starting at reach root:

for each root variable r

r = copy (r, inactiveHeap);

swap (activeHeap, inactiveHeap);

The copy method is complicated by the fact that it needs to update all object references contained in the objects as it copies those objects. In order to facilitate this, we record in every object a reference to its copy. That is, we add a special field to each object called forward which is a reference to the copy of this object.

The recursive copy method given below, copies a given object and all the objects indirectly accessible from the given object to the destination heap. When the forward field of an object is null, it indicates that the given object has not yet been copied. In this case, the method creates a new instance of the object class in the destination heap. Then, the fields of the object are copied one-by-one. If the field is a primitive type, the value of that field is copied. However, if the field refers to another object, the copy method calls itself recursively to copy that object.

If the copy method is invoked for an object whose forward field is non-null, that object has already been copied and the forward field refers to the copy of that object in the destination heap. In that case, the copy method simply returns a reference to the previously copied object.

The following figure shows the execution of the stop-and-copy garbage collection algorithm. When the algorithm is invoked and before any objects have been copied, the forward field of every object in the active region is null as shown in figure 19(a).

The figure 19(b) shows a copy of object A, called A', has been created in the inactive region, and the forward field of A refers to A'.

Since A refers to B, the next object copied is object B. As shown in Figure 19(c), fragmentation is eliminated by allocating storage for B' immediately next to A'. Next, object C is copied. Notice that C refers to A, but A has already been copied. Object C' obtains its reference to A' from the forward field of A as shown in Figure 19(d).

questi

questions

questions

questions

questions

questions