Q.Answer the following questions regarding (noncircular) doublylinked lists im
ID: 3737520 • Letter: Q
Question
Q.Answer the following questions regarding (noncircular) doublylinked lists implemented using the Node struct definition as given in file dnode.h. Assume that T has been defined and use it wherever the list element type is needed. Note: you are not required to implement these functions in a program that runs, but you can if you want to.
1. (6 points) Write a function is_ascending that receives the head (node) pointer of a doublylinked list and returns true if the items are in strictly ascending order (compared using operator<); false otherwise.
2. (7 points) Write a function remove_duplicates that receives the head (node) pointer of a doublylinked list and removes any duplicates in the list. This can be done by having one scanning pointer that is used to scan the list and for each item, use another scanning pointer that is used to look for duplicates (as defined by operator==) starting with the next item.
3. (7 points) Write a function split_list that receives a head (node) pointer of a doublylinked list and a target data value, and passes back the head pointers for two new doublylinked lists. The first list will contain copies of the items that are less than the target value (compared using operator<) in the same order as they are given in the source list, and the second list will contain copies of all other items (i.e., those greater than or equal to the target value) in the same order as they are given in the source list.
Note that the source list is not in any particular order, and the source list should not be modified by this function
Explanation / Answer
/**************************************************************
Definition of is_ascending function.
This function will return true if list is in ascending order
otherwise it return false
**************************************************************/
bool is_ascending(struct Node* head){
//Initiallizing ptr to head
struct Node *ptr = head;
//loop will run till the last node of the list
while(ptr!=NULL){
if(ptr->data >= ptr->next-data){
return false; //list is not in ascending order
}
ptr = ptr->next;
}
return true;
}
/**************************************************************
Definition of remove_duplicates function.
This function will remove the duplicate item (if any)
from the list.
**************************************************************/
void remove_duplicates(struct Node *head){
struct Node *ptr,*ptrNext;
ptr = head;
while(ptr!=NULL){
ptrNext = ptr->next;
while(ptrNext!=NULL){
if(ptr->data == ptrNext->data){
if(ptrNext->next == NULL){
ptrNext->prev->next == NULL;
free(ptrNext);
}else {
ptrNext->prev->next = ptrNext->next;
free(ptrNext);
}
}
ptrNext = ptrNext->next;
}
ptr = ptr->next;
}
}
/**************************************************************
Definition of split_list function.
This function will divide list in two new list such that one new
list will contain the value lesser than the passed value and second
new list will contain greater or equal value of passed value.
The source list will not be modified.
**************************************************************/
void split_list(struct Node *head,int value,struct Node *head1,struct Node *head2){
struct Node *ptr,*ptr1,*ptr2;
ptr = head; //pointer of source list initializingwith the head of source list.
ptr1 = head1; //pointer of first newly list initializingwith the head of first list.
ptr2 = head2; //pointer of second newly list initializingwith the head of second list.
while(ptr!=NULL){
/*If source list value is lesser than the passed value, it will be added in the first newly list*/
if(ptr->data < value){
/*If node is the first node of this new list*/
if(ptr1 == NULL){
ptr1 = ptr;
ptr1->next = NULL;
ptr1->prev = head1;
/*Otherwise all other node will be added as the last nodeof this list */
}else{
while(ptr1!=NULL){
ptr1 = ptr1->next;
}
ptr1 = ptr;
ptr1->next = NULL;
}
/*If source list value is greater than the passed value, it will be added in the second newly list*/
}else{
/*If node is the first node of this new list*/
if(ptr2 == NULL){
ptr2 = ptr;
ptr2->next = NULL;
ptr2->prev = head2;
/*Otherwise all other node will be added as the last nodeof this list */
}else{
while(ptr2!=NULL){
ptr2 = ptr2->next;
}
ptr2 = ptr;
ptr2->next = NULL;
}
}
ptr = ptr->next;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.