From c1b6ffe70bd281c6c230fd63fabcaac2aff47514 Mon Sep 17 00:00:00 2001 From: Fuwn Date: Sun, 7 Apr 2024 23:18:32 -0700 Subject: feat: initial commit --- chapter7/node2.h | 204 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 204 insertions(+) create mode 100644 chapter7/node2.h (limited to 'chapter7/node2.h') diff --git a/chapter7/node2.h b/chapter7/node2.h new file mode 100644 index 0000000..a161683 --- /dev/null +++ b/chapter7/node2.h @@ -0,0 +1,204 @@ +// FILE: node2.h (part of the namespace main_savitch_6B) +// PROVIDES: A template class for a node in a linked list, and list manipulation +// functions. The template parameter is the type of the data in each node. +// This file also defines a template class: node_iterator. +// The node_iterator is a forward iterators with two constructors: +// (1) A constructor (with a node* parameter) that attaches the iterator +// to the specified node in a linked list, and (2) a default constructor that +// creates a special iterator that marks the position that is beyond the end of a +// linked list. There is also a const_node_iterator for use with +// const node* . +// +// TYPEDEF for the node template class: +// Each node of the list contains a piece of data and a pointer to the +// next node. The type of the data (node::value_type) is the Item type +// from the template parameter. The type may be any of the built-in C++ classes +// (int, char, ...) or a class with a default constructor, an assignment +// operator, and a test for equality (x == y). +// NOTE: +// Many compilers require the use of the new keyword typename before using +// the expression node::value_type. Otherwise +// the compiler doesn't have enough information to realize that it is the +// name of a data type. +// +// CONSTRUCTOR for the node class: +// node( +// const Item& init_data = Item(), +// node* init_link = NULL +// ) +// Postcondition: The node contains the specified data and link. +// NOTE: The default value for the init_data is obtained from the default +// constructor of the Item. In the ANSI/ISO standard, this notation +// is also allowed for the built-in types, providing a default value of +// zero. The init_link has a default value of NULL. +// +// NOTE about two versions of some functions: +// The data function returns a reference to the data field of a node and +// the link function returns a copy of the link field of a node. +// Each of these functions comes in two versions: a const version and a +// non-const version. If the function is activated by a const node, then the +// compiler choses the const version (and the return value is const). +// If the function is activated by a non-const node, then the compiler choses +// the non-const version (and the return value will be non-const). +// EXAMPLES: +// const node *c; +// c->link( ) activates the const version of link returning const node* +// c->data( ) activates the const version of data returning const Item& +// c->data( ) = 42; ... is forbidden +// node *p; +// p->link( ) activates the non-const version of link returning node* +// p->data( ) activates the non-const version of data returning Item& +// p->data( ) = 42; ... actually changes the data in p's node +// +// MEMBER FUNCTIONS for the node class: +// const Item& data( ) const <----- const version +// and +// Item& data( ) <----------------- non-const version +// See the note (above) about the const version and non-const versions: +// Postcondition: The return value is a reference to the data from this node. +// +// const node* link( ) const <----- const version +// and +// node* link( ) <----------------- non-const version +// See the note (above) about the const version and non-const versions: +// Postcondition: The return value is the link from this node. +// +// void set_data(const Item& new_data) +// Postcondition: The node now contains the specified new data. +// +// void set_link(node* new_link) +// Postcondition: The node now contains the specified new link. +// +// FUNCTIONS in the linked list toolkit: +// template +// void list_clear(node*& head_ptr) +// Precondition: head_ptr is the head pointer of a linked list. +// Postcondition: All nodes of the list have been returned to the heap, +// and the head_ptr is now NULL. +// +// template +// void list_copy +// (const node* source_ptr, node*& head_ptr, node*& tail_ptr) +// Precondition: source_ptr is the head pointer of a linked list. +// Postcondition: head_ptr and tail_ptr are the head and tail pointers for +// a new list that contains the same items as the list pointed to by +// source_ptr. The original list is unaltered. +// +// template +// void list_head_insert(node*& head_ptr, const Item& entry) +// Precondition: head_ptr is the head pointer of a linked list. +// Postcondition: A new node containing the given entry has been added at +// the head of the linked list; head_ptr now points to the head of the new, +// longer linked list. +// +// template +// void list_head_remove(node*& head_ptr) +// Precondition: head_ptr is the head pointer of a linked list, with at +// least one node. +// Postcondition: The head node has been removed and returned to the heap; +// head_ptr is now the head pointer of the new, shorter linked list. +// +// template +// void list_insert(node* previous_ptr, const Item& entry) +// Precondition: previous_ptr points to a node in a linked list. +// Postcondition: A new node containing the given entry has been added +// after the node that previous_ptr points to. +// +// template +// size_t list_length(const node* head_ptr) +// Precondition: head_ptr is the head pointer of a linked list. +// Postcondition: The value returned is the number of nodes in the linked +// list. +// +// template +// NodePtr list_locate(NodePtr head_ptr, SizeType position) +// The NodePtr may be either node* or const node* +// Precondition: head_ptr is the head pointer of a linked list, and +// position > 0. +// Postcondition: The return value is a pointer that points to the node at +// the specified position in the list. (The head node is position 1, the +// next node is position 2, and so on). If there is no such position, then +// the null pointer is returned. +// +// template +// void list_remove(node* previous_ptr) +// Precondition: previous_ptr points to a node in a linked list, and this +// is not the tail node of the list. +// Postcondition: The node after previous_ptr has been removed from the +// linked list. +// +// template +// NodePtr list_search +// (NodePtr head_ptr, const Item& target) +// The NodePtr may be either node* or const node* +// Precondition: head_ptr is the head pointer of a linked list. +// Postcondition: The return value is a pointer that points to the first +// node containing the specified target in its data member. If there is no +// such node, the null pointer is returned. +// +// DYNAMIC MEMORY usage by the toolkit: +// If there is insufficient dynamic memory, then the following functions throw +// bad_alloc: the constructor, list_head_insert, list_insert, list_copy. + +#ifndef MAIN_SAVITCH_NODE2_H +#define MAIN_SAVITCH_NODE2_H +#include // Provides NULL and size_t +#include // Provides iterator and forward_iterator_tag + +namespace main_savitch_6B +{ + template + class node + { + public: + // TYPEDEF + typedef Item value_type; + // CONSTRUCTOR + node(const Item& init_data=Item( ), node* init_link=NULL) + { data_field = init_data; link_field = init_link; } + // MODIFICATION MEMBER FUNCTIONS + Item& data( ) { return data_field; } + node* link( ) { return link_field; } + void set_data(const Item& new_data) { data_field = new_data; } + void set_link(node* new_link) { link_field = new_link; } + // CONST MEMBER FUNCTIONS + const Item& data( ) const { return data_field; } + const node* link( ) const { return link_field; } + private: + Item data_field; + node *link_field; + }; + + // FUNCTIONS to manipulate a linked list: + template + void list_clear(node*& head_ptr); + + template + void list_copy + (const node* source_ptr, node*& head_ptr, node*& tail_ptr); + + template + void list_head_insert(node*& head_ptr, const Item& entry); + + template + void list_head_remove(node*& head_ptr); + + template + void list_insert(node* previous_ptr, const Item& entry); + + template + std::size_t list_length(const node* head_ptr); + + template + NodePtr list_locate(NodePtr head_ptr, SizeType position); + + template + void list_remove(node* previous_ptr); + + template + NodePtr list_search(NodePtr head_ptr, const Item& target); + +} + +#include "node2.template" +#endif -- cgit v1.2.3