线性表：
最基本和最常用的一种数据结构由零个或多个数据元素组成的有限序列，表示线性结构分为顺序存储结构和链式存储结构两种。特点：
数据元素的数据类型相同位顺从1开始有唯一前驱和后继（除第一个和最后一个元素外）链式存储结构：
用一段不连续的内存空间存储线性表中的数据元素。插入数据原理：
创建新的节点使用循环指针变量找到需要插入节点的位置插入节点： newnode->next = pCurrent->next; pCurrent->next = newnode;更改size：size++注： 在使用模板类时，函数的声明和实现必须在同一个文件中，否则会报错
链表类的声明
#include <iostream> //链表节点 template <typename T> class LinkNode { public: T data; LinkNode<T> *next; }; //链表类 template <typename T> class SList { private: LinkNode<T> *head; int size; public: SList(/* args */); ~SList(); //指定位置插入数据 void insert(T data, int pos); //删除指定位置的值 void remove(int pos); //获得链表的长度 int getSize(); //返回第一个节点 T front(); //查找位置 int find(T data); //查找数据 T at(int pos); //清空链表 void clear(); //打印链表节点 void show(); };链表类的定义（实现）
template <typename T> SList<T>::SList() { size = 0; //头节点（不保存数据），目的：使链表实现起来更加方便 head = new LinkNode<T>; head->next = NULL; } template <typename T> SList<T>::~SList() { clear(); delete head; } //指定位置插入数据 template <typename T> void SList<T>::insert(T data, int pos) { //友好处理：若pos越界，默认插入到尾部 if (pos < 0 || pos > size) pos = size; //创建新的节点 LinkNode<T> *newnode = new LinkNode<T>; newnode->data = data; newnode->next = NULL; //找节点：辅助指针变量 LinkNode<T> *pCurrent = head; for (int i = 0; pCurrent != NULL && i < pos; i++) pCurrent = pCurrent->next; //新节点插入链表 newnode->next = pCurrent->next; pCurrent->next = newnode; size++; } //删除指定位置的值 template <typename T> void SList<T>::remove(int pos) { if (pos < 0 || pos >= size) { std::cout << "ERROR: The pos is out of bounds!" << std::endl; return; } //找节点：辅助指针变量 LinkNode<T> *pCurrent = head; for (int i = 0; pCurrent != NULL && i < pos; i++) pCurrent = pCurrent->next; //缓存要删除的节点 LinkNode<T> *pDel = pCurrent->next; //删除节点 pCurrent->next = pDel->next; delete pDel; } //获得链表的长度 template <typename T> int SList<T>::getSize() { return size; } //返回第一个节点 template <typename T> T SList<T>::front() { return head->next; } //查找位置 template <typename T> int SList<T>::find(T data) { //遍历查找 LinkNode<T> *pCurrent = head->next; for (int i = 0; pCurrent != NULL; i++) { if (pCurrent->data == data) //注意 该类型必须支持 == 操作符，如果不支持需要进行运算符重载 return i; pCurrent = pCurrent->next; } return -1; } //查找数据 template <typename T> T SList<T>::at(int pos) { if (pos < 0 || pos >= size) { std::cout << "ERROR: The pos is out of bounds!" << std::endl; exit(EXIT_FAILURE); } //遍历找节点：辅助指针变量 LinkNode<T> *pCurrent = head; for (int i = 0; i <= pos; i++) pCurrent = pCurrent->next; return pCurrent->data; } //清空链表(除表头外) template <typename T> void SList<T>::clear() { LinkNode<T> *pCurrent = head->next; while (pCurrent != NULL) { head->next = pCurrent->next; delete pCurrent; pCurrent = head->next; } size = 0; } //打印链表节点 template <typename T> void SList<T>::show() { if (size == 0) { std::cout << "There is no data in this list!" << std::endl; return; } LinkNode<T> *pCurrent = head->next; for (int i = 0; pCurrent != NULL && i < size; i++) { std::cout << i << ": " << pCurrent->data << std::endl; pCurrent = pCurrent->next; } }单链表的测试
#include <iostream> #include "slist.hpp" void test_01(); void test_02(); //自定义数据类型 struct Person { char name[64]; int age; int score; }; int main() { test_01(); test_02(); return 0; } //注意：自定义结构体时，未重载cout函数和==运算符，部分函数无法使用 void test_01() { //创建链表 SList<Person> list1; //创建数据 Person p1 = {"XiaoMeng", 23, 95}; Person p2 = {"aaa", 32, 90}; Person p3 = {"bbb", 32, 53}; Person p4 = {"ccc", 53, 76}; Person p5 = {"ddd", 12, 43}; //插入数据 list1.insert(p5, 0); list1.insert(p4, 0); list1.insert(p3, 0); list1.insert(p2, 0); list1.insert(p1, 0); std::cout << "测试查找函数：" << std::endl; std::cout << list1.at(3).name << std::endl; //测试删除函数 list1.remove(2); list1.clear(); } //测试一般数据类型（int） void test_02() { //创建链表 SList<int> list2; //插入数据 list2.insert(5, 0); list2.insert(4, 0); list2.insert(3, 0); list2.insert(2, 0); list2.insert(1, 0); //打印数据 list2.show(); std::cout << "测试查找函数：" << std::endl; std::cout << list2.at(3) << std::endl; std::cout << list2.find(3) << std::endl; //测试删除函数 list2.remove(2); list2.show(); list2.clear(); list2.show(); }