/*--------------------------------------------------------------
CHANGE_NODE: The steps to change a selected node are:
A. Complain if list empty.
B. Get the node number from the user. Note that the first node in the
list is number 0, then 1, 2, etc. The number of the node and the
subscript it occupies in ary are NOT related even though they can
be the same.
C. Traverse list starting at the root node looking for the requested
node. When it is found, display its data.
D. Get the replacement data and update node.
--------------------------------------------------------------*/
case CHANGE_NODE:
/*A*/ if (root_node == EOLIST) {
printf("\n List contains no nodes\n");
break;
}
/*B*/ while (1) {
printf("\n Enter node number: ");
scanf("%d", &node);
if (node >= 0 && node < nodes_in_use)
break;
printf("\n No such node (%d) in list\n", node);
}
/*C*/ j = root_node; /* find nth node */
for (i = 0; i < node; ++i)
j = ary[j].fwd_ptr;
/*D*/ printf("\t[%d] => %3d\n", j, ary[j].value);
printf("\n Enter new value: ");
scanf("%3d", &ary[j].value);
printf("\n Node changed");
break;
/*--------------------------------------------------------------
SEARCH_FNODE: The steps to find the first node with a given value are:
A. Complain if list empty.
B. Get the required node value from user.
C. Traverse list starting at the root node looking for the node with
the requested value. If it's found, display its data else say
there is no such node.
--------------------------------------------------------------*/
case SEARCH_FNODE:
/*A*/ if (root_node == EOLIST) {
printf("\n List contains no nodes\n");
break;
}
/*B*/ printf("\n Enter search value: ");
scanf("%d", &temp);
/*C*/ node = root_node;
i = 0;
while (node != EOLIST) {
if (ary[node].value == temp) {
printf("\tValue %3d found in node %3d\n",
temp, i);
goto found1;
}
node = ary[node].fwd_ptr;
++i;
}
printf("\n No such value (%d) in list\n", temp);
found1:
break;
/*---------------------------------------------------------------------------
SORT_NODES: The steps to sort the nodes in ascending order of value are:
A. Complain if list empty.
B. Perform a simple bubble sort.
--------------------------------------------------------------*/
case SORT_NODES:
/*A*/ if (root_node == EOLIST) {
printf("\n List contains no nodes\n");
break;
}
/*B*/ for (i = nodes_in_use - 2; i >= 0; --i) {
k = root_node;
for (j = 0; j <= i; ++j) {
if (ary[k].value > ary[ary[k].fwd_ptr].value) {
temp = ary[k].value;
ary[k].value = ary[ary[k].fwd_ptr].value;
ary[ary[k].fwd_ptr].value = temp;
}
k = ary[k].fwd_ptr;
}
}
printf("\n Nodes sorted");
break;
/*-----------------------------------------------------------------
INSERT_NODE: The steps to insert a new node in front of an existing
one are:
A. Complain if list empty.
B. Get a new free node from free node list. If no more, get out.
C. Get the node number from the user. Note that the first node in the
list is number 0, then 1, 2, etc. The number of the node and the
subscript it occupies in ary are NOT related even though they can
be the same.
D. Traverse list starting at the root node looking for the requested
node. Then that when we find it we will have gone one node too
many so we must keep track of the next-to-current code.
E. Have a new node so fill it with data.
F. If this is to be the new first node, make it the root otherwise
update the forward pointer from the previous node to point to
this new node. Make the new node's forward pointer point to the
node we are inserting ahead of.
------------------------------------------------------------------*/
case INSERT_NODE:
/*A*/ if (root_node == EOLIST) {
printf("\n List contains no nodes\n");
break;
}
/*B*/ if ((new_node = get_free_node()) == EOLIST) {
printf("\n List is full\n");
break;
}
/*C*/ while (1) {
printf("\n Enter number of node to insert before: ");
scanf("%d", &node);
if (node >= 0 && node < nodes_in_use - 1) /* exclude new
node */
break;
printf("\n No such node (%d) in list\n", node);
}
/*D*/ j = root_node; /* find nth node */
for (i = 0; i < node; ++i) {
temp = j;
j = ary[j].fwd_ptr;
}
/*E*/ printf("\n Enter new node's value: ");
scanf("%3d", &ary[new_node].value);
/*F*/ if (root_node == j)
root_node = new_node;
else
ary[temp].fwd_ptr = new_node;
ary[new_node].fwd_ptr = j;
printf("\n Node inserted");
break;
/*-------------------------------------------------------------------
REMOVE_NODE: The steps to remove a node are:
A. Complain if list empty.
B. Get the node number from the user. Note that the first node in the
list is number 0, then 1, 2, etc. The number of the node and the
subscript it occupies in ary are NOT related even though they can
be the same.
C. Traverse list starting at the root node looking for the requested
node. Then that when we find it we will have gone one node too
many so we must keep track of the next-to-current code.
D. If this is the last node make the tail EOLIST otherwise make tail
point to the node ahead of this one.
E. If this is the first node, make the root point to its successor
node which, if that is EOLIST, is fine. Otherwise make it's
predecessor point to the current node's successor.
F. Free the node.
-------------------------------------------------------------------*/
case REMOVE_NODE:
/*A*/ if (root_node == EOLIST) {
printf("\n List contains no nodes\n");
break;
}
/*B*/ while (1) {
printf("\n Enter node number: ");
scanf("%d", &node);
if (node >= 0 && node < nodes_in_use)
break;
printf("\n No such node (%d) in list\n", node);
}
/*C*/ j = root_node; /* find nth node */
for (i = 0; i < node; ++i) {
temp = j;
j = ary[j].fwd_ptr;
}
/*D*/ if (tail_node == j) {
if (root_node == j)
tail_node = EOLIST;
else
tail_node = temp;
}
/*E*/ if (root_node == j)
root_node = ary[j].fwd_ptr;
else
ary[temp].fwd_ptr = ary[j].fwd_ptr;
/*F*/ put_free_node(j);
printf("\n Node removed");
break;
/*-------------------------------------------------------------*/
The remaining function, that which frees up a node, follows:
/*---------------------------------------------------------------
FUNCTION put_free_node
Release an active node and add it to the front of the free list using
the following steps:
A. The newly freed node always points to the previous list head since
we add to the front of the list. If the list is currently empty,
free_node would be EOLIST and that's what we would want for the
new forward pointer anyway.
B. Make the free_node point to the new head-of-list.
C. Decrement the active node count.
---------------------------------------------------------------------*/
void put_free_node(int node)
{
ary[node].fwd_ptr = free_node;
free_node = node;
--nodes_in_use;
}
/*--------------------------------------------------------------------*/
The results of running this program with some test data are as follows:
Enter Action Code (? for help): t
List nodes are as follows:
[0] => 350, fwd_ptr: 1
[1] => 200, fwd_ptr: 2
[2] => 500, fwd_ptr: -1
Enter Action Code (? for help): i
Enter number of node to insert before: 1
Enter new node's value: 900
Node inserted
Enter Action Code (? for help): t
List nodes are as follows:
[0] => 350, fwd_ptr: 3
[3] => 900, fwd_ptr: 1
[1] => 200, fwd_ptr: 2
[2] => 500, fwd_ptr: -1
Enter Action Code (? for help): s
Nodes sorted
Enter Action Code (? for help): t
List nodes are as follows:
[0] => 200, fwd_ptr: 3
[3] => 350, fwd_ptr: 1
[1] => 500, fwd_ptr: 2
[2] => 900, fwd_ptr: -1
Enter Action Code (? for help): r
Enter node number: 1
node removed
Enter Action Code (? for help): t
List nodes are as follows:
[0] => 200, fwd_ptr: 1
[1] => 500, fwd_ptr: 2
[2] => 900, fwd_ptr: -1
/* End of File */