Print the information field of each stock record of the list-structure brokerage (shown in Figure 6.1(e)) which was bought prior to a specified date and which we store in date. A solution may be obtained by traversing brokerage and printing the relevant stock records. To do this requires only that we write the process function invoked by traverse. Either the recursive or the nonrecursive version may be used. The function process must be written to turn traverse into a solution to this problem.
The task is straightforward except for the determination, within process, of whether the record it is to process is currently a stock record. Since only stock records are simple, a test for complexity of the current record will provide this nformation. Process may be written as where prior returns true if datebought of the record pointed to by ptr is prior to date, and false otherwise, and printinfo prints the information field value of the record pointed to by ptr. n
process (pls, ptr)
/* Print the stock record of ls
pointed to by ptr if it was
bought prior to date
*/
liststructurepointer *pls, ptr;
{
if(!complex(ptr) && prior(ptr,&date))
printinfo (ptr);
}
Example 6.7
Consider again the list-structure brokerage in Figure 6.1(e). The task now is to print, for each client, the total value of his or her portfolio. n
In detail, what has to be done is
1. To traverse brokerage, and each time a client's record is encountered
2. Print the name
3. Then accumulate the total value of the portfolio as it is being traversed
4. Print this total when the portfolio has been completely traversed
While this seems straightforward and simple enough, some details require attention. We can apply the traverse function to this task. To do so, process must be written to turn traverse into a solution. Thus process must be able to recognize when the record it is to work on is a client's record. At this point, it must initialize the accumulated total to zero. For each ensuing record of the client's portfolio, it must then update the accumulated total by the value of that record's stock. Finally, process must recognize the end of the portfolio list and print the accumulated total.
If total is used to store the accumulated value, then it must be preserved between calls to process. This can be achieved by making total a static variable in process or by making total global. We choose the former. Process may be written as follows.
The if conditions are used to determine if this is the first call to process for a portfolio and, if so, to initialize and print the client's name or, after updating a client's total, to see if the record is the last of a portfolio. Assume null is nonlocal to process. Process will work with either version of traverse.
Example 6.8
Suppose book, the list-structure shown in Figure 6.1(c), stores the current version of a text that you wish to modify by replacing the current paragraph p of page pg of chapter c with a new paragraph. The new paragraph is stored as a list newp. To solve this problem we will write a new nonrecursive traverse function, called paragraphinsert, tailored to the situation. Since not all records of book need to be accessed, we do not want to traverse the entire list-structure as we have done in the previous two examples. Two versions of the function are presented. In both versions the idea is to
1. Traverse the main list searching for chapter c
2. Traverse that chapter's sublist searching for page pg
3. Traverse that page's sublist searching for paragraph p
4. Finally, replace that paragraph with newp n
The first version assumes that records representing chapters, pages, or paragraphs have a number field. In the case of a chapter record the field contains the number of that chapter; for a page record it contains the number of that page; and for a paragraph it contains the number of that paragraph. These field values are shown in Figure 6.1(c). The program keeps track of whether it is currently looking for a chapter, a page, or a paragraph by using a variable currentlist. The value stored in currentlist will be CH (denoting that the search is now for a chapter), PAGE (denoting that the search is for a page), or PAR (denoting the search is for a paragraph) . Similarly, a variable currentnumber will keep track of the particular chapter, page, or paragraph number currently being sought by the search. A variable ptr keeps track of the record currently being processed. Once the search for a chapter or a page is complete, currentlist, currentnumber, and ptr must be updated. Once the search for a paragraph has completed, the searching terminates and the new paragraph replaces the old.
Version 1
Setsublist sets the sublist field of the record pointed to by its first parameter to the value of its second parameter. Just before setsublist is invoked, code (not shown here) could be inserted to reclaim the storage used by the replaced paragraph. This is also true for the second version.
The second version assumes no number field, so the records are indistinguishable. Hence they must be kept in order?/FONT>that is, chapters are in order on the main list, pages are in order on their lists, etc. Note that this ordering is not required by the first version. Now a count of list records must be maintained, to determine when the appropriate record number has been encountered. In the second version below only the differences between it and the first version have been annotated. Notice that this second program requires less storage for the list-structure (as the number fields are not needed), but it does somewhat more processing. Also, the sublists must be kept in order. This is another example of trading storage for time.
Version 2
Example 6.9
Consider again the list-structure formula shown in Figure 6.4. It may be interpreted as representing the formula
Notice that each complex record's sublist is an arithmetic expression that must be evaluated. Thus the operand each represents must be obtained before the operator represented by the list on which it appears may be evaluated. For example, the sublists of complex records 2 and 22 must be evaluated before QT of record 1 can be applied to them.
The task is to write a function evaluate to return the value of an arithmetic expression represented by a list-structure. As with formula, the evaluation can be accomplished by traversing the expression's main list and, whenever a complex record is encountered, evaluating its sublist. When the last list record has been processed in this way, the operator and each of its operands are known. The final result is obtained by applying the operator to its known operands. Of course, in evaluating an operand, more complex records may be encountered, such as record 4, and they must then be evaluated before continuing. A process function can be written to turn either the recursive or the nonrecursive traversal program into evaluate.
One important detail remains: how to store the operands that are generated during the traversal so that they are available when needed. Suppose each operand encountered by process is stored in an operand stack, and each operator encountered is stored in an operator stack. If the current record being processed is the last record of a list (its link value is null), then the operator currently at the top of the stack will have its operands at the top of the operand stack. Process can then pop both these stacks, apply the operator to the operands, and place the result back onto the operand stack. If the record being processed represents the last record on the main list (the operator stack will then be empty), instead of placing the result on the operand stack it should copy it into evaluate.
A detailed description of process follows.
If next(ptr) is not null and the record pointed to by ptr is simple, then
if it contains an operator, then
place the operator on the operator stack
else
place the operand on the operand stack
else
pop the operator stack, remove the top k operands from the operand stack (k is
the number of operands of the operator just popped), and apply the operator to
the k operands.
If the operator stack is not empty then
push the result onto the operand stack
else
set evaluate to the result.
This solution may also be applied to the evaluation of logical or boolean expressions. In fact, it forms the basis of the interpretive language LISP.
We have now seen a number of applications of traverse to examples involving list-structures. The example, presented next, is not discussed in detail but points out another possible application.
Example 6.10
Suppose polynomials are represented as p is in Figure 6.1(d). It is then possible to write functions to perform important algebraic operations on polynomials such as the addition and multiplication of two polynomials. Even symbolic differentiation can be performed. Note that traversal of the list-structures representing the polynomials would form the heart of such functions. n
process(ptr)
/* If the current record points to a
client's portfolio record that client's
total portfolio value is updated.
If the record is the last record on
the client's portfolio list its total
value is printed.
*/
liststructurepointer null,setnull(),
sublist(),next();
float value();
static float total;
null = setnull();
if(complex(ptr))
if(sublist(ptr) != null)
if(!complex(sublist(ptr)))
{total = 0.0;
printname(ptr);
}
else
{total = total + value(ptr);
if(next(ptr) == null)
printf("\n Portfolio value is%12.2f \n",total);
}
}
#define CH 1
#define PAGE 2
#define PAR 3
#define TRUE 1
#define FALSE 0
paragraphinsert(book,newp,c,pg,p)
/* Replaces paragraph p of page pg
of chapter c of book by the
paragraph pointed to by newp.
Assumes the records of book contain
number fields.
*/
liststructurepointer book,newp;
int c,pg,p;
{int currentnumber,currentlist,found;
liststructurepointer null,ptr,setnull(),next(),sublist();
null = setnull();
ptr = book;
currentnumber = c;
currentlist = CH;
found = FALSE;
while(!found && (ptr != null))
{if(currentnumber != number(ptr))
ptr = next(ptr);
else
switch(currentlist)
{case CH:
currentlist = PAGE;
currentnumber = pg;
ptr = sublist(ptr);
break;
case PAGE:
currentlist = PAR;
currentnumber = p;
ptr = sublist(ptr);
break;
case PAR:
found = TRUE;
}
}
if(found)
setsublist(ptr,newp);
else
printf("\n Paragraph not found \n");1 print message
}
#define CH 1
#define PAGE 2
#define PAR 3
#define TRUE 1
#define FALSE 0
paragraphinsert(book,newp,c,pg,p)
/* Replaces paragraph p of page pg
of chapter c of book by the
paragraph pointed to by newp.
Assumes the sublists of book are
in order.
*/
liststructurepointer book,newp;
int c,pg,p;
{int currentnumber,count,currentlist,found;
liststructurepointer null,ptr,setnull(),next(),sublist();
null = setnull();
ptr = book;
currentnumber = c;
currentlist = CH;
found = FALSE;
count = 1;
while(!found && (ptr != null))
{if(currentnumber != count)
{count++;
ptr = next(ptr);
}
else
switch(currentlist)
{case CH:
currentlist = PAGE;
currentnumber = pg;
count = 1;
ptr = sublist(ptr);
break;
case PAGE:
currentlist = PAR:
currentnumber = p;
count = 1;
ptr = sublist(ptr);
break;
case PAR:
found = TRUE;
}
}
if(found)
setsublist(ptr,newp);
else
printf("\n Paragraph not found \n");}
. This happens to be the root of the quadratic equation ax2 + bx + c = 0. In formula the symbols QT, PS, TS, MS, DIFF, and SQ stand for the operations of division, addition, multiplication, changing sign, taking the difference, and taking the square root, respectively. The square root and sign change operations apply to one operand. The others apply to two operands. The main list (and each sublist) represents an arithmetic expression. Their first records contain an arithmetic operator such as QT, PS, TS, MS, and DIFF. Their remaining list records represent the operand values of that arithmetic operator. The expression represented by such a list is to be evaluated by applying the operation to its operands. Thus sublist 4 would be evaluated by multiplying the operands in records 13 and 14 (b and b respectively), together. n