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