链表的概念
链表是常用的基本数据结构之一，属于线性表。同属于线性表的还有顺序表，我们常说的数组就是顺序表。
带表头链表
链表的实现有带表头和不带表头两种方式。最原始的方式，也就是不带表头的实现方式，是用一个指向头结点的指针变量来记录链表的起始位置，当我们要进行插入或删除结点的操作时，必须要针对第一个结点和其它结点做出不同判断，然后用不同的代码来分别处理这两种情况。
所谓带表头的实现方式，就是用一个空的结点来作为头结点，其data域不放数据，其next指针指向第一个存有数据的结点。这样的好处是：每一个数据结点都有相同类型的前驱结点，不管在哪个位置实现操作，都能用统一的形式来表述，即可以用同样的代码来实现，而无需判断是在链表的起始位置、中间位置或者尾部位置。
实现思路
我们将实现链表类的几个基本方法：
- 添加结点（至链表末尾）
- 插入结点（至任意位置）
- 删除结点
- 查找结点
- 获取链表长度
- 获取结点数据
- 排序
链表类Linklist的定义部分
template <typename ElemType>
class Linklist {
private:
struct Node{
ElemType data;
Node* next;
Node():next(nullptr){};
Node(ElemType data, Node* next = nullptr):
data(data), next(next){};
};
Node Head;
public:
Linklist() {};
~Linklist();
void append(ElemType data);
void insert(ElemType data, int pos = 0);
bool del(int pos);
int search(ElemType data);
int getLength();
ElemType getData(int pos);
void sort(int(*compare)(ElemType& a, ElemType& b));
};
Linklist的实现部分
template <typename ElemType>
Linklist<ElemType>::~Linklist() {
Node *ptr = &Head;
Node *t = nullptr;
while(ptr->next != nullptr) {
t = ptr->next;
ptr->next = t->next;
delete t;
}
}
template <typename ElemType>
void Linklist<ElemType>::append(ElemType data) {
Node *ptr = &Head;
while(ptr->next != nullptr) {
ptr = ptr->next;
}
ptr->next = new Node(data);
}
/* 当插入位置大于链表长度时，将元素插到链表末尾 */
template <typename ElemType>
void Linklist<ElemType>::insert(ElemType data, int pos) {
Node *ptr = &Head;
int p = 0;
while(ptr->next != nullptr)
{
if(p == pos) break;
p++;
ptr = ptr->next;
}
ptr->next = new Node(data, ptr->next);
}
template <typename ElemType>
bool Linklist<ElemType>::del(int pos) {
Node *ptr = &Head;
Node *t = nullptr;
int p = 0;
while(ptr->next != nullptr) {
if(p == pos) break;
p++;
ptr = ptr->next;
}
if(p == pos) {
t = ptr->next;
ptr->next = t->next;
delete t;
return true;
} else {
return false;
}
}
/* 成功找到元素则返回索引，否则返回-1 */
template <typename ElemType>
int Linklist<ElemType>::search(ElemType data) {
Node *ptr = &Head;
int p = 0;
while(ptr->next != nullptr) {
if(ptr->next->data == data) {
return p;
}
p++;
ptr = ptr->next;
}
return -1;
}
template <typename ElemType>
int Linklist<ElemType>::getLength() {
Node *ptr = &Head;
int p = 0;
while(ptr->next != nullptr) {
p++;
ptr = ptr->next;
}
return p;
}
template <typename ElemType>
ElemType Linklist<ElemType>::getData(int pos) {
Node *ptr = &Head;
int p = 0;
while(ptr->next != nullptr) {
if(p == pos) break;
p++;
ptr = ptr->next;
}
return ptr->next->data;
}
/* 排序函数需要一个返回值为int型的比较函数作为参数
* 升序排列：当a>b时，令compare(a, b)的返回值大于0
* 降序排列：当a<b时，令compare(a, b)的返回值大于0
* 注意：当a=b时，compare(a, b)的返回值必须小于或等于0。
*/
template <typename ElemType>
void Linklist<ElemType>::sort(int(*compare)(ElemType& a, ElemType& b)) {
Node *ptr;
Node *t;
int tmp;
bool sorted = false;
while(!sorted) {
sorted = true;
ptr = &Head;
t = ptr->next;
while(ptr->next != nullptr && t->next != nullptr) {
tmp = compare(t->data, t->next->data);
if(tmp > 0) {
ptr->next = t->next;
t->next = ptr->next->next;
ptr->next->next = t;
sorted = false;
}
ptr = t;
t = t->next;
}
}
}
作者：Wray Zheng
原文：http://www.codebelief.com/article/2016/11/linklist-implementation/
