表(Lists)和字符串.doc

1、 定义： The insertions,deletions and retrieval can occured at any point of the list.2、 实现：*utility.h：#include #include #include #include #include enum Error_code success, fail, range_error, underflow, overflow, fatal, not_present, duplicate_error, entry_inserted, entry_found, internal_error ;顺序实现：*list.h:#include utility.hconst int max_list = 1000; template class List public:/ methods of the List ADT List(); int size() const; bool full() const; bool empty() const; void clear(); void traverse(void (*visit)(List_entry &); Error_code retrieve(int position, List_entry &x) const; Error_code replace(int position, const List_entry &x); Error_code remove(int position, List_entry &x); Error_code insert(int position, const List_entry &x);protected:/ data members for a contiguous list implementation int count; List_entry entrymax_list;template List:List() count = 0;template void List:clear() count = 0;template int List:size() const return count;template bool List:empty() const return count = 0;template bool List:full() const return count = max_list;template void List:traverse(void (*visit)(List_entry &) for (int i = 0; i count; i+) (*visit)(entryi);template Error_code List:insert(int position, const List_entry &x) if (full() return overflow; if (position count) return range_error; for (int i = count - 1; i = position; i-) entryi + 1 = entryi; entryposition = x; count+; return success;template Error_code List:retrieve(int position, List_entry &x) const if (position = count) return range_error; x = entryposition; return success;template Error_code List:replace(int position, const List_entry &x) if (position = count) return range_error; entryposition = x; return success;template Error_code List:remove(int position, List_entry &x) if (count = 0) return underflow; if (position = count) return range_error; x = entryposition; count-; while (position count) entryposition = entryposition + 1; position+; return success;链式实现：*node.h:template struct Node / data members Node_entry entry; Node *next;/ constructors Node(); Node(Node_entry, Node *link = NULL);template Node:Node() next = NULL;template Node:Node (List_entry data, Node *link) entry = data; next = link;*list.h:#include utility.h#include node.htemplate class List public:/ Specifications for the methods of the list ADT go here. List(); int size() const; bool full() const; bool empty() const; void clear(); void traverse(void (*visit)(List_entry &); Error_code retrieve(int position, List_entry &x) const; Error_code replace(int position, const List_entry &x); Error_code remove(int position, List_entry &x); Error_code insert(int position, const List_entry &x);/ The following methods replace compiler-generated defaults. List(); List(const List ©); void operator =(const List ©);protected:/ Data members for the linked list implementation now follow. int count; Node *head;/ The following auxiliary function is used to locate list positions Node *set_position(int position) const;template List:List() count = 0; head = NULL;template void List:clear() Node *p, *q; for (p = head; p; p = q) q = p-next; delete p; count = 0; head = NULL;template int List:size() const return count;template bool List:empty() const return count = 0;template bool List:full() const return false;template void List:traverse(void (*visit)(List_entry &) Node *q; for (q = head; q; q = q-next) (*visit)(q-entry);template Error_code List:insert(int position, const List_entry &x) if (position count) return range_error; Node *new_node, *previous, *following; if (position 0) previous = set_position(position - 1); following = previous-next; else following = head; new_node = new Node(x, following); if (new_node = NULL) return overflow; if (position = 0) head = new_node; else previous-next = new_node; count+; return success;template Error_code List:retrieve(int position, List_entry &x) const Node *current; if (position = count) return range_error; current = set_position(position); x = current-entry; return success;template Error_code List:replace(int position, const List_entry &x) Node *current; if (position = count) return range_error; current = set_position(position); current-entry = x; return success;template Error_code List:remove(int position, List_entry &x) Node *prior, *current; if (count = 0) return fail; if (position = count) return range_error; if (position 0) prior = set_position(position - 1); current = prior-next; prior-next = current-next; else current = head; head = head-next; x = current-entry; delete current; count-; return success;template Node *List:set_position(int position) const Node *q = head; for (int i = 0; i next; return q;template List:List() clear();template List:List(const List ©) count = copy.count; Node *new_node, *old_node = copy.head; if (old_node = NULL) head = NULL; else new_node = head = new Node(old_node-entry); while (old_node-next != NULL) old_node = old_node-next; new_n