12/15/05 Review Session for CISC105 Final Exam The students made a list of topics they wanted me to cover. Here is their list. Some topics are covered out of order, or are combined (1,7): chmod command, and writing things to web pages See also the file reviewNotes.html chmod -R a+rx directoryName chmod -R 755 directoryName either of these commands will make both "directoryName" and everything UNDER directoryName readable on the web. ls -l will show you the file permissions, for example: drwx------ 2 pconrad 0376 4096 Dec 14 10:38 12.14.review.session shows that 12.14.review.session is NOT readable on the web. but if we do: chmod -R a+rx 12.14.review.session then it will be, and everything inside that directory will be also. The foolproof way to make all your web pages accessible, regardless of your current working directory: chmod -R a+rx ~/public_html OR chmod -R 755 ~/public_html If you already did a "cd" command into your home directory, the following will also work. However, you MUST already be in your home directory. chmod -R a+rx public_html chmod -R 755 public_html If you edit an existing file after you do the chmod command, you don't have to redo the chmod command. BUT, if you add a NEW file, you may need to repeat the chmod command to pick up the new file. (2) Sorting Structs The title on the board was "sorting structs", but in fact, we cannot, or at least, usually do not, sort a struct.... what we _sort_, is not a single struct, but rather an __________ of structs. Fill in the blank: array Yes, we sort an array of structs. First, how do declare an array of structs? Q1: Declare a struct to store information about a skyscraper. Your struct should have four fields: name of skyscraper (up to 30 characters) location of skyscraper (up to 40 characters) height in feet (can have a decimal point) year constructed (as an integer) A1: /* the _S is optional; just a naming convention */ /* question: is it ok that Sky is capitalized answer: yes, actually it is preferred for names of structs to be capitalized, and for names of functions and variables to start with a lowercase letter */ /* remember NO semicolon after a #define!!! */ #define NAME_LEN 30 #define LOC_LEN 40 struct SkyScraperData_S { char name[NAME_LEN]; char location[LOC_LEN]; double height; int year; }; /* don't forget the semicolon at the end!!! */ Aside: When do you need a semicolon after a closing brace? Answer: On the exam: (1) after a struct declartion (2) after an array initializer, e.g. int scores[5] = {98, 67, 82, 91, 86}; Not on the exam: (3) a few other obscure ones that we didn't cover this semester, and so will not be on the exam, e.g. after an enumerated type declaration. C++ has a few others as well, e.g. after a class declartion Q2: Now, inside a main program, declare an array that can hold up to 15 skyscrapers (i.e. an array of 15 struct SkyScraper_S records) #define MAX_NUM_SCRAPERS 15 int main(void) { struct SkyScraper_S buildings[MAX_NUM_SCRAPERS]; /* some other code to manipulate the array would go here */ return 0; } Aside: int nums[15]; /* that declares an array of 15 ints */ struct SkyScraper_S buildings[MAX_NUM_SCRAPERS]; /* array of skyscrapers */ We use MAX_NUM_SCRAPERS instead of 15 so that if we want to change how many there are we can do it in only one place in the program. Q3: Explain the difference between what happens when you do the code labelled "A" below, and what happens when you do the code labelled "B" below: /**** begin A *********/ struct SkyScraperData_S { char name[NAME_LEN]; char location[LOC_LEN]; double height; int year; }; /* don't forget the semicolon at the end!!! */ /**** end A *********/ #define MAX_NUM_SCRAPERS 15 int main(void) { int nums[15]; /********** begin B *********/ struct SkyScraper_S buildings[MAX_NUM_SCRAPERS]; /********** end B *********/ /* some other code to manipulate the array would go here */ return 0; } Hint: Remember the analogy about the blueprint and the house. Remember the analogy about the cookie cutter and the cookies. How much memory is allocated by "A"? How much is allocated by "B"? Answer: A is "declaring a new struct type." A is like making a blueprint or a cookie cutter. B is "declaring an array of structs" B is like actually baking the cookies or building an apartment building. A allocates NO MEMORY WHATSOEVER!!! (How much flour and butter does a cookie cutter require? NONE) (How much land and lumber is required for a blueprint? NONE) B allocates enough memory for 15 instances of a struct that contains four fields, and creates 15 places in memory, each of which has four fields that can contain data. Q3: How would you write a function to sort an array of structs? Answer: First you have to decide what field you will use to sort on. Let's choose "year constructed", and sort from oldest building to newest building. (oldest building first, newest building last). Second, to do a "selection sort" (the technique we've learned for sorting this semester) you should write two helper functions: int findIndexOfLargest(struct SkyScraper_S array[], int count); void swapSkyScrapers(struct SkyScraper_S array[], int i, int j); The first helper function just finds the index of the largest value in the array, or some _portion_ of the array. (Note: if you were sorting largest to smallest, you'd make this function findIndexOfSmallest() instead.) For example in an array with three SkyScrapers: (note that I totally made up this data) [0] [1] [2] +-------------------+--------------------+------------------- |Empire State | Sears Tower | Chrysler Bldg | |New York City | Chicago | New York City | |1200.5 | 1500.7 | 1155.2 | |1930 | 1970 | 1935 | +-------------------+--------------------+------------------+ The numbers [0] [1] and [2] are the "indexes" (or if you prefer, "indices", which is correct plural of "index"). Recall the notation for arrays of structs. If this array is called "buildings", and i is 1 and j is 2, buildings[0].location is "New York City" buildings[i].year is 1970 buildings[j].year is 1935 How do I refer to the field containing "1200.5", the height of the Empire State building? buildings[0].height So we want to find the index of the SkyScraper_S with the largest year. So for the data above, findIndexOfLargest should 2. If I changed the data to this: [0] [1] [2] +-------------------+--------------------+------------------- | Sears Tower |Chrysler Bldg |Empire State | | Chicago |New York City |New York City | | 1500.7 |1155.2 |1200.5 | | 1970 |1935 |1930 | +-------------------+--------------------+------------------+ Now, findIndexOfLargest should return 0. The second helper function swaps the values of two elements in the array. Note that there are several different ways to write this swap function.. the way I'm showing you here is different from what we did in class, but is probably easier to understand. So for example, suppose I do findIndexOfLargest on the following array, and I determine that the indexOfLargest is 1. [0] [1] [2] +-------------------+--------------------+------------------- | Chrysler Bldg |Sears Tower |Empire State | | New York City |Chicago |New York City | | 1155.2 |1500.7 |1200.5 | | 1935 |1970 |1930 | +-------------------+--------------------+------------------+ Then I could do: swapSkyScrapers(buildings, 1, 2);, and the array starts as: to put the largestSkyScraper in the end position. Afterwards the array will look like this: [0] [1] [2] +-------------------+--------------------+------------------+ | Chrysler Bldg |Empire State |Sears Tower | | New York City |New York City |Chicago | | 1155.2 |1200.5 |1500.7 | | 1935 |1930 |1970 | +-------------------+--------------------+------------------+ The general idea of selection sort is you start with an array of "n" elements---let's say for instance n=6. Six numbers, numbered 0 through 5. [0] [1] [2] [3] [4] [5] 8 13 15 2 7 9 The first thing we want to do is figure out which element goes in position 5: [0] [1] [2] [3] [4] [5] +---+ 8 13 15 2 7 | 9 | +---+ So, we do findIndexOfLargest, and we discover that the index of largest is 2. So we swap 2 and 5, and get: [0] [1] [2] [3] [4] [5] +---+ 8 13 9 2 7 |15 | +---+ Now we do findIndexOfLargest, but ONLY ON THE FIRST 5 elements of the array (0 thru 4), giving us: 1 [0] [1] [2] [3] [4] [5] +---+ 8 13 9 2 7 |15 | +---+ Then we swap 1 and 4, giving us: [0] [1] [2] [3] [4] [5] +----+---+ 8 7 9 2 | 13 |15 | +----+---+ The indices stay where they are. This process continues until all the elements are sorted. **************************************** Now the actual helper functions... *************************************** First, findIndexOfLargest int findIndexOfLargest(struct SkyScraper_S array[], int count) { int i; int indexOfLargest = 0; for (i=1; i array[indexOfLargest].year) indexOfLargest = i; return indexOfLargest; } Next, we write our swap function (a bit different from how we did it before.) void swapSkyScrapers(struct SkyScraper_S array[], int i, int j) { /* declare temporary variables */ struct SkyScraper_S temp; /* swap each of the four fields separately */ strncpy(temp.name, array[i].name, NAME_LEN); strncpy(temp.location, array[i].location, LOC_LEN); temp.height = array[i].height; temp.year = array[i].year; strncpy(array[i].name,array[j].name, NAME_LEN); strncpy(array[i].location, array[j].location, LOC_LEN); array[i].height = array[j].height; array[i].year = array[j].year; strncpy(array[j].name, temp.name,NAME_LEN); strncpy(array[j].location, temp.location, LOC_LEN); array[j].height = temp.height; array[j].year = temp.year; } Now with the two helper functions, sorting is easy: int findIndexOfLargest(struct SkyScraper_S array[], int count); void swapSkyScrapers(struct SkyScraper_S array[], int i, int j); Can you fill in the blanks? void sortSkyscrapers(struct SkyScraper_S array[], int count) { int i; int indexOfLargest; for (i = ____ ; ____________; _______) { indexOfLargest = findIndexOfLargest(array, ____); swapSkyScrapers(array, _______, ______); } } Answer: void sortSkyscrapers(struct SkyScraper_S array[], int count) { int i; int indexOfLargest; for (i = count ; i > 1; i-- ) { indexOfLargest = findIndexOfLargest(array, i); swapSkyScrapers(array,indexOfLargest,i-1); } }