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 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(_________________ , __________________________);

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,3));
    }


    ____________   ____________   ____________ 


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));

	}

            ____________   ____________   ____________ 



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));
	}

            ____________    ____________    ____________    ____________ 



5.   Write the  output the following program produces.

    #include <stdio.h>
    #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)  );

    }

        _________________________________________________________

        _________________________________________________________

        _________________________________________________________

        _________________________________________________________

        _________________________________________________________

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);

	}


                 
      __________________      

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 is a recursive way to compute binomial coefficients. Fill in the blanks to complete a recursive function named binomial , that given two integer arguments n and k computes and returns n choose k . We will assume that n >= k.

	#include <stdio.h>

	int binomial(int n, int k)

	{

		/* Voom! check whether n equals 0 or k equals 0 or n equals k */







		if( _______________________________________________________________ )


			return 1;


		else

		/* else use Pascal's formula shown above */




		
					return    binomial(   n - 1 , __________________________________) + 


							 binomial(________________________________________ , __________________________________);

	}




	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

11. Obtain a signature from your lab TA.

      _____________________________________________________________________

Congratulations! You are done with CS101 labs!