Discuss the good, the bad and the ugly aspects of their code.
Please be gentle in any criticism - we are all learning!
Do you have any questions? Have you learned anything that would be useful to share with the rest of the tutorial?
struct node { int data; struct node *next; };
See list_empty.c and list.h for this weeks linked list tute questions, and testList.c for autotests. Alternatively download all three files at tut_list_files.zip.
struct node *copy(struct node *head);It should call malloc to create a new linked list of the same length and containg the same data.
struct node *copy(struct node *head) { if (head == NULL) { return NULL; } struct node *new_head = malloc(sizeof (struct node)); assert(new_head); new_head->data = head->data; struct node *last_new_node = new_head; struct node *p = head->next; while (p != NULL) { last_new_node->next = malloc(sizeof (struct node)); last_new_node = last_new_node->next; assert(last_new_node != NULL); last_new_node->data = p->data; p = p->next; } last_new_node->next = NULL; return new_head; }A recursive solution:
struct node *copy(struct node *head) { if (head == NULL) { return NULL; } struct node *new_head = malloc(sizeof (struct node)); assert(new_head); new_head->data = head->data; new_head->next = copy(head->next); return new_head; }
int identical(struct node *head1, struct node *head2);
int identical(struct node *head1, struct node *head2) { struct node *p1 = head1; struct node *p2 = head2; while (p1 != NULL && p2 != NULL) { if (p1->data != p2->data) { return 0; } p1 = p1->next; p2 = p2->next; } return p1 == p2; }A recursive solution:
int identical(struct node *head1, struct node *head2) { if (head1 == NULL && head2 == NULL) { return 1; } if (head1 == NULL || head2 == NULL || head1->data != head2->data) { return 0; } return identical(head1->next, head2->next); }
int ordered(struct node *head);
int ordered(struct node *head) { if (head == NULL || head->next == NULL) { return 1; } struct node *p = head; while (p->next->next != NULL) { if (p->data >= p->next->data) { return 0; } } return 1; }A recursive solution:
int ordered(struct node *head) { if (head == NULL || head->next == NULL) { return 1; } if (head->data >= head->next->data) { return 0; } return ordered(head->next); }
The new linked list should also be in strictly increasing order. It should include only elements found in both lists.
set_intersection should call malloc to create the nodes of the new linked list.
set_intersection should have this prototype:
struct node *set_intersection(struct node *set1, struct node *set2);
struct node *set_intersection(struct node *set1, struct node *set2) { if (set1 == NULL || set2 == NULL) { return NULL; } if (set1->data == set2->data) { struct node *new_head = malloc(sizeof (struct node)); assert(new_head != NULL); new_head->data = set1->data; new_head->next = set_intersection(set1->next, set2->next); return new_head; } else if (set1->data < set2->data) { return set_intersection(set1->next, set2); } else { return set_intersection(set1, set2->next); } }
The new linked list should also be in strictly increasing order. Elements found in both lists should only occur once in the new linked list.
set_union should call malloc to create the nodes of the new linked list.
set_union should have this prototype:
struct node *set_union(struct node *set1, struct node *set2);
struct node *set_union(struct node *set1, struct node *set2) { if (set1 == NULL && set2 == NULL) { return NULL; } struct node *new_head = malloc(sizeof (struct node)); assert(new_head != NULL); if (set1 != NULL && set2 != NULL && set1->data == set2->data) { new_head->data = set1->data; new_head->next = set_union(set1->next, set2->next); } else if (set2 == NULL || (set1 != NULL && set1->data < set2->data)) { new_head->data = set1->data; new_head->next = set_union(set1->next, set2); } else { new_head->data = set2->data; new_head->next = set_union(set1, set2->next); } return new_head; }
Your tutor may still choose to cover some of the questions time permitting.
thirteen_stdin.c
which reads 2 integers from standard input
and then prints all integers divisble
by 13 between those numbers.
Your program should behave like this:
./a.out Enter start: 10 Enter finish: 42 13 26 39
thirteen_stdin.c
#include <stdio.h> int main(void) { int i, lower, upper; printf("Enter start: "); scanf("%d", &lower); printf("Enter finish: "); scanf("%d", &upper); i = lower + 1; while (i < upper) { if (i % 13 == 0) { printf("%d\n", i); } i = i + 1; } return 0; }
Your program should behave like this:
./a.out 10 42 13 26 39
thirteen_atoi.c
#include <stdio.h> #include <stdlib.h> int main(int argc, char *argv[]) { int i, lower, upper; lower = atoi(argv[1]); upper = atoi(argv[2]); i = lower + 1; while (i < upper) { if (i % 13 == 0) { printf("%d\n", i); } i = i + 1; } return 0; }
If error checking was required - what checking would you add to the programs from the previous 2 questions?
Check two arguments present (argv == 3).
In both cases you might check first number is not greater than first.
You might check arguments or input are numeric (more difficult)
median.c
which reads integers until end-of-input is reached.
It should then print the median (middle) of the integers.
If there are an even number of integer you can print either of the two middle integers.
Assume the numbers of integer is > 0 and < 1000.
Assume the integer are entered in sorted (non-decreasing) order.
Your program should behave like this:
./a.out 1 2 4 8 16 5 numbers read. Median was 4
median.c
#include <stdio.h> #define MAX 1000 int main(void) { int x[MAX]; int number; int numbersRead; numbersRead = 0; while (scanf("%d", &number) == 1) { x[numbersRead] = number; numbersRead = numbersRead + 1; } printf("%d numbers read. Median was %d\n", numbersRead, x[numbersRead/2]); return 0; }
median.c
#include <stdio.h> #define MAX 1000 int main(void) { int x[MAX]; int number; int numbersRead; numbersRead = 0; while (scanf("%d", &number) == 1 && numbersRead < MAX) { if (numbersRead > 0 && number < x[numbersRead - 1]) { printf("Numbers not in order\n"); return 1; } x[numbersRead] = number; numbersRead = numbersRead + 1; } if (numbersRead > 1) { printf("%d numbers read. Median was %d\n", numbersRead, x[numbersRead/2]); } return 0; }
./a.out 16 8 2 1 4 5 numbers read. Median was 4
median.c
#include <stdio.h> #define MAX 1000 int main(void) { int x[MAX]; int i, number, numbersRead; numbersRead = 0; while (scanf("%d", &number) == 1 && numbersRead < MAX) { i = numbersRead; while (i > 0 && x[i - 1] > number) { x[i] = x[i - 1]; i = i - 1; } x[i] = number; numbersRead = numbersRead + 1; } if (numbersRead > 1) { printf("%d numbers read. Median was %d\n", numbersRead, x[numbersRead/2]); } return 0; }
Since the length of the array is variable you should not create additional arrays, nor assume a maximum array length. You may write extra functions in answering this question. Your function should have the following prototype:
int distinct_nums(int size, int nums[size]);Running the function with the following input:
int nums[] = {7,3,1,4,7,3,6,5,3}; int numDistinct = distinct_nums(9, nums);Should return the value 6 and the first six elements of the array should be changed to: {7,3,1,4,6,5}
#include <stdio.h> int distinct_nums(int size,int nums[size]); void print_array(int size, int nums[size]); int main(int argc, char * argv[]){ int nums[] = {7,3,1,4,7,3,6,5,3}; print_array(9, nums); int numDistinct = distinct_nums(9, nums); print_array(numDistinct, nums); return 0; } // Moves the distinct numbers down to the front of the array int distinct_nums(int size, int nums[size]) { int distinct = 0; // search through the distinct part of the array to see if // it is a duplicate. for (int i = 0 ; i < size; i++) { int seen = 0; for (int j = 0; j < distinct; j++) { if (nums[i] == nums[j]) { seen = 1; } } // If it is distinct, move down into the next distinct location if (seen == 0) { nums[distinct] = nums[i]; distinct++; } } return distinct; } void print_array(int size, int nums[size]) { for (int i = 0; i < size; i++) { printf("%d ",nums[i]); } printf("\n"); }
void scalar_mutliply(int rows, int columns, int matrix[rows][columns], int scalar){ int i,j; for (i = 0;i < rows; i = i + 1) { for (j = 0;j < columns; j = j + 1) { matrix[i][j] = matrix[i][j] * scalar; } } }
int remove_char(char str[], char c)
int remove_char(char str[], char c) { int i; // Find the first occurrence of the character c i = 0 while (str[i] != '\0' && str[i] != c) { i = i + 1; } if (str[i] == '\0') { return 0; } // We found the letter, do shift all the letters // after it, down one cell in the array while (str[i] != '\0') { str[i] = str[i + 1]; i = i + 1; } return 1; }
For example "carpark" and "carpet" have a common prefix length of 4.
int prefixLen(char s1[], char s2[]) { int i = 0; while (s1[i] == s2[i] && s1[i] != '\0') { i = i + 1 } return i; }
// text - the array of strings // arraySize - the number of strings in the array // numChars - print out any strings in the array with more than this number // of characters void printIfLonger(int arraySize, char text[arraySize][MAX_LEN], int numChars);
void printIfLonger(char *text[],int arraySize, int numChars){ int i; for (i = 0; i < arraySize; i = i + 1) { if (strlen(text[i]) > numChars) { printf("%s",text[i]); } } }
int x = -9; int *p1 = &x; int *p2; p2 = p1; printf("%d\n", *p2); *p2 = 10; printf("%d\n",x);
-9 10
int x = -9; int y = 0; while (x != 0){ y--; x++; } printf("%d\n", x); printf("%d\n",y);
0 -9
int i = -7; int j = 0; while (i != 0){ j = j - i; i++; } printf("%d\n", i); printf("%d\n",j);
0 -28
char goals[] = "All your goals belong to us."; char *a, *b, *c; a = goals + 5; b = &goals[10]; c = goals + (b - goals) + (b - a);The fragment is valid C. It executes without error. Indicate clearly and exactly what the following expressions evaluate to:
a == goals
a > goals
goals > c
c - b
goals - a
a[0] != b[0]
*c
goals[a - goals] == *a
c[a - b]
int i = 0; int j = 0; char *s = "ceded"; while (s[i] != '\0') { j = j + s[i] - 'a'; i = i + 1; } printf("%d %d\n", i, j);The fragment is valid C. It executes without error. Indicate clearly and exactly what output will be printed.
5 16
Here, s is a char pointer that points to the first letter of the string "str".
We can index into it since strings are arrays. The loop terminates when
s[i] is '\0', i.e., 0, which happens when i is 5.
Indexing into s gives individual characters; subtracting 'a' from each
of those gives the 'distance' between the character and 'a', e.g.,
s[0] - 'a' => 'c' - 'a' = 2.
void sum_prod(int len, int nums[len], int *sum, int *product);
#include <stdio.h> void sumProd(int len, int nums[len], int *sum, int *product); int main(int argc, char *argv[]){ int nums[] = {3,4,1,5,6,1}; int prod; int sum; //Pass in the address of the sum and product variables sumProd(6, nums, &sum, &prod); printf("The sum is %d and prod is %d\n",sum,prod); return 0; } // Calculates the sum and product of the array nums. // Actually modifies the variables that *sum and *product are pointing to void sumProd(int len, int nums[len], int *sum, int *product) { int i; *sum = 0; *product = 1; for (i = 0; i < len; i = i + 1) { *sum = *sum + nums[i]; *product = *product * nums[i]; } }
int findChar(char str[], char c) { if (str[0] == c) { return 1; } else if (str[0] == '\0') { return 0; } else { return findChar(&str[1], c); } }
The name of the input file will be the first command line argument.
The name of the output file will be the second command line argument.
In both files there should be one number per line and there will be a maximum of 1000 numbers.
#include <stdio.h> #define MAX 1000 int readNumbers(char *filename, int nums[], int max); void bubbleSort(int a[], int size); void writeNumbers(char *filename, int nums[], int size); int main(int argc, char *argv[]) { int nums[MAX]; int size = 0; if (argc < 3) { fprintf(stderr,"Incorrect Usage\n"); }else{ size = readNumbers(argv[1], nums, MAX); bubbleSort(nums, size); writeNumbers(argv[2], nums, size); } return 0; } //Reads in a maximum of max numbers into the array nums, from //a specified file. Returns the number of lines //actually read in. int readNumbers(char *filename, int nums[], int max){ FILE *fp; int counter = 0; fp = fopen(filename,"r"); if (fp == NULL) { fprintf(stderr,"Unable to open file %s\n",filename); } else { while (counter < max && fscanf(fp,"%d",&nums[counter]) == 1) { counter = counter + 1; } fclose(fp); } return counter; } //Sorts the given array using bubble sort void bubbleSort(int a[], int size) { int swapped = 1; int tmp,i; while (swapped == 1) { swapped = 0; for (i = 0; i < size - 1; i = i + 1) { if (a[i] > a[i + 1]) { tmp = a[i]; a[i] = a[i + 1]; a[i + 1] = tmp; swapped = 1; } } size = size - 1; } } //Writes one number per line from the array nums //into the specified file void writeNumbers(char *filename, int nums[], int size) { FILE *fp; int i; fp = fopen(filename,"w"); if (fp == NULL) { fprintf(stderr, "Unable to open file %s\n", filename); } else { for (i = 0; i < size; i = i + 1) { fprintf(fp, "%d\n", nums[i]); } fclose(fp); } }