前情提要
前传:
线性数据结构1
事先声明: 本篇讲解的模板仅做娱乐，请不要用于正规比赛等！
引子
大家一定知道 链表 对吧？
这是一个基础的数据结构。
在 我之前的讲解 下，这显然不是一个很难的东西。
（Tips: 文中可以理解思路，但是代码以下面的第一个回复为准！）
虽然链表简单，但是不难发现一个问题：
用原来的写法不可以适应多种数据类型，
但是如果多复制几份显然会超出 信友队 多数评测机器的代码长度上限。
那我们该如何是好呢？
——模板！
模板
介绍
函数
模板，也就是 template 。
可以适应多种类型。
例如自己写的 max ：
int max (int a, int b) {
return a > b ? a : b;
}
显然只可以适用于 int 一种类型。
那么，就要请出 template 了！
template <class T>
T max (T a, T b) {
return a > b ? a : b;
}
这里，T 就是指定的数据类型，
不过两边的参数必须要一致，否则……
我们还可以以此重新写快速读入
template <class T>
void read (T &a) {
a = 0;
T f = 1;
char ch = getchar ();
while (ch > '9' || ch < '0') {
if (ch == '-') f = -f;
ch = getchar ();
}
while (ch >= '0' && ch <= '9') {
a = (a << 3) + (a << 1) + (ch ^ 48);
ch = getchar ();
}
return;
}
虽然只是支持整形变量，但也足够了。
（快读只是一个优化，最多只是当一个优化就够了）
（这里快读只是举个例子，所以不细讲）
结构体
你肯定很想自己写一个可以像栈一样定义的数据结构对吧？
（即用 My_Type <typename> 的形式定义的结构）
那么就可以这样！
template <typename T>
struct Node {
T data;
T a, b;
T *ptr;
// ...
};
缺点
好用是好用，但是在使用过程中不难发现它只能用于下一条语句。
除此之外， template 还会增加大量编译时间，有些编译器还不支持 template 的使用。
有办法才能稳定地让它在多个函数内都能使用而尽量少重复这个 template 呢？
那就是 struct 结构体了！
大家对于它肯定不会感到陌生，
毕竟在算法段大家就知道 struct 声明一个结构体了。
重点就在于如何使用。
二讲链表
链表是线性数据结构的一种，
申请着非连续的空间而使用指针找到自己的下个元素。
如果想要只声明一种链表内存放不同类型的元素，就可以这样：
template <typename T>
struct Chain {
// 节点
struct Node {
int data;
Node *next;
};
// 哑节点和空间
Node *head = nullptr;
int memory = 0;
// 判断空
bool empty (void) {
return memory == 0;
}
// 链表大小
int size (void) {
return memory;
} int length (void) {
return memory;
}
// 查找元素
Node *find (int val) {
Node *ptr = &head;
while (ptr -> next -> data != val) {
if (ptr -> next -> next == nullptr) return nullptr;
else if (ptr -> next -> data == val) return ptr -> next;
ptr = ptr -> next;
}
return nullptr;
}
// 增删改查
void insert (int val, int key) {
Node *pss = find (key); // pss 表示 posision （位置）
Node *p = new Node;
p -> data = val;
p -> next = pss -> next;
pss -> next = p;
return;
}
void update (int org, int neval) {
// org -> oringinal 原始值
// neval -> new value 新的值
Node *p = find (org);
p -> data = neval;
return;
}
int find_pos (int val) {
int cnt = 0;
Node *ptr = head;
while (ptr -> next -> data != val) {
if (ptr -> next -> next == nullptr) return -1;
else if (ptr -> next -> data == val) return cnt + 1;
ptr = ptr -> next;
++ cnt;
}
return -1;
}
void dlt (int val) {
Node* prev = head;
Node* curr = head->next;
while (curr != nullptr && curr->val != val) {
prev = curr;
curr = curr -> next;
}
if (curr == nullptr) return;
prev -> next = curr -> next;
delete curr;
}
};
结尾
大概就是结尾了吧，这次讲的有点水。
主要就是用于美化代码、减少代码量的吧。
最后再说三遍：