I am writing a program in C that manipulates the items of linked list. My progra
ID: 3870781 • Letter: I
Question
I am writing a program in C that manipulates the items of linked list. My program goes as follow:
// following are the given functions I am given to exploit:(funtions below are provided to me with all its full code)
//function to convert an array into a list
//create a new link, that contains the value specified in the argument and points to target address as specified in the argument
// deletes the link(temp) and frees the memory as specified in the argument
// check if the list is Null, returns 1 if null, returns 0 if not
// creates and returns an empty list
list newList() {
list result = (list) malloc(sizeof (*result));
}
void destroyList(list the_list){ //deallacates memory for all nodes in the list and the list object itself.
}
//returns the address of first item on the list
1) SO GIVEN THE ABOVE FUNTIONS, I AM TO WRITE A FUNCTION void MoveMaxEnd(list A) that moves all the nodes containing the maximum value to the end of the list. However, I am to do this by moving the nodes and updating the list, but I am not allowed to delete nodes and make a copy at the end. Following the example of desired output:
if the list contains:
A= 13, 100,56,100,5,3,2
after the execution of the MoveMaxEnd(list A)
A should be, A = 13,56,5,3,2,100,100
2) Also I need another function void swapFirstThird(list A), that swaps the first and third elements of the list. The task should be done by adjusting and shifting links, I am not allowed to copy the items of the list.
for example:
if A = 2,3,6,7,8,9
after executing swapFirstThird(A), A should be, A = 6,3,2,7,8,9
Explanation / Answer
Item FindMax(list A)
{
link current = A->first;
Item max = current->item;
while(1)
{
if(current == NULL)
break;
if(current->next!= NULL) //Need to check next of current before using it.
{
if(current->next->item > max) //Can be combined with immediate parent if condition
{
max = current->next->item;
}
}
current = current->next;
}
return max;
}
int MaxCount(Item max, list A)
{
int pos = 0;
link current = A->first;
while(1)
{
if(current == NULL)
break;
if(current->item == max) //Can be combined with immediate parent if condition
{
pos++;
}
current = current->next;
}
return pos;
}
int GetMaxPosition(Item max, list A)
{
int pos = 0;
link current = A->first;
while(1)
{
if(current == NULL)
break;
if(current->item == max) //Can be combined with immediate parent if condition
{
break;
}
current = current->next;
pos++;
}
return pos;
}
void MoveMaxEnd(list A)
{
Item max = FindMax(A);
link head = A->first;
for(Item maxCountIndex = 0; maxCountIndex < MaxCount(max, A); maxCountIndex++)
{
for(Item index = 0; index < GetMaxPosition(max, A); index++)
{
head = head->next;
}
while (head)
{
if(head->next == NULL)
{
head = A->first;
break;
}
else if(head->next != NULL)
{
Item temp =head->item;
head->item = head->next->item;
head->next->item = temp;
}
head = head->next;
}
}
}
Swap function
void swapFirstThird(list &A)
{
link p = A->first;
link p1 = A->first;
link r = A->first;
link r1 = A->first;
while(p1 != p)
{
p1 = p;
p = p->next;
}
while(r1 != A->first->next)
{
r1 = r;
r = r->next;
}
link temp =r->next;
r->next=p->next;
p->next=temp;
r->next->next = p;
A->first = r;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.