Description

5/5 - (1 vote)

Question 1a: Advanced Linked Lists

[bonus 10% for Q1 – doubly linked lists]

typedef struct NODE { typedef struct NODE { value_typekey_type key value; ; or value_typekey_type key; value;

struct NODE * next; struct NODE * next; struct NODE * sort; struct NODE * sort;

} Node; struct NODE * prev; struct NODE * prev_sorted;

} Node;

In this linked list:

The datatype for the value being stored is called value_type
The datatype for the key being stored is called key_type
As in lab 4, next links to the node in the order it was added to the list (either at the head or the tail) o This will be referred to as insertion order
Similar to lab 4, sort links to the node where the key is greater or equal to its key o e. the list is kept in ascending order by key o This will be referred to as key sort order o Note: unlike lab 4, there is only one key

Create a Sorted List abstract data type

Has two heads (head for insertion order, head_sort for key sort order)
Has two tails (tail for insertion order, tail_sort for key sort order)
Has an int field called size that stored the node count (the number of elements in the list)
The datatype should be called Sorted_List

Note: technically you will be implementing only be a subset of the Sorted List ADT as you will not be asked to implement all functions of the full ADT

Functions to be implemented

All functions, except where noted, return SUCCESS if the function can complete or FAIL if not

int size (Sorted_List *)
- returns the number of nodes in the list (not SUCCESS/FAIL as the function cannot fail)
int push ( Sorted_List *, value_type , key_type )
- add the node to the head of the list
- the node must also be inserted in ascending sort order by key, using the sort link
int append ( Sorted_List * , value_type , key_type ) o similar to push, except the node gets added to tail
int remove_first ( Sorted_List * , value_type * , key_type *) o removes the node from the head of the list
- returns the value and key of the removed node through the parameter values

(and frees the node) o returns SUCCESS (alternatively you can change the signature to return void) o remember to update the sort order links

if not using doubly linked lists, you will need to find the previous sorted node to change its sort order link

int remove_last ( Sorted_List * , value_type * , key_type * )
- similar to remove_first, except it removes the node from the tail
int remove_smallest_key ( Sorted_List * , value_type * , key_type * ) o removes the node with the smallest key
- returns the value and key of the removed node (and frees the node) o remember to update the insertion order links
  - if not using doubly linked lists, you will need to find the previous insert order node to change its insertion order link
- int remove_largest_key ( Sorted_List * , value_type * , key_type * )
  - similar to remove_smallest_key, except it removes the node with the largest key
- void empty_list ( Sorted_List *)
  - empties the contents of the list
  - remember to free the memory of the contents
- void destroy_list ( Sorted_List *)
  - empties the contents of the list, as well as freeing the list itself

To test the Sorted List ADT

Write two programs called a4q1a_char.c and a4q1a_int.c

Data types used o c
- has its value_type datatype set equal to int
- has it key_type datatype set equal to double o c
- has its value_type datatype set equal to char[80]
e. it can take strings up to 79 characters in length
has its key_type datatype set equal to int
its value is set equal to the length of the string
Both programs read in a text file that contains a series of commands, one per line

(i.e each ending with a newline) o The name of the text file should be entered as a command line argument

If there is no file name, read from stdin
this can use IO redirect, i.e. a4q1a_int < filename.txt
If using keyboard input, exit using ^d
All commands are echoed to stdout, followed by a colon :, o After that the results of the command follows,
usually on the same line following 11 – strlen(cmd name) spaces or on the next line when noted

Note: Silent commands do not have the colon : after the command, but rather after the command name

Remember to free the sorted list at the end of the program (use destroy_list)

General Note: The two programs should be almost identical, with the following differences o The file input will be slightly different depending on the data type and nature of the input data o Your will have to write similar, but not identical void print_list_all ( Sorted_List * ) and void print_list_sort ( Sorted_List * ) functions

These functions print out the lists according to their respective sort orders
See the report commands section below for details

(the print_all and print_sort commands)

o You will have to have your make file recompile all files that mention or use value_type and key_type variables or Sort_List structs when compiling the two programs

To do this you will need to use condition compilation (see Week1 lecture notes)
In specific, use #ifdef CHAR to compile using the char[80] typedef definition of value_type

and #ifdef INT to compile using the int typedef definition of value_type

g. if you stored all your Sort_List ADT functions in a single file called sort_list.c Then for a4q1a_char.c you could have in your make file a command like

gcc -Wall -ansi -DCHAR -c sort_list.c

List of Commands

Silent Commands (modifies the list but does not print anything other than the command itself)

a = append

o a4q1a_int.c

input line: a key value

note: there can be any number of spaces in the input been the command and args, or between args

example

commands, as stored in the input file

a 3.27 1427 a 0.94 984

a 7.21 346

output(11 – 1 spaces after the colon)

a: 3.27 1427 a: 0.94 984 a: 7.21 346

c
- input line: a value
- example
- commands, as stored in the input file

a The sun did not shine. a It was too wet to play. a So we sat in the house a All that cold, cold, wet day.

Note: skip the white space between the command ‘a’ and the input string

The key values for the above are 22, 23, 22, 29

g. strlen(“The sun did not shine.”) == 22
- output (11 – 1 spaces after the colon)

a: The sun did not shine. a: It was too wet to play. a: So we sat in the house a: All that cold, cold, wet day.

p = push o same as a except it pushes instead of appends the key/value pair onto the list

Verbose Commands (modifies the list and then reports to stdout)

rem_first = remove first node of the list by insertion order o also prints the element’s key-value pair, with two spaces between the key and the value

Example for c assuming the first list element key is 2.465 and value is 212 rem_first: 2.465 212
Note the two spaces after rem_first: “rem_first” is 9 characters in length, so the number of spaces following should be 11 – 9 = 2
If the list is empty, remove will fail. It should print then print the following rem_first: Nothing to remove
rem_last = remove last node of the list by insertion order and print the element’s key-value pair
rem_small = remove the node with the smallest key and print the element’s key-value pair rem_large = remove the node with the largest key and print the element’s key-value pair
empty = empty the list o the output of this command should be

empty: size = 0

Report Commands (prints information, but does not modify the list)

size = size of sorted linked list

o if there are 21 nodes in the list it prints size: List size = 21

print_all = print list in insertion order o The type of order is printed on the same line as the command o The list starts printing on the next line, one element per line

o Each element is prefaced by 5 spaces, then the key, then 2 spaces, then the value o Example using the input from the append examples

a4q1a_int.c print_all: Insertion Order

3.27 1427

0.94 984

7.21 346

a4q1a_char.c print_all: Insertion Order
- The sun did not shine.
- It was too wet to play.

22 So we sat in the house 29 All that cold, cold, wet day.

print_sort = print list in key sort order o The output is the same as with print_all except the order of the lines are in key sort order and the command line will read Key Sort Order

o Example using the input from the append examples

a4q1a_int.c print_sort: Key Sort Order

0.94 984

3.27 1427

7.21 346

a4q1a_char.c

print_sort: Key Sort Order

22 The sun did not shine.

So we sat in the house
It was too wet to play.

29 All that cold, cold, wet day.

The assignment continues with Question 1b Function Pointers to be released by March 26

the relevant lecture notes for Q1b, presented the last week of face-to-face classes, have now been posted

Question 1b: List ADT and Function Pointers

Using the same data type Sorted_List as in q1a,

Implement

Sorted_List * map ( Sorted_List *, fn ptr) o map only applies to the values, not the sort keys

o however, make sure that the new list produced has the same key values and links (both next and sort)

value_type reduce ( Sorted_List *, reduce fn ptr, value_type init, int order ) o like map, reduce only applies to values, not keys

o however, reduce also takes an extra parameter, int order

order is either INSERTED_ORDER or SORTED_ORDER and determines which set of links to follow while reducing: next or sort respectively
note: while the order of the reduction does not matter when using add or mult as the reducing function, it could with other reduction functions

value_type map_reduce (Sorted_List *list, map fn ptr, reduce fn ptr, value_type init, int order ) o Conceptually, you are first applying map, and then reduce

o However, both map_fn and reduce_fn should be applied together, node-by-node

e. do not create a full map list and then apply reduce to it
instead apply the map function to list’s node, then store the result in the reduce accumulator

o This allows you to avoid creating and freeing the memory that would be used if an intermediate map list were to have been created and only then reduced

value_type * map_2_array ( Sorted_List *list1, List_Sort *list2, fn ptr, int order) o map_2_array takes two lists and applies a function, passed in as a function pointer, that takes two values (from the nodes at the same position in their respective lists) and returns a value of type value_type
- The values are collected in an array with element type value_type in the same order as traversed along the links chosen (i.e. next if INSERTED_ORDER was chosen or sort if SORTED_ORDER was)
- the function then returns the above array

note: unlike map, order of traversal matters with map_2_array as different nodes will be paired together depending on the order

value_type map_2_reduce( Sorted_List *list1, List_Sort *list2, map fptr, reduce fptr, int order) o Similar to map_reduce,

o However, node by node, it should

apply the map function to the value of list1’s node as its first argument and the value of list2’s node as its second argument
then store the result in reduce’s accumulator

Below list1 and list2 only depict the value and next fields

where add and mult are functions that take two int arguments as seen in the reduce example in the lecture notes

Figure 1: Example of map_2array and map_2_reduce using INSERTED_ORDER

list1 and list2 are the same as before,  but now depict the key and sort fields where key was set equal to value

Figure 2: Example of map_2array and map_2_reduce using SORTED_ORDER

To test within, map, reduce, etc.

Write a program called a4q1b.c

Data types used
- value_type datatype is equal to int o key_type datatype is equal to double o same as a4q1a_int.c, so compile files containing Sorted_List functions using -DINT
The program reads in a text file that contains a series of commands, one per line, with the name of the text file entered as a command line argument o Base this code on the code you used in q1a to implement command entries from a file o However, the code will need to be extended to allow for new commands that are detailed below
Again, all commands are echoed to stdout, followed by a colon : in the same format as used with q1
Include a void print_array(value_type *, int size) o this prints out values in the array produced by map_2_array
- the values in the array should be printed one per line, with five spaces preceding the value
Make sure you have declared an array that can hold up to 10 Sorted_List pointers o Do not confuse this with the array produced by map_2_array, this array holds Sorted_List pointers not value_type values.
Remember to free all sorted lists and nodes (and arrays that may contain them) at the end of the program

To implement the new commands, write the following functions use either map, reduce, map_reduce, map_2_array, or map_2_reduce when implementing

• sum

o sums the values of a list and returns the sum o see lecture notes

diff o takes two sorted lists of the same size
returns NULL if the sizes are different o produces an array whose values are the differences of the values in the sorted lists args o you should also take a third argument that can be set to SORTED_ORDER or INSERTED_ORDER in order to follow the appropriate links
square o takes a sorted list and produces a new sorted list whose value at a node equals the original value (not key) squared

o the keys and links should be copied unchanged

sum_of_sq_diff o takes two sorted lists of the same size
- returns NULL if the sizes are different o produces a value computed as follows:
- at each node position, take the difference between the values
- square the resulting difference
- sum across all nodes into a single result o you should also take a third argument that can be set to SORTED_ORDER or INSERTED_ORDER in order to follow the appropriate links

note: these should be 1 or 2 line programs that take function pointers to functions that are also only a few lines long

List of Commands

All commands from q1a should be made available as well as the following

Silent Commands (modifies the list but does not print anything other than the command itself)

a|n key value
- append to the nth index of the array of sorted list pointers that you have set up for the program to use (see the 5^th point on how to set up the program two pages back)
- same as the a command but appends the key/value pair into the array of sorted lists
p|n key value

o same as a|n except it pushes instead of appends the key/value pair into the array of sorted lists

Report Commands (prints information, but does not modify the list)

For all examples, the sorted list at index 3 holds the values <1, 2, 3> where the key equals the value the sorted list at index 5 holds the values <3, 1, 7> where the key equals the value

print_all|n
- print the sorted list at index n in insertion order
- Using the input from the append examples in q1a that had been stored at index 2

For the command “print_all|2”, the output should be

print_all: list = 2, Insertion Order

3.27 1427

0.94 984

7.21 346

print_sort|n

o print the sorted list at index n in key sort order

sum|n

o sums the values of the sorted list at index n o For the command “sum|3”, the output should be sum: list = 3, result = 6

square|n o For the command “square|3”, the output should be square: list = 3

1.0 1

2.0 4

3.0 9

o remember to free any new list produced, after it has been printing

diff|n:m order o For the command “diff|5:3 INSERTED_ORDER”, the output should be diff: list1 = 5, list2 = 3, Insertion Order

-1

4 o remember to free any new list produced, after it has been printing

sum_sq_d|n:m order o For the command “sum_sq_d |5:3 INSERTED_ORDER”, the output should be sum_sq_d: list = 5, list2 = 3, Insertion Order, result = 21

The assignment continues with Question 2: Recursion

Question 2: Recursion

2a. Recursive functions

Implement the following functions using recursion (see the next page for examples) o Count up from 0 to n o Count down from 2n to 0 by 2 o nth, nth_sorted
this applies to Sorted Lists from Q1a o remove_nth, remove_nth_sorted
this applies to Sorted Lists from Q1a

note: no marks will be awarded if implemented iteratively, even if the answer produced is correct when run

2b. Greatest Common Divisor (GCD)

Read up on the Euclidean Algorithm for solving GCD in Wikipedia o First Section: https://en.wikipedia.org/wiki/Euclidean_algorithm o Procedure: https://en.wikipedia.org/wiki/Euclidean_algorithm#Procedure o Example: https://en.wikipedia.org/wiki/Euclidean_algorithm#Worked_example o Using mod: https://en.wikipedia.org/wiki/Euclidean_algorithm#Euclidean_division o Implementations: https://en.wikipedia.org/wiki/Euclidean_algorithm#Implementations
Examine the final implementation, which is recursive, and implement it in C o it should have the signature long gcd(long, long)
This implementation (as yours should be) is naturally “tail recursive” o explain why it is tail recursive in the readme

o make sure your make file uses the appropriate gcc flag to run tail recursive code efficiently

To test question 2

Write a program called a4q2.c

The program must read in a text file that contains a series of commands, one per line, with the name of the text file entered as a command line argument o Base this code on the code you used in q1a to implement command entries from a file o However, the code will need to be extended to allow for new commands that are detailed below
Some of the questions in 2a use the Sorted_List data type with key_type as double and value_type as int, the same as a4q1a_int.c.

o So when compiling files containing Sorted_List functions in your make file, use –DINT

All new commands for entry from the input file are listed on the next page

The assignment concludes with Question 3: Fraction ADT to be released early next week

List of Commands from the Input File

All commands from q1a should be made available as well as the following

count_up n

o Prints the integers from 0 to n on a single line, comma separated, with 5 spaces before o Using the following commands count_up 4 the output should be

count_up from 0 to 4

0, 1, 2, 3, 4

count_down n

o Same as count_up, but printing the integers down from 2n to 0 on by 2 o Using the following commands count_down 4 the output should be

count_down from 8 to 0 by 2

8, 6, 4, 2, 0

nth n order o Displays the nth element in the list according to the order specified (inserted or key sort) on its own line as key value
- Indented 5 spaces with 2 spaces between the key and the value
- Firsts prints the command – see below for an example o Using the input from the append examples in q1a and the following commands print_all nth 1 INSERTED_ORDER nth 1 SORTED_ORDER nth 5 INSERTED_ORDER the output should be

print_all: Insertion Order

3.27 1427

0.94 984

7.21 346

nth: n = 1, Insertion Order

0.94 984

nth: n = 1, Key Sort Order

3.27 1427

nth: n = 5, FAILED, n >= size where size = 3

remove_nth n order o removes the nth element in the list according to the order specified (inserted or key sort) and displays the removed element on its own line as key value

o Again using the input from the append examples in q1a For the commands

remove_nth 2 INSERTED_ORDER print_all

remove_nth 1 SORTED_ORDER print_all

the output should be

remove_nth: n = 2, Insertion Order

7.21 346

print_all: Insertion Order

3.27 1427

0.94 984

remove_nth: n = 1, Key Sort Order

3.27 1427

print_all: Insertion Order

0.94 984

Question 3: Interacting Abstract Data Types –

New ADT – Fraction

You may not use functions from any C library that implements fractions

typedef struct { long num; long denom; /* you may also use “unsigned long denom”, either approach is fine */

} Fraction;

Implement int set_fraction(Fraction * fract, int num, int denom)
- Sets the numerator and denominator in the Fraction structure o Only the numerator can be negative
  - If the denom parameter is negative, negate the num parameter and store denom in the struct as a positive value
- The denom parameter cannot be 0
  - If it is zero do not set the num and denom in fract and return FALSE (where FALSE is a #define set to 0)
- If the num and denom can be successfully set, return TRUE

(where TRUE is a #define set to 1)

Implement print_fract(Fraction * fract, int mode) o When mode is SIMPLE
- Print out num/denom
- If fract has num = 4 and a denom = 3 it should print “4/3” to stdout o When mode is MIXED
- If fract has num = 3 and a denom = 4, print “3/4” to stdout
- If fract has num = 4 and a denom = 3, print “1 1/3” to stdout
- If fract has num = 4 and a denom = 1, print “4” to stdout o SIMPLE and MIXED are two integers of your choice, using #define in a .h
Implement void simplify(Fraction * fract)
- This is computed by finding the GCD of the numerator and the denominator and dividing it out from each respectively i.e. for a / b
find g = gcd(a, b)
the simplified form of a / b is

(a/g) / (b/g)

e.g. 6/18
gcd(9, 12) == 3 (9/3) / (12/3) == 3 / 4

note: when you wrote GCD for Q2, qcd(a,b) should equal gcd(b,a)

Implement int add_fract(Fraction * result, Fraction * x, Fraction * y)

o To compute a/b + c/d, i.e. to add two fractions, use the following formula

(a d + b c)/b d , simplified o Check to make sure that the result doesn’t overflow/underflow

e the addition produces a result greater than a long can represent
when the result is positive it is called an overflow
when negative it is called an underflow o to check for an overflow/underflow, understand and use the solution posted in the most popular reply from the following stackoverflow page
https://stackoverflow.com/questions/199333/how-do-i-detect-unsigned-integer-multiply-overflow o If the addition overflows/underflows, return FALSE and do not update fract o Otherwise return TRUE

Extend Map/Reduce/etc. with Filter

Implement Sorted_List * filter (Sorted_List * list, filter_fn pointer)
the function creates a new sorted list based on the filtered values (added node by node), remember the nodes have to be copied
the function filters based on the value, not the key o for full marks, implement filter() using recursion
store filter() in the same .c file where the other map/reduce/ etc. functions are stored
you do not need to submit two different .c files, just one will do • filter will just not be exercised when the Q1b is tested

To test question 3

Write a program called a4q3.c

The program must read in a text file that contains a series of commands, one per line, with the name of the text file entered as a command line argument o Base this code on the code you used in q1a to implement command entries from a file o However, the code will need to be modified as detailed below
You will need to store fractions in a sorted list using the Sorted_List data type o value_type should be of type Fraction

o key_type should be a double and hold the decimal equivalent of the value stored in the Node

e.g. if value stores the fraction 11/4, then key == 2.75
You will have to have your make file recompile all files that mention or use value_type and key_type variables or Sort_List structs when compiling the program o You will need to add #ifdef FRACT to compile using the Fraction typedef definition of value_type

o E.g. if you stored all your Sort_List ADT functions in a single file called sort_list.c Then for a4q4.c you could have in your make file a command like

gcc -Wall -ansi -DFRACT -c sort_list.c

All commands for entry from the input file are listed on the next couple of pages

List of Commands from the Input File

You only need a single Sorted List, like in q1a, and q2, not the array of sorted lists as in q1b

Silent Commands (modifies the list but does not print anything other than the command itself)

a n/d

o appends to a sorted list

with n stored in the numerator field of the Fraction held in node->value, and d stored in the denominator field of the Fraction
the decimal value equivalent of the fraction should be stored in the key field

note: when echoing the command, the fraction is output without simplification and the key is displayed with 3 decimal places o example

commands, as stored in the input file a 5/4 a 3 a 4/6
output(11 – 1 spaces after the colon)

a: 1.250 5/4 a: 3.000 3 a: 0.667 4/6

p n/d

o same as a except it pushes instead of appends the key-value pair onto the sorted list

Report Commands (prints information, but does not modify the list)

print_all print_mode

o print the sorted list at index n in insertion order o Using the input from the append examples above

For the command “print_all SIMPLE”, the output should be

print_all: Simple Fractions, Insertion Order

1.250 5/4

3.000 3/1

0.667 2/3

print_sort print_mode

o print the sorted list at index n in key sort order o Using the input from the append examples above

For the command “print_sort MIXED”, the output should be print_all: Mixed Fraction, Sorted Order

0.667 2/3

1.250 1 1/4

3.000 3

sum print_mode o sums the values of the sorted list into a simplified fraction, which is printed (in insertion order) o Using the input from the append examples above For two commands sum SIMPLE sum MIXED

the output should be

sum: result = 4 11/12 sum: result = 59/12

o If the sum enters an overflow situation, the output should be sum: result = OVERFLOW

This could happen in either the numerator or denominator at any point in the calculation
If the numerator would be negative, instead of OVERFLOW, it should print UNDERFLOW

fract print_mode o uses the filter function to only keep fractions and ignore whole numbers when producing the new sorted list; then print the filtered list

o remember to free the new list produced by filter after printing

(hint: you had to do that for various commands in q1b as well) o Using the input from the append examples above

For the command “fract MIXED”, the output should be fract: Mixed Fractions, Insertion Order

1.250 1 1/4

0.667 2/3

whole_num print_mode o similar to fract except it uses the filter function to filter out all fractions leaving only the whole numbers in the new list

o Using the input from the append examples above

For the command “whole_num MIXED”, the output should be

whole_num: Mixed Fractions, Insertion Order 3.000 3

rem_mixed print_mode o similar to fract except it uses the filter function to keep only the whole numbers and simple fractions (removes the mixed numbers)
i.e. leaving out the numbers that, when printed as MIXED, have both a whole number and fraction parts, such as 7 2/3

o Using the input from the append examples above

For the command “rem_mixed MIXED”, the output should be

rem_mixed: Mixed Fractions, Insertion Order

3.000 3

0.667 2/3

linked-list-program-qigvhs.zip
Recursion_with_double_link_list-nwfoik.zip

CIS*2500 Assignment 4 Linked Lists, Recursion and ADTs Solved

If Helpful Share:

Description

Create a Sorted List abstract data type

Functions to be implemented

To test the Sorted List ADT

List of Commands

Figure 1: Example of map_2array and map_2_reduce using INSERTED_ORDER

Figure 2: Example of map_2array and map_2_reduce using SORTED_ORDER

• sum

Question 2: Recursion

2a. Recursive functions

2b. Greatest Common Divisor (GCD)

To test question 2

The assignment concludes with Question 3: Fraction ADT to be released early next week

Question 3: Interacting Abstract Data Types –

New ADT – Fraction

Extend Map/Reduce/etc. with Filter

To test question 3