// Implementation of the list module.
#include “list.h”
#include
#include
Copyright By PowCoder代写 加微信 powcoder
#include
// Each node in a doubly linked list is stored in this structure. The user of the
// module does not have any knowledge of nodes.
struct node { struct node *back; item x; struct node *next; };
typedef struct node node;
// A list is to be represented as a circular list. It has to contain a doubly linked list
// of item nodes and one special sentinel node that links to the two ends of the item list.
// The none field holds this sentinel node. It has a default item, must always be present for
// a list and always sits before the first item node and after the last item node. For a list
// that holds no item nodes the back and next fields of the sentinel node point to the sentinel
// node itself. The current node refers to the currently selected item node in the list. If
// the current node is the none node then no item is selected.
struct list { node *none, *current; };
typedef struct list list;
// ———- ADD YOUR 13 FUNCTIONS HERE ———-
// Test the list module, using int as the item type. Strings are used as
// ‘pictograms’ to describe lists. 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.
#ifdef test_list
// Build a list from a pictogram, with -1 as the default item.
list *build(char *s) {
list *xs = malloc(sizeof(list));
int n = strlen(s);
node *nodes[n];
for (int i = 0; i < n; i++) nodes[i] = malloc(sizeof(node));
for (int i = 0; i < n; i++) nodes[i]->next = nodes[(i + 1) % n];
for (int i = 1; i < n + 1; i++) nodes[i % n]->back = nodes[i – 1];
xs->none = nodes[0];
xs->none->x = -1;
node *p = xs->none->next;
for (int i = 0; i < strlen(s); i++) {
if (s[i] == '|') xs->current = p;
p->x = s[i] – ‘0’;
p = p->next;
return xs;
// Destroy a list which was created with the build function and which matches a
// pictogram.
void destroy(list *xs, char *s) {
int n = strlen(s);
node *nodes[n];
nodes[0] = xs->none;
for (int i = 1; i < n; i++) nodes[i] = nodes[i-1]->next;
for (int i = 0; i < n; i++) free(nodes[i]);
// Check that a list matches a pictogram.
bool match(list *xs, char *s) {
int n = strlen(s);
node *nodes[n];
nodes[0] = xs->none;
for (int i = 1; i < n; i++) nodes[i] = nodes[i - 1]->next;
if (nodes[n – 1]->next != xs->none) return false;
for (int i = 1; i < n; i++) {
if (nodes[i]->back != nodes[i – 1]) return false;
node *p = xs->none->next;
for (int i = 0; i < strlen(s); i++) {
if (s[i] == '|') {
if (p != xs->current) return false;
if (p->x != s[i] – ‘0’) return false;
p = p->next;
return true;
// Use constants to say which function to call.
enum { First, Last, None, After, Before, Get, Set, InsertAfter, InsertBefore, DeleteToAfter, DeleteToBefore};
typedef int function;
// A replacement for the library assert function.
void assert(int line, bool b) {
if (b) return;
printf(“The test on line %d fails.\n”, line);
// Call a given function with a possible integer argument, returning a possible
// integer or boolean result (or -1).
int call(function f, list *xs, int arg) {
int result = -1;
switch (f) {
case None: result = none(xs); break;
case First: first(xs); break;
case Last: last(xs); break;
case After: result = after(xs); break;
case Before: result = before(xs); break;
case Get: result = get(xs); break;
case Set: result = set(xs, arg); break;
case InsertAfter: insertAfter(xs, arg); break;
case InsertBefore: insertBefore(xs, arg); break;
case DeleteToBefore: result = deleteToBefore(xs); break;
case DeleteToAfter: result = deleteToAfter(xs); break;
default: assert(__LINE__, false);
return result;
// Check that a given function does the right thing. The ‘in’ value is passed to
// the function or is -1. The ‘out’ value is the expected result, or -1.
bool check(function f, int in, char *before, char *after, int out) {
list *xs = build(before);
int result = call(f, xs, in);
//check circular list structure
assert(__LINE__, (xs->none == xs->none->next->back));
assert(__LINE__, (xs->none == xs->none->back->next));
//check correct workings of the function
bool ok = (match(xs, after) && (result == out));
destroy(xs, after);
return ok;
// Test newList, and call freeList. The test for freeList is that the memory
// leak detector in the -fsanitize=address or -fsanitize=leak compiler option
// reports no problems.
void testNewList() {
list *xs = newList(-1);
//check circular list structure
assert(__LINE__, (xs->none == xs->none->next));
assert(__LINE__, (xs->none == xs->none->back));
//check that an empty list is produced with a sentinel correctly
assert(__LINE__, match(xs, “|”));
freeList(xs);
// Test the various functions.
void testFirst() {
assert(__LINE__, check(First, -1, “|”, “|”, -1));
assert(__LINE__, check(First, -1, “|37”, “|37”, -1));
assert(__LINE__, check(First, -1, “3|7”, “|37”, -1));
assert(__LINE__, check(First, -1, “37|”, “|37”, -1));
void testLast() {
assert(__LINE__, check(Last, -1, “|”, “|”, -1));
assert(__LINE__, check(Last, -1, “|37”, “3|7”, -1));
assert(__LINE__, check(Last, -1, “3|7”, “3|7”, -1));
assert(__LINE__, check(Last, -1, “37|”, “3|7”, -1));
void testNone() {
assert(__LINE__, check(None, -1, “|”, “|”, true));
assert(__LINE__, check(None, -1, “|37”, “|37”, false));
assert(__LINE__, check(None, -1, “3|7”, “3|7”, false));
assert(__LINE__, check(None, -1, “37|”, “37|”, true));
void testAfter() {
assert(__LINE__, check(After, -1, “|”, “|”, false));
assert(__LINE__, check(After, -1, “|37”, “3|7”, true));
assert(__LINE__, check(After, -1, “3|7”, “37|”, true));
assert(__LINE__, check(After, -1, “37|”, “37|”, false));
void testBefore() {
assert(__LINE__, check(Before, -1, “|”, “|”, false));
assert(__LINE__, check(Before, -1, “|37”, “37|”, true));
assert(__LINE__, check(Before, -1, “3|7”, “|37”, true));
assert(__LINE__, check(Before, -1, “37|”, “37|”, false));
void testGet() {
assert(__LINE__, check(Get, -1, “|”, “|”, -1));
assert(__LINE__, check(Get, -1, “|37”, “|37”, 3));
assert(__LINE__, check(Get, -1, “3|7”, “3|7”, 7));
assert(__LINE__, check(Get, -1, “37|”, “37|”, -1));
void testSet() {
assert(__LINE__, check(Set, 5, “|”, “|”, false));
assert(__LINE__, check(Set, 5, “|37”, “|57”, true));
assert(__LINE__, check(Set, 5, “3|7”, “3|5”, true));
assert(__LINE__, check(Set, 5, “37|”, “37|”, false));
void testInsertAfter() {
assert(__LINE__, check(InsertAfter, 5, “|”, “|5”, -1));
assert(__LINE__, check(InsertAfter, 5, “|37”, “3|57”, -1));
assert(__LINE__, check(InsertAfter, 5, “3|7”, “37|5”, -1));
assert(__LINE__, check(InsertAfter, 5, “37|”, “|537”, -1));
void testInsertBefore() {
assert(__LINE__, check(InsertBefore, 5, “|”, “|5”, -1));
assert(__LINE__, check(InsertBefore, 5, “|37”, “|537”, -1));
assert(__LINE__, check(InsertBefore, 5, “3|7”, “3|57”, -1));
assert(__LINE__, check(InsertBefore, 5, “37|”, “37|5”, -1));
void testDeleteToAfter() {
assert(__LINE__, check(DeleteToAfter, -1, “|”, “|”, false));
assert(__LINE__, check(DeleteToAfter, -1, “|37”, “|7”, true));
assert(__LINE__, check(DeleteToAfter, -1, “3|7”, “3|”, true));
assert(__LINE__, check(DeleteToAfter, -1, “37|”, “37|”, false));
assert(__LINE__, check(DeleteToAfter, -1, “|5”, “|”, true));
void testDeleteToBefore() {
assert(__LINE__, check(DeleteToBefore, -1, “|”, “|”, false));
assert(__LINE__, check(DeleteToBefore, -1, “|37”, “7|”, true));
assert(__LINE__, check(DeleteToBefore, -1, “3|7”, “|3”, true));
assert(__LINE__, check(DeleteToBefore, -1, “37|”, “37|”, false));
assert(__LINE__, check(DeleteToBefore, -1, “|5”, “|”, true));
int main() {
testNewList();
testFirst();
testLast();
testNone();
testAfter();
testBefore();
testGet();
testSet();
testInsertAfter();
testInsertBefore();
testDeleteToAfter();
testDeleteToBefore();
printf(“List module tests run OK.\n”);
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com