Simulate a linear linked-list by an array Simulate a linear linked-list by an ar
ID: 3564137 • Letter: S
Question
Simulate a linear linked-list by an array
Simulate a linear linked-list by an array Let L be a linear linked list. We will use array A to represent L. Your task is to write a C++ program that simulates operations on L by using A, and outputs results. The following is an example snapshot of L and A at some given time: struct node { int data; int next; } struct node A[100]; ASSUME THAT THE LIST DOES NOT CONTAIN MORE THAN 100 ELEMENTS, AND ALL ELEMENTS IN THE LIST ARE DISTINCT head Again, we assume that each node in L contains a distinct data value Do the following operations on A: HERE WE IMAGINE OPERATIONS ON L, BUT ACTUALLY DO THEM ON A NEVER USE A[0] THE next field in A[1] GIVES YOU THE SUCCESSOR NODE YOU MAY USE ADDITIONAL VARIABLES FOR HEAD AND LAST NODES YOU MAY USE -1 IN THE NEXT FIELD TO MARK THE FREE CELLS IN A, AND WHEN YOU NEED A CELL FOR NEW NODE YOU CAN USE THESE FREE CELLS Ay : Create a new node with data value y, and append this node to L I x y : Find the node t with value x, create a new node p with data value y, and insert node p after t in L D y : Find the node with data value y, and delete that node from L R : Reverse L T : Output all data values in L Sample Input/Output: A5 A1 1 5 4 1 1 9 A7 1 9 8 D9 D8 T 5 4 1 7 R T 7 1 4 5Explanation / Answer
#include struct node //Each node in list will contain data and next pointer { int data; struct node *next; }; struct node *start; void insertbeg(void) { struct node *nn; int a; nn=(struct node *)malloc(sizeof(struct node)); printf("enter data:"); scanf("%d",&nn->data); a=nn->data; if(start==NULL) //checking if List is empty { nn->next=NULL; start=nn; } else { nn->next=start; start=nn; } printf("%d succ. inserted ",a); return; } void insertend(void) { struct node *nn,*lp;int b; nn=(struct node *)malloc(sizeof(struct node)); printf("enter data:"); scanf("%d",&nn->data); b=nn->data; if(start==NULL) { nn->next=NULL; start=nn; } else { lp=start; while(lp->next!=NULL) { lp=lp->next; } lp->next=nn; nn->next=NULL; } printf("%d is succ. inserted ",b); return; } void insertmid(void) { struct node *nn,*temp,*ptemp;int x,v; nn=(struct node *)malloc(sizeof(struct node)); if(start==NULL) { printf("sll is empty "); return; } printf("enter data before which no. is to be inserted: "); scanf("%d",&x); if(x==start->data) { insertbeg(); return; } ptemp=start; temp=start->next; while(temp!=NULL&&temp->data!=x) { ptemp=temp; temp=temp->next; } if(temp==NULL) { printf("%d data does not exist ",x); } else { printf("enter data:"); scanf("%d",&nn->data); v=nn->data; ptemp->next=nn; nn->next=temp; printf("%d succ. inserted ",v); } return; } void deletion(void) { struct node *pt,*t; int x; if(start==NULL) { printf("sll is empty "); return; } printf("enter data to be deleted:"); scanf("%d",&x); if(x==start->data) { t=start; start=start->next; free(t); printf("%d is succ. deleted ",x); return; } pt=start; t=start->next; while(t!=NULL&&t->data!=x) { pt=t;t=t->next; } if(t==NULL) { printf("%d does not exist ",x);return; } else { pt->next=t->next; } printf("%d is succ. deleted ",x); free(t); return; } void display(void) { struct node *temp; if(start==NULL) { printf("sll is empty "); return; } printf("elements are: "); temp=start; while(temp!=NULL) { printf("%d ",temp->data); temp=temp->next; } return; } void main() { int c,a; start=NULL; do { printf("1:insert 2:delete 3:display 4:exit enter choice:"); scanf("%d",&c); switch(c) { case 1: printf("1:insertbeg 2:insert end 3:insert mid enter choice:"); scanf("%d",&a); switch(a) { case 1:insertbeg();break; case 2:insertend();break; case 3:insertmid();break; } break; case 2:deletion();break; case 3:display();break; case 4:printf("program ends ");break; default:printf("wrong choice "); break; } }while(c!=4); }