CS 305 Test 3

CS 305, Computer Algorithms I

Fall 2003 - Test 3

In class we derived an expression to map indices to array elements. That derivation depended on knowing the address of the first array element.
Derive the expression to map indices to array elements when we know the address of the last array element. Don't forget to explain your derivation. You should assume C++ style arrays and only answer the question for 1-dimensional arrays.
See test 1 for the answer.
How does type restrict pointers? That is, if T1 and T2 are types, and t1p and t2p are variables of type T1 * and T2 * respectively, what's the difference between t1p and t2p?
If p is a pointer variable of type T *, then p contains the address of a memory location related to a value of type T.
The differences between t1p and t2p is the type of the values to which each pointer variable refers.
Write a recursive function to count the elements in a list. Your function should be recursive and work for all valid lists.
```
unsigned count_links(link_list_node * np)

  if np == null
    return 0
  else
    return 1 + count_links(np->next)
```
The swap(a, b) operator swaps the values of its two operands. For example
```
int i = 3
int j = 4

swap(i, j)

// j = 3
// i = 4
```
Write a function that uses swap() to exchange two elements in a linked list. Your function must exchange the elements themselves, not just the values stored in the elements, and should work for any two valid list elements (you may not assume the two elements are different).
To simplify matters, assume we have pointers to the linked-list nodes before the elements to be swapped.
```
void exchange(linked_list_node * np1, linked_list_node * np2)

  swap(np1->next->next, np2->next->next)
  swap(np1->next, np2->next)
```

This page last modified on 3 November 2003.