in c, create a function with the following typedef struct node { ElemType val; s
ID: 656656 • Letter: I
Question
in c, create a function with the following typedef struct node { ElemType val; struct node *next; } NODE; struct list_struct { NODE *front; NODE *back; }; function: lst_merge_sorted * * description: assumes both list a and b are in * sorted (non-descending) order and merges them * into a single sorted list with the same * elements. * * This single sorted list is stored in a while * b becomes empty. * * if either of given lists are not sorted, * we blame the caller and the behavior is * implementation dependent -- i.e., don't worry * about it! * * Example: * * a: [2 3 4 9 10 30] * b: [5 8 8 11 20 40] * * after call on (a,b) * * a: [2 3 4 5 8 8 9 10 11 20 30 40] * b: [] * * implementation: should not allocate ANY new list * nodes -- it should just re-link existing * nodes. * * Must be linear time in the |a|+|b| -- i.e., * the total number of elements being processed. */ void lst_merge_sorted(LIST *a, LIST *b){
Explanation / Answer
extern void lst_merge_sorted(LIST *a, LIST *b);
void lst_merge_sorted(LIST *a, LIST *b){
NODE *aCurr,*bCurr,*aTemp,*bTemp;
aCurr = a->front;
bCurr = b->front;
aTemp = a->front;
bTemp = b->front;
int aLength = 2, bLength = 2;
while(aCurr->next != NULL){
aLength++;
aCurr = aCurr->next;
}
while(bCurr->next != NULL){
bLength++;
bCurr = bCurr->next;
}
int i,j;
for (i = 0; i < aLength; i++){
for(j = 0; j < bLength; j++){
if (bTemp->val < aTemp->val){
bTemp->next = aTemp->next;
aTemp->next = bTemp;
}
bTemp = bTemp->next;
}
aTemp = aTemp->next;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.