Lab Activity 14
In this lab, you will:
-
Dynamic Memory Allocation Lecture 19
-
Recursion Lecture 25
- Use FILE I/O.
- Create an array of structure
elements.
- Use qsort.
- Output the sorted structure elements as a table on an HTML page.
Part 1: Prelab (Part 1
is worth 3 points, 1/7 point per blank)
Part A DMA
1. Fill in the blanks below with the correct C code to dynamically allocate an array named albums that holds 750 elements of datatype Album.
typedef struct
{
char name[40]; /* track name or song name */
int length; /* in seconds */
} Track;
typedef struct
{
int cdno; /* cd number */
char title[30];
char artist[20];
int year;
int num_tracks; /* number of tracks */
int quantity;
float price;
float sales[MONTHS]; /* cd sales ($US) over the 12 months in 2005 */
Track tracks[20]; /* info for each track */
} Album;
Album * albums;
albums = calloc(_____750____________ , ________sizeof(Album) or sizeof(albums[0]__________________);
ORalbums = calloc(_____sizeof(Album) or sizeof(albums[0]________ , ________750__________________);
Part B: Recursion
2. Write the output the following program produces.#include <stdio.h>
int power( int x, int n)
{
if ( n == 1) /* Voom! --- means base case (or simplest) case of the problem */
return x;
return power(x, n/2) * power(x, n-n/2);
}
void main(void)
{
printf(" %i ", power(2,1));
printf(" %i ", power(2,2));
printf(" %i ", power(2,4));
}
_____2_______ _____4_______ _____16_______
3. Write the output the following program produces.
#include <stdio.h>
int mystery( int n)
{
if ( n <= 1) /* Voom! */
return n;
else
return mystery(n - 2); /* mystery is a recursive function because it calls itself */
}
void main(void)
{
printf(" %i ", mystery(3));
printf(" %i ", mystery(4));
printf(" %i ", mystery(5));
}
_____1_______ ______0______ _____1_______
4. Write the output the following program produces.
#include <stdio.h>
int euclid( int a, int b)
{
if ( (a % b) == 0) /* if b divides into a without remainder ... Voom!*/
return b;
else
return euclid(b, a % b);
}
void main(void)
{
printf(" %i ", euclid(2,4));
printf(" %i ", euclid(2,5));
printf(" %i ", euclid(4, 16));
}
_____2_______ _____1_______ _____4_______
5. Write the output the following program produces.
#include <stdlib.h>
int recFunc (int array[], int left, int right , int value)
{
int midpt = (left+right)/2; /* integer division */
if (value == array[midpt])
{
printf("left = %i, right = %i, mid-point = %i, and value = %i\n", left, right, midpt, value);
return midpt;
}
else if (value < array[midpt])
{
printf("left = %i, right = %i, mid-point = %i, and value = %i\n", left, midpt-1, midpt, value);
return recFunc(array,left, midpt-1, value);
}
else
{
printf("left = %i, right = %i, mid-point = %i, and value = %i\n", midpt+1, right, midpt, value);
return recFunc(array,midpt+1, right,value);
}
}
int compare( int * ptr1 , int * ptr2)
{
return *ptr1 - *ptr2;
}
void main (void)
{
int i;
int data[] = { 7, 4, 3, 8, 5, 9};
qsort(data, 6, sizeof(int), compare);
printf("After sort: ");
for(i=0;i<6;i++)
printf("%i ", data[i]);
printf("\n");
printf("Mid-point: %i \n", recFunc(data,0,5,7) );
}
After sort: 3 4 5 7 8 9
left = 3, right = 5, mid-point = 2, and value = 7
left = 3, right = 3, mid-point = 4, and value = 7
left = 3, right = 3, mid-point = 3, and value = 7
Mid-point: 3
6. The following program compiles and runs with errors. Write the output the program produces.
#include <stdio.h>
void printStr(char str[], int n);
void main(void)
{
char Str[] = "abcdefghijklmnopqrstuvwxyz";
printStr(Str, 5);
return;
}
void printStr(char str[ ], int n)
{
if(n < 1)
{
return;
}
printf(" %c ", str[n - 1]);
printStr(str, n - 1);
}
__ e d c b a________________
7. Binomial coefficients
(read
'n choose k') are used to denote the number of k-combinations
of an n-set, which can be found using the formula 
. Pascal's formula,
written below
#include <stdio.h>
int binomial(int n, int k)
{
/* Voom! check whether n equals 0 or k equals 0 or n equals k */
if( _________(n == 0) || (k == 0) || (n == k)________________ )
return 1;
else
/* else use Pascal's formula shown above */
return binomial( n - 1 , ______________k____________________) +
binomial(_________n-1_______________________________ , _______k-1___________________________);
}
void main(void)
{
printf("(0, 0) = %i \n", binomial(0,0)); /* prints 1 */
printf("(1, 0) = %i \n", binomial(1,0)); /* prints 1 */
printf("(1, 1) = %i \n", binomial(1,1)); /* prints 1 */
printf("(10, 10) = %i \n", binomial(10,10)); /* prints 1 */
printf("(3, 2) = %i \n", binomial(3,2)); /* prints 3 */
printf("(4, 2) = %i \n", binomial(4,2)); /* prints 6 */
}
Part 2: Creating an html document
Setup:
Make a directory called lab14 in
your home directory. Download the files lab14.c and input.dat into it. There’s also a demo
file that you can download and try out to see how the program
works.
Coding:
1. Write
the type definition for the structure Person with last
name, first name and year of birth.
2. Let’s
start coding the main function. We’re going to read in data from
an input file, perform the sorting operations and write the
sorted array to an output file, so let’s ask the user for the
names of these files, and store them in character arrays.
Declare two character arrays, say infilename[20] and outfilename[20] to hold these names.
3. Prompt
the user to enter the name of the input file, and store this in
infilename.
4. Prompt
the user to enter the name of the output file, and store this in
outfilename. Let’s
make the output file name a .html
file, so that we can view the result in a browser.
5. Now
we are going to prep these two files before reading from
them/writing to them. Before accessing a file, you have to open
the file for reading/writing/appending, so use fopen to open the input
file in the read mode, and the output file in the write mode.
You will need to declare two file pointers for the return values
of fopen.
The function fopen
return a FILE pointer, which is what you will use to refer to
the file from now on.
6. Now
that you have the files open, let’s get the data from the input
file into the program. Declare an array of structures of type
Person, called musicians, and let the maximum size be
MAX_PERSONS. Now read in the data from the input.dat file, using
fscanf, one line at a time, into the corresponding parts of each
of the array elements.
Look at the input.dat file to get an idea of what you need to
do. The file looks like this:
Adamson Barry 1950
Aguilera Christina 1980
Allman Gregg 1956
and so on…..
For example, for the first line of input.dat, you would read Adamson
into musicians[0].last,
Barry into musicians[0].first,
and 1950 into musicians[0].year.
Remember that you have to simultaneously count the number of
lines of the input.dat file that you are reading. This
corresponds to the number of persons in your file, and will be
used later when you perform the sorting. Declare a variable counter to count the
number of lines you are reading in.
7. Now
that you have the data in the array, let’s proceed to sort it.
We’ll use qsort, so
you have to write a compare function for it. We’re going to sort
the list of musicians in ascending order of last name, and in
the case of ties, in ascending order of first name. You have to
write the compare function before use, so declare compare_last at the top,
and write the definition of the function compare_last. Then call qsort with the array musicians, the number of
elements, the size of EACH element, and the compare function.
Comparison in compare_last:
Sort in ascending order of last names, if there is a tie for
last names, soft in ascending order of first name and return a 0
if the entire name is equal.
8. Output
the sorted array, into the output.html file instead of
displaying it on the screen.
Copy the following lines to create the starting and ending tags
for the html page, and then use fprintf in the loop in the
middle to write out each element of the array to a line of the
output.html file.
/*opening tags */
fprintf(outputfileptr,"<html>\n<body>\n<title>LAB14</title>\n");
/* for loop: use the <br> tag to get each
element onto a new line, not \n*/
for(.. .. .. )
.. .. ..
/*closing tags*/
fprintf(outputfileptr,
"%</body>\n</html>\n");
9. Close both files using fclose. Save your code, and compile it.
When you run the program, it should prompt you for the names
of the input and output files. Make sure you specify the name
of the output file as something.html.
10. You should be able to view the
result of this lab in a browser. Either type firefox
~/lab14/somethng.html
(or whatever you named your output file), or open a browser
and open this file in there. You should see the sorted list of
musicians, one to a line, in the file.
11. Obtain a
signature from your lab TA.
Congratulations! You are done with CS101 labs!