Coding in C Programming Code Worksheet

Lab 5: Linked ListsIn this lab, you will extend a linked list implementation, implementing four functions and then
use linked list implementation to improve Problem 1 from Lab 4.
Preparation
1. Complete Assignment 0 or ensure that the tools you would need to complete it are installed.
2. Locate the man pages for these Standard C Library functions and bookmark them for the lab.
• malloc()
• free()
• scanf()
• printf()
• memset()
3. Clone your lab repository
Inside the repository there are two directories: problem1 and problem2, in which the code is
to be written. Inside each of these directories there is a tests directory that contains tests that
will be executed each time you submit your code. Please do not modify the tests directories
or the .gitlab-ci.yml file that is found in the root directory. Modifying these files may break
the tests. These files will be replaced with originals when the lab is graded.
Resources
Tutorials on Brightspace
The Man pages on timberlea or https://man7.org/linux/man-pages/man3/intro.3.html
Procedure
Set-up
1. Each of the directories, problem1 and problem2 contains a problem to be solved in this
lab. Prepare these directories for writing code, just like you did for Lab 4.
2. Prepare to work on Problem 1.
Part 1: Extending the Linked List
3. Read the description of Problem 1 below and extend the linked list module in
linked_list.c in the problem1 directory. A test program (main.c) is provided to test
your code and linked_list.c and linked_list.h are set up for you to use.
4. Commit and push your submission.
If any of the tests 0 – 4 fail, fix linked_list.c and resubmit before moving to the next part.
Part 2: Problem 2: A bill of unknown size
5.Copy the linked_list.c and linked_list.h files from problem1 to problem2.
6.Read the description of Problem 2 below and solve the problem by writing the C program
in main.c in the problem2 directory. For this problem you will need to use the linked list
implementation, scanf() and printf(). See the main.c in the problem1 directory
for example of how to use the linked list.
7. Commit and push your submission.
8. If any of the tests 5 – 9 fail, fix your program and resubmit.
9. You’re done!
Grading
The lab will be marked out of 4 points:
Task
2 Points
1 Point
Program is completed and Program attempted but, is not
Part 1
correct.
correct.
Program is completed and Program attempted but, is not
Part 2
correct.
correct.
0 Points
No attempt made.
No attempt made.
Problem Descriptions
Problem 1
We will extend the linked list we discussed in class. For this problem you will need to add four
functions to the provided linked list implementation.
These functions are:
int ll_is_empty(linked_list_t * list)
returns a 1 if the list is empty and 0 otherwise.
int ll_size(linked_list_t * list)
returns the number of items in the list.
int ll_insert(linked_list_t *list, ll_node_t *node, void *item)
adds item after node in list. Return 1 on success and 0 on failure.
void * ll_remove(linked_list_t *list, ll_node_t *node)
removes the node from the list. Returns the item in the node on success and NULL on
failure. The node should be freed.
A test program is provided to test the list. You do not need to modify the test program. This is
what the test program does.
Test Program Input:
All input is done from stdin. The program reads the following commands:
• new : create a new empty list.
Example
• destroy : destroy the list.
Input
Output
• empty : returns whether list is empty.
new
[ ]
append alpha [ alpha ]
• size : returns size of the list
append gamma [ alpha gamma ]
• front : returns word at front of the list.
find alpha
‘alpha’ found in list
insert beta
[ alpha gamma ]
• back : returns word at back of the list.
find beta
[ alpha beta gamma ]
• append : appends word to the list.
remove
‘beta’ found in list
end
[ alpha beta gamma ]
• prepend : prepends word to the list.
[ alpha gamma ]
• remove_front : remove the word at front of list.
• remove_back : remove the word at back of list.
• find : finds the node in the list containing the word.
• insert : inserts word into the list after the last-found node. A find operation must
be performed before this command can be performed.
• remove : remove the last-found node in the list. A find operation must be performed before
this command can be performed. See example.
Test Program Processing
For each command perform the corresponding operation on the list and print out the resulting
list.
Test Program Output
All output should be to stdout. For each command, program will print out the result of the
operation, followed by the contents of the list.
Problem 2
Write a program called problem2 that reads in a shopping bill and combines all the duplicate
items into one item. Note: This is the same as in Lab 4, except that the number of items is not
known up front. Hence, a linked list should be used. ☺
Input:
All input is done from stdin. Zero or more lines of the form
Amount Name UnitCost where
• Amount is a positive integer denoting amount of this item
• Name is a single word denoting the name of the item, at most 19 characters long.
• UnitCost is a decimal number (float) denoting the amount a single item costs The last line
will have an Amount of 0 and should be ignored. See example below.
Processing
• Load the bill into memory. You will need a struct that represents an item and should
allocate a struct for each line, storing the allocated structs in the linked list. In the struct,
o Use an int variable for the amount.
o Use a float variable for the unit cost. Add each struct to the list.
•
Compare each item in the bill to the items ahead of it.
o If a duplicate item is found merge it the first item.
o Two items are the same if the Name and the UnitCost are the same.
o After the merge you may wish to mark the second item as merged by setting its
Amount to 0.
IMPORTANT: Because the linked list used pointers of type void * you will need to cast
the pointer back to a pointer of the struct type before using it. For example,
void *data = …; /*pointer to struct stored in list */
/* cast data pointer to struct type pointer */
struct item *entry = (struct item *)data;
/* We can now access amount, name, and price from
entry*/
• When printing out the bill, print out entries with positive amounts.
Output
Output the bill in the same format as the input. Example
Output the items with positive amounts in the same
Input
Output
format as the input. Hint: Use the %.2f format 6 Carrots 1.25 6 Carrots 1.25
3 Milk 5.69
specifier in your printf() to print out decimal 1 Milk 5.69
2 Bread 4.99
2 Bread 4.99
numbers to two places. See example.
3 Carrots 1.29 3 Carrots 1.29
2 Milk 5.69