Homework 6 Solutions

Consider the following code:
```
	int *int_array = (int *)malloc(sizeof(int) * 40);
	
```
Write a loop that will use scanf to read 40 integers from stdin directly into the elements of the integer array.
Solution: The above code allocates a block of memory that can accommodate 40 integers. In other words, it has allocated an array of 40 integers. You now need to pass the address of each array element to scanf. There are two ways to do this. First you can take the address of each element:
```
	for (i = 0; i < 40; i++)
	    scanf("%d", &int_array[i]);
     
```
Alternatively you can use pointer arithmetic:
```
	for (i = 0; i < 40; i++)
	    scanf("%d", int_array + i);
	
```
(15 points) Consider the following code:
```
     char word[7];
     char *string_ptr;
     int *double_string_ptr;
     int i;

     (1) string_ptr = (char *)malloc(sizeof(char) * 50);
     (2) double_string_ptr = (char **)malloc(sizeof(char *) * 10);
     for (i = 0; i < 10; i++) 
	double_string_ptr[i] = string_ptr + (i * 5);
     
     
```
Further suppose that you are given the following information (all addresses are in base 10):
```
     address of word = 1000
     address of string_ptr = 1008
     address of double_string_ptr = 1012
     address returned by malloc in statement (1) = 5000
     address returned by malloc in statement (2) = 6000
     sizeof(char) = 1
     sizeof(char *) = 4
     
```
1. What is the address of word[4]? We want the address of the fourth element of word[4]. Since word is a character array and since characters are single bytes, the address of word[4] is equal to address(word)+(4*1) which is 1004.
2. What is the value of string_ptr? It is 5000, which is the pointer address returned by malloc and assigned to string_ptr.
3. What is the value of double_string_ptr? It is 6000, which is the pointer address returned by malloc and assigned to string_ptr.
4. What is the value of &string_ptr[6]? string_ptr points to an array of 50 characters. We are asked for the address of the 6th element of this array. Since characters are 1 byte each, the address is string_ptr+(6*1) = 5000 + 6 = 5006
5. What is the value of &double_string_ptr[6]? 6024: double_string_ptr points to an array of 10 character string pointers (char *'s). We are asked for the address of the 6th element of this array. Since pointers are 4 bytes each, the address is double_string_ptr + (6*4) = 6000 + 24 = 6024
6. What is the value of double_string_ptr[4]? 5020: double_string_ptr is an array of character string pointers and we are asked for the value of the 4th pointer. It was assigned the pointer address string_ptr + (4 * 5) = 5000 + 20 = 5020

Draw what one of Dr. Plank's dllists will look like after the following sequence of operations is performed:

	Dllist my_list = new_dllist();
	Dllist one_node = dll_append(my_list, new_jval_i(1));
	Dllist two_node = dll_prepend(my_list, new_jval_i(2));
	Dllist three_node = dll_insert_a(two_node, new_jval_i(3));
        Dllist four_node = dll_insert_b(two_node, new_jval_i(4));

                  ||-----------------------------------------------------------------------
                  \/									  |
my_list --> -------------   -------------   -------------   -------------   ------------- |
            | flink-----|-->| flink-----|-->| flink-----|-->| flink-----|-->| flink-----|-|
          |-| blink     |<--|-blink     |<--|-blink     |<--|-blink     |<--|-blink     |
	  | | val.i = ? |   | val.i = 4 |   | val.i = 2 |   | val.i = 3 |   | val.i = 1 |
          | -------------   -------------   -------------   -------------   -------------
	  |									^
	  |									|
	  |----------------------------------------------------------------------

Write the code question from the first midterm using Dr. Plank's dllist library. Here is a slightly re-written version of the question:

You are to write a function that given two sorted lists of integers, L1 and L2, prints the integers that are common to both lists. For example, if L1 contains the integers 1, 3, 6, 10, 12 and L2 contains the integers 2, 3, 10, 12, 15 then your program should print:

	3
	10
	12

You should assume that the lists are stored as Dllists and that the integers are stored in Jvals in the Dllists.

	void print_common_elements(Dllist L1, Dllist L2) {
	    Dllist list1, list2;  // temporary pointers for iterating thru L1 and L2
	    list1 = dll_first(L1);  // make list1 and list2 point to the first elements in
	    list2 = dll_first(L2);  // their respective lists
	    int value1, value2;     // hold the integer values of the current elements in L1/L2
	    while ((list1 != dll_nil(L1)) && (list2 != dll_nil(L2))) {
		value1 = jval_i(dll_val(list1));
		value2 = jval_i(dll_val(list2));
		if (value1 == value2) {
		    printf("%d\n", value1);
		    list1 = dll_next(list1);
		    list2 = dll_next(list2);
		}
		else if (value1 < value2)
		    list1 = dll_next(list1);
		else
		    list2 = dll_next(list2);
	    }
	}

Write a function called reverse that takes a Dllist as input and returns a new Dllist with the elements of the first Dllist reversed. The first Dllist should be left unaltered. Note that you will have to copy the value fields of nodes in the input list to nodes in the reversed list. Since the value fields are Jvals you can simply pass them to the appropriate function and they will be copied.
Solution 1: The first solution iterates through the elements of the input list and prepends them to the reversed list:
```
	Dllist reverse(Dllist list) {
	    Dllist reversed_list = new_dllist();
	    Dllist list_ptr;

            dll_traverse(list_ptr, list) {
		dll_prepend(reversed_list, dll_val(list_ptr));
	    }
	}
	
```
Solution 2: The second solution iterates through the elements of the input list in reverse order and appends them to the reversed list:
```
	Dllist reverse(Dllist list) {
	    Dllist reversed_list = new_dllist();
	    Dllist list_ptr;

            dll_rtraverse(list_ptr, list) {
		dll_append(reversed_list, dll_val(list_ptr));
	    }
	}
	
```