单链表的衍生，许多函数和单链表想同，多了一个first表头结点。 带表头结点的数据域element不存放线性表中的元素，要么为空，要么存放辅助数据。 有了表头结点以后，单链表中每个元素结点都有一个前驱结点，简化了插入和删除操作的描述。 给出构造函数，插入函数以及删除函数的实现代码。 实现代码： ~~~ template<class T> HeaderList<T>::HeaderList() { Node<T> *first = new Node<T>; first -> Link = NULL; n = 0; } template<class T> bool HeaderList<T>::Insert(int i, T x) // 在i后插入x { if(i < -1 || i > n - 1) { // i不在范围内 cout << "Out of Bounds" << endl; return false; } Node<T> *p = first; for(int j = 0; j <= i; ++j) // 结束循环时 P指向i p = p -> Link; Node<T> *q = new Node<T>; q -> element = x; q -> Link = p -> Link; p -> Link = q; n++; return true; } template<class T> bool HeaderList<T>::Delete(int i) { if(!n) { // 空链表 cout << "UndeFlow" << endl; return false; } if(i < 0 || i > n - 1) { cout << "Out of << Bounds" << endl; return false; } Node<T> *q = first, *p; for(int j = 0; j < i; ++i) // 结束循环时 q指向i - 1 q = q -> Link; p = q -> Link; q -> Link = p -> Link; delete p; n--; return true; } ~~~