Homework 5 Solutions

  1. Suppose you are given the following declarations:
          Jval val;
          int age;
          double salary;
          char *name;
          struct node *ptr;
          
    1. Write a statement that assigns the variable age to val
              val.i = age;
              
    2. Write a statement that assigns the variable salary to val
              val.d = salary;
              
    3. Write a statement that assigns the variable name to val
              val.s = name; // use the char * field that Jval makes available
              
    4. Write a statement that assigns the variable ptr to val
              val.v = ptr;  // now we must use the generic pointer field in a Jval
              
    5. Write a statement that assigns the value in val to ptr
              ptr = (struct node *)val.v;  // remember to do the cast
              

  2. Write a union that contains an integer field named age, a pointer to a character string named address, and a three element integer array named test_scores.
    	union Item {
    	    int age;
    	    char *address;
    	    int test_scores[3];
    	};
    	

  3. The personnel department at State University has to keep track of three types of people: students, professors, and staff. The information it must keep about these groups is as follows:

    1. All three groups of people have an integer social security number, a name of at most 20 characters, and a single character code that denotes whether they are male or female.

    2. Students have a floating point gpa, a floating point fee balance, and a pointer to a list of courses they are taking. The pointer points to a struct course node.

    3. Professors have a floating point salary, a single character code that denotes their rank, a 10 character string that denotes their office, and a pointer to a list of courses they are teaching. The pointer points to a struct course node.

    4. Staff have a floating point hourly rate, an integer that denotes their job classification, and a 10 character string that denotes their office.

  4. You are given a linked list, L, and another linked list, P, containing integers sorted in ascending order. You are to write a function named extract_list that will find the elements in L that are in the positions specified by P and copy their contents to a new list that you will create and return to the user. For example, if P = 1, 3, 4, 6, the first, third, fourth, and sixth elements of L will be copied to the new list. Your function should return a pointer to the new list. Use Dr. Plank's sllist library to represent your linked lists. To copy an element you will simply need to copy the val field to your new list. Since the elements of P are sorted you should only have to make one pass through L in order to create your new list. You do not have to compile or run your program. Just make a good faith effort to write the program. If you want to test your program you can find the sllist.h and .c files in ~cs140/www-home/spring-2005/notes/Sllists.
    Sllist extract_list(Sllist L, Sllist P) {
        Sllist new_list;  // new list to be created
        Sllist P_ptr, L_ptr; // temp ptrs for traversing P and L lists
        int index;   // index of next node to be extracted from L
        int L_count = 0; // position of current node in L
        Sllist last_node; // pointer to last node in new_list
    
        new_list = new_sllist();
        last_node = new_list;
        L_ptr = L;
        for (P_ptr = sll_first(P); P_ptr != sll_nil(P); P_ptr = sll_next(P_ptr)) {
    	index = P_ptr->val.i;
    	// traverse thru L until we reach the index position
    	while (L_count < index) {
    	    L_ptr = sll_next(L_ptr);
    	    L_count++;
    	}
    	// append the value in L to the end of the new list. sll_insert_after
    	// returns a pointer to the created node, which is the new last
    	// node in the list.
    	last_node = sll_insert_after(last_node, new_jval_i(L_ptr->val.i));
        }
        return new_list;
    }
    

  5. Write a function called sll_delete_node that deletes a node from an Sllist. You should use the book's solution of keeping a pointer to the previous node as you search the list for the node to delete.
    void sll_delete_node(Sllist list, Sllist node_to_delete) {
        Sllist prev_node;
        Sllist tmp_ptr;
    
        // find the node that precedes the node to be deleted
        sll_traverse(tmp_ptr, node_to_delete) {
    	if (tmp_ptr == node_to_delete) 
    	    break;
    	else
    	    prev_node = tmp_ptr;
        }
        // delete the node only if we found it
        if (tmp_ptr != sll_nil(list)) {
    	prev_node->link = node_to_delete->link;
    	free(node_to_delete);
        }
    }