list.h

C++应用教程原码,里面包含该书中有十三章内容的代码,详细具体

template <class Type>
class hashTable;

template <class Type>
class Node {
  public:
    Type data;
    Node(const Type &item, Node <Type> *ptrnext = NULL);
    void insertAfter(Node <Type> *p);
    Node <Type> *deleteAfter();
    Node <Type> *nextNode() const;
  private:
    Node <Type> *next;
} ;
 template <class Type>
    Node <Type> :: Node(const Type &item, Node <Type> *ptrnext = NULL)
       : data(item), next(ptrnext)
       {}
template <class Type>
    Node <Type> * Node <Type> ::nextNode() const
       { return next;}
template <class Type>
void Node <Type> :: insertAfter(Node <Type> *p)
{ p->next = next;
  next = p;
} 
template <class Type>
Node <Type>*  Node <Type> :: deleteAfter ()
{  Node <Type> *tempPtr = next;
   if (next == NULL) return NULL;
   next = tempPtr->next;
   return tempPtr;
} 
template <class Type>
class List {
  friend class hashTable;  // 将类hashTable定义为友元类
  public:
    List();
    //List(List <Type> &l);
    ~List();
    Type &data();  // 读取当前结点中的数据
    void next();    // 向后移一个结点
    void reset(int pos = 0);  // 设定当前指针的位置
    // 插入操作
    void insert(const Type &item);
    // 删除操作
    void deleteNode();
    // 遍历操作
    void traversal(int pos = 0);
  private:
    int size;  // 链表的长度
    Node <Type> *head, *rear, *currPtr, *prePtr;
    Node <Type>* getNode(const Type &item, Node <Type> *prtNext = NULL);
    void freeNode(Node <Type> *p);
};
template <class Type>
Node <Type> * List<Type>::getNode(const Type &item, Node <Type>* nextPtr = NULL)
{ Node <Type> *newNode;
  newNode = new Node <Type>(item, nextPtr);
  if (newNode == NULL) 
    { cout <<"内存空间分配错误！"<<endl;
      exit(-1);
    }
  return newNode;
}
template <class Type>
void List<Type> :: freeNode(Node <Type> *p)
{ delete p;
}
template <class Type>
List<Type> :: List()
      : head(NULL), rear(NULL), prePtr(NULL),currPtr(NULL), size(0)
    {}
template <class Type>
List<Type> :: ~List()
{  Node <Type> *temp,*temp1;
   temp = head;
   do{  temp1 = temp->nextNode();
      delete temp;
	  temp = temp1;
   }while (temp!=NULL);
}
template <class Type>
Type & List<Type> :: data()
    { if (size == 0 || currPtr == NULL)
       cout << "无法读取当前位置的数据";
     else
       return currPtr -> data;
    }
template <class Type>
void List<Type> :: reset(int pos)
    {  if (head == NULL) return;
       if (pos <0 || pos > size -1) 
         { cout << "位置重置失败！"<<endl;
           return;
         }
       if (pos ==0 )         // 移到首部
         { prePtr = NULL;
           currPtr = head;
         }
       else
         { currPtr = head->nextNode();  // 取下一个结点的地址
           prePtr = head;
           for (int i=1; i < pos; i++)
             { prePtr = currPtr;
               currPtr = currPtr -> nextNode();
             }
          }
    }
template <class Type>
void List <Type> :: next()
{  if (currPtr != NULL)
     { prePtr = currPtr;
       currPtr = currPtr ->nextNode();
     }
} 
template <class Type>
void List <Type> :: insert(const Type& item)
{ Node <Type> *newNode;
  if (currPtr == NULL)   // 判断是否是在首部插入
   { newNode = getNode(item, head);
     head = newNode;
   }
  else
   { newNode = getNode(item);
     currPtr -> insertAfter(newNode); 
	 prePtr = currPtr;
   }
  currPtr = newNode;
  if (currPtr->nextNode() == NULL)  // 如果在尾部插入，则修改尾指针
     rear = newNode;
  size ++;
     }
template <class Type>
void List<Type> :: deleteNode()
    {  Node <Type> *p,*temp;
       if (currPtr == NULL)  // 链表空或已经链表的尾部，则删除操作错误
        { cout << "删除操作失败！"<<endl;
          return;
        }
       if (prePtr == NULL)  // 判断被删除的结点是首结点
        { p = head;
          head = p ->nextNode();
        }
       else
	      p = prePtr ->deleteAfter(); // 删除当前结点
       currPtr = p->nextNode();    // 重新设置当前指针
	   if (p == rear)  // 被删除结点是尾部结点
		  {  rear = prePtr;
             currPtr = prePtr;
		     prePtr = NULL;
			 temp = head;
		     while (temp!=currPtr)
			 {
		       prePtr = temp;	
			   temp = temp->nextNode();
			 }
		  }
       freeNode(p);
       size--;
  }
template <class Type>
void List<Type> ::traversal(int pos = 0)
{ if (size>0)
   {  reset(pos);
      cout << "链表中的元素为："<<endl;
	  do
      { cout << setw(10)<<currPtr->data;
        next();
       }while (currPtr != rear);
	  cout << setw(10)<<currPtr->data<<endl;
   }
   else
     cout << "链表为空。"<<endl;
}