home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
The C Users' Group Library 1994 August
/
wc-cdrom-cusersgrouplibrary-1994-08.iso
/
listings
/
v_09_07
/
9n07018a
< prev
next >
Wrap
Text File
|
1991-05-22
|
9KB
|
328 lines
/* --------------------------------------------------------------
This program allocates memory for an array ary, as follows:
struct node ary[MAX_NODES];
Each element of this array represents a link in a linked list. The
user can perform various operations on the whole list or on specific
nodes within it. They may, for example, add, remove, or change a
node, or display or sort the whole list.
-------------------------------------------------------------- */
#include <stdio.h>
#include <ctype.h>
#define MAX_NODES 4 /* max number of nodes in array */
#define EOLIST (-1) /* end-of-list indicator for fwd_ptr */
#define ADD_NODE 'A'
#define CHANGE_NODE 'C'
#define DISPLAY_NODE 'D'
#define EXIT 'E'
#define SEARCH_FNODE 'F'
#define HELP '?'
#define INSERT_NODE 'I'
#define COUNT_NODES 'N'
#define REMOVE_NODE 'R'
#define SORT_NODES 'S'
#define DUMP_LIST 'T'
void init_free_list(void);
int get_free_node(void);
void put_free_node(int node);
struct node {
int value; /* the node's data value */
int fwd_ptr; /* ptr to next node in list */
};
struct node ary[MAX_NODES];
int root_node = EOLIST; /* start of list */
int tail_node = EOLIST; /* end of list */
int free_node = 0; /* next free node */
int nodes_in_use = 0;
/* ----------------------------------------------------------- */
main()
{
int node, new_node;
int temp, i, j, k;
int inchar = 'x'; /* force initial prompt */
int done = 0;
/* ----------------------------------------------------------- */
init_free_list();
while (!done) {
if (inchar != ' ')
printf("\nEnter Action Code (%c for help): ", HELP);
switch(toupper(inchar = getchar())) {
/* ----------------------------------------------------------- */
case EXIT:
done = 1;
break;
/* ----------------------------------------------------------- */
default:
printf("\n Invalid command. Please try again\n");
break;
/* ----------------------------------------------------------- */
case HELP:
printf("\n The action codes are:\n");
printf("\t%c - produces this help message\n", HELP);
printf("\t%c - Add a new node to the end\n", ADD_NODE);
printf("\t%c - Change a user-selected node\n", CHANGE_NODE);
printf("\t%c - Display a user-selected node\n", DISPLAY_NODE);
printf("\t%c - Exit this program\n", EXIT);
printf("\t%c - Search for first occurrence\n", SEARCH_FNODE);
printf("\t%c - Insert a new node\n", INSERT_NODE);
printf("\t%c - Report the number of nodes\n", COUNT_NODES);
printf("\t%c - Remove a user-selected node\n", REMOVE_NODE);
printf("\t%c - Sort the nodes in ascending order\n", SORT_NODES);
printf("\t%c - Show all entries in the list\n", DUMP_LIST);
break;
/* ----------------------------------------------------------- */
case '\n': /* ignore white space on input */
case ' ' :
case '\t':
case '\v':
case '\f':
inchar = ' '; /* indicate white space input */
break;
/* --------------------------------------------------------------
ADD_NODE: The steps to add a new node to the end of the list are:
A. Get a new free node from free node list. If no more, get out.
B. Have a new node so fill it with data.
C. If this is the first node, make it the root otherwise update the
forward pointer from the previous end-of-list node to point to
this new end-of-list node.
D. Indicate this is the new end-of-list node and update tail node.
-------------------------------------------------------------- */
case ADD_NODE:
/*A*/ if ((new_node = get_free_node()) == EOLIST) {
printf("\n List is full\n");
break;
}
/*B*/ printf("\n Enter new node's value: ");
scanf("%3d", &ary[new_node].value);
/*C*/ if (root_node == EOLIST)
root_node = new_node;
else
ary[tail_node].fwd_ptr = new_node;
/*D*/ ary[new_node].fwd_ptr = EOLIST;
tail_node = new_node;
printf("\n Node added");
break;
/* --------------------------------------------------------------
DUMP_LIST: The steps to display all nodes in the list are:
A. Complain if list empty.
B. Traverse list starting at the root node displaying each node's
data and forward pointer.
-------------------------------------------------------------- */
case DUMP_LIST:
/*A*/ if (root_node == EOLIST) {
printf("\n List contains no nodes\n");
break;
}
printf("\n List nodes are as follows:\n");
/*B*/ node = root_node;
while (node != EOLIST) {
printf("\t[%d] => %3d, fwd_ptr: %3d\n", node,
ary[node].value, ary[node].fwd_ptr);
node = ary[node].fwd_ptr;
}
break;
/* --------------------------------------------------------------
COUNT_NODES: Just display the counter we've been keeping.
-------------------------------------------------------------- */
case COUNT_NODES:
printf("\tThere are %d nodes in the list\n", nodes_in_use);
break;
/* --------------------------------------------------------------
DISPLAY_NODE: The steps to display 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 and forward pointer.
-------------------------------------------------------------- */
case DISPLAY_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;
printf("\t[%d] => %3d, fwd_ptr: %3d\n", j,
ary[j].value, ary[j].fwd_ptr);
break;
/* --------------------------------------------------------------
The rest of the cases will be published next month.
-------------------------------------------------------------- */
}
}
return (0);
}
/* ----------------------------------------------------------- */
/* --------------------------------------------------------------
FUNCTION init_free_list
Initialize the list of free nodes using the following steps:
A. Initialize various counters and pointers.
B. Since all nodes are in the free list, have each node point to the
array element immediately following.
C. The last node has a special forward pointer to indicate the
it is the end-of-list.
-------------------------------------------------------------- */
void init_free_list(void)
{
int i;
/*A*/ free_node = 0; /* [0] is first free node */
nodes_in_use = 0;
root_node = EOLIST;
tail_node = EOLIST;
/*B*/ for (i = 0; i < MAX_NODES; ++i)
ary[i].fwd_ptr = i + 1;
/*C*/ ary[MAX_NODES - 1].fwd_ptr = EOLIST;
}
/* --------------------------------------------------------------
FUNCTION get_free_node
Get a node from the free node list using the following steps:
A. Since free_node always points to the first node in the free list,
always return that value. If the free list is empty, free_node
will be EOLIST and that's what we want to return in such a
condition anyway.
B. If there is actually a free node, make free_node point to the next
free node in the list and increment allocated node count. If there
are no more nodes in the free list, free_note will conveniently be
set to EOLIST.
C. Return the subscript of the next available free node or EOLIST.
-------------------------------------------------------------- */
int get_free_node(void)
{
/*A*/ int new_node = free_node;
/*B*/ if (free_node != EOLIST) {
free_node = ary[free_node].fwd_ptr;
++nodes_in_use;
}
/*C*/ return new_node;
}
Output:
Enter Action Code (? for help): a
Enter new node's value: 100
Node added
Enter Action Code (? for help): a
Enter new node's value: 200
Node added
Enter Action Code (? for help): a
Enter new node's value: 500
Node added
Enter Action Code (? for help): t
List nodes are as follows:
[0] => 100, fwd_ptr: 1
[1] => 200, fwd_ptr: 2
[2] => 500, fwd_ptr: -1
Enter Action Code (? for help): n
There are 3 nodes in the list
Enter Action Code (? for help): d
Enter node number: 0
[0] => 100, fwd_ptr: 1