(Linked List with Header and Trailer Nodes) This chapter defined and identified
ID: 3630182 • Letter: #
Question
(Linked List with Header and Trailer Nodes) This chapter defined and identified various operations on a linked list with header and trailer nodes.a. Write the definition of the class that defines a linked list with header and trailer nodes as an ADT.
b. Write the definitions of the member functions of the class defined in (a). (You may assume that the elements of the linked list with header and trailer nodes are in ascending order.)
c. Write a program to test various operations of the class defined in (a).
Explanation / Answer
Dear,
#include <stdio.h>
#include <stdlib.h>
#define SIZE 6
struct NODE
{
int data;
NODE *next;
};
NODE *deleteNode(NODE *list, int sim)
{
NODE *prevNODE, *curNODE;
prevNODE = curNODE = list;
while(curNODE != NULL)
{
if( (curNODE -> data) == sim )
{
prevNODE -> next = curNODE -> next;
if(curNODE == list)
{
list = (NODE *)prevNODE -> next;
}
printf(" Deleting NODE %d...", curNODE -> data);
free(curNODE);
return list;
}
prevNODE = curNODE;
curNODE = (NODE *)curNODE -> next;
}
printf(" NODE %d not found... ", sim);
return list;
} // End of deleteNode
NODE *insertNode(NODE *list, NODE *newNode, int pos)
{
NODE *cur, *nxt;
int count = 0;
cur = nxt = list;
while(nxt != NULL)
{
if(count++ == pos)
{
newNode->next = nxt;
if(nxt != list)
{
cur -> next = (NODE *) newNode;
printf(" Inserting NODE %d at %d pos", newNode -> data, pos);
return list;
}
printf(" Inserting NODE %d at %d pos", newNode -> data, pos);
return newNode;
}
cur = (NODE *)nxt;
nxt = (NODE *)nxt -> next;
}
printf(" Position out of bounds ...");
printf(" Unable to insert NODE %d at %d position.", newNode -> data, pos);
return list;
}// End of insertNode
NODE *createList(int size)
{
NODE *list, *head;
list = head = NULL;
if(size <= 0)
{
printf(" Enter valid size of the linked list. ");
return list;
}
list = (NODE *)malloc(sizeof(NODE));
head = list;
list -> data = size;
while(--size)
{
list -> next = (NODE *)malloc(sizeof(NODE));
list = (NODE *)list -> next;
list -> data = size;
}
list -> next = NULL;
return head;
}// End of createList
/* Reverse a single linked list non-recursively */
NODE *reverseList(NODE *list)
{
NODE *prev, *cur, *last, *next;
if(list -> next == NULL)
{
printf(" Cannot reverse list, because only one node is present in the list.");
return list;
}
printf(" Reversing the list......non-recursive mode.");
prev = cur = last = next = list;
cur = (NODE *)(list -> next);
next = (NODE *)(cur -> next);
while(cur != NULL)
{
cur -> next = prev;
last -> next = next;
prev = cur;
cur = next;
if(next)
{
next = (NODE *)(next -> next);
}
}
return prev;
} // End of reverseList
NODE *reverseList_rec(NODE *list, NODE *prev, NODE *cur)
{
NODE *next, *temp;
if(cur == NULL)
{
return prev;
}
next = cur -> next;
cur -> next = prev;
list -> next = next;
temp = reverseList_rec(list, cur, next);
return temp;
} // End of reverseList_rec
/* Delete nth node from back */
NODE *delete_nth_NODE_from_back(NODE *list, int node_n)
{
NODE *temp, *prev ,*cur;
int count;
if(list == NULL)
{
printf(" Not applicable, List is empty. ");
return NULL;
}
printf(" Deleting %dth node from Single list from back... ", node_n);
cur = prev = NULL;
temp = list;
count = 1;
while(count++ != node_n)
{
temp = temp -> next;
}
cur = list;
while(temp = temp -> next)
{
prev = cur;
cur = cur -> next;
}
/* End of while */
if(cur == list)
{
list = list -> next;
free(cur);
return list;
}
prev -> next = cur -> next;
free(cur);
return list;
} // End of delete_nth_NODE_from_back
/* Deleting the middle node of a list */
NODE *del_mid_node(NODE *list)
{
NODE *temp, *cur, *prev;
int count = 2;
if(list == NULL)
{
printf(" Error: Empty single linked list. ");
return NULL;
}
temp = list;
temp = temp -> next;
cur = list;
while(temp)
{
count++;
if(count % 2 == 0)
{
prev = cur;
cur = cur -> next;
}
temp = temp -> next;
}
if(cur == list)
{
list = list -> next;
free(cur);
return list;
}
prev -> next = cur -> next;
free(cur);
return list;
} // End of del_mid_node
void displayList(NODE *list)
{
printf(" ");
while(list != NULL)
{
printf(" %d ->", list -> data);
list = (NODE *)list -> next;
}
printf(" NULL ");
} // End of displayList
void freeList(NODE *list)
{
NODE *temp;
while(list != NULL)
{
temp = list;
list = (NODE *)list -> next;
printf(" Freeing NODE %d... ", temp -> data);
free(temp);
}
} // End of freeList
int main()
{
NODE *head;
head = (NODE *)createList(SIZE);
displayList(head);
head = (NODE *)deleteNode(head, 1);
displayList(head);
printf(" Deleting middle node from this list. ");
head = (NODE *)del_mid_node(head);
displayList(head);
NODE *newNode = (NODE *)malloc(sizeof(NODE));
newNode -> data = 59;
head = (NODE *)insertNode(head, newNode, 1);
displayList(head);
printf(" Reversing the Single list recursively...");
head = (NODE *)reverseList_rec(head, head, head -> next);
displayList(head);
head = (NODE *)deleteNode(head, 59);
head = (NODE *)deleteNode(head, 2);
displayList(head);
head = (NODE *)delete_nth_NODE_from_back(head, 1);
displayList(head);
head = (NODE *)reverseList(head);
displayList(head);
printf(" Reversing the Single list recursively...");
head = (NODE *)reverseList_rec(head, head, head -> next);
displayList(head);
freeList(head);
return 0;
} // End of main
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.