12.1 Funktionen date_compare
På den tilknyttede slide har vi programmeret funktionen date_before. Den returnerer en boolsk værdi: Hvorvidt datoen d1 kommer forud for d2.
Programer på basis af date_before funktionen date_compare, som sammenligner to datoer efter de gængse konventioner i C (som vi bl.a. har studeret i forbindelse med sammenligningen af to tekststrenge). Funktionen date_compare skal altså kunne returnere enten et negativt, positivt eller nul resultat.
12.2 Sortering af et array af bøger
Programmer en funktion, sort_books_by_title, som kan kaldes på variablen shelf fra programmet på den tilhørende slide. Tag udgangspunkt i dette program. Overfør også indekset af den sidste bog som en parameter til sort_books_by_title, således at sorteringsfunktionen ved hvor mange bøger, der skal sorteres:
void sort_books_by_title(book shelf[], int last){
qsort(shelf, last+1, ..., ...);
} Som antydet af funktionsnavnet, skal funktionen ordne bøgerne således at titlerne kommer i alfabetisk orden. Efter sorteringen er den første bog således 'C by Dissection', og den sidste bog er 'The C Programming Language'. Sorteringen skal foregå ved at bytte om på bøgerne i arrayet (ikke ved at danne en ny, sorteret kopi af arrayet).
Ved løsningen af denne opgave skal du anvende funktionen qsort fra stdlib.h, som tidligere har været beskrevet i dette undervisningsmateriale.
Programmer dernæst en funktion sort_books_by_kind_and_year. Denne funktion skal primært sortere bøgerne således at alle skønliterære bøger kommer før lærebøgerne (university text books). Inden for begge disse grupper skal funktionen sekundært sortere bøgerne efter udgivelsesår. Relativt til eksemplet på den tilknytede side i undervisningsmaterialet skal det give følgende ordning på bøgerne:
Title: Pelle Erobreren Year: 1910 University text book: no Title: Ditte Menneskebarn Year: 1917 University text book: no Title: The C Programming Language Year: 1988 University text book: yes Title: C by Disssection Year: 2001 University text book: yes Title: Problem Solving and Program Design in C Year: 2010 University text book: yes
Afprøv begge sorterings-funktionerne på de fem bøger i variablen shelf.
12.3 Funktionen tomorrow
På den omkringliggende slide er der vist et program, der genererer en kalender på et helt år.
Vi har på en tidligere slide programmeret struct date.
I denne opgave skal du programmere den manglende funktion tomorrow. Funktionen tomorrow tager en dato som parameter, og den returnerer datoen på den efterfølgende dag. Du kan taget udgangspunkt i dette program.
Hint: Lad i udgangspunktet resultatet være den overførte parameter, og gennemfør (pr. assignment til enkelte felter) de nødvendige ændringer.
12.4 Spillekort
Et spillekort er karakteriseret af en kulør (klør, ruder, hjerter og spar) og en værdi (es, 2, .., 10, knægt, dame, og konge). Alternativt kan et spillekort være en joker (som hverken har kulør eller værdi).
Definer en struct i C (med felter kuloer og vaerdi) som repræsenterer et spillekort. Beslut selv typen af felterne. Enumerationtyper kan være attraktive. Overvej hvordan du ønsker at håndtere jokeren!
Lav et spil kort bestående af de 52 "normale" spillekort og 3 jokere, altså ialt 55 kort. Organiser disse i et array af structs.
Programmer en funktion sorter_kort som sorterer kortene således:
I programmeringen af sorter_kort forventes at du benytter qsort med en passende sammenligningsfunktion.
Da kortene typisk er ordnet per konstruktion kan det anbefales du også programmerer en funktion, som blander kortene tilfældigt. Med en sådan funktion kan du blande kortene inden de sorteres. Blanding af kortene kan gøres på mange forskellige måder. Det kan f.eks. ske ved at gennemløbe alle kort, og at bytte det aktuelle kort om med et tilfældigt valgt andet kort.
Målet med opgaven er at opnå viden og færdigheder i programmering med structs og array af structs. Det er endvidere målet at opnå viden og færdigheder om sortering af et array af structs.
12.5 Brøker og structs
Lav en struct, som repræsenterer en brøk (engelsk: fraction). Den nye type skal naturligvis have to felter, for hhv. tæller og nævner (engelsk: numerator og denominator). I denne opgave ønsker vi at disse skal være af typen unsigned int. Vi arbejder således udelukkende med positive brøker.
Programmer nu følgende funktioner på brøker:
Det kan også anbefales at lave en funktion der laver en brøk ud fra en tæller og en nævner. Altså en funktion der returnerer en brøk konstrueret ud fra tæller og nævner input.
Vi har tidligere i kurset arbejdet med en funktion, der finder den største fælles divisor af to positive heltal. For ikke at bruge for meget tid på dette aspekt, er der en mulig implementation af denne funktion her (Euclids algoritme):
unsigned int gcd(unsigned int large, unsigned int small){
unsigned int remainder;
while (small > 0){
remainder = large % small;
large = small;
small = remainder;
}
return large;
} Når man skal addere to brøkker skal man først finde en fælles nævner. Dette kan gøres ved at multiplicere begge brøker med den anden brøks nævner.
Hvis du har brug for mere matematisk viden om brøker henviser vi til Wikipedias side om brøker.
Skriv også en main funktion som giver eksempler på hvordan givne brøker kan konstrueres, adderes og multipliceres.
12.6 Funktioner på cirkulære lister
I denne opgave skal du tage udgangspunkt i diskussionen af cirkulære lister i videoen, som hører til denne lektion. Jeg foreslår at du laver en cirkulær liste med punkter.
Start med at programmere en funktion der beregner listens længde: length_of_circular_list
Programmer dernæst de fire funktioner der hhv. indsætter og sletter det første og det sidste element i en liste:
Det forventes at alle pånær én af disse kan køres i konstant tid (altså uafhængig af listens længde). Hvilken funktion er markant mindre effektiv end i de andre?
Her et udgangspunkt, som gør det lidt lettere at komme i gang:
#include <stdio.h>
#include <stdlib.h>
struct point {int x; int y;};
typedef struct point point;
struct list_node {
void *data;
struct list_node *next;
};
typedef struct list_node list_node;
void print_point(point *p);
void print_circular_point_list(list_node *cl);
list_node *insert_head(list_node *cl, void *el);
list_node *insert_tail(list_node *cl, void *el);
list_node *delete_head(list_node *cl);
list_node *delete_tail(list_node *cl);
int length_of_circular_list(list_node *cl);
list_node *find_previous_node(list_node *cl);
int main(void) {
point p1 = {1,2}, p2 = {3,4}, p3 = {5,6}, p4 = {7,8};
list_node *circular_list = NULL;
printf("Length of circular list: %d\n", length_of_circular_list(circular_list));
return EXIT_SUCCESS;
}
void print_point(point *p){
printf("(%1d, %1d)\n", p->x, p->y);
}
void print_circular_point_list(list_node *cl){
list_node *cur, *prev;
if (cl != NULL){
cur = cl->next;
do{
prev = cur;
print_point(cur->data);
cur = cur->next;
}
while(prev != cl);
}
}
/* An exercise */
int length_of_circular_list(list_node *cl){
return 0;
}12.7 Højde-funktion af binært træ
Højden af et binært træ defineres som højden af træets rod.
Højden af en knude K i træet er den længste sti fra K til et blad. Med dette bliver højden af et blad altså 0.
Skriv en funktion i C der beregner højden af et træ. Udgangspunktet (parameteren) skal være en pointer til en knude i træet. Afprøv funktionen på forskellige træer.
Her er et godt udgangspunkt for denne opgave - dog givet i kontekst af binære søgetræer - og svarende til de programmer der er diskuteret i lektionsvideoen.
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
struct tree_node{
int key;
struct tree_node *leftp, *rightp;
};
typedef struct tree_node tree_node;
tree_node *make_tree(int key, tree_node *left, tree_node *right);
void assert_allocation_success(void *alloc_pointer);
tree_node *insert_in_binary_search_tree(tree_node *tree_ptr, int e);
void print_tree(tree_node *tree_ptr);
void print_tree_helper(tree_node *tree_ptr, int level);
int tree_height(tree_node *tree_ptr);
int main(void) {
tree_node *tree4 = NULL;
tree4 = insert_in_binary_search_tree(tree4, 6);
tree4 = insert_in_binary_search_tree(tree4, 2);
tree4 = insert_in_binary_search_tree(tree4, 1);
tree4 = insert_in_binary_search_tree(tree4, 4);
tree4 = insert_in_binary_search_tree(tree4, 3);
tree4 = insert_in_binary_search_tree(tree4, 5);
tree4 = insert_in_binary_search_tree(tree4, 7);
tree4 = insert_in_binary_search_tree(tree4, 9);
tree4 = insert_in_binary_search_tree(tree4, 8);
printf("tree4:\n");
print_tree(tree4);
exit(EXIT_FAILURE);
}
tree_node *make_tree(int key, tree_node *left, tree_node *right){
tree_node *the_tree = malloc(sizeof(tree_node));
assert_allocation_success(the_tree);
the_tree->key = key;
the_tree->leftp = left;
the_tree->rightp = right;
return the_tree;
}
void assert_allocation_success(void *alloc_pointer){
if (alloc_pointer == NULL){
printf("Allocation problems. Your program stops.");
exit(EXIT_FAILURE);
}
}
/* Insert the element e i the binary search tree, designated by tree_ptr.
Drop the insertion if e is already in the tree.
Return the tree in terms of a pointer to its root node. */
tree_node *insert_in_binary_search_tree(tree_node *tree_ptr, int e){
if (tree_ptr == NULL){
/* Make a small tree rooted with e and empty subtrees */
/* This branch is never reached via recursion */
tree_node *the_tree = make_tree(e, NULL, NULL);
return the_tree;
}
else if (e == tree_ptr->key){
/* Do nothing */
return tree_ptr;
}
else if (e < tree_ptr->key && tree_ptr->leftp == NULL){
tree_node *the_tree = make_tree(e, NULL, NULL);
tree_ptr->leftp = the_tree;
return tree_ptr;
}
else if (e < tree_ptr->key){
insert_in_binary_search_tree(tree_ptr->leftp, e);
return tree_ptr;
}
else if (e > tree_ptr->key && tree_ptr->rightp == NULL){
tree_node *the_tree = make_tree(e, NULL, NULL);
tree_ptr->rightp = the_tree;
return tree_ptr;
}
else { /* e > tree_ptr->key) */
insert_in_binary_search_tree(tree_ptr->rightp, e);
return tree_ptr;
}
}
void print_tree(tree_node *tree_ptr){
print_tree_helper(tree_ptr, 0);
}
/* print the tree designated by tree_ptr as horizotally, as an indented text, on standard output.
Empty subtrees are printed as "." if tree_ptr is passsed as NULL */
void print_tree_helper(tree_node *tree_ptr, int level){
int i;
/* print indented root */
for(i = 0; i < level; ++i)
printf(" ");
if (tree_ptr == NULL)
printf(".\n"); /* Missing part */
else
printf("%d\n", tree_ptr->key);
if(tree_ptr != NULL){
/* print branches */
if (tree_ptr->leftp == NULL && tree_ptr->rightp == NULL){
/* print nothing */
}
else if (tree_ptr->leftp != NULL && tree_ptr->rightp == NULL){
print_tree_helper(tree_ptr->leftp, level+1);
print_tree_helper(NULL, level+1);
}
else if (tree_ptr->leftp == NULL && tree_ptr->rightp != NULL){
print_tree_helper(NULL, level+1);
print_tree_helper(tree_ptr->rightp, level+1);
}
else {
print_tree_helper(tree_ptr->leftp, level+1);
print_tree_helper(tree_ptr->rightp, level+1);
}
}
}
/* Opgave */
int tree_height(tree_node *tree_ptr){
return 0;
}12.8 En funktion der genkender et binært søgetræ
Programmer en funktion, is_binary_search_tree, der tager et binært træ som input, og som returnerer hvorvidt dette træ er et (binært) søgetræ.
Afprøv funktionen på forskellige binære træer.
Herunder er der et godt udgangspunkt for denne opgave. Det vil også være en god ide at konsultere denne del af lektionsvidoen, hvor et binært søgetræ defineres.
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
struct tree_node{
int key;
struct tree_node *leftp, *rightp;
};
typedef struct tree_node tree_node;
tree_node *make_tree(int key, tree_node *left, tree_node *right);
void assert_allocation_success(void *alloc_pointer);
void print_tree(tree_node *tree_ptr);
void print_tree_helper(tree_node *tree_ptr, int level);
tree_node *insert_in_binary_search_tree(tree_node *tree_ptr, int e);
int is_binary_search_tree(tree_node *tree_ptr);
int main(void) {
tree_node *tree4 = NULL;
tree4 = insert_in_binary_search_tree(tree4, 6);
tree4 = insert_in_binary_search_tree(tree4, 2);
tree4 = insert_in_binary_search_tree(tree4, 1);
tree4 = insert_in_binary_search_tree(tree4, 4);
tree4 = insert_in_binary_search_tree(tree4, 3);
tree4 = insert_in_binary_search_tree(tree4, 5);
tree4 = insert_in_binary_search_tree(tree4, 7);
tree4 = insert_in_binary_search_tree(tree4, 9);
tree4 = insert_in_binary_search_tree(tree4, 8);
/* Per construction, tree4 should be a binary search tree */
/* You can use make_tree to construct other trees which are not binary search trees */
printf("tree4:\n");
print_tree(tree4);
exit(EXIT_FAILURE);
}
tree_node *make_tree(int key, tree_node *left, tree_node *right){
tree_node *the_tree = malloc(sizeof(tree_node));
assert_allocation_success(the_tree);
the_tree->key = key;
the_tree->leftp = left;
the_tree->rightp = right;
return the_tree;
}
void assert_allocation_success(void *alloc_pointer){
if (alloc_pointer == NULL){
printf("Allocation problems. Your program stops.");
exit(EXIT_FAILURE);
}
}
/* Insert the element e i the binary search tree, designated by tree_ptr.
Drop the insertion if e is already in the tree.
Return the tree in terms of a pointer to its root node. */
tree_node *insert_in_binary_search_tree(tree_node *tree_ptr, int e){
if (tree_ptr == NULL){
/* Make a small tree rooted with e and empty subtrees */
/* This branch is never reached via recursion */
tree_node *the_tree = make_tree(e, NULL, NULL);
return the_tree;
}
else if (e == tree_ptr->key){
/* Do nothing */
return tree_ptr;
}
else if (e < tree_ptr->key && tree_ptr->leftp == NULL){
tree_node *the_tree = make_tree(e, NULL, NULL);
tree_ptr->leftp = the_tree;
return tree_ptr;
}
else if (e < tree_ptr->key){
insert_in_binary_search_tree(tree_ptr->leftp, e);
return tree_ptr;
}
else if (e > tree_ptr->key && tree_ptr->rightp == NULL){
tree_node *the_tree = make_tree(e, NULL, NULL);
tree_ptr->rightp = the_tree;
return tree_ptr;
}
else { /* e > tree_ptr->key) */
insert_in_binary_search_tree(tree_ptr->rightp, e);
return tree_ptr;
}
}
/* void delete_tree(tree_node *tree_ptr)
Rather difficult to program because it requires access to parents */
void print_tree(tree_node *tree_ptr){
print_tree_helper(tree_ptr, 0);
}
/* print the tree designated by tree_ptr as horizotally, as an indented text, on standard output.
Empty subtrees are printed as "." if tree_ptr is passsed as NULL */
void print_tree_helper(tree_node *tree_ptr, int level){
int i;
/* print indented root */
for(i = 0; i < level; ++i)
printf(" ");
if (tree_ptr == NULL)
printf(".\n"); /* Missing part */
else
printf("%d\n", tree_ptr->key);
if(tree_ptr != NULL){
/* print branches */
if (tree_ptr->leftp == NULL && tree_ptr->rightp == NULL){
/* print nothing */
}
else if (tree_ptr->leftp != NULL && tree_ptr->rightp == NULL){
print_tree_helper(tree_ptr->leftp, level+1);
print_tree_helper(NULL, level+1);
}
else if (tree_ptr->leftp == NULL && tree_ptr->rightp != NULL){
print_tree_helper(NULL, level+1);
print_tree_helper(tree_ptr->rightp, level+1);
}
else {
print_tree_helper(tree_ptr->leftp, level+1);
print_tree_helper(tree_ptr->rightp, level+1);
}
}
}
int int_max(int a, int b){
return a > b ? a : b;
}
/* Opgaven */
int is_binary_search_tree(tree_node *tree_ptr){
return 0;
}
Genereret: Mandag 9. maj 2022, 14:00:28