There are three questions in this assignment. Answer all the questions. You may use illustrations and diagrams to enhance your explanations.
Question 1: Write an algorithm for the implementation of a circular doubly linked list (10 Marks)
Operations
1)insertion
2)forward traversal
3)reverse traversal
4)search
#include<iostream.h>
cll*hd;
struct cll
{
private:
int data;
cll *next;
public:
cll* insert_one(int d,cll* c)
{
cll*NEW;
NEW=new cll;
NEW->data=d;
NEW->next=NULL;
if(c==NULL)
{
c=NEW;
c->next=c;
}
else
{
cll*c1=c;
while(c1->next!=c)
c1=c1->next;
c1->next=NEW;
NEW->next=c;
}
return c;
}
cll* delete_one(int,cll*);
void ftraverse(cll* c)
{
if(c==NULL)
{
cout<<"\nlist empty\n";
return;
}
else
{
cll *c1=c;
cout<<c1->data<<"->";
c1=c1->next;
while(c1!=c)
{
cout<<c1->data<<"->";
c1=c1->next;
}
cout<<"NULL\n";
}
}
void rtraverse(cll* c)
{
if(c->next==hd)
{
cout<<c->data<<"->";
return;
}
else
rtraverse(c->next);
cout<<c->data<<"->";
}
void search(int d,cll* c)
{
cll*c1=c;
if(c==NULL)
{
cout<<"\nlist empty\n";
return;
}
else
{
if(c->data == d)
{
cout<<"found\n";
return ;
}
while(c->next !=c1)
{
if(c->data==d)
{
cout<<"found\n";
return ;
}
c=c->next;
}
if(c->data ==d)
{
cout<<"found\n";
return ;
}
cout<<" search unsuccess ful \n";
}
}
void function()
{
cout<<"******************************************\n";
cout<<"program to implement a circular linked list \n";
cout<<"******************************************\n";
cll * head;
head=NULL;
cout<<"\n\nMENU :\n";
cout<<"1)insertion\n"
<<"2forward traversal\n"
<<"3)reverse traversal\n"
<<"4)search\n"
<<"5)exit\n\n";
cout<<"Enter your option :";
int opt;
cin>>opt;
int d;
while(opt!=5)
{
switch(opt)
{
case 1:
cout<<"Enter data to the node :";
cin>>d;
head=insert_one(d,head);
cout<<"inserted\n";
break;
case 2:
cout<<"The forward traversal is :\n";
ftraverse(head);
break;
case 3:
cout<<"The reverse traversal is :\n";
hd=head;
rtraverse(head);
cout<<"NULL\n";
break;
case 4:
cout<<"Enter the element to be searched :";
int d;
cin>>d;
search(d,head);
break;
case 5:
break;
default:
cout<<"invalid option";
break;
}
cout<<"\n\nMENU :\n";
cout<<"1)insertion\n"
<<"2)forward traversal\n"
<<"3)reverse traversal\n"
<<"4)search\n"
<<"5)exit\n\n";
cout<<"Enter your option :";
cin>>opt;
}
}
};
void main()
{
cll list;
list.function();
}
Question 2: What are the advantages of Arrays and Pointers? What is the basis for selection of Arrays or Pointers as data structure in a program. (5 Marks)
POINTERS
Pointers are generally useful in the context where we need a continuous memory allocation. Using pointers dynamic allocation of memory is achieved pointers basically hold the address of a variable. they are mainly used as function parameters to pass values of parameters as references rather than values
ARRAYS
You can use one name for similar objects and save then with the same name but different indexes. Arrays are very useful when you are working with sequences of the same kind of data (similar to the first point but has a different meaning). Arrays use reference type and so.
The principal benefit of a linked list (using pointer) over a conventional array is that the list elements can easily be added or removed without reallocation or reorganization of the entire structure because the data items need not be stored contiguously in memory or on disk. Linked lists (pointer) allow insertion and removal of nodes at any point in the list, and can do so with a constant number of operations if the link previous to the link being added or removed is maintained during list traversal.
On the other hand, simple linked lists by themselves do not allow random access to the data other than the first node's data, or any form of efficient indexing. Thus, many basic operations — such as obtaining the last node of the list (assuming that the last node is not maintained as separate node reference in the list structure), or finding a node that contains a given datum, or locating the place where a new node should be inserted — may require scanning most or all of the list elements.
A pointer can refer to an individual item or to an array of items. In fact, an array is just a way of creating both a list of items and a pointer to that list's first item in one declaration. The array and pointer concepts are more or less completely interchangeable in C.
This means that subscripts can be used with pointers, as if they were arrays held at the address of the pointer. As C does no array bound checking, this is completely unsafe. You may assign the address of a simple int variable to a pointer to int and than access locations following it as if they belonged to an array of ints, as follows.
void main()
{
int i, * ip;
ip = & i;
ip[0] = 3;
ip[1] = 2;
ip[2] = 1;
}
On the other hand, an array can be used as if it was a pointer. We have
seen that arrays are always passed by reference, even though no & is written,
and this is why. The only
difference is that the address of an array cannot be changed by assignment. Thus,
the following would not be allowed:
void main()
{
int i, ia[];
ia = &i;
}
Question 3: What is a row major order? What is a column major order? How will you find the location of an element of an array , if the array is stored using row major order? Answer the question, if the array is stored in column major order. (10 Marks)
Lets now see how the data represented in an array is actually stored in the memory cells of the machine. Because computer memory is linear, a one-dimensional array can be mapped on to the memory cells in a rther straight forward manner. Sotrage for element A[I+1] will be adjacent to storage for element A[I] for I=0,1,2,… N-1. To find the actual address of an element one merely needs to subtract one from the position of the desired entry and then add the result to the address of the first cell in the sequence. Let us see it through an example. Consider an array A of 26 elements. We require to find the addressof A[4]. If the first cell in the sequence A[0] A[1],A[2],….A[25]. Was at address 16, then A[4] would be located at 16+4 = 20, as shown in Firgure. We assume that the size of each elemtn stored is one unit.
Therefore, it is necessary to know the starting address of the space allocated to the array and the size of the each element, which is same for all the elements of an array. We may call the starting address as a base address and denote it by B. then the location of 1th element would be
B + I*S (1)
Where S is the size of each element of array.
Let us now consider storage mapping for multi-dimentional arrays. As we had seen in previous section that in a 2-dimentional array must be simulated we first calculated the amount of storage area needed and allocate a block of contigous memory cells of that size. One way to stoe the data in the cells is row by row. That is, we store first the fist row of the array, then the second row of the aray and then the next and so on. For example the array defined by A, which logically appears as given in Firgure2 appears physically as given in Figure3 such a storage scheme is called Row Major Order.
The other alternative is to store the array column by column. It is called Column Major Order as in Figure 4.
0 comments:
Post a Comment