C++ Program for Cursor Implementation of List ADT

Cursor implementation of List ADT

AIM:

• To Write a C++ Program for Cursor implementation of list ADT.

Algorithm:
Step1: Create nodes first,last,next,prev and cur then set the value as NULL.
Step 2: Read the list operation type.
step 3: If operation type is create then process the following steps.
1. Allocate memory for node cur.
2. Read data in cur's data area.
3. Assign cur link as NULL.
4. Assign first=last=cur.
Step 4: If operation type is Insert then process the following steps.
1. Allocate memory for node cur.
2. Read data in cur's data area.
3. Read the position the Data to be inserting.
4. Availability of the position is true then assign cur's link as first and first=cur.
5. If availability of position is false then do following steps.
1. Assign next as cur and count as zero.
2. Repeat the following steps until count less than position.
1 .Assign prev as next
2. Next as prev of link.
3. Add count by one.
4. If prev as NULL then display the message INVALID POSITION.
5. If prev not qual to NULL then do the following steps.
1. Assign cur's link as prev's link.
2. Assign prev's link as cur.
Step5: If operation type is delete then do the following steps.
1. Read the position .
2. Check list is Empty .If it is true display the message List empty.
3. If position is first.
1. Assign cur as first.
2. Assign First as first of link.
3. Reallocate the cur from memory.
4. If position is last.
1. Move the current node to prev.
2. cur's link as Null.
3. Reallocate the Last from memory.
4. Assign last as cur.
5. If position is enter Mediate.
1. Move the cur to required position.
2. Move the Previous to cur's previous position
3. Move the Next to cur's Next position.
4. Now assign previous of link as next.
5. Reallocate the cur from memory.
step 6: If operation is traverse.
1. Assign current as first.
2. Repeat the following steps until cur becomes NULL.

Program:
#include<iostream.h>
#include<conio.h>
#include<process.h>
#define max 5
struct node
{
int data;
int next;
};
typedef struct node NODE;
int avail,list = -1;
NODE curs[max];
void initial()
{
int i;
avail = 0;
for(i=0;i<max-1;i++)
curs[i].next=i+1;
curs[i].next=-1;
}
void create()
{
int n,i,item,temp;
cout<<"\nEnter the no of elements: ";
cin>>n;
//cout<<n;
if(n>=max)
cout<<"\n Size exists";
else
{
initial();
if(avail==-1)
{
cout<<"\nThere is no space to insert";
exit(0);
}
list = avail;
if(n==max-1) avail = -1;
else avail=n+1;
cout<<"\nEnter the elements one by one: ";
for(i=0;i<n;i++)
{
cout<<"\n Enter the "<<i+1<<"th element ";
cin>>item;
cout<<"\t";
//cout<<item;
curs[i+1].data=item;
}
curs[n].next=-1;
}
}
void display()
{
int i;
cout<<"\nCursor space: ";
cout<<"\n\nAvail = "<<avail<<" \t ";
cout<<"List = "<<list<<"\n";
cout<<"_______________";
cout<<"\n DATA NEXT \n";
cout<<"_______________";
i=0;
while(i<max)
{
cout<<"\n"<<curs[i].data<<" \t "<<curs[i].next;
cout<<"\n_______________";
i++;
}
}
void insbeg()
{
int item,i;
cout<<"\nEnter the item to be inserted: ";
cin>>item;
//cout<<item;
cout<<"\n";
i=avail;
avail=curs[avail].next;
curs[i].data=item;
curs[i].next=curs[list].next;
curs[list].next=i;
}
void insend()
{
int item,i;
cout<<"\nEnter the item to be inserted: ";
cin>>item;
//cout<<item;
cout<<endl;
i=list;
while(curs[i].next!=-1)
i=curs[i].next;
curs[i].next=avail;
avail=curs[avail].next;
i=curs[i].next;
curs[i].data=item;
curs[i].next=-1;
}
void insint()
{
int item,i,pos,count,temp;
cout<<"\nEnter the item to be inserted: ";
cin>>item;
//cout<<item;
cout<<endl;
cout<<"\nEnter the position of the item: ";
cin>>pos;
//cout<<pos;
cout<<endl;
i=list;
count=1;
while(count<pos)
{
i=curs[i].next;
count=count+1;
}
temp=avail;
avail=curs[avail].next;
curs[temp].data=item;
curs[temp].next=curs[i].next;
curs[i].next=temp;
}
void delbeg()
{
int i;
i=curs[list].next;
curs[list].next=curs[i].next;
curs[i].next=avail;
avail=i;
curs[avail].data=0;
if(curs[list].next==-1)
{
curs[list].next=avail;
avail=list;
list=-1;
}
}
void delend()
{
int i,prev;
i=list;
while(curs[i].next!=-1)
{
prev=i;
i=curs[i].next;
}
curs[prev].next=-1;
curs[i].next=avail;
avail=i;
curs[avail].data=0;
if(curs[list].next==-1)
{
curs[list].next=avail;
avail=list;
list=-1;
}
}
void delint()
{
int pos,i,count,prev;
cout<<"\nEnter the position: ";
cin>>pos;
//cout<<pos;
cout<<endl;
i=list;
count=1;
while(count<=pos)
{
prev=i;
i=curs[i].next;
count=count+1;
}
curs[prev].next=curs[i].next;
curs[i].next=avail;
avail=i;
curs[avail].data=0;
if(curs[list].next==-1)
{
curs[list].next=avail;
avail=list;
list=-1;
}
}
void main()
{
int ch;
clrscr();
do
{
cout<<"\n ***********************************************************";
cout<<"\n\t\t\t\t LIST\n";
cout<<" ***********************************************************";
cout<<"\n1. Create";
cout<<"\n2. Insert at begin";
cout<<"\n3. Insert at end";
cout<<"\n4. Insert at intermediate";
cout<<"\n5. Delete at begin";
cout<<"\n6. Delete at end";
cout<<"\n7. Delete at intermediate";
cout<<"\n8. Display";
cout<<"\n9. Exit";
cout<<"\n\nEnter your choice:";
cin>>ch;
//cout<<"\n"<<ch;
switch(ch)
{
case 1:
create();
break;
case 2:
if(avail==-1) cout<<"\nThere is no space";
else insbeg();
break;
case 3:
if(avail==-1) cout<<"\nThere is no space";
else insend();
break;
case 4:
if(avail==-1) cout<<"\nThere is no space";
else insint();
break;
case 5:
if(list==-1) cout<<"\nNo element to delete";
else delbeg();
break;
case 6:
if(list==-1) cout<<"\nNo element to delete";
else delend();
break;
case 7:
if(list==-1) cout<<"\nNo element to delete";
else delint();
break;
case 8:
display();
break;
case 9:
cout<<"\nEnd of the operation";
break;
default:
cout<<"\nEnter only 1 to 9: ";
}
}while(ch!=9);
}

OUTPUT:
LIST
1. Create
2. Insert at begin
3. Insert at end
4. Insert at intermediate
5. Delete at begin
6. Delete at end
7. Delete at intermediate
8. Display
9. Exit
Enter your choice:1
1
Enter the no of elments: 4
4
Enter the elements one by one:
enter the element 2
2
enter the element 3
M.Rajeswari ( Department of Information Technology)
3
enter the element 4
4
enter the element 5
5
LIST
1. Create
2. Insert at begin
3. Insert at end
4. Insert at intermediate
5. Delete at begin
6. Delete at end
7. Delete at intermediate
8. Display
9. Exit
Enter your choice:8
8
Cursor space:
Avail = -1 List = 0
______________
DATA NEXT
______________
0 1
_______________
2 2
_______________
3 3
_______________
4 4
_______________
5 -1
_______________
LIST
1. Create
2. Insert at begin
3. Insert at end
4. Insert at intermediate
5. Delete at begin
6. Delete at end
7. Delete at intermediate
8. Display
M.Rajeswari ( Department of Information Technology)
9. Exit
Enter your choice:6
6
LIST
1. Create
2. Insert at begin
3. Insert at end
4. Insert at intermediate
5. Delete at begin
6. Delete at end
7. Delete at intermediate
8. Display
9. Exit
Enter your choice:8
8
Cursor space:
Avail = 4 List = 0
______________
DATA NEXT
______________
0 1
_______________
2 2
_______________
3 3
_______________
4 -1
_______________
0 -1
_______________
LIST
1. Create
2. Insert at begin
3. Insert at end
4. Insert at intermediate
5. Delete at begin
6. Delete at end
7. Delete at intermediate
8. Display
9. Exit
Enter your choice:2
2
Enter the item to be inserted: 6
6
LIST
1. Create
2. Insert at begin
3. Insert at end
4. Insert at intermediate
5. Delete at begin
6. Delete at end
7. Delete at intermediate
8. Display
9. Exit
Enter your choice:8
8
Cursor space:
Avail = -1 List = 0
______________
DATA NEXT
______________
0 4
_______________
2 2
_______________
3 3
_______________
4 -1
_______________
6 1
_______________
LIST
1. Create
2. Insert at begin
3. Insert at end
4. Insert at intermediate
5. Delete at begin
6. Delete at end
7. Delete at intermediate
8. Display
9. Exit
Enter your choice:7
7
Enter the position: 2
2
LIST
1. Create
2. Insert at begin
3. Insert at end
4. Insert at intermediate
5. Delete at begin
6. Delete at end
7. Delete at intermediate
8. Display
9. Exit
Enter your choice:8
8
Cursor space:
Avail = 1 List = 0
______________
DATA NEXT
______________
0 4
_______________
0 -1
_______________
3 3
_______________
4 -1
_______________
6 2
_______________
LIST
1. Create
2. Insert at begin
3. Insert at end
4. Insert at intermediate
5. Delete at begin
6. Delete at end
7. Delete at intermediate
8. Display
9. Exit
Enter your choice:3
3
Enter the item to be inserted: 9
9
LIST
1. Create
2. Insert at begin
3. Insert at end
4. Insert at intermediate
5. Delete at begin
6. Delete at end
7. Delete at intermediate
8. Display
9. Exit
Enter your choice:8
8
Cursor space:
Avail = -1 List = 0
______________
DATA NEXT
______________
0 4
_______________
9 -1
_______________
3 3
_______________
4 1
_______________
6 2
_______________
LIST
1. Create
2. Insert at begin
3. Insert at end
4. Insert at intermediate
5. Delete at begin
6. Delete at end
7. Delete at intermediate
8. Display
9. Exit
Enter your choice:5
5
LIST
1. Create
2. Insert at begin
3. Insert at end
4. Insert at intermediate
5. Delete at begin
6. Delete at end
7. Delete at intermediate
8. Display
9. Exit
Enter your choice:8
8
Cursor space:
Avail = 4 List = 0
______________
DATA NEXT
______________
0 2
_______________
9 -1
_______________
3 3
_______________
4 1
_______________
0 -1
_______________
LIST
1. Create
2. Insert at begin
3. Insert at end
4. Insert at intermediate
5. Delete at begin
6. Delete at end
7. Delete at intermediate
8. Display
9. Exit
Enter your choice:4
4
Enter the item to be inserted: 21
21
Enter the position of the item: 2
2
LIST
1. Create
2. Insert at begin
3. Insert at end
4. Insert at intermediate
5. Delete at begin
6. Delete at end
7. Delete at intermediate
8. Display
9. Exit
Enter your choice:8
8
Cursor space:
Avail = -1 List = 0
______________
DATA NEXT
______________
0 2
_______________
9 -1
_______________
3 4
_______________
4 1
_______________
21 3
_______________
LIST
1. Create
2. Insert at begin
3. Insert at end
4. Insert at intermediate
5. Delete at begin
6. Delete at end
7. Delete at intermediate
8. Display
9. Exit
Enter your choice:9

Result:

• Thus, the cursor implementation of list ADT for singly linked list program has been written and executed successfully.