2022/7/22 22:22 University of Bristol – Computer Science – COMS10016: Imperative and Functional Programming
COMS10016 | Summative Resit Courseworks:
LIST AND SKETCH
This resit coursework comes in two parts called LIST and SKETCH. If you did not receive credit for the COMS10016 unit and/or did not overall achieve at least 40/100 marks for the unit overall you will have resits for this unit (that can be the exam courseworks or both), otherwise you will not – if you have to do resits and failed one or both of the courseworks LIST or SKETCH you will have to resit one or both of them here. Check your year results on eVision to find out which courseworks you need to resit. The two tasks LIST and SKETCH align exactly with the two summative coursework tasks given in the original unit. Respectively, the two parts contribute 40% and 60% towards the coursework, which overall counts 50% towards the COMS10016 unit mark. If you have a capped resit instead of a supplementary then your mark will be capped at pass level. (Please talk to your personal tutor or email for academic or administrative advise, respectively. The task itself is complete and clearly described on this page, the unit staff cannot help further in this regard.)
Copyright By PowCoder代写 加微信 powcoder
The Blackboard submission deadline is 8 Aug 2022 1pm – but submit at least an hour early. You must work individually in any case, not in collaboration with anyone else. All code you submit must be your own, do not copy any code parts from peers or other sources and do not publish parts of your own code anywhere. The programs we use for checking against the web, your peers and other sources are advanced. Changing parts of someone else’s work to try and obfuscate plagiarism only makes the problem worse. On the other hand all unit materials are available to you. Thus, revise all materials and work on the tasks yourself without using any external help. The skills you learn by doing that are the ones that will allow you to build a successful career after your studies. Plagiarism, on the other hand, will usually result in failing the unit, failing the year, or in some cases being forced to withdraw from studies. Use only standard libraries as given in the skeleton code for this task, so your code compiles and runs without linking any other libraries. Each of the two tasks comes itself in two parts: a closed task and an open-ended task. Backup your work regularly. Do not attempt any open-ended task before successfully and fully finishing the closed tasks.
Summative Resit Coursework Task 01:
https://www.ole.bris.ac.uk/bbcswebdav/pid-607753-dt-announcement-rid-27823520_2/courses/COMS10016_2021_TB-1/content/imperative/resit… 1/27
2022/7/22 22:22 University of Bristol – Computer Science – COMS10016: Imperative and Functional Programming
LIST CHALLENGE
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 linkedlist.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 x (e.g. just an int) and two pointers: back and next. The back pointer always points to the predecessor node and the next pointer always points to the successor node. Two neighbouring nodes in a doubly- linked list can therefore be pictured like this:
This emphasizes that a node structure contains three fields. However, for most purposes you can simplify the visualisation by depicting the above two nodes like this:
In this simplified visualisation, a pointer from the left end of a node represents its back 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.
The Sentinel Node. It used to be a standard solution to implement doubly-linked lists by keeping track of the first and last node of the list (like the 3 node and 7 node
https://www.ole.bris.ac.uk/bbcswebdav/pid-607753-dt-announcement-rid-27823520_2/courses/COMS10016_2021_TB-1/content/imperative/resit… 2/27
2022/7/22 22:22 University of Bristol – Computer Science – COMS10016: Imperative and Functional Programming
in the picture above), where the first node would point backward to NULL, and the last node would point forward to NULL. However, it turns out that adding an extra node, called a sentinel node, simplifies list implementations and makes the code much more readable. For a circular, doubly-linked list our sentinel node (pictured with no payload x) is linked in between the first and last item in the list:
Using this idea, the nodes of a new ’empty’ list with no item nodes look like this:
Here both the back and next pointers of the sentinel node simply point to the sentinel node itself.
The Structure list. To represent a list in a list data structure we need two node pointers: one fixed pointer to the sentinel node (called none) to access both list ends in constant time, and one current pointer that points to a current node in the list allowing for traversals:
https://www.ole.bris.ac.uk/bbcswebdav/pid-607753-dt-announcement-rid-27823520_2/courses/COMS10016_2021_TB-1/content/imperative/resit… 3/27
2022/7/22 22:22 University of Bristol – Computer Science – COMS10016: Imperative and Functional Programming
In the above image the current position is the node that holds 7, so item 7 is selected. If the current pointer in a list points to none then we will interpret this as ‘no item is selected’:
If there are item nodes in our list, none->next should link to the first item, and none- >back 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.
Picturing List Manipulations. To visualize what a function does to a list, draw a picture of the situation before the function call, and another of the situation after the call. For instance, consider the function after. If an item is selected it moves the current pointer one element forward. When applying the function to our list with the item 3 selected, it would have the simple effect of moving the current pointer one step forward to item 7:
https://www.ole.bris.ac.uk/bbcswebdav/pid-607753-dt-announcement-rid-27823520_2/courses/COMS10016_2021_TB-1/content/imperative/resit… 4/27
2022/7/22 22:22 University of Bristol – Computer Science – COMS10016: Imperative and Functional Programming
Applying the after function to our list when the item 7 is selected moves the current pointer one step forward to the sentinel node, meaning ‘no item’ is selected after the call:
https://www.ole.bris.ac.uk/bbcswebdav/pid-607753-dt-announcement-rid-27823520_2/courses/COMS10016_2021_TB-1/content/imperative/resit… 5/27
2022/7/22 22:22 University of Bristol – Computer Science – COMS10016: Imperative and Functional Programming
Thus, whenever in doubt, draw a picture of a particular situation before and after a function call to understand the detailed workings.
Step 2: Understand the Closed Task (50% of 1st Task)
Your closed task is to implement 13 missing procedures in the skeleton file list.c all of which manipulate circular doubly-linked lists with one sentinel node. You must use the provided files and are not allowed to alter any of the provided code, only add the 13 missing functions where marked:
list.h (header file) list.c (skeleton) Makefile
https://www.ole.bris.ac.uk/bbcswebdav/pid-607753-dt-announcement-rid-27823520_2/courses/COMS10016_2021_TB-1/content/imperative/resit… 6/27
2022/7/22 22:22 University of Bristol – Computer Science – COMS10016: Imperative and Functional Programming
The header file lists.h forms an API, which you should read carefully because the comments describe what the functions you will have to implement in list.c have to do. The list.c file has just two data structures node and list 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.
Step 3: Create a Compiling Skeleton
Your first task is to turn lists.c into a full skeleton program that compiles. You can do this without understanding all of the technicalities of the assignment.
Two Key Data Structures. In the file lists.c a structure for the nodes which make up the list is defined, and a structure for the list itself. The node structure struct node is not visible to the user of the module. Each node is used to hold an item x and pointers to the two neighbouring nodes (next and back) which define the list ordering. The overall list structure struct list represents a list and is essential so that your newList function can return something to the user which is well defined. This structure holds two pointers: one to the sentinel node of the list and one to the currently selected node. Read the code comments about the list structure carefully. You will have to use the two data structures exactly as described to comply with the tests.
Define Dummy Functions. Write a minimal dummy definition of each of the 13 functions mentioned in the header file. The safest way to do that is to copy-and- paste a function’s declaration from lists.h, then replace the semicolon by curly brackets. If the function returns anything other than void, add a return statement which returns the easiest temporary value of that type you can think of (e.g. NULL for a pointer, false for a boolean). For functions returning an item, you can return 0 for now, but beware that depends on item being int, so it may need to be fixed later. At this point, check that the program compiles fine via make test or directly via:
clang -Dtest_list -std=c11 -Wall -pedantic -g list.c -o list -fsanitize=undefined – fsanitize=address
Pay attention to use the exact line for compilation, including that the parameter – Dtest_list must be used to run the tests.
https://www.ole.bris.ac.uk/bbcswebdav/pid-607753-dt-announcement-rid-27823520_2/courses/COMS10016_2021_TB-1/content/imperative/resit… 7/27
2022/7/22 22:22 University of Bristol – Computer Science – COMS10016: Imperative and Functional Programming
Step 4: Understand the Tests
There is a separate test function in lists.h for each of the 13 list functions you need to implement, except for freeList 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 ‘|’ 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 after function when item 3 is selected in our example list will be encoded as:
assert(__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 insertAfter function is:
assert(__LINE__, check(InsertAfter, 5, “|37”, “3|57”));
There is a different check function for each function type. The check function builds a list matching the before picture, calls the given function (in this case insertAfter with 5 as the second argument) and compares the result to the after picture.
Checks and Default. Most functions are designed to return a testable value. For example, if no item is selected, a call of after does nothing and returns false, which is easy to test. The get function returns an item in any case. To make sure there is an item which can be returned in any case, the newList function is passed a default item. The default item should be stored in the sentinel node.
Function Descriptions. What does each function do? There is a detailed comment for each function in the list.h header which gives a summary. For each function, there is a test function with some assert calls. These show precisely what the function does on the empty list “|” and a list with two items in at least each of the three cases “|37” and “3|7” and “37|”. That should be enough for you to work out what the function does in every possible case.
https://www.ole.bris.ac.uk/bbcswebdav/pid-607753-dt-announcement-rid-27823520_2/courses/COMS10016_2021_TB-1/content/imperative/resit… 8/27
2022/7/22 22:22 University of Bristol – Computer Science – COMS10016: Imperative and Functional Programming
Details on Support Functions. The functions build, destroy and match form the heart of the testing and are implemented ‘brute force’. The build function is used to build a list from the ‘before’ picture of a test, the function being tested is applied to the list, match is used to check that the result list matches the ‘after’ picture, and destroy 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 functions must take O(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 time.
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 -Wall -pedantic
the sanitize options to pinpoint segfaults and memory leaks print statements
Develop newList. The first thing to do is to comment out all the tests except testNewList in main. After that, keep all the tests beyond the one you are working on commented out. That’s because if a test fails, causing a segfault, it may be unreasonably difficult to know which test function caused it. Develop newList until it passes its test, and you don’t get any messages from the various compiler options. In newList you will essentially have to allocate memory on the heap for a new list structure and a new sentinal node, initialise the sentinal node with the default item, let the current and none pointers in the list point to the sentinel node, and link the two pointers in the sentinel node point to the sentinal node itself.
Develop freeList. For all the functions, the compiler options test things that the tests themselves can’t. In the case of freeList, there is no explicit testing that can be done. Therefore the only testing is that memory leak detection does not give any messages. Your freeList procedure should first free all nodes of the list including the sentinel node and finally free the list structure itself.
Develop in Small Steps. You may want to stick to the development sequence given by the test sequence for the functions. Thus, step by step uncomment the call to its testing function first, develop and test. Remember, the more exceptions and
https://www.ole.bris.ac.uk/bbcswebdav/pid-607753-dt-announcement-rid-27823520_2/courses/COMS10016_2021_TB-1/content/imperative/resit… 9/27
2022/7/22 22:22 University of Bristol – Computer Science – COMS10016: Imperative and Functional Programming
different cases your code handles, the more liable it is to have bugs in, because there are more places for bugs to hide, and it is harder for you to see at a glance that the code is correct. You aren’t being given much opportunity for making your own implementation decisions in this closed part of the assignment. That simplifies checking correctness, and allows us to help you more easily. It is very tempting to write lines of code like this, with lots of arrows:
current->back->next->…
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. p, q and r 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.
Enjoy programming and make sure your code adheres to the C Programming Style Guide! As always use the labs and the Teams chat for help and feedback throughout the two weeks. Once your program compiles and runs without errors and warnings, and passes all the tests you will have gained the first 50% of this coursework’s marks. Everybody should work hard to get to this point.
Step 6: Notes on the Design
A List of Items. The header is set up to store item values in lists. In the header item is defined as int to provide an example case. However, item must be used as a
https://www.ole.bris.ac.uk/bbcswebdav/pid-607753-dt-announcement-rid-27823520_2/courses/COMS10016_2021_TB-1/content/imperative/res… 10/27
2022/7/22 22:22 University of Bristol – Computer Science – COMS10016: Imperative and Functional Programming
synonym for int everywhere in your code, so that there is only one place in the header file where a change would need to be made to store some other type of items. This means the module can be used with different item types in different programs. For those who are interested, note that even this it is not truly generic since the setup cannot be used multiple times for different item types in the same program. There is no really satisfying way of making fully generic modules in C. It is recommended, as a last test before submitting, that you change the item type to double, to check that you haven’t inadvertently assumed int anywhere. (The numbers used in the tests should still work as doubles.)
Conceptual Design. The header doesn’t say that the list is to be doubly linked, nor to be circular, or use a sentinel node (comments in list.c do though). That’s because a user of the module need not know or care, and the implementation could be changed to something completely different in a later version of the module, without any effect on programs that use it. On the other hand, the header does say that all the operations are constant time. This is a strong hint that the implementation does use a doubly linked list or something similar, because it is difficult to achieve constant time operations otherwise. The claim of constant time doesn’t cover the vagueness in the time taken by malloc and free calls but, conventionally, memory management costs are considered separately from the ‘logic’ costs of operations. The function names use the camelCase convention, where capitals ma
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com