CS/CE218 --- Unix and C Programming. 18 November 91 Name: TA: HOMEWORK 7: C pointers and structures There are 2 parts to this homework, parts A and B. Part A should be completed before part B. You don't need to use the computer to do part A, so if you can, it will be to your advantage to finish that part by Monday December 2. Part B is Due Monday, December 9. That due date is immovable, so don't expect any extensions. PART A Due: 4 December 1991 This part of the homework is intended to help you systematically plan the work for part B below. The CS/CE 218 staff has noted that on the last homework, many of your problems have been due to a lack of such planning. As you have learned from personal experience that such planning is necessary, we hope that this part of the homework will be helpful rather than burdensome. You may already be good at planning such work, but the true student of computer science knows that the process is at least as important and interesting as the code, and always bears closer examination. (The following is adapted from the staff's experience, various texts on Software Engineering, and Polya's "How to Solve It".) The problems of part B referred to in this part are those with points attached; they do NOT include the extra credit problems of part B. a. (5 points) [What is the problem?] Read each of the problems in part B below. For each of these problems describe exactly what you have to do in your own words. b. (extra credit only) In as precise a mathematical notation as you know how, formally specify some or all of the problems of part B. c. (10 points) [Can you give an example?] For each of the problems in part B, give three sets of examples. Examples should be either input and expected output for complete programs, or arguments and expected results for functions. The first set of examples should illustrate the normal behavior. The second should illustrate the boundary conditions. The third should illustrate errors that are close to being right. If some of the problems don't have all three kinds of examples, state that. d. (10 points) [What are the givens?] For each of the problems in part B for which we have given you code or there is code in the book, explain what the code does in your own words. Describe all the relevant data structures and how they are used. Is all the given code correct? (We might have mistyped something...) You don't have to write a lot, but you should be sure you understand the code. (Don't give us a blow-by-blow account of the code, "...then 0 is assigned to x...", think more abstractly.) How does it relate to your examples? e. (10 points) [Develop a plan] For each of the problems in part B, write pseudo-code for your solution. You may write declarations for functions and data structures, but otherwise only sketch the solution. Think abstractly, don't write C. It may help to think about the following. Are there any problems whose solution you have seen or in the book that resemble the given problems? Are there any library routines you can use in your solution? f. (extra credit only) [Plan how the work will be done] Are there intermediate steps you can add to your plan that will allow you to get something working at several stages? Are there simplifications of the given problems that you can solve first that will help you in solving the assigned problems? If so, describe these. g. (10 points) [Check the plan] For each of your solutions to part e, describe why you think that your solution will work. Go over your examples (from part c) and explain why they do what is expected. h. (5 points) [Estimate the cost] Estimate how many lines of code you'll have to write for each problem. Estimate how long it will take you to write and to debug that code. It's okay to ask the course staff to clarify ambiguities in the problems below; we expect that you will find parts of the problem statements that are unclear. The above part will be graded partly on the thought that went into it, not just it's correctness. It will NOT be graded on how much (long) you write, so don't be verbose. We don't want to read a lot, we want you to plan carefully. A final note, when you are coding, you may find that, despite your best efforts, your plan is flawed. Don't despair, but it may be helpful to revise your plan (at least mentally) before continuing coding. PART B Due: 9 December 1991 To start this part of the homework, execute the following commands: cd $HOME mkdir hw7 chgrp cs218s . hw7 chmod 750 . hw7 Then leave the files described below in your directory $HOME/hw7. These will be readable by the course staff, but not by other students. Although we will not grade you on this, we encourage you to use RCS to maintain file versions. You should also use `make' to build programs. You are required to hand in a printout of your Makefile along with your code. 1. (30 points) Copy the file $PUB/hw7/option.c to $HOME/hw7/option.c. Fill in code where the comments are /* YOUR CODE GOES HERE */ The problem is to implement a package that handles options by processing them all at once (with option_initialize), and then managing access to them (by calls to option_present or option_value). Your main task is to decide on suitable data structures for the static data in the file option.c, and to fill in the code. For this problem you may, if you like, use the standard C library function getopt (3C). (See the manual page by typing ``man 3 getopt''). 2. (extra credit only) Compare the package in option.c with getopt (3C). What advantages and disadvantages does it have? Which is better for information hiding? Which is more convenient to use? What are the limitations of each? 3. (30 points) Copy the following files from $PUB/hw7 to your $HOME/hw7: Makefile, emacs_std_outline.c, outline.c, outline.h, print_errors.c, and print_errors.h. Fill in code in emacs_std_outline.c and outline.c wherever you find /* YOUR CODE HERE */. The program is described in some detail in the comment at the top of emacs_std_outline.c. The basic idea is to change emacs outline format to standard outline format. The skills needed are the ability to work with arrays and pointers, and strings. 4. (15 points) Given the following declaration typedef struct { int num; int denom; } Rational; Implement the following operations on rational numbers. Rational rat_make(int numerator, int denominator); Rational rat_add(Rational x, Rational y); Rational rat_sub(Rational x, Rational y); Rational rat_mul(Rational x, Rational y); Rational rat_div(Rational x, Rational y); int rat_equal(Rational x, Rational y); The operation rat_make returns the rational numerator/denominator. The operations rat_add, rat_sub, rat_mul, rat_div return x + y, x - y, x * y, and x / y, respectively. The operation rat_equal returns 1 if its arguments are the same when reduced to lowest terms; recall that (a/b) = (c/d) if and only if a*d = b*c. The operations rat_make and rat_div require that their second argument be nonzero. Put all these operations in a file called rat.c; also write a main program in a file test_rat.c. (You may want to have a file rat.h with the extern versions of the above declarations.) 5. (40 points) Do exercise 6-3 on page 143 of "The C programming Language (second edition)". This exercise requires the use of structures. Code for the word frequency program of section 6.5 of the C book is found in the directory $PUB/hw7 in the files input.c, getword.c, tree.c, tree.h, and word_freq.c. You will have to keep track of line numbers as you read input words, and you will have to store them in the tree. Count as a noise word any word that occurs more than 20 times. The output should look like the following: all 1,3 are 3 farmers 2 good 1,5,7 really 4 6. (extra credit only) Do exercise 6-5 on page 145 of "The C programming Language (second edition)". 7. (extra credit only) Arrays in C are fixed in size, and their size is determined statically (i.e., at compile time). Using malloc, structures, pointers, and arrays, design and write a set of functions that can manipulate dynamic arrays of characters (of one dimension). The basic idea is to use a "dope vector", which contains a pointer to the C array storing the elements, the size of the array, and the lower bound of the array. Your design might have the following operations: DynamicArray dynamic_array_create(void); void dynamic_array_store(DynamicArray a, int index, char value); char dynamic_array_fetch(DynamicArray a, int index); void dynamic_array_add_low_end(DynamicArray a, char value); void dynamic_array_add_high_end(DynamicArray a, char value); void dynamic_array_remove_from_low_end(DynamicArray a); void dynamic_array_remove_from_high_end(DynamicArray a); int dynamic_array_size(DynamicArray a); int dynamic_array_low_bound(DynamicArray a); void dynamic_array_set_low_bound(DynamicArray a); and any others that you think appropriate. 8. (extra credit only) Do exercise 7-8 on page 165 of the C book. Would this be easier to do in the shell? 9. (extra credit only) Do exercise 8-3 on page 179 of the C book.