CProg :: MT2 sample

Zsolt Kohári · 2019.11.15.

Test of 2017

Remember my advice about preparation for the tests!

The midterm group A (from 2021) with solutions is here

The midterm group B (from 2021) with solutions is here

1. List

MINIMUM: Define a new type List that can be used to build a singly linked list of integer values.

Write a function that returns the length of the list

Write a function that deletes the listelements of those values that can be divided by 5. (you can suppose that the first element cannot be divided by 5)

Solution

typedef struct Listelem {
    int data;
    struct Listelem *nxt;
} Listelem;

int length(Listelem *head) {
    int i=0;
	Listelem* ptr=head;
    while(ptr!=NULL){
	i++;
	ptr=ptr->nxt;}
	return i;
}

void delete_lstelem(Listelem* Lst){ //points one before the deleted element
	Listelem* pre=Lst;
	Listelem* act=Lst->nxt;
	Listelem* post=Lst->nxt->nxt;
	pre->nxt=post;
	free(act);
	}


void num_5(Listelem *head) {
    if(head==NULL){ return;}
    Listelem* p=head;
	Listelem* q=head;
	while(q!=NULL)
	if(q->data%5==0){
	delete_lstelem(p);
	q=p->nxt;}   //the element behind q is destroyed, the new next can be set from p
	else
	{p=q;
	q=q->nxt;}
	return;


}

2. Merging arrays

MINIMUM: Write a C function that reads a series of real values into an array. The sequence of values is terminated by 0, the terminating zero should not be stored. The number of entries is not known. The array must be of exactly the needed size. Return the array and its size via the parameter list.

Write a function that receives three real arrays but does not receive the size of the third one. The function should merge the values in the first two arrays (sources) into the third one (destination) in the following manner: take one element from the first source and store it in destination, then take one from the second source and store it in destination. Repeat these two steps to merge the arrays. When there are no more elements in one of the sources, copy the rest of the elements from the other source. For example the arrays 1, 3 and 2, 4, 6, 8 should result in 1, 2, 3, 4, 6, 8. (Memory is allocated in the program for the destination.)

Write a C program that first reads two arrays, allocates memory for the merged array, then merges the two input arrays into a single one. At last it prints the merged array.

Ensure that there is no memory leak in the program.

Solution

#include<stdlib.h>
#include<stdio.h>

void readarray(double ** arr, int *nn) {
    double act, *a=NULL;
    int n=0;
    scanf("%lf", &act);
    while(act!=0) {
        int i;
        double *tmp=malloc((n+1)*sizeof(double));
        for(i=0; i<n; ++i)
            tmp[i]=a[i];
        tmp[i]=act;
        ++n;
        free(a);
        a=tmp;
        scanf("%lf", &act);
    }
    *arr=a;
    *nn=n;
}

void merge(double *s1, int n1, double *s2, int n2, double *d) {
    int i,j,k;
    i=j=k=0;
    while(i<n1 || j<n2) {
        if(i<n1) d[k++]=s1[i++];
        if(j<n2) d[k++]=s2[j++];
    }
}

int main(void) {
    int n1, n2, i;
    double *in1, *in2, *merged;
    readarray(&in1, &n1);
    readarray(&in2, &n2);
    merged=(double*)malloc((n1+n2)*sizeof(double));
    merge(in1, n1, in2, n2, merged);
    for (i = 0; i<n1+n2; ++i)
        printf("%g ",merged[i]);
    free(in1);
    free(in2);
    free(merged);
    return 0;
}

3. Snow White and Little Red Riding Hood (20 pts)

Snow White plans a journey to Oz. She wants to remember everyone she meets on her way, so decides to store their names in a singly linked list. She asks these fellows if they join her on her journey and she needs to store this fact, too. Snow White told Little Red Riding Hood about her plans and Red Riding Hood decided to start her own expedition: keeping track of people she meets exactly the same way. The two ladies agreed that each start their own journey and will meet at Oz at the end.
Write the following parts:

MINIMUM: Define a new type Fellow that represents a real or fictional person: the name (at most 30 characters), and whether she or he joined the journey.
Define a new type to build a singly linked list of Fellows.
Write a function that destroys the list.

Write a function that receives the head of a list and a fellow and adds it to the end of the list. It must be able to add to an empty list as well.

Write a function that receives two lists and finds a common fellow in the lists (does not matter which one if there are several). The function should return a pointer to the name of the fellow or NULL if there is no common name.

Create another function that receives the head of a list and prints the names of those who joined the journey.

Write the program that administers the two journeys. Create two fellows: Snow White and Little Red Riding Hood. Create two lists and add Snow White to one, Little Red Riding Hood to the other. Suppose their lists get populated on their journey and they arrive at Oz with some fellows.
Find a person who met both Snow White and Little Red Riding Hood on their way. Print all the persons that visited Oz. Ensure that there is no memory leak in the program.

Solution

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

typedef struct {char name[30+1]; bool joined;} Fellow;
typedef struct le{ Fellow d; struct le *next;}le;

void destroy(le *h){
    le *act=h;
    while (act!=NULL){
        le *tmp=act;
        act=act->next;
        free(tmp);
    }
}

void add_fellow(le **h, Fellow f) {
    if (*h==NULL){
        *h=(le*)malloc(sizeof(le));
        (*h)->next=NULL;
        (*h)->d=f;
    }
    else {
        le *act=*h;
        while(act->next!=NULL)
           act=act->next;
        act->next=(le*)malloc(sizeof(le));
        act->next->next=NULL;
        act->next->d=f;
    }
}

char *common_f(le *h1, le*h2)
{
    le *h;
    for(;h1!=NULL;h1=h1->next)
        for(h=h2;h!=NULL;h=h->next)
            if(strcmp(h1->d.name,h->d.name)==0)
                return h->d.name;
    return NULL;
}

void print_mates(le*h){
    while(h!=NULL){
        if(h->d.joined)
            printf("%s\n",h->d.name);
        h=h->next;
    }
}

le *last_mate(le *h){
    le *m=NULL;
    while(h!=NULL){
        if(h->d.joined)
            m=h;
        h=h->next;
    }
    return m;
}

int main(void) {
    char *found;
    Fellow f1={"Snow White",true}, f2={"Little Red Riding Hood",true};
    le *sw=NULL, *lrrh=NULL;
    add_fellow(&sw,f1); add_fellow(&lrrh,f2);
    /*not needed in the test*/
    strcpy(f1.name,"Cinderella"); add_fellow(&sw,f1);
    strcpy(f1.name,"Aladdin"); add_fellow(&sw,f1);
    f1.joined=false; add_fellow(&lrrh,f1);
    strcpy(f1.name,"Mickey Mouse"); f1.joined=true; add_fellow(&lrrh,f1);
    strcpy(f1.name,"Winnie the Pooh"); f1.joined=true; add_fellow(&lrrh,f1);
    strcpy(f1.name,"Toto"); f1.joined=false; add_fellow(&lrrh,f1);
    /*till here*/
    found=common_f(sw,lrrh);
    if(found!=NULL) puts(found);
    print_mates(sw);
    print_mates(lrrh);
    destroy(sw);sw=NULL;
    destroy(lrrh);lrrh=NULL;
    return 0;
}