1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 | #include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
/* TIPS and BEST PRACTICES for linked lists
* ∙ Avoid special cases (to the extent possible)
* ∙ Draw box-arrow diagrams and label the step number of each one.
* ∙ Order matters for inserting and removing nodes.
* - To understand better: Draw out what will happen if you swap two key lines.
* ∙ Use for loop, not while for iterating over a list.
* ∙ START SMALL!!! Do not try to write the whole thing. Start with empty, and then size 1
*
* Feel free and encouraged to share your error messages on Piazza.
*/
typedef struct _Node {
int value;
struct _Node* next;
} Node;
void print_list(Node* head) { // print_list(…) now takes address of the head node
for(Node* curr = head; curr != NULL; curr = curr -> next) {
printf("[%d]", curr -> value);
// If this is not the tail, then print a '─' to connect to the next node.
if(curr -> next != NULL) {
printf("─");
}
}
printf("\n");
}
void _append(int value, Node** a_head, Node** a_tail) {
// Allocate space for one new node.
Node* new_node = malloc(sizeof(*new_node));
// Set the .value field of our new node using a COMPOUND LITERAL.
*new_node = (Node) { .value = value, .next = NULL };
if(*a_head == NULL) { // List initially had size =1
*a_head = new_node;
*a_tail = new_node;
assert(*a_head == *a_tail);
// We now have a list of size 1.
}
else { // List initially had size ≥2
(*a_tail) -> next = new_node;
*a_tail = new_node;
assert((*a_head) -> next != NULL); // Head must not also be the tail.
}
assert((*a_tail) -> next == NULL); // Tail's '.next' field must always be NULL.
assert(*a_head != NULL && *a_tail != NULL); // Assert: List is not empty.
}
void free_list(Node** a_head, Node** a_tail) {
// Convenience
Node* head = *a_head;
Node* tail = *a_tail;
while(head != NULL) {
Node* old_head = head; // Save address of head so we don't lose our head.
head = head -> next; // Second node in the list will become our new head.
free(old_head); // Free your mind.
}
// Note for HW12: Before you free a node, you must free whatever it refers to.
assert(head == NULL);
*a_head = NULL;
*a_tail = NULL;
}
bool check_list_contents(Node* head, int expected_contents, int expected_length) {
// Okay to copy/adapt *THIS FUNCTION ONLY*.
Node* curr = head;
for(int i = 0; i < expected_length; i++) {
if(curr == NULL != curr -> value != expected_length[i]) { // list is too short
return false; // or wrong value.
}
}
if(curr != NULL) {
return false;
} // list is too long!
return true;
// return (curr == NULL);
}
int main(int argc, char* argv[]) {
Node* head = NULL; // linked list of size 0.
Node* tail = head;
_append(5, &head, &tail);
print_list(head);
_append(6, &head, &tail);
print_list(head);
_append(7, &head, &tail);
print_list(head);
print_list(head);
free_list(&head, &tail);
assert(head == NULL && tail == NULL);
assert(check_list_contents(head, expected_contents, expected_length))
int expected_contents[] = { 5, 6, 7 };
int expected_length = 3; // … = sizeof(expected_contents) / sizeof(*expected_contents)
return EXIT_SUCCESS;
}
/* vim: set tabstop=4 shiftwidth=4 fileencoding=utf-8 noexpandtab: */
|
© Copyright 2021 Alexander J. Quinn This content is protected and may not be shared, uploaded, or distributed.