Week 10 Code Examples
/*Problem 1:
find_range takes one parameter: a pointer to the head of
the list to search through. find_range should return a single integer:
the difference between the smallest value and the largest value in the list.
For example, if the list contained:
3->4->5->6->X
find_range should return 3, as 6 - 3 = 3
As another example, if the list contained:
1->X
find_range should return 1, as it is the only value in the list.
Testing
list_find_range.c</b> also contains a <b>main</b> function which
allows you to test your <b>find_range</b> function.
This main function:
converts the command-line arguments to a linked list
assigns a pointer to the first node in the linked list to head
calls find_range(head)
prints the result.
Do not change this main function. If you want to change it, you have
misread the question.
Your find_range function will be called directly in marking.
The main function is only to let you test your find_range function
Here is how the main function allows you to test find_range:
dcc list_find_range.c -o list_find_range
./list_find_range 3 4 5
The range is: 2
./list_find_range 10 9 8 7 6 5 4 3 2 1
The range is: 9
./list_find_range 1
The range is: 1
./list_find_range
The list is empty!
Assumptions/Restrictions/Clarifications.
find_range should return only a single integer: the range of the list.
find_range should not change the linked list it is given.
find_range should not change the next or data fields of list nodes.
find_range should not use arrays.
find_range should not call malloc.
find_range should not call scanf (or getchar or fgets).
find_range should not print anything. It should not call printf.
Do not change the definition of struct node.
Do not change the supplied main function. It will not be tested or marked.
*/
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
// Do not change these #defines, or your program will fail the autotests!
#define EMPTY_LIST -42
struct node {
struct node *next;
int data;
};
// find_range should return the range of the list, or
// EMPTY_LIST if the list is empty.
// 3 4 6 7 8 (head)
int find_range(struct node *head) {
return 42;
}
////////////////////////////////////////////////////////////////////////
// DO NOT CHANGE THE CODE BELOW //
////////////////////////////////////////////////////////////////////////
int find_range(struct node *head);
struct node *strings_to_list(int len, char *strings[]);
// DO NOT CHANGE THIS MAIN FUNCTION
int main(int argc, char *argv[]) {
// create linked list from command line arguments
struct node *head = strings_to_list(argc - 1, &argv[1]);
// If you're getting an error here,
// you have returned an uninitialized value
int range = find_range(head);
if (range == EMPTY_LIST) {
printf("The list is empty!\n");
} else {
printf("The range is: %d\n", range);
}
return 0;
}
// DO NOT CHANGE THIS FUNCTION
// create linked list from array of strings
struct node *strings_to_list(int len, char *strings[]) {
struct node *head = NULL;
for (int i = len - 1; i >= 0; i = i - 1) {
struct node *n = malloc(sizeof (struct node));
assert(n != NULL);
n->next = head;
n->data = atoi(strings[i]);
head = n;
}
return head;
}
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
struct node {
struct node *next;
int data;
};
// After every two nodes, insert a new node
// whose value is the sum of the previous two nodes.
struct node *insert_run_sum_node(struct node *head) {
// 1. Empty list, or if it has less than two nodes
/*if (head == NULL || head->next == NULL) {
return head;
}*/
struct node *current = head;
while (current != NULL && current->next != NULL) {
int sum = current->data + current->next->data;
struct node *new_node = malloc(sizeof(struct node));
new_node->data = sum;
new_node->next = NULL;
// current->next_node->NEW_NODE->rest of the list
struct node *second_node = current->next;
new_node->next = second_node->next;
second_node->next = new_node;
current = new_node->next;
}
/*while (current->next->next != NULL) {
int sum = current->data + current->next->data;
// Malloc some space
// Intialise some stuff!
struct node *new_node = malloc(sizeof(struct node));
new_node->data = sum;
new_node->next = NULL;
// c c>n c>n>n
// 2 3 4 5 6 7
// 2 3 5 4 5 9 6 7 13
new_node->next = current->next->next;
current->next = new_node;
current = new_node->next;
}*/
// Odd number of nodes (in the exam, you would have
// a clarification that would say even number of nodes
// only!)
return head;
}
////////////////////////////////////////////////////////////////////////
// DO NOT CHANGE THE CODE BELOW //
////////////////////////////////////////////////////////////////////////
void print_list(struct node *head);
struct node *strings_to_list(int len, char *strings[]);
// DO NOT CHANGE THIS MAIN FUNCTION
int main(int argc, char *argv[]) {
// create linked list from command line arguments
struct node *head = strings_to_list(argc - 1, &argv[1]);
// If you're getting an error here,
// you have returned an uninitialized value
struct node *new_head = insert_run_sum_node(head);
print_list(new_head);
return 0;
}
// DO NOT CHANGE THIS FUNCTION
// create linked list from array of strings
struct node *strings_to_list(int len, char *strings[]) {
struct node *head = NULL;
for (int i = len - 1; i >= 0; i = i - 1) {
struct node *n = malloc(sizeof (struct node));
assert(n != NULL);
n->next = head;
n->data = atoi(strings[i]);
head = n;
}
return head;
}
// print linked list
void print_list(struct node *head) {
printf("[");
for (struct node *n = head; n != NULL; n = n->next) {
// If you're getting an error here,
// you have returned an invalid list
printf("%d", n->data);
if (n->next != NULL) {
printf(", ");
}
}
printf("]\n");
}
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define SIZE 5
// closest_to_target should return the sum of two elements of the array that
// are closest to the target within the array
int closest_to_target(int array[SIZE], int target) {
int closest_sum = array[0] + array[1];
for (int i = 0; i < SIZE; i++) {
for (int j = i + 1; j < SIZE; j++) {
int current_sum = array[i] + array[j];
int current_dist = abs(current_sum - target);
int closest_dist = abs(closest_sum - target);
if (current_dist < closest_dist) {
closest_sum = current_sum;
}
}
}
return closest_sum;
}
// This is a simple main function which could be used
// to test your closest_to_target function.
// It will not be marked.
// Only your closest_to_target function will be marked.
int main(void) {
// Test array and target
int array[] = {-10, -3, -2, 5, -1};
int target = 12;
// Call the function and print the result
int result = closest_to_target(array, target);
printf("The closest sum to %d is %d\n", target, result);
return 0;
}
#include <stdio.h>
#define MAX_SIZE 10000
// reads integers into an array from terminal until a number is entered
// which when multiplied by at least one other number previously entered
// results in 56.
int main(void) {
// PUT YOUR CODE HERE
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#define SIZE 10
// sum_cont_subarray should return the largest contiguous sum
// of a subarray in a given array
//
int sum_cont_subarray(int array[SIZE]) {
// 1. Start with the first element, and I am going
// to decide that the first index holds the initial max
int max_so_far = array[0];
int current_max = array[0];
for (int i = 1; i < SIZE; i++) {
// I need to know decide whether to start a new subarray or
// or add the current index to an exisiting subarray sum?
// For example current_max = -10 and array[i] = 5
// -10 + 5 = -5
if (array[i] > current_max + array[i]) {
current_max = array[i];
} else {
current_max = current_max + array[i];
}
// Update
if (current_max > max_so_far) {
max_so_far = current_max;
}
}
return max_so_far;
}
// This is a simple main function which could be used
// to test your sum_cont_subarray function.
// It will not be marked.
// Only your sum_cont_subarray function will be marked.
int main(void) {
int test_array[SIZE] = {-8, -3, -5, 20, -8, -3, -5, -4}; //20
// What is the largest sum of numbers next to each other that
// you can get in this array
int max_subarray_sum = sum_cont_subarray(test_array);
printf("%d\n", max_subarray_sum);
return 0;
}
// An isogram is a word, in which no letter of the alphabet
// occurs more than once. Write a C program that reads in
// words until Ctrl+D, and checks whether the word is an isogram.
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define MAX 100
int is_isogram(char word[MAX]);
int main (void) {
char word[MAX];
while(fgets(word, MAX, stdin) != NULL) {
// Get rid of teh new line at the end of the string
word[strlen(word) - 1] = '\0';
if (is_isogram(word)) {
printf("This is an isogram.\n");
} else {
printf("This is not an isogram.\n");
}
}
// PUT YOUR CODE HERE
return 0;
}
int is_isogram(char word[MAX]) {
int count[26] = {0};
int i = 0;
while (word[i] != '\0') {
char c = tolower(word[i]);
if (isalpha(c)) {
if (count[c - 'a'] > 0) {
return 0;
}
count[c - 'a']++;
}
i++;
}
return 1;
}
// Problem 14: Write a C program that reads in words until
// Ctrl+D, and checks whether a word read
// in as a command line argument appears in the main word.
// If it appears, print it again.
#include <stdio.h>
#include <string.h>
#define MAX 100
int main(int argc, char *argv[]) {
// PUT YOUR CODE HERE
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
struct node {
struct node *next;
int data;
};
// if I have a
// list1: 4 5 6 (head = 4)
// list2: 7 8 9 (head = 7)
// list: 4 5 6 7 8 9
struct node *concatenate(struct node *head1, struct node *head2) {
return 0;
}
struct node *strings_to_list(int len, char *strings[]);
// DO NOT CHANGE THIS MAIN FUNCTION
int main(int argc, char *argv[]) {
// create two linked lists from command line arguments
int dash_arg = argc - 1;
while (dash_arg > 0 && strcmp(argv[dash_arg], "-") != 0) {
dash_arg = dash_arg - 1;
}
struct node *head1 = strings_to_list(dash_arg - 1, &argv[1]);
struct node *head2 = strings_to_list(argc - dash_arg - 1, &argv[dash_arg + 1]);
struct node *new_head = concatenate(head1, head2);
while (new_head != NULL) {
printf("%d->", new_head->data);
new_head = new_head->next;
}
printf("X\n");
return 0;
}
// DO NOT CHANGE THIS FUNCTION
// create linked list from array of strings
struct node *strings_to_list(int len, char *strings[]) {
struct node *head = NULL;
for (int i = len - 1; i >= 0; i = i - 1) {
struct node *n = malloc(sizeof (struct node));
assert(n != NULL);
n->next = head;
n->data = atoi(strings[i]);
head = n;
}
return head;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
struct node {
struct node *next;
int data;
};
// list 1: 3 4 5 6 7 (5 nodes)
// list 2: 1 2 3 (3 nodes)
// return 2 as the difference
int difference(struct node *head1, struct node *head2) {
return 42;
}
struct node *strings_to_list(int len, char *strings[]);
// DO NOT CHANGE THIS MAIN FUNCTION
int main(int argc, char *argv[]) {
// create two linked lists from command line arguments
int dash_arg = argc - 1;
while (dash_arg > 0 && strcmp(argv[dash_arg], "-") != 0) {
dash_arg = dash_arg - 1;
}
struct node *head1 = strings_to_list(dash_arg - 1, &argv[1]);
struct node *head2 = strings_to_list(argc - dash_arg - 1, &argv[dash_arg + 1]);
int diff = difference(head1, head2);
printf("%d\n", diff);
return 0;
}
// DO NOT CHANGE THIS FUNCTION
// create linked list from array of strings
struct node *strings_to_list(int len, char *strings[]) {
struct node *head = NULL;
for (int i = len - 1; i >= 0; i = i - 1) {
struct node *n = malloc(sizeof (struct node));
assert(n != NULL);
n->next = head;
n->data = atoi(strings[i]);
head = n;
}
return head;
}
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
struct node {
struct node *next;
int data;
};
// find_divisible by 6 should return the number of items in the list
// divisible by 6
int find_divisible(struct node *head) {
return 42;
}
////////////////////////////////////////////////////////////////////////
// DO NOT CHANGE THE CODE BELOW //
////////////////////////////////////////////////////////////////////////
void print_list(struct node *head);
struct node *strings_to_list(int len, char *strings[]);
// DO NOT CHANGE THIS MAIN FUNCTION
int main(int argc, char *argv[]) {
// create linked list from command line arguments
struct node *head = strings_to_list(argc - 1, &argv[1]);
// If you're getting an error here,
// you have returned an uninitialized value
//struct node *new_head = delete_divisible(head);
//print_list(new_head);
printf("%d\n", find_divisible(head));
return 0;
}
// DO NOT CHANGE THIS FUNCTION
// create linked list from array of strings
struct node *strings_to_list(int len, char *strings[]) {
struct node *head = NULL;
for (int i = len - 1; i >= 0; i = i - 1) {
struct node *n = malloc(sizeof (struct node));
assert(n != NULL);
n->next = head;
n->data = atoi(strings[i]);
head = n;
}
return head;
}
// print linked list
void print_list(struct node *head) {
printf("[");
for (struct node *n = head; n != NULL; n = n->next) {
// If you're getting an error here,
// you have returned an invalid list
printf("%d", n->data);
if (n->next != NULL) {
printf(", ");
}
}
printf("]\n");
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
struct node {
struct node *next;
int data;
};
// Given two linked lists, count the number of even
// numbers in both linked lists and return the difference.
int even_diff(struct node *head1, struct node *head2) {
// PUT YOUR CODE HERE
return NULL;
}
struct node *strings_to_list(int len, char *strings[]);
// DO NOT CHANGE THIS MAIN FUNCTION
int main(int argc, char *argv[]) {
// create two linked lists from command line arguments
int dash_arg = argc - 1;
while (dash_arg > 0 && strcmp(argv[dash_arg], "-") != 0) {
dash_arg = dash_arg - 1;
}
struct node *head1 = strings_to_list(dash_arg - 1, &argv[1]);
struct node *head2 = strings_to_list(argc - dash_arg - 1, &argv[dash_arg + 1]);
printf("%d\n", even_diff(head1, head2));
return 0;
}
// DO NOT CHANGE THIS FUNCTION
// create linked list from array of strings
struct node *strings_to_list(int len, char *strings[]) {
struct node *head = NULL;
for (int i = len - 1; i >= 0; i = i - 1) {
struct node *n = malloc(sizeof (struct node));
assert(n != NULL);
n->next = head;
n->data = atoi(strings[i]);
head = n;
}
return head;
}
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
struct node {
struct node *next;
int data;
};
// Find the smallest element in the linked list
// and return its position in the list.
int smallest_posn(struct node *head) {
return 42;
}
////////////////////////////////////////////////////////////////////////
// DO NOT CHANGE THE CODE BELOW //
////////////////////////////////////////////////////////////////////////
void print_list(struct node *head);
struct node *strings_to_list(int len, char *strings[]);
// DO NOT CHANGE THIS MAIN FUNCTION
int main(int argc, char *argv[]) {
// create linked list from command line arguments
struct node *head = strings_to_list(argc - 1, &argv[1]);
// If you're getting an error here,
// you have returned an uninitialized value
printf("%d\n", smallest_posn(head));
return 0;
}
// DO NOT CHANGE THIS FUNCTION
// create linked list from array of strings
struct node *strings_to_list(int len, char *strings[]) {
struct node *head = NULL;
for (int i = len - 1; i >= 0; i = i - 1) {
struct node *n = malloc(sizeof (struct node));
assert(n != NULL);
n->next = head;
n->data = atoi(strings[i]);
head = n;
}
return head;
}
// print linked list
void print_list(struct node *head) {
printf("[");
for (struct node *n = head; n != NULL; n = n->next) {
// If you're getting an error here,
// you have returned an invalid list
printf("%d", n->data);
if (n->next != NULL) {
printf(", ");
}
}
printf("]\n");
}
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
struct node {
struct node *next;
int data;
};
// delete_div_six should delete the first node that is divisible by 6
// If there are no nodes that are divisible by 6, it should return
// the list unchanged.
struct node *delete_div_six(struct node *head) {
// traverse the list
// find the node % 6 == 0
// delete the node
// make other connections
struct node *current = head;
struct node *previous = NULL;
while (current != NULL) {
if (current->data % 6 == 0) {
// 1. Case 1 - it is my first node
// and I am deleting the head of the list
if (previous == NULL) {
head = current->next;
} else {
// pre cur
// 2 12 4 5
previous->next = current->next;
}
free(current);
return head;
}
previous = current;
current = current->next;
}
return head;
}
////////////////////////////////////////////////////////////////////////
// DO NOT CHANGE THE CODE BELOW //
////////////////////////////////////////////////////////////////////////
void print_list(struct node *head);
struct node *strings_to_list(int len, char *strings[]);
// DO NOT CHANGE THIS MAIN FUNCTION
int main(int argc, char *argv[]) {
// create linked list from command line arguments
struct node *head = strings_to_list(argc - 1, &argv[1]);
// If you're getting an error here,
// you have returned an uninitialized value
struct node *new_head = delete_div_six(head);
print_list(new_head);
return 0;
}
// DO NOT CHANGE THIS FUNCTION
// create linked list from array of strings
struct node *strings_to_list(int len, char *strings[]) {
struct node *head = NULL;
for (int i = len - 1; i >= 0; i = i - 1) {
struct node *n = malloc(sizeof (struct node));
assert(n != NULL);
n->next = head;
n->data = atoi(strings[i]);
head = n;
}
return head;
}
// print linked list
void print_list(struct node *head) {
printf("[");
for (struct node *n = head; n != NULL; n = n->next) {
// If you're getting an error here,
// you have returned an invalid list
printf("%d", n->data);
if (n->next != NULL) {
printf(", ");
}
}
printf("]\n");
}
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
struct node {
struct node *next;
int data;
};
// duplicate should duplicate every node in the list, inserting the new
// node after the original node
// 3 4 5 6 ..... 3 3 4 4 5 5 6 6
struct node *duplicate(struct node *head) {
return NULL;
}
////////////////////////////////////////////////////////////////////////
// DO NOT CHANGE THE CODE BELOW //
////////////////////////////////////////////////////////////////////////
void print_list(struct node *head);
struct node *strings_to_list(int len, char *strings[]);
// DO NOT CHANGE THIS MAIN FUNCTION
int main(int argc, char *argv[]) {
// create linked list from command line arguments
struct node *head = strings_to_list(argc - 1, &argv[1]);
// If you're getting an error here,
// you have returned an uninitialized value
struct node *new_head = duplicate(head);
print_list(new_head);
return 0;
}
// DO NOT CHANGE THIS FUNCTION
// create linked list from array of strings
struct node *strings_to_list(int len, char *strings[]) {
struct node *head = NULL;
for (int i = len - 1; i >= 0; i = i - 1) {
struct node *n = malloc(sizeof (struct node));
assert(n != NULL);
n->next = head;
n->data = atoi(strings[i]);
head = n;
}
return head;
}
// print linked list
void print_list(struct node *head) {
printf("[");
for (struct node *n = head; n != NULL; n = n->next) {
// If you're getting an error here,
// you have returned an invalid list
printf("%d", n->data);
if (n->next != NULL) {
printf(", ");
}
}
printf("]\n");
}
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
struct node {
struct node *next;
int data;
};
// sum node at the head of the list that contains
// the total sum of all previous nodes' data.
struct node *insert_sum_node(struct node *head) {
return NULL;
}
////////////////////////////////////////////////////////////////////////
// DO NOT CHANGE THE CODE BELOW //
////////////////////////////////////////////////////////////////////////
void print_list(struct node *head);
struct node *strings_to_list(int len, char *strings[]);
// DO NOT CHANGE THIS MAIN FUNCTION
int main(int argc, char *argv[]) {
// create linked list from command line arguments
struct node *head = strings_to_list(argc - 1, &argv[1]);
// If you're getting an error here,
// you have returned an uninitialized value
struct node *new_head = insert_sum_node(head);
print_list(new_head);
return 0;
}
// DO NOT CHANGE THIS FUNCTION
// create linked list from array of strings
struct node *strings_to_list(int len, char *strings[]) {
struct node *head = NULL;
for (int i = len - 1; i >= 0; i = i - 1) {
struct node *n = malloc(sizeof (struct node));
assert(n != NULL);
n->next = head;
n->data = atoi(strings[i]);
head = n;
}
return head;
}
// print linked list
void print_list(struct node *head) {
printf("[");
for (struct node *n = head; n != NULL; n = n->next) {
// If you're getting an error here,
// you have returned an invalid list
printf("%d", n->data);
if (n->next != NULL) {
printf(", ");
}
}
printf("]\n");
}