c++链表ADT 和主要函数实现
template <class Type>struct nodeType { int info; nodeType *next;};template <class Type>class linkedListType { friend ostream& operator<< (ostream&, const linkedListType<Type>&);public: const linkedListType<Type>& operator= (const linkedListType<Type>&); void initializedList(); bool isEmptyList(); int length(); void destroyList(); Type front(); Type back(); bool search(const Type& searchItem); void insertFirst(const Type& newItem); void insertLast(const Type& newItem); void deleteNode(const Type& deleteItem); linkedListType(); linkedListType(const linkedListType<Type>& otherList); ~linkedListType();protected: int count; nodeType<Type> *first; nodeType<Type> *last;private: void copyList(const linkedListType<Type>& otherList);};template <class Type>bool linkedListType<Type>::search(const Type& searchItem) { nodeType<Type> *current; current = first; while(current!=NULL) { if(current->info == searchItem) return true; else current = current->next; } return false;}template <class Type>void linkedListType<Type>::deleteNode(const Type& deleteItem) { nodeType<Type> *current; nodeType<Type> *trailCurrent; bool found; /* * if the list is empty */ if(first == NULL) cerr<<"Cannot delete from an empty list.\n"; /* * if the list is not empty */ else { /* * if the delete item is equal to the first element of the list * */ if(first->info == deleteItem) { current = first; first = first->next; count--; /* * if after delete the first element of list * the list become empty * do something(make the last pointer to be NULL) */ if(first == NULL) { last = NULL; delete current; } } /* * if not equal to the first element of the list */ else { found = false; trailCurrent = first; current = first->next; /* *squence search the list */ while(current!=NULL&&!found) { if(current->info != deleteItem) { trailCurrent = current; current = current->next; }else { found = true; } } /* * if find the delete item in the list */ if(found) { trailCurrent->next = current->next; count--; if(last==current) last = trailCurrent; delete current; }else { cout<<"Item to be deleted is not in the list."<<endl; } } }}