- 论坛徽章:
- 0
|
- #ifndef _LINKEDLIST_H_
- #define _LINKEDLIST_H_
- #include <stdexcept>
- using namespace std;
- class EmptyListException : public logic_error {
- public:
- EmptyListException(const string& what_arg ) throw() :
- logic_error ("Empty list exception: " + what_arg) {}
- };
- template <class T>
- class Node {
- private:
- T data;
- Node* next;
- public:
- Node(T d, Node* n = NULL) : data(d), next(n) {}
- T& getData() { return data;}
- Node*& getNext() { return next;}
- };
- template <class T>
- class LinkedList {
- protected:
- Node<T>* head; // Beginning of list
- Node<T>* tail; // End of list
- int count; // Number of nodes in list
- public:
- LinkedList(void) : head(NULL), tail(NULL), count(0) {}
- LinkedList(const LinkedList<T>& src); // Copy constructor
- virtual ~LinkedList(void); // Destructor
- virtual T& front(void) {
- if (head == NULL) {
- throw EmptyListException("front()");
- }
- return head->getData();
- }
- virtual T& back(void) {
- if (tail == NULL) {
- throw EmptyListException("back()");
- }
- return tail->getData();
- }
- virtual int size(void) {
- return count;
- }
- virtual bool empty(void) {
- return count == 0;
- }
- virtual void push_front(T); // Insert element at beginning
- virtual void push_back(T); // Insert element at end
- virtual void pop_front(void); // Remove element from beginning
- virtual void pop_back(void); // Remove element from end
- virtual void dump(void); // Output contents of list
- };
- // Copy constructor
- template <class T>
- LinkedList<T>::LinkedList(const LinkedList<T>& src) :
- count(0), head(NULL), tail(NULL) {
- Node<T>* current = src.head;
- while (current != NULL) {
- this->push_back(current->getData());
- current = current->getNext();
- }
- }
- // Destructor
- template <class T>
- LinkedList<T>::~LinkedList(void) {
- while (!this->empty()) {
- this->pop_front();
- }
- }
- // Insert an element at the beginning
- template <class T>
- void LinkedList<T>::push_front(T d) {
- Node<T>* new_head = new Node<T>(d, head);
- if (this->empty()) {
- head = tail = new_head;
- }
- else {
- head = new_head;
- }
- count++;
- }
- // Insert an element at the end
- template <class T>
- void LinkedList<T>::push_back(T d) {
- Node<T>* new_tail = new Node<T>(d, NULL);
- if (this->empty()) {
- head = new_tail;
- }
- else {
- tail->getNext() = new_tail;
- }
- tail = new_tail;
- count++;
- }
- // Remove an element from the beginning
- template <class T>
- void LinkedList<T>::pop_front(void) {
- if (head == NULL) {
- throw EmptyListException("pop_front()");
- }
- Node<T>* old_head = head;
- if (this->size() == 1) {
- head = NULL;
- tail = NULL;
- }
- else {
- head = head->getNext();
- }
- delete old_head;
- count--;
- }
- // Remove an element from the end
- template <class T>
- void LinkedList<T>::pop_back(void) {
- if (tail == NULL) {
- throw EmptyListException("pop_back()");
- }
- Node<T>* old_tail = tail;
- if (this->size() == 1) {
- head = NULL;
- tail = NULL;
- }
- else {
- // Traverse the list
- Node<T>* current = head;
- while (current->getNext() != tail) {
- current = current->getNext();
- }
- // Unlink and reposition
- current->getNext() = NULL;
- tail = current;
- }
- delete old_tail;
- count--;
- }
- // Display the contents of the list
- template <class T>
- void LinkedList<T>::dump(void) {
- cout << "(";
- if (head != NULL) {
- Node<T>* current = head;
- while (current->getNext() != NULL) {
- cout << current->getData() << ", ";
- current = current->getNext();
- }
- cout << current->getData();
- }
- cout << ")" << endl;
- }
- #endif
- #ifndef _ENHANCELINKLIST_H_
- #define _ENHANCELINKLIST_H_
- #include "LinkedList.h"
- template<typename T>
- class EnhancedLinkedList: public LinkedList<T>
- {
- public:
- T& find_first (const T& key);
- //Method find_first should search the EnhancedLinkedList for the first
- //occurrence of an item that matches the value in the parameter key.
- //It should return a reference to the first matching item.
- //If the invoking EnhancedLinkedList object is empty or no item is found
- //that matches the parameter, a ListItemNotFoundException should be thrown.
- //You will have to define this exception
- //(Hint: define this exception much the same way that the
- //EmptyListException exception is defined in LinkedList.h).
- EnhancedLinkedList find_all (const T& key);
- //Method find_all should search the invoking EnhancedLinkedList
- //for all elements that match the value in the parameter key.
- //It should return an EnhancedLinkedList object containing
- //copies of all the items that match the parameter key.
- //If the invoking EnhancedLinkedList object is empty or
- //no item is found that matches the parameter,
- //this function should return an empty EnhancedLinkedList.
- void remove_first (const T& key);
- //Method remove_first should remove the first element from the
- //invoking EnhancedLinkedList whose data item matches the parameter key.
- //If the invoking EnhancedLinkedList object is empty or no item is found
- //that matches the parameter, this function should do nothing.
- //Remember to leave no memory leaks.
- void remove_all (const T& key);
- //Method remove_all should remove all elements from the invoking
- //EnhancedLinkedList whose data items match the parameter key.
- //If the invoking EnhancedLinkedList object is empty or no item is found
- //that matches the parameter, this function should do nothing.
- //Remember to leave no memory leaks.
- };
- template<typename T>
- T& EnhancedLinkedList<T>::find_first(const T& key)
- {
- Node<T>* temp = this->head;
- if(temp == NULL)
- throw EmptyListException("Find first emptylist");
- while(NULL != temp->getNext())
- {
- if(temp->getData()==key)
- return temp->getData();
- else
- temp=temp->getNext();
- }
- throw EmptyListException("Find first not found");
- }
- template<typename T>
- EnhancedLinkedList<T>
- EnhancedLinkedList<T>::find_all(const T& key)
- {
- EnhancedLinkedList<T> resualt;
- Node<T>* temp = this->head;
- while(NULL != temp)
- {
- if(temp->getData()==key)
- resualt.push_back(temp->getData());
- temp=temp->getNext();
- }
- end:
- return resualt;
- }
- template<typename T>
- void
- EnhancedLinkedList<T>::remove_first(const T& key)
- {
- EnhancedLinkedList<T> list;
- while(NULL!=this->head)
- {
- if(this->head->getData()!=key)
- list.push_front(this->head->getData());
- else{
- T* temp = this->front();
- this->pop_front();
- delete temp;
- break;
- }
- this->pop_front();
- }
- while(list.head!=NULL)
- {
- this->push_front(list.front());
- list.pop_front();
- }
- }
- template<typename T>
- void
- EnhancedLinkedList<T>::remove_all(const T& key)
- {
- EnhancedLinkedList<T> list;
- while(NULL!=this->head)
- {
- if(this->head->getData()!=key){
- list.push_front(this->head->getData());
- this->pop_front();
- }
- else{
- T* temp = this->front();
- this->pop_front();
- delete temp;
- }
- }
- while(list.head!=NULL)
- {
- this->push_front(list.front());
- list.pop_front();
- }
- }
- #endif //_ENHANCELINKLIST_H_
复制代码
大学时候的一道作业题 有你想要的东西
[ 本帖最后由 DraculaW 于 2008-8-11 16:55 编辑 ] |
|