5. (20 pt) We use the following cell structure to store the IDs and names of som
ID: 3912201 • Letter: 5
Question
5. (20 pt) We use the following cell structure to store the IDs and names of some students in a sing linked list data structure typedef struct cell ( int ID; char name [20]; struct cell next,; ) cellT, cellPtrT; Suppose somehow we have created the following two single linked lists, namely M and S, to store the IDs and names of the students who are taking Math and Science, respectively. Lists are sorted w.r.t. IDs. "T K." A. Z." NULL 14 W.A. NULL "N. K T.K Z. E P.T Now we are asked to write a function that removes/eliminates the common students from both lists such that each list will only contain the students who are not in the other list. After calling your function, the resulting lists M and S should be as follows (still sorted w.r.t. IDs). 14 W.A." NULL "N. K. Z. E Implement a function, void remove_common_students (cellT "ptrM, cellT *ptrs), which can be called as follows to remove/eliminate the common students from both lists cellT *M, *S; / somehow the lists pointed by M and S are created / remove_common students ( M, &S;) fter your function, M and S should be changed as you need to remove the common cells from M and S!Explanation / Answer
#include <stdio.h>
#include <stdlib.h>
typedef struct cell
{
int ID;
struct cell *next;
} cellT, *cellPtrT;
void remove_common_elements(cellT **ptrM, cellT **ptrS)
{
cellT *M, *S, *prevM=NULL , *prevS =NULL, *nextCell;
M = *ptrM;
S = *ptrS;
while (M != NULL && S != NULL) {
//If both the IDs are same(i.e. common students in both the subjects)
if (M->ID == S->ID)
{
nextCell = M->next; //move the current student's next pointer to temporary node
free(M); //remove the common student in one list (Maths list)
if(prevM == NULL) //if the common student is the first student in this list
*ptrM = nextCell; //make the next student in the list as first student
else
prevM->next = nextCell; //else not a first student, then make the previous student's next pointer pointing to common student's next pointer
M= nextCell; //now proceed with the next student after the common student in the list
nextCell = S->next; //move the current student's next pointer to temporary node
free(S); //remove the common student in one list (Science list)
if(prevS == NULL) //if the common student is the first student in this list
*ptrS = nextCell; //make the next student in the list as first student
else
prevS->next = nextCell;//else not a first student, then make the previous student's next pointer pointing to common student's next pointer
S= nextCell;//now proceed with the next student after the common student in the list
}
// IF current Student Id in Maths list is greater than current Student ID in science list
else if (M->ID > S->ID)
{
prevS = S; //make current student as previous student traversed in the list
S = S->next; //traverse only the science list
}
else
{ // // IF current Student Id in Science list is greater than current Student ID in maths list
prevM = M; ////make current student as previous student traversed in the list
M = M->next; //traverse only the maths list
}
}
}
cellPtrT createNode(){
cellPtrT temp; // declare a node
temp = (cellPtrT)malloc(sizeof(struct cell)); // allocate memory using malloc()
temp->next = NULL;// make next point to NULL
return temp;//return the new node
}
cellPtrT addNode(cellPtrT head, int value){
cellPtrT temp,p;// declare two nodes temp and p
temp = createNode();//createNode will return a new node with data = value and next pointing to NULL.
temp->ID = value; // add element's value to data part of node
if(head == NULL){
head = temp; //when linked list is empty
}
else{
p = head;//assign head to p
while(p->next != NULL){
p = p->next;//traverse the list until p is the last node.The last node always points to NULL.
}
p->next = temp;//Point the previous last node to the new node created.
}
return head;
}
void print(cellT *head)
{
cellT *temp = head;
while(temp != NULL)
{
printf("%d, ",temp->ID);
temp = temp->next;
}
printf(" ");
}
int main()
{
struct cell *head1 = NULL;
head1=addNode(head1,1);
head1=addNode(head1,3);
head1=addNode(head1,5);
head1=addNode(head1,7);
head1=addNode(head1,8);
print(head1);
struct cell *head2 = NULL;
head2=addNode(head2,1);
head2=addNode(head2,3);
head2=addNode(head2,6);
head2=addNode(head2,8);
print(head2);
remove_common_elements(&head1,&head2);
print(head1);
print(head2);
return 0;
}
output:
1, 3, 5, 7, 8,
1, 3, 6, 8,
5, 7,
6,
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.