数据结构：双向链表的实现和测试(C++).doc

/在Doublelinkedlist.h内#includeutility.h#includeusing namespace std;template struct NodeNode_entry entry;Node *next;Node *back;Node();Node(Node_entry x ,Node *link_back =NULL , Node *link_next =NULL);template Node:Node()next = NULL;back = NULL;template Node:Node(Node_entry x ,Node *link_back , Node *link_next )entry = x;next = link_next;back = link_back;template class Listpublic:List();void clear();bool empty() const;bool full() const;int size() const;Error_code insert(int position, const List_entry & x);Error_code remove(int position, List_entry & x);Error_code retrieve(int position,List_entry &x) const;Error_code replace (int position,const List_entry &x);protected:int count;mutable int current_position;mutable Node *current ;void set_position(int pisition) const;template List:List()count = 0;current_position = 0; current = NULL; template void List:clear () List_entry temp;for(int i = 0; icount ; i+)remove(i, temp);return ;template bool List:empty() constreturn count = 0;template bool List:full () constreturn false;template int List :size() constreturn count;template void List :set_position(int position) constif(current_positionnext ;elsefor(;current_position !=position; current_position-)current=current-back ;return ;template Error_code List:insert(int position, const List_entry &x)Node *new_node , *following , *preceding; if(positioncount)return Error_code:range_error;if(position =0)if(count=0)following =NULL;elseset_position(0);following =current;preceding =NULL;elseset_position(position-1);preceding = current;following = preceding-next ;new_node = new Node (x,preceding,following);if(new_node =NULL)return overflow;if(preceding !=NULL)preceding-next = new_node;if(following !=NULL)following -back =new_node;current = new_node;current_position = position;count+;return success;template Error_code List:remove(int position, List_entry &x)Node *dele_node , *following , *preceding; if(position=count)return range_error;if( position = 0 )set_position(0);dele_node = current;following = dele_node -next;following-back = NULL;x = dele_node-entry;delete dele_node;count-;return success;if(position =count-1)set_position(position-1); preceding = current; dele_node = current-next; preceding-next = NULL; x = dele_node-entry; delete dele_node; count-; return sucess;elseset_position(position-1); preceding = current; dele_node = current-next; following = dele_node-next; preceding-next = following; following-back = preceding; x = dele_node-entry; delete dele_node; count-; return sucess;template Error_code List:retrieve(int position, List_entry &x) const if(position=count)return Error_code:range_error;set_position(position);x=current-entry;return success;template Error_code List:replace(int position,const List_entry &x) if(position=count)return range_error;set_position(position);current-entry = x;return success;/main.cpp内#includeDoublelinkedlist.h#includeutility.h#includeusing namespace std;int m