COMS10016 Imperative and Functional Programming - Coursework: LIST AND SKETCH
COMS10016 Summative Resit Courseworks:
LIST AND SKETCH
Step 1: Understand Doubly-linked Lists
Before you start on this task make sure you watched all lectures up to Lecture 15. You should have compiled, run, and understood all the code provided for pointers, dynamic data, stacks, and lists. In particular, be sure you you have run, compiled and understood in detail the program IinkedIist.c from Lecture 15.
Your task will evolve around doubly-linked lists with a sentinel node. Thus, let us understand and visualise this concept first. In essence, a doubly-linked list is made up of a sequence of nodes where neighbouring nodes point to each other. Each node is a structure that has a payload item (e.g. just an ) and two pointers: and . The pointer always points to the predecessor node and the pointer always points to the successor node. Two neighbouring nodes in a doubly-linked list can therefore be pictured like
pointer, and a pointer from the right end is its next pointer. A pointer to anywhere on a node's rectangle means a pointer to the start of the node.
Using this idea, the nodes of a new ’empty’ list with no item nodes look like this:
Here both the and pointers of the sentinel node simply point to the sentinel node
If there are item nodes in our list, should link to the first item, and should link to the last item. So we get simple access to both ends of the list and we do not need to store pointers to the first or last node anywhere else.none—/nextnone—Aback
Step 2: Understand the Closed Task (50% of 1st Task)
Your closed task is to implement 13 missing procedures in the skeleton file all of which manipulate circular doubly-linked lists with one sentinel node. You must use the provided files and are nof allowed to a/ter any of ffie provided cone, only add the 13 missing functions where marked:list. c
list.h (header file) list.c (skeleton) Makefile
The header file forms an API, which you should read carefully because the comments describe what the functions you will have to implement in have to do. The file has just two data structures and which you must use, and a lot of tests. The program as given to you will not compile initially. So, our first task is to produce a compiling skeleton by studying
the signatures of the 13 missing procedures and accordingly defining some initial dummy
functions. l i sts. ht i st. ct i st. cnodel i st
Step 4: Understand the Tests
There is a separate test function in for each of the 13 list functions you need to implement, except for which can't be tested directly. The tests specify each function using before and after pictograms compressed into strings. Single digits represent items and the ’|’ symbol in front of a digit indicates that this is the current item. If the "I symbol is at the end of the
string then ’none’ of the items is selected. The strings "|37”, "3|7”, "37|” represent a list of
two items, with the current position at the first item, the last item, and a situation where ’none' of the items is selected. The tests utilise this pictogram string notation to drive the
testing. For example, the one-line test for applying the function when item 3 is selected in
our example list will be encoded as:li sts. hfreeLi staffer
as sert LINE , check (After, —1, ” | 37”, ”3 | 7”, true) ) :
The one-line test for inserting 5 when the current item is 3 in our example list using the
function is:insert/tfter
assert( LINE , check(InsertAfter, 5, ”|37”, ”3 57”)):
Details on Support Functions. The functions , and form the heart of the testing and are implemented 'brute force'. The function is used to build a list from the 'before' picture of a test, the function being tested is applied to the list, is used to check that the result list matches the 'after' picture, and frees up the list. Each of the functions uses an array of nodes in a very direct manner, so there is no ambiguity about what is going on. But that is not a technique you are supposed to be using in the list functions, because all of your 13
/'onctions must take 0(1) constant time. The style of testing set up here is very carefully designed to allow you to work on one list function at a
Step 5: Write the 13 Functions One by One
Programming with pointers is difficult. When a test fails, there is generally a segfault or similar, which can be very difficult to track down. You will need to use several or maybe all of:
• the warning options —Tal I —pedant i c
• the options to pinpoint segfaults and memory leakssani ti ze
• print statements
The trouble is, this is very error-prone. The code may be written with a mental picture of where the nodes were at the start of the function, but one or more of the pointers used in the expression may have been changed already by the time this line is executed. Trouble can arise particularly when shuffling lines of code around. A line of code that used to work may suddenly no longer work. And it is possible to 'lose' a node altogether, because there are no pointers left pointing to it, and therefore no way to reach it.
Use Robust Strategies. In this assignment, the insert and delete functions are the most difficult ones. They involve handling three nodes, either a new ’middle’ node being inserted between (up to) two existing ones, or one existing node being deleted and its (up to) two neighbours being linked up together to close the gap in the circular list. A good strategy is to set up three local pointer variables (e.g. , and or whatever you like) for these three nodes at the beginning of a function, so that you can keep track of them no matter what changes are made to the pointers between them. Each line of code after that can then be written simply using only one arrow, and the order in which the lines of code are executed doen't matter, making the code much more robust.pqr
thread safe. A more thread-safe approach is to create a separate iterator object each time the list is traversed. However, that approach can still easily lead to ’concurrent
Step 7: The Open-ended Task
Only if both your closed tasks are finished and you have time left, then you can do some extra open ended work in your own program called on the following problem: Using only
. /v i sual i se char 255 Input error.
. /v i sual i se char 08
Input error.
. /v i sual i se char —x0
Input error.
We recommend to keep things relatively simple at first, for instance, by starting with investigating just . The knowledge you already gained in computer architecture may be handy. Most importantly for this unit, your program should contain detailed unit tests for all functions which are run if no command ine parameters are provided:char
./visualise
AM tests pass.
. /v i sual i se uns i gned char 255 1111 1111
. /v i sual i se int 10000000
0000 0000 1001 1000 1001 0110 1000 0000
. /v i sual i se doub Ie —1. 25
1011 1111 1111 0100 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
. /v i sual i se int 0000 0000 1001 1000 1001 0110 1000 000
Input error.
. /v i sual i se doub 1 e 1011 1111 1111 0100 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
—1. 25
Note that it is always clear from the structure of your input if you are converting to decimal or to binary since binary input has leading zeros and comes in chunks of a nibble. You can extend your program further (keeping all previous functionality intact) by allowing for structured input using semicolon separated and {} enclosed types such as:
. /v i sual i se {char\ ; int \ ; uns i gned char} 7 10000000 255
0000 0111 0000 0000 1001 1000 1001 0110 1000 0000 1111 1111
. /v i sual i se {char \ : int \ : uns i gned char} 0000 0111 0000 0000 1001 1000 1001 0110 1000 0000 1111 1111
7 10000000 255
Your source file must compile error-free and warning-free for a valid submission in any case. Your program MUST comply exactly with the specified format for input and output. You are encouraged to write a summary file which describes what your program can do in no more than 100 words (strict limit). There are no marks for report writing, but the summary may be necessary for us to make sense of your program. As long as your program works, even if your program is very basic (e.g. just checks for that some the input char is valid), still submit it. Whenever you have reached a well working version, take a copy of your work, so you can revert back to it at any point. Rather submit something simple that works bug-free and is well tested than something that contains bugs - you will not get many marks for buggy code. Be careful not to over spend on time, since the task is completely open-ended. Make sure you manage your time well and stop at appropriate point Make s re o r programming adheres to the C Programming St ie Gide Enjo
