(20pt) We use the following cell structure to store the IDs and names of some st
ID: 3909584 • Letter: #
Question
(20pt) We use the following cell structure to store the IDs and names of some students in a single linked list data structure typedef struct cell ( int ID; char name [20]; struct cell *next; cellT; Suppose somehow we have already 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 Both lists are sorted with respect to (w.r.t.) IDs. 10 T.T" NULL T. K A. Z 14 N. K "P.T ZE NULL Now we are interested in creating a new list, say D, to store the IDs and names of the students who are taking Math but NOT Science. As you may know this operation is known as difference of two sets (M - S) such that D contains the elements that appear in M but NOT in S. So list D will look like as follows (elements in list D should be sorted w.r.t. IDs, as in the original lists): 10 T. T." NULL You are asked to implement cellT difference M_S (cellT *M, cellT s), which can be called as follows to find the difference between M and S. cellT *M, S,*D; / somehow the lists pointed by M and s are created / D difference MS (M, S) ; After your function, M and S should be intact. So do not remove the cells from M or S! When needed, create new cells and copy the IDs and names from the cells in MExplanation / Answer
//ptr1 will point to M list and
//ptr2 will point to S list
//the logic is, M and S both are in ascending order with their IDs
//So, we check M IDs with S IDs that are lessthan M ID number
//if ptr2 is pointing to greater number(ID) ptr1 pointing ID,
//then it is M-S node. we can copy to D list
//function that returns a cellT node
cellT *difference_M_S(cellT *M,cellT *S)
{
cellT *D=NULL,*ptr1,*ptr2;
//ptr1 will point to M list and
//ptr2 will point to S list
ptr1=M;
ptr2=S;
//we concered about nodes that are in M but not in S
//so we just need check all the nodes in M
//that why until ptr1 not equals to null
while(ptr1!=NULL)
{
//if both ID's are same, then increment both pointers
if(ptr2.ID==ptr1.ID){
ptr1++;
ptr2++;
}
//if ptr2's id is greater than ptr1's id
else if(ptr2.ID>ptr1.ID)
{
//creating a new node
cellT *newNode=(cellT*)malloc(sizeof(cellT));
//copying id and name from ptr1 node to new node
newNode.ID=ptr1.ID;
newNode.name=ptr1.name;
newNode.next=NULL;
//if D empty list,then new node will be the D
if(D==NULL)
D=newNode;
//else we assign it to next of D node
else
D.next=newNode;
//increment to next node to check further
ptr1++;
}
//increment ptr2 to check further
else
{
ptr2++;
}
}
//return final D list to main
return D;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.