Directions: Answers are in red.

1. (20)Here are some simple questions about pointers. Each part is to be used by later parts:
   1. Declare x to be an int. int x;
   2. Declare xp to be a pointer to an int. int *xp;
   3. Give xp a value so that it points to x. xp = &x;
   4. Use xp to give x the value 47. *xp = 47;
   5. At this point, what is the value of *&x. 47;
   6. What does the statement (*xp)++; do? It increments the value of x, to 48
   7. What does the statement *(xp++); do? First it dereferences the address xp points to (returning 48, but no use of the 48 is made here), and then it increments the pointer to x, so that it no longer points to x, but to the next location, whatever is stored there.
   8. Give two forms for the type of an array of strings in C. (If an array of strings was a parameter, how would you declare it?) Either char ** or char *[]
   9. Given the declaration int *a, b;, what is the type of a and what is the type of b? a is an int *, or a pointer to int; b is an int

2. (20)Java has a method in the String class: toLowerCase that converts each character of a string to lowercase if it was uppercase and leaves the other characters unchanged. C only has the function tolower that will convert a single character to lowercase and return it. (If the character is not uppercase, tolower just returns it unchanged.)

   Write a C function to_lower that will take a C string as input parameter, and will return a new malloced string that is a copy of the input parameter except that any uppercase letter has been converted to lowercase. See the function to_lower in the next question.

3. (20)Complete the program below by supplying single function and two calls to this function to print the two arrays of strings (one string to a line). For full credit, your function must not use square brackets. You must use a loop, and you must use the NULL at the end. Here are two solutions printit and printit2.

   File: sins.c

   Runs of sins

   #include <stdio.h> /* prototypes here */ void printitlower(char **p); char *to_lower(char *s); void main(void) { char *sins[] = {"ENVY", "SLOTH", "GLUTTONY", "WRATH", "PRIDE", "LUST", "GREED", NULL}; char *laws[] = {"Trustworthy", "Loyal", "Helpful", "Friendly", "Courteous", "Kind", "Obedient", "Cheerful", "Thrifty", "Brave", "Clean", "Reverent", NULL}; /* 2 calls to the function here */ printit(sins); printf("\n"); printit(laws); printf("\n"); printitlower2(sins); printf("\n"); printitlower(laws); } /* code for the function here */ void printit(char **p) { while (*p != NULL) { printf("%s\n", *(p++)); } } void printit2(char **p) { char *s; while (*p) { s = *p; while (*s) putchar(*s++); putchar('\n'); p++; } } void printitlower(char **p) { while (*p) printf("%s\n", to_lower(*(p++))); } char *to_lower(char *s) { char *t = (char *)malloc(sizeof(char)*(strlen(s) + 1));  char *tsave = t; while (*s != '\0') { *t = tolower(*s); t++; s++; } *t = '\0'; return tsave; }

   % cc -o sins sins.c % sins ENVY SLOTH GLUTTONY WRATH PRIDE LUST GREED Trustworthy Loyal Helpful Friendly Courteous Kind Obedient Cheerful Thrifty Brave Clean Reverent envy sloth gluttony wrath pride lust greed trustworthy loyal helpful friendly courteous kind obedient cheerful thrifty brave clean reverent

4. (20)Standard C has a problem with 2-dimensional arrays -- unlike Java and Fortran, C cannot declare an "ordinary" 2-dimensional array with dimensions determined at run-time, nor can C pass such an array as a parameter. Here "ordinary" means that it is declared as with a[5][4]. All dimensions of such a declaration must be constants known at compile time. Thus the following function is illegal in standard C:

   void f(int m, int n) { double r[m][n]; /* other stuff */ }

   1. In the above example, would it be possible to use malloc to declare r as an array of pointers to 1-dimensional arrays? (Yes or No). If "No", say why not, and if "Yes", say why this method nevertheless might not be used.Yes, you can always malloc an array of pointers to 1-dimensional arrays, and then malloc each of the 1-dimensional arrays, assigning them to each of the original pointers. The dimensions do NOT need to be constants and do NOT need to be known at compile time. In ordinary C programs, one would not want to proceed this way mainly for efficiency reasons, since this approach would slow things down (as it does in Java).
      This approach in C also requires explicit freeing of storage: first the 1-dimensional arrays and then the array of pointers.

      For the above reasons, it is not straightforward to write a function in C that will take an arbitrary 2-dimensional array as input parameter. Instead, one must resort to trickery, as in the following examples:

#include <stdio.h>


int index(int i, int j, int n);
void readarray(double *r, int m, int n);
void writearray(double *r, int m, int n);

int main() {
   int m, n; /* m-by-n arrays */
   double *r;
   scanf("%i %i", &m, &n);
   r = (double *)malloc(sizeof(double)*m*n);
   readarray(r, m, n);
   writearray(r, m, n);
}

void readarray(double *r, int m, int n) {
   int i, j;
   for (i = 0; i < m; i++)
      for (j = 0; j < n; j++) {
         scanf("%lf", &r[index(i, j, n)]);
      }
}

void writearray(double *r, int m, int n) {
   int i, j;
   for (i = 0; i < m; i++) {
      for (j = 0; j < n; j++)
         printf("%6.1f", r[index(i, j, n)]);
      printf("\n");
   }
}

/* DEFINITION FOR FUNCTION "index" HERE */
int index(int i, int j, int n) {
   return i*n + j;
}
% cat arr.txt
3 4
1.0  2.0  3.0  4.0
11.0  12.0  13.0 14.0
21.0  22.0  23.0 24.0
31.0  32.0  33.0 34.0
% cc -o arr arr.c
% arr < arr.txt
   1.0   2.0   3.0   4.0
  11.0  12.0  13.0  14.0
  21.0  22.0  23.0  24.0

#include <stdio.h>
/* DEFINITION FOR MACRO "R" HERE */
/* #define R(i, j, n)  r[(i)*(n) + (j)] */
#define R(i, j, n)  *(r + (i)*(n) + (j))
void readarray(double *r, int m, int n);
void writearray(double *r, int m, int n);

int main() {
   int m, n; /* m-by-n arrays */
   double *r;
   scanf("%i %i", &m, &n);
   r = (double *)malloc(sizeof(double)*m*n);
   readarray(r, m, n);
   writearray(r, m, n);
}

void readarray(double *r, int m, int n) {
   int i, j;
   for (i = 0; i < m; i++)
      for (j = 0; j < n; j++) {
         scanf("%lf", &R(i, j, n));
      }
}

void writearray(double *r, int m, int n) {
   int i, j;
   for (i = 0; i < m; i++) {
      for (j = 0; j < n; j++)
         printf("%6.1f", R(i, j, n));
      printf("\n");
   }
}





% cat arr.txt
3 4
1.0  2.0  3.0  4.0
11.0  12.0  13.0 14.0
21.0  22.0  23.0 24.0
31.0  32.0  33.0 34.0
% cc -o arr2 arr2.c
% arr2 < arr.txt
   1.0   2.0   3.0   4.0
  11.0  12.0  13.0  14.0
  21.0  22.0  23.0  24.0

2. For use on the left, give a definition for a function index that will return the correct value for use in the program. See function index above.

3. For use on the right, give a macro definition for a macro R that will return the correct value for use in the program. Two different macros are given above, one commented out.

4. (Extra credit) Can you think of some other (perhaps better) way to do this?

5. (20)Suppose we are using hashing with open addressing to insert into a hash table h of size 11 (an array of pointers to char, each initially NULL, with indexes from 0 through 10, inclusive). We want to insert the following items into this table.

   Items to insert	Diagram of array
   "rat", with hash("rat") == 8 "cat", with hash("cat") == 10 "dog", with hash("dog") == 8 "pig", with hash("pig") == 9 "cow", with hash("cow") == 0 "bat", with hash("bat") == 0	h[0] ---> "pig" h[1] ---> "cow" h[2] ---> "bat" h[3] ---> NULL h[4] ---> NULL h[5] ---> NULL h[6] ---> NULL h[7] ---> NULL h[8] ---> "rat" h[9] ---> "dog" h[10]---> "cat"

   1. Show in a diagram the result of inserting into the array the above items with the given hash values. (Assume that the search goes to the next larger item, and wraps around.) See above at the right.

   2. In the above situation, if one now wants to delete the entry for "pig", explain why it doesn't work to just set the pointer equal to NULL. Say what we did in class to handle this problem. The naive method would just replace the pointer in h[0] (where "pig" ends up) with NULL. This will make a search for "cow" or "bat" fail, however, since in looking up "cow", we start at hash address 0 and terminate the lookup because there is a NULL at this address.

      Instead one can use a special entry in h[0]. It can be anything at all (such as -1 or a pointer to a string that is never used as a legitimate entry). The software interprets this entry as "deleted", and skips over it in searches. (Actually, a "deleted" entry could be used for insertions.)

      One could recreate the hash table to eliminate "deleted" entries. There is a clever algorithm (not presented in the course), that rearranged entries in a minimal way on deletions, so that no "deleted" category is needed.

6. (20)Consider the following incomplete program (left) and data (right):

   File: adjlist.c

   Run of: adjlist

   #include <stdio.h> #include <stdlib.h> #include <stdlib.h> #define N 5 struct gnode { int v; int dist; struct gnode *next; }; void adjlist(struct gnode *g[]); void insert(struct gnode *g[], int v1, int v2, int d); int main(void) { struct gnode *g[N]; int i; for (i = 0; i < N; i++) g[i] = NULL; adjlist(g); } void adjlist(struct gnode *g[]) { /* POSSIBLE ADDITIONAL DECLARATION(S) HERE */ /* because of the separate function, none needed */ FILE *edges; int i; int v1, v2, d; for (i = 0; i < N; i++) g[i] = NULL; if ((edges = fopen("edges.dat", "r")) == NULL) { printf("Can't open file: edges.dat\n"); exit(1); } while (fscanf(edges, "%i %i %i", &v1, &v2, &d) != EOF) { /* PUT PART OF YOUR ANSWER HERE */ insert(g, v1, v2, d); } } /* POSSIBLE ADDITIONAL FUNCTION(S) HERE */ void insert(struct gnode *g[], int v1, int v2, int d) { struct gnode *t = (struct gnode *) malloc(sizeof(struct gnode)); t -> v = v2; t -> dist = d; t -> next = g[v1]; g[v1] = t; } void dumpgraph(struct gnode *g[]) { int i; struct gnode *p; for (i = 0; i < N; i++) { printf("g[%i]:", i); p = g[i]; while (p != NULL) { printf("-->(%i,%i)", p -> v, p -> dist); p = p -> next; } printf("-->NULL\n"); } }

   % cat edges.dat 0 1 10 0 3 5 1 2 1 1 3 2 2 4 4 3 1 3 3 2 9 3 4 2 4 0 7 4 2 6 % cc -o adjlist adjlist.c % adjlist g[0]:-->(3,5)-->(1,10)-->NULL g[1]:-->(3,2)-->(2,1)-->NULL g[2]:-->(4,4)-->NULL g[3]:-->(4,2)-->(2,9)-->(1,3)-->NULL g[4]:-->(2,6)-->(0,7)-->NULL

   1. The numbers at the right above describe a directed graph, where first come two vertices, the starting and ending vertex of an edge, and then the weight of the edge. The graph has 5 vertices: 0, 1, 2, 3, and 4. Draw a diagram showing the adjacency list representation of this graph. This diagram is printed above on the right by the dumpgraph function above on the left.

   2. The program on the left above reads the data at the right: a list of pairs of vertices representing a directed edge, each pair followed by a number representing the weight on the edge. The program should then construct the adjacency list representation of the graph as it was presented in the course. The program is missing the key code that actually inserts each new edge into the adjacency list and puts in the weight. Otherwise the program is complete. You are to supply the missing code. (Some code must be supplied inside the while loop. You may want to or need to supply one or more additional declarations or functions.) See the red code above on the left for one solution.

7. (20)Consider the array: int A[] = {0, 7, 29, 10, 14, 8, 9, 2, 3, 11};, where A[0] is not used.
   1. Write this array in diagram form as a complete binary tree.
   2. Show on the diagram how to convert this tree to a heap. (Just move elements around, crossing out as you go. Ignore element A[0]. You must write this carefully enough so that I can read it.)
   3. Show the first step of heapsort, where the largest element ends up in its proper place, and the heap property is restored for the remaining elements. The first three diagrams of diagrams shows answers to these questions.