C++进阶03 模板与群体数据

听课笔记简单整理，供小伙伴们参考~🥝🥝

第1版：听课的记录代码~🧩🧩

编辑：梅头脑🌸

审核：文心一言

🐳课程来源

🐋模板

🐋8.1 函数模板

🐋8.1.1 函数模版（数据模板）

🐋8.1.2 函数模版（类模板）

🐋8.2 类模板

🐋群体类数据和群体数据的组织

🐋8.3 线性群体

🐋8.3.1 数组

🐋8.3.2 链表

🐋8.3.3 栈

🐋8.3.4 队列

🐋8.4 排序

🐋8.4.1 插入排序

🐋8.4.2 选择排序

🐋8.4.3 交换排序

🐋8.5 查找

🐋8.5.1 顺序查找

🐋8.5.2 折半查找

🔚结语

🐳课程来源

郑莉、李超老师的公开课：🌸C++语言程序设计进阶

🐋模板

📇相关概念

计算机的优势在于可以迅速处理大批量的数据。然而，面对多种多样的数据类型，我们需要为每一种数据类型都单独编写一种处理函数吗？

不是的，尽管我们之前已经提供了函数重载的机制（🌸C++入门04）——根据参数类型的不同，编写多个同名函数。例如同名的sum函数，参数名分别修改为int、float，编译器就可以通过参数类型实现函数重载，接受不同的参数完成同一种功能。这种机制，可以让用户用得很开心，但是编写函数的人却要遭殃了——同一个函数，不仅每个类型重写一遍，而且后期在修改的某个功能的时候，每个函数再重改一遍，实在是太啰嗦了~

正因为如此，我们引入模板的概念。模板允许我们编写一种通用的代码，该代码可以处理多种数据类型，而无需针对每种类型都重新编写函数。实现了开着者只需要重写一遍，用户也只需要调用一种函数的效果~

🐋8.1 函数模板

🐋8.1.1 函数模版（数据模板）

当我们想要创建一个能够兼容所有数据类型的函数模版时，可以使用typename T作为数据参数的占位符。这样，我们就能够定义一个可以接受任何数据类型作为参数的函数模板。

例如，如果我们想要编写一个求取不同数据类型绝对值的函数，可以这样实现：

⌨️代码实现

#include <iostream>
using namespace std;

template<typename T>	// 函数模板，返回类型为T
T abs(T x) {			// 返回x的绝对值
	return x < 0 ? -x : x;
}

int main() {
	int n = -5;
	double d = -5.5;
	cout << "abs(" << n << ") = " << abs(n) << endl;
	cout << "abs(" << d << ") = " << abs(d) << endl;
	return 0;
}

📇执行结果

在这个例子中，我们定义了一个名为abs_value的函数模板，它接受一个类型为T的参数，并返回该参数的绝对值。在main函数中，我们分别调用了abs_value函数来计算整数(int)和双精度浮点数(double)的绝对值，并打印结果。

🐋8.1.2 函数模版（类模板）

除了基本的数据类型，当被调用的参数是一个类型数据时，我们也可以编写兼容所有数据类型的函数模板。这时模板的占位符需要相应修改为：“template <class T> ”。

例如，如果我们想要编写一个输出类中数组元素的函数，可以这样实现：

⌨️代码实现

#include <iostream>
using namespace std;

template <class T>  //定义函数模板
void outputArray(const T* array, int count) {
    for (int i = 0; i < count; i++)
        cout << array[i] << " "; //如果数组元素是类的对象，需要该对象所属类重载了流插入运算符“<<”
    cout << endl;
}

int main() {
    const int A_COUNT = 8, B_COUNT = 8, C_COUNT = 20;
    int a[A_COUNT] = { 1, 2, 3, 4, 5, 6, 7, 8 };
    double b[B_COUNT] = { 1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7, 8.8 };
    char c[C_COUNT] = "Welcome!";

    cout << "a array contains:" << endl;
    outputArray(a, A_COUNT);
    cout << "b array contains:" << endl;
    outputArray(b, B_COUNT);
    cout << "c array contains:" << endl;
    outputArray(c, C_COUNT);
    return 0;
}

📇执行结果

在这个例子中，我们定义了一个名为outputArray的函数模板，它接受一个类型为T的数组、int型的长度参数，并依次打印这些数组中的元素。在main函数中，我们分别调用了outputArray函数来打印含有整数(int)、双精度浮点数(double)和符号(char)的数组元素。

📇小问题

我其实有点没有搞懂，为什么处理的是基本数组，而用的是class类型？

AI是这样回复的：

在C++模板编程中，class T和typename T在大多数情况下是可以互换使用的，它们在这里的作用是指定一个类型参数。在模板定义中，class关键字并不特指“类”这种数据类型，而是用作类型参数的声明。这可能会引起一些混淆，因为它与定义实际类时使用的class关键字相同。

在模板上下文中，class和typename主要区别在于它们用于模板参数声明的语境：

typename在模板中使用时，更加直观地表明这是一个类型参数，而非一个类。
class在模板参数中使用时，它的含义扩展为了表示任何类型，包括基本数据类型、类类型、结构体等。

在C++标准中，class和typename作为模板参数时的功能是相同的，选择哪一个主要是基于编码风格和团队约定。有些团队可能会倾向于始终使用typename以增加代码的清晰度，而有些团队则可能会选择class，尤其是在模板参数明显指代一个类类型的时候。

实际上，class T和typename T在模板函数或模板类中定义类型参数时是完全等效的。因此，您可以选择您认为更清晰或更符合您团队编码风格的那个。

在您的例子中，使用template <class T>是完全有效的，它定义了一个类型参数T，这个T可以是任何类型，包括内置类型（如int、double）、类类型或用户定义的类型。所以，不要因为它用了class这个关键字而感到困惑，这里的class T只是定义了一个泛型类型参数T。

🐋8.2 类模板

尽管template <class T> 并不是专用于处理类的数据，但是类确实也是拥有模板的。例如，我们可以将类的私有变量设置为泛型T。

⌨️代码实现

这里我们定义了一个名为Store的类模板，它能够存储任意类型的数据。

#include <iostream>
#include <cstdlib>
using namespace std;
struct Student {
    int id;          // 学号
    float gpa;       // 平均分
};
template <class T>
class Store {        // 类模板：实现对任意类型数据进行存取
private:
    T item;          // item用于存放任意类型的数据
    bool haveValue;  // haveValue标记item是否已被存入内容
public:
    Store();				   // 构造函数
    T& getElem();              // 提取数据函数
    void putElem(const T& x);  // 存入数据函数
};

template <class T>
Store<T>::Store() : haveValue(false) { }	  // 构造函数，初始化haveValue为false
template <class T>
T& Store<T>::getElem() {
    if (!haveValue) {                         // 如试图提取未初始化的数据，则终止程序
        cout << "No item present!" << endl;
        exit(1);                              // 使程序完全退出，返回到操作系统。
    }
    return item;                              // 返回item中存放的数据 
}
template <class T>
void Store<T>::putElem(const T& x) {
    haveValue = true;   // 将haveValue 置为true，表示item中已存入数值   
    item = x;           // 将x值存入item
}

int main() {
    Store<int> s1, s2;
    s1.putElem(3);
    s2.putElem(-7);
    cout << s1.getElem() << "  " << s2.getElem() << endl;

    Student g = { 1000, 23 };
    Store<Student> s3;
    s3.putElem(g);
    cout << "The student id is " << s3.getElem().id << endl;

    Store<double> d;
    cout << "Retrieving object D... ";
    cout << d.getElem() << endl;
    //d未初始化，执行函数D.getElement()时导致程序终止
    return 0;
}

📇执行结果

📇代码说明

通过s1和s2的示例，我们实现了为item存放整数值，并通过getElem函数提取它们；
通过s3的示例，我们构建了学生g的结构体，其中包含了学生的id(1000)与gpa(23)。这个结构体也可以作为参数传送给类，因为没有具体指定传哪个属性，因此整个student对象（包括id与gpa）均被赋值给item；
通过d的示例，我们展示了当Store对象没有被赋值时（即haveValue为false），如果尝试调用getElem函数，程序会输出错误信息并终止，因为此时不满足提取数据的条件。这是为了防止未初始化数据的访问，确保程序的安全性。

🐋群体类数据和群体数据的组织

在处理大型数据时，我们常常会遇到两个问题：如何有效地存储数据，以及如何高效地调用和处理这些数据。在之前的内容中，我们已经简单探讨了数据的调用与处理，而在其后的内容，我们将聚焦于数据的存储——这也是数据结构的基础知识。

🐋8.3 线性群体

线性结构，顾名思义，其数据排列呈现出一种“线性”特点。想象一下排队的场景，除了队伍的最前端和最后端，队伍中的每个人前面和后面都各站着一个人。这种结构就被称为线性结构。接下来，我们会简要介绍一些适用于线性结构的通用模板，帮助大家初步了解C++库编写的基本原理。

请注意，对于每段代码，我不会做详细解释。如果对于线性结构感兴趣，欢迎移步至我的“数据结构”相关系列博文~

🐋8.3.1 数组

⌨️代码实现

Array.h

在Array.h中，我们定义了一个动态数组类模板Array。这个类提供了动态调整数组大小的功能，并且能够像普通数组一样通过下标访问元素。关键功能包括构造函数、析构函数、复制构造函数、赋值运算符重载、下标运算符重载以及resize方法用于动态调整数组大小。

// 动态数组类模板程序
#ifndef ARRAY_H
#define ARRAY_H
#include <cassert>

template <class T>  // 数组类模板定义
class Array {
private:
    T* list;        // 用于存放动态分配的数组内存首地址
    int size;       // 数组大小（元素个数）
public:
    Array(int sz = 50);         // 构造函数，默认数组大小为50
    Array(const Array<T>& a);   // 复制构造函数
    ~Array();                   // 析构函数
    Array<T>& operator = (const Array<T>& rhs); // 重载"=“
    T& operator[] (int i);                      // 重载"[]”，返回引用使得可通过[]修改数组元素
    const T& operator[] (int i) const;          // 重载"[]”常函数
    operator T* ();                             // 重载到T*类型的转换，使得可以像普通数组名一样使用对象
    operator const T* () const; 				// 重载到T*类型常对象的转换
    int getSize() const;        // 取数组的大小
    void resize(int sz);        // 修改数组的大小
};

template <class T>
Array<T>::Array(int sz) {       // 构造函数
    assert(sz >= 0);            // sz为数组大小（元素个数），应当非负
    size = sz;                  // 将元素个数赋值给变量size
    list = new T[size];         // 动态分配size个T类型的元素空间
}

template <class T>
Array<T>::~Array() {            // 析构函数
    delete[] list;  			// 释放list所指内存，防止内存泄漏
}

template <class T>
Array<T>::Array(const Array<T>& a) {    // 复制构造函数，对象需要新建，因为有指针成员，所以需要深拷贝
    size = a.size;                      // 从对象x取得数组大小，并赋值给当前对象的成员
    list = new T[size];                 // 动态分配n个T类型的元素空间
    for (int i = 0; i < size; i++)      // 从对象X复制数组元素到本对象 
        list[i] = a.list[i];
}

template <class T>                      // 重载"="运算符，对象已存续一段时间，相比复制构造函数，需要先释放原有内存
Array<T>& Array<T>::operator = (const Array<T>& rhs) {
    if (&rhs != this) {                 // 判断是否为自身赋值
        if (size != rhs.size) {         // 如果本对象中数组大小与rhs不同，则删除数组原有内存，然后重新分配
            delete[] list;              // 删除数组原有内存
            size = rhs.size;            // 设置本对象的数组大小
            list = new T[size];         // 重新分配size个元素的内存
        }

        for (int i = 0; i < size; i++)  // 从对象X复制数组元素到本对象  
            list[i] = rhs.list[i];
    }
    return *this;                       // 返回当前对象的引用
}

template <class T>
T& Array<T>::operator[] (int n) {       // 重载下标运算符(非常量版本)，实现与普通数组一样通过下标访问元素，具有越界检查功能
    assert(n >= 0 && n < size);         // 检查下标是否越界
    return list[n];                     // 返回下标为n的数组元素，通过引用可以对元素进行修改
}

template <class T>
const T& Array<T>::operator[](int n) const {         // 重载下标运算符，实现与普通数组一样通过下标访问元素，具有越界检查功能}
    assert(n >= 0 && n < size);                      // 检查下标是否越界
    return list[n];                                  // 返回下标为n的数组元素
}

template <class T>  
Array<T>::operator T* () {                       // 重载指针转换运算符，将Array类的对象名转换为T类型的指针
    return list;                                 // 返回当前对象中私有数组的首地址
}

template <class T>
int Array<T>::getSize() const {      // 取当前数组的大小
    return size;
}


template <class T>
void Array<T>::resize(int sz) {      // 将数组大小修改为sz，实现动态扩展数组功能
    assert(sz >= 0);                 // 检查sz是否非负
    if (sz == size)                  // 如果指定的大小与原有大小一样，什么也不做
        return;
    T* newList = new T[sz];          // 申请新的数组内存
    int n = (sz < size) ? sz : size; // 将sz与size中较小的一个赋值给n，即新旧数组都有的元素个数
    for (int i = 0; i < n; i++)      // 将原有数组中前n个元素复制到新数组中，复制原有数组中的元素
        newList[i] = list[i];
    delete[] list;                   // 删除原数组
    list = newList;                  // 使list指向新数组
    size = sz;                       // 更新size
}
#endif

main.cpp

在main.cpp中，我们使用Array类来存储质数。程序首先创建一个具有初始大小的Array对象，然后通过用户输入确定质数的上限。接着，程序通过一个循环检查每个数是否为质数，如果是，则将其添加到数组中。如果数组空间不足，则通过resize方法动态扩展数组。

// 求范围2~N中的质数，N在程序运行时由键盘输入
#include <iostream>
#include <iomanip>
#include "Array.h"
using namespace std;
int main() {
    // 用来存放质数的数组，初始状态有10个元素
    Array<int> a(10);
    int n, count = 0;
    cout << "Enter a value >= 2 as upper limit for prime numbers: ";
    cin >> n;

    for (int i = 2; i <= n; i++) {    // 检查i是否能被比它小的质数整除
        bool isPrime = true;
        for (int j = 0; j < count; j++)
            if (i % a[j] == 0) {      // 若i被a[j]整除，说明i不是质数，跳出循环
                isPrime = false; break;
            }
        if (isPrime) {  	          // 若i是质数，将i存入数组a
            if (count == a.getSize()) // 若数组a已满，将数组大小扩大一倍
                a.resize(count * 2); 
            a[count++] = i;
        }
    }
    for (int i = 0; i < count; i++)	  // 输出数组a中的质数
        cout << setw(8) << a[i];
    cout << endl;
    return 0;
}

📇执行结果

📇代码说明

Array.h

动态数组与静态数组最大的区别，就是数组在执行过程中，根据需要可以扩大或者缩小；但是怎么实现这个功能呢？看向resize函数，实现这个功能，需要开辟O(n)那么大的空间，并且遍历O(n)那么长的数据，然后把数组的元素一个一个复制进去，再销毁旧数组。

因此，动态数组虽然方便，但是如果来回调整数组大小，照样很浪费内存；如果已知大小的情况下，使用静态数组可能会更加高效。

main.cpp

整个代码就是在计算输入元素N以后，从2-N的质数，并存入数组中。这个代码的基本逻辑就是，往后存入的元素，不能被数组前面所存放的元素整除，否则他就不是质数。

在main.cpp中，我们使用了动态数组来存储质数。这是因为质数的数量是未知的，而且可能会随着用户输入的上限的增加而增加。使用动态数组可以确保我们有足够的空间来存储所有找到的质数，而无需事先确定数组的大小。

📇小问题

每次执行a[count++] = i;时，虽然没有明显的标识，但是头文件还是会自动检查空间是否够用；每次执行if (i % a[j] == 0)时，头文件也会自动判断下标是否越界。明明没有明显触发的函数名，为什么相关函数会被自动调用呢？

AI是这样回复的：

在您提供的代码中，并没有明显的函数调用去检查数组空间或下标是否越界，但实际上这些检查是隐藏在类的成员函数中的。当您使用Array类的实例，并调用其成员函数（如operator[]）时，这些检查是自动进行的。

具体来说：

空间检查：在Array类中，并没有直接的空间检查机制来在每次添加元素前判断数组是否已满。但是，当您尝试通过a[count++] = i;添加一个新元素时，如果count的值等于数组的当前大小（即size），则下一次尝试添加元素将会越界，因为C++不会自动扩展数组。为了防止这种情况，您在代码中显式地检查了是否需要扩展数组：
if (count == a.getSize()) // 若数组a已满，将数组大小扩大一倍  
    a.resize(count * 2);
这段代码确保了每次当数组空间不足时，都会通过调用resize函数来扩大数组的大小。所以，虽然看起来没有明显的空间检查，但实际上您在代码中已经实现了这一功能。

下标越界检查：在Array类的operator[]成员函数中，您使用了assert语句来检查下标是否越界：
assert(n >= 0 && n < size); // 检查下标是否越界
这意味着每次通过a[j]访问数组元素时，都会隐式地执行这个检查。如果j不在有效范围内（即小于0或大于等于size），程序将触发断言并终止执行。虽然这不是一个优雅的错误处理方式（在生产环境中通常会使用更复杂的错误处理机制），但它确实提供了一种在调试阶段捕获错误的方法。

总的来说，虽然看起来没有明显的函数调用或检查语句，但实际上这些检查是嵌入在类的成员函数中的。每次通过这些成员函数访问数组时，都会自动执行相应的检查。这也是面向对象编程封装性的一个体现：类内部隐藏了实现细节，使得外部调用者无需关心内部是如何工作的。

感觉听完还是有点迷糊，因为确实不是卡在有明显函数语句处判定的，反而像是重载的运算符在默默判定——

🐋8.3.2 链表

⌨️代码实现

Node.h

//Node.h
#ifndef NODE_H
#define NODE_H
template <class T>
class Node {
private:
	T data;			//数据域
	Node<T> *next;	//指针域
public:	
	Node(const T& item, Node<T>* next = 0);	// 构造函数，初始化数据和指针成员
	void insertAfter(Node<T> *p);			// 在本结点之后插入一个同类结点p
	Node<T> *deleteAfter();					// 删除本结点之后的结点，并返回其地址
	Node<T> *nextNode();					// 返回后继结点的指针
	const Node<T> *nextNode() const;		// 返回后继结点的指针

	template <class U>
	friend class LinkedList;					// 声明友元类
};

//类的实现部分
//构造函数，初始化数据和指针成员
template <class T>
Node<T>::Node(const T& data, Node<T>* next) : data(data), next(next) { }

//返回后继结点的指针
template <class T>
Node<T>* Node<T>::nextNode() {
	return next;
}

//删除当前结点的后继结点，并返回其地址
template <class T> Node<T>* Node<T>::deleteAfter() {
	Node<T>* tempPtr = next;//将欲删除的结点地址存储到tempPtr中
	if (next == 0)			//如果当前结点没有后继结点，则返回空指针
		return 0;
	next = tempPtr->next;   //使当前结点的指针域指向tempPtr的后继结点
	return tempPtr;         //返回被删除的结点的地址
}


//返回后继结点的指针
template <class T>
const Node<T>* Node<T>::nextNode() const {
	return next;
}

//返回后继结点的指针
template <class T>
void Node<T>::insertAfter(Node<T>* p) {
	p->next = next;	//p节点指针域指向当前节点的后继节点
	next = p;		//当前节点的指针域指向p 
}

#endif //NODE_H

LinkedList.h

//LinkedList.h
#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include "Node.h"
#include <iostream>

template <class T>
class LinkedList {
private:
    //数据成员：
    Node<T>* front, * rear;        //表头和表尾指针
    Node<T>* prevPtr, * currPtr;   //记录表当前遍历位置的指针，由插入和删除操作更新；CurrPtr指向当前结点，prevPtr指向当前结点的前一个结点
    int size;                      //表中的元素个数
    int position;                  //当前元素在表中的位置序号，由函数reset使用

    //函数成员：
    Node<T>* newNode(const T& item, Node<T>* ptrNext = NULL);   //生成新结点，数据域为item，指针域为ptrNext
    void freeNode(Node<T>* p);                                  //释放结点
    void copy(const LinkedList<T>& L);                          //将链表L 拷贝到当前表（假设当前表为空），被拷贝构造函数、operator = 调用，统一构造函数与函数的复制算法

public:
    LinkedList();                                       //构造函数
    LinkedList(const LinkedList<T>& L);                 //拷贝构造函数
    ~LinkedList();                                      //析构函数
    LinkedList<T>& operator = (const LinkedList<T>& L); //重载赋值运算符

    int getSize() const;                //返回链表中元素个数
    bool isEmpty() const;               //链表是否为空

    void reset(int pos = 0);            //初始化游标的位置
    void next();                        //使游标移动到下一个结点
    bool endOfList() const;             //游标是否到了链尾
    int currentPosition() const;        //返回游标当前的位置

    void insertFront(const T& item);    //在表头插入结点
    void insertRear(const T& item);     //在表尾添加结点
    void insertAt(const T& item);       //在当前结点之前插入结点
    void insertAfter(const T& item);    //在当前结点之后插入结点

    T deleteFront();                    //删除头结点
    void deleteCurrent();               //删除当前结点

    T& data();                          //返回对当前结点成员数据的引用
    const T& data() const;              //返回对当前结点成员数据的常引用

    void clear();                       //清空链表：释放所有结点的内存空间。被析构函数、operator= 调用
};

template <class T> //生成新结点
Node<T>* LinkedList<T>::newNode(const T& item, Node<T>* ptrNext)
{
    Node<T>* p;
    p = new Node<T>(item, ptrNext);
    if (p == NULL)
    {
        std::cout << "Memory allocation failure!\n";
        exit(1);
    }
    return p;
}

template <class T>
void LinkedList<T>::freeNode(Node<T>* p) //释放结点
{
    delete p;
}

template <class T>
void LinkedList<T>::copy(const LinkedList<T>& L) //链表复制函数
{
    Node<T>* p = L.front;   //P用来遍历L 
    int pos;
    while (p != NULL)   //将L中的每一个元素插入到当前链表最后
    {
        insertRear(p->data);
        p = p->nextNode();
    }
    if (position == -1) //如果链表空,返回
        return;
    //在新链表中重新设置prevPtr和currPtr
    prevPtr = NULL;
    currPtr = front;
    for (pos = 0; pos != position; pos++)
    {
        prevPtr = currPtr;
        currPtr = currPtr->nextNode();
    }
}

template <class T>  //构造一个新链表，将有关指针设置为空，size为0，position为-1
LinkedList<T>::LinkedList() : front(NULL), rear(NULL),
prevPtr(NULL), currPtr(NULL), size(0), position(-1)
{}

template <class T>
LinkedList<T>::LinkedList(const LinkedList<T>& L)  //拷贝构造函数
{
    front = rear = NULL;
    prevPtr = currPtr = NULL;
    size = 0;
    position = -1;
    copy(L);
}

template <class T>
LinkedList<T>::~LinkedList()    //析构函数
{
    clear();
}

template <class T>
LinkedList<T>& LinkedList<T>::operator=(const LinkedList<T>& L)//重载"="
{
    if (this == &L)             //不能将链表赋值给它自身
        return *this;
    clear();
    copy(L);
    return *this;
}

template <class T>
int LinkedList<T>::getSize() const  //返回链表大小的函数
{
    return size;
}

template <class T>
bool LinkedList<T>::isEmpty() const //判断链表为空否
{
    return size == 0;
}

template <class T>
void LinkedList<T>::reset(int pos)  //将链表当前位置设置为pos 
{
    int startPos;
    if (front == NULL)  // 如果链表为空，返回
        return;
    if (pos < 0 || pos > size - 1)  // 如果指定位置不合法，中止程序
    {
        std::cerr << "Reset: Invalid list position: " << pos << std::endl;
        return;
    }
    // 设置与遍历链表有关的成员
    if (pos == 0)   // 如果pos为0，将指针重新设置到表头
    {
        prevPtr = NULL;
        currPtr = front;
        position = 0;
    }
    else    // 重新设置 currPtr, prevPtr, 和 position 
    {
        currPtr = front->nextNode();
        prevPtr = front;
        startPos = 1;
        for (position = startPos; position != pos; position++)
        {
            prevPtr = currPtr;
            currPtr = currPtr->nextNode();
        }
    }
}

template <class T>
void LinkedList<T>::next()  //将prevPtr和currPtr向前移动一个结点
{
    if (currPtr != NULL)
    {
        prevPtr = currPtr;
        currPtr = currPtr->nextNode();
        position++;
    }
}

template <class T>
bool LinkedList<T>::endOfList() const   // 判断是否已达表尾
{
    return currPtr == NULL;
}

template <class T>
int LinkedList<T>::currentPosition() const  // 返回当前结点的位置
{
    return position;
}

template <class T>
void LinkedList<T>::insertFront(const T& item)   // 将item插入在表头
{
    if (front != NULL)  // 如果链表不空则调用Reset 
        reset();
    insertAt(item); // 在表头插入
}

template <class T>
void LinkedList<T>::insertRear(const T& item)   // 在表尾插入结点
{
    Node<T>* nNode;
    prevPtr = rear;
    nNode = newNode(item);  // 创建新结点
    if (rear == NULL)   // 如果表空则插入在表头
        front = rear = nNode;
    else
    {
        rear->insertAfter(nNode);
        rear = nNode;
    }
    currPtr = rear;
    position = size;
    size++;
}

template <class T>
void LinkedList<T>::insertAt(const T& item) // 将item插入在链表当前位置
{
    Node<T>* nNode;
    if (prevPtr == NULL)    // 插入在链表头，包括将结点插入到空表中
    {
        nNode = newNode(item, front);
        front = nNode;
    }
    else    // 插入到链表之中. 将结点置于prevPtr之后
    {
        nNode = newNode(item);
        prevPtr->insertAfter(nNode);
    }
    if (prevPtr == rear)    //正在向空表中插入，或者是插入到非空表的表尾
    {
        rear = nNode;   //更新rear 
        position = size;    //更新position 
    }
    currPtr = nNode;    //更新currPtr
    size++; //使size增值
}

template <class T>
void LinkedList<T>::insertAfter(const T& item)  // 将item 插入到链表当前位置之后
{
    Node<T>* p;
    p = newNode(item);
    if (front == NULL)   // 向空表中插入
    {
        front = currPtr = rear = p;
        position = 0;
    }
    else    // 插入到最后一个结点之后
    {
        if (currPtr == NULL)
            currPtr = prevPtr;
        currPtr->insertAfter(p);
        if (currPtr == rear)
        {
            rear = p;
            position = size;
        }
        else
            position++;
        prevPtr = currPtr;
        currPtr = p;
    }
    size++;              // 使链表长度增值
}

template <class T>
T LinkedList<T>::deleteFront()  // 删除表头结点
{
    T item;
    reset();
    if (front == NULL)
    {
        std::cerr << "Invalid deletion!" << std::endl;
        exit(1);
    }
    item = currPtr->data;
    deleteCurrent();
    return item;
}

template <class T>
void LinkedList<T>::deleteCurrent() // 删除链表当前位置的结点
{
    Node<T>* p;
    if (currPtr == NULL)    // 如果表空或达到表尾则出错
    {
        std::cerr << "Invalid deletion!" << std::endl;
        exit(1);
    }
    if (prevPtr == NULL)    // 删除将发生在表头或链表之中
    {
        p = front;  // 保存头结点地址
        front = front->nextNode();  //将其从链表中分离
    }
    else    //分离prevPtr之后的一个内部结点，保存其地址
        p = prevPtr->deleteAfter();

    if (p == rear)  // 如果表尾结点被删除
    {
        rear = prevPtr; //新的表尾是prevPtr 
        position--; //position自减
    }
    currPtr = p->nextNode();    // 使currPtr越过被删除的结点
    freeNode(p);    // 释放结点，并
    size--; //使链表长度自减
}

template <class T>
T& LinkedList<T>::data()    //返回一个当前结点数值的引用
{
    if (size == 0 || currPtr == NULL)   // 如果链表为空或已经完成遍历则出错
    {
        std::cerr << "Data: invalid reference!" << std::endl;
        exit(1);
    }
    return currPtr->data;
}

template <class T>
void LinkedList<T>::clear() //清空链表
{
    Node<T>* currPosition, * nextPosition;
    currPosition = front;
    while (currPosition != NULL)
    {
        nextPosition = currPosition->nextNode(); //取得下一结点的地址
        freeNode(currPosition); //删除当前结点
        currPosition = nextPosition;    //当前指针移动到下一结点
    }
    front = rear = NULL;
    prevPtr = currPtr = NULL;
    size = 0;
    position = -1;
}
#endif  //LINKEDLIST_H

main.cpp

#include <iostream>
#include "LinkedList.h"
using namespace std;

int main()
{
    LinkedList<int> list;
    for (int i = 0; i < 10; i++) {
        int item;
        cin >> item;
        list.insertFront(item);       // 头插法，可以作为栈使用
    }
    cout << "List:";
    list.reset();                     // 将游标指向链表头
    while(!list.endOfList()) {
		cout << list.data() << " ";
		list.next();                  // 使游标指向下一个元素
	}
    cout << endl;
    int key;
    cout << "Please enter some integer needed to be deleted: ";
    cin >> key;
    list.reset();
    while(!list.endOfList()){
		if (list.data() == key) {
			list.deleteCurrent();
		}
		list.next();
	}
    cout << "List:";
    list.reset();
    while (!list.endOfList()) {
        cout << list.data() << " ";
        list.next();                  // 使游标指向下一个元素
    }
	cout << endl;
	return 0;
}

📇执行结果

（成功）

（失败）

📇代码说明

只是测试的时候发现删除稍微有点小问题，大概是遇到重复的数字时，会跳过下一个重复数字的删除判定。但是这段代码实在是太太太长了，可能有点超过了我的修改能力...

我曾经改过一个功能类似，但是没有这么复杂和全面的版本，有兴趣可以看向这里：

🌸答题01 单链表打印-CSDN博客

或许有一天我会心血来潮修改这段代码，具体来说：

(1)如果指针的后一个数字与当前数字相同，则Next指针继续向后判定，直到数字不同为止，next指向该数字。然而这又不是一个专门针对删除重复节点的模板代码；

(2)如果把currPtr的位置重新判定一下呢，如果后一个元素与当前元素相同，CurrPtr退回当前节点。但是，这个会不会影响其它链表的删除功能啊，想想又要调试，重新考虑尾结点的处理，很头秃——

(3)不如在main函数写一个while循环删除，直到链表里检测不到7比较方便，但这么做感觉又有点诡异。

算了，瘫，现在我只想发个没什么人看的博文凑数...

🐋8.3.3 栈

🧩题目

⌨️代码实现

stack.h

//Stack.h
#ifndef STACK_H
#define STACK_H
#include <cassert> 
template <class T, int SIZE = 50>   // 模板中可以设置默认参数
class Stack {
private:
    T list[SIZE];
    int top;
public:
    Stack();                        // 构造函数
    void push(const T& item);       // 入栈
    T pop();    		            // 出栈
    void clear();                   // 清空栈
    const T& peek() const;          // 返回栈顶元素
    bool isEmpty() const;           // 判断栈是否为空
    bool isFull() const;		    // 判断栈是否为满
};

//模板的实现
template <class T, int SIZE>
Stack<T, SIZE>::Stack() : top(-1) { }         // 构造函数，初始化栈顶指针为-1

template <class T, int SIZE>
void Stack<T, SIZE>::push(const T& item) {    
    assert(!isFull());                        // 判断栈是否为满
    list[++top] = item; 					  // 入栈
}
template <class T, int SIZE>
T Stack<T, SIZE>::pop() {
    assert(!isEmpty()); 				      // 判断栈是否为空
    return list[top--]; 				      // 出栈
}
template <class T, int SIZE>
const T& Stack<T, SIZE>::peek() const {
    assert(!isEmpty());
    return list[top];                         // 返回栈顶元素
}
template <class T, int SIZE>
bool Stack<T, SIZE>::isEmpty() const {
    return top == -1;                         // 判断栈是否为空
}
template <class T, int SIZE>
bool Stack<T, SIZE>::isFull() const {
    return top == SIZE - 1; 			      // 判断栈是否为满
}

template <class T, int SIZE>
void Stack<T, SIZE>::clear() {
    top = -1;								  // 清空栈
}

#endif  //STACK_H

Calculator.h

这段代码不是为栈而写，而是为表达式求值而写~

//Calculator.h
#ifndef CALCULATOR_H
#define CALCULATOR_H
#include "Stack.h"  // 包含栈类模板定义文件
#include <iostream>
#include <sstream>
#include <cmath>
using namespace std;

class Calculator {  //计算器类
private:
    Stack<double> s;    // 操作数栈
    void enter(double num); //将操作数num压入栈
    //连续将两个操作数弹出栈，放在opnd1和opnd2中
    bool getTwoOperands(double& opnd1, double& opnd2);
    void compute(char op);  //执行由操作符op指定的运算
public:
    void run();     //运行计算器程序
    void clear();   //清空操作数栈
};

inline double stringToDouble(const string& str) {   // 工具函数，用于将字符串转换为实数
    istringstream stream(str);                      // 字符串输入流
    double result;
    stream >> result;
    return result;
}

void Calculator::enter(double num) {                // 将操作数num压入栈
    s.push(num);
}

bool Calculator::getTwoOperands(double& opnd1, double& opnd2) {
    if (s.isEmpty()) {  // 检查栈是否空
        cerr << "Missing operand!" << endl;
        return false;
    }
    opnd1 = s.pop();    // 将右操作数弹出栈
    if (s.isEmpty()) {  // 检查栈是否空
        cerr << "Missing operand!" << endl;
        return false;
    }
    opnd2 = s.pop();    // 将左操作数弹出栈
    return true;
}

void Calculator::compute(char op) { // 执行运算
    double operand1, operand2;
    bool result = getTwoOperands(operand1, operand2);
    if (result) {                   // 如果成功，执行运算并将运算结果压入栈
        switch (op) {
        case '+': s.push(operand2 + operand1); break;
        case '-': s.push(operand2 - operand1); break;
        case '*': s.push(operand2 * operand1); break;
        case '/': if (operand1 == 0) {      // 检查除数是否为0
            cerr << "Divided by 0!" << endl;
            s.clear();                      // 除数为0时清空栈
        }
                else
            s.push(operand2 / operand1);
            break;
        case '^': s.push(pow(operand2, operand1)); break;
        default:  cerr << "Unrecognized operator!" << endl;
            break;
        }
        cout << "= " << s.peek() << " ";    // 输出本次运算结果 
    }
    else
        s.clear();                          // 操作数不够，清空栈
}

void Calculator::run() {                    // 读入并处理后缀表达式
    string str;
    while (cin >> str, str != "q") {        // 读入字符串，若为"q"则退出，以逗号后的表达式为循环终止条件
        switch (str[0]) {
        case 'c': s.clear(); break;
        case '-':                           // 遇'-'需判断是减号还是负号
            if (str.size() > 1)             // 若是负号，转换为整型后压入栈
                enter(stringToDouble(str));
            else
                compute(str[0]);			// 若是减号，执行减法运算
            break;
        case '+':                           // 遇到其它操作符时
        case '*':
        case '/':
        case '^':
            compute(str[0]);   break;	    // 执行相应运算
        default:                            // 若读入的是操作数，转换为整型后压入栈
            enter(stringToDouble(str)); break;
        }
    }
}
void Calculator::clear() {                  // 清空操作数栈
    s.clear();
}

#endif //CALCULATOR_H

main.cpp

#include "Calculator.h"
using namespace std;

int main() {
    Calculator c;
    c.run();
    return 0;
}

📇执行结果

输入3、5、+，回车后可输出8；

这段代码的基本原理与之前写过的一篇博文相同，里面的案例4 表达式求值有详细说明算法思想：

🌸数据结构03：栈、队列和数组_向空栈依次输入a b c操作结束后暂定-CSDN博客

🐋8.3.4 队列

⌨️代码实现

Queue.h

//Queue.h
#ifndef QUEUE_H
#define QUEUE_H
#include <cassert>
//类模板的定义
template <class T, int SIZE = 50>
class Queue {
private:
    int front, rear, count;     //队头指针、队尾指针、元素个数
    T list[SIZE];               //队列元素数组
public:
    Queue();                    //构造函数，初始化队头指针、队尾指针、元素个数
  
    void insert(const T& item); //新元素入队
    T remove();                 //元素出队
    void clear();               //清空队列
    const T& getFront() const;  //访问队首元素
  
    //测试队列状态
    int getLength() const;      //求队列长度
    bool isEmpty() const;       //判断队列空否
    bool isFull() const;        //判断队列满否
};

template <class T, int SIZE>    //构造函数，初始化队头指针、队尾指针、元素个数
Queue<T, SIZE>::Queue() : front(0), rear(0), count(0) { }

template <class T, int SIZE>    //向队尾插入元素
void Queue<T, SIZE>::insert(const T& item) {
    assert(count != SIZE);
    count++;                    //元素个数增1
    list[rear] = item;          //向队尾插入元素
    rear = (rear + 1) % SIZE;   //队尾指针增1，用取余运算实现循环队列
}
template <class T, int SIZE> T Queue<T, SIZE>::remove() {
    assert(count != 0);
    int temp = front;           //记录下原先的队首指针
    count--;                    //元素个数自减
    front = (front + 1) % SIZE; //队首指针增1。取余以实现循环队列
    return list[temp];          //返回首元素值
}
template <class T, int SIZE>
const T& Queue<T, SIZE>::getFront() const {
    return list[front];
}
template <class T, int SIZE>
int Queue<T, SIZE>::getLength() const { //返回队列元素个数
    return count;
}

template <class T, int SIZE>
bool Queue<T, SIZE>::isEmpty() const {  //测试队空否
    return count == 0;
}
template <class T, int SIZE>
bool Queue<T, SIZE>::isFull() const {   //测试队满否
    return count == SIZE;
}
template <class T, int SIZE>
void Queue<T, SIZE>::clear() {          //清空队列
    count = 0;
    front = 0;
    rear = 0;
}
#endif  //QUEUE_H

📇执行结果

没有main，因此也没有执行结果（挠头）——

对队的实例感兴趣，可以参考：🌸数据结构03：栈、队列和数组队习题01[C++]-CSDN博客

🐋8.4 排序

在数据处理中，排序是一个常见的操作。目前，简单且主流的内部排序算法主要有三种类型：插入排序、选择排序和交换排序。

🐋8.4.1 插入排序

插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

⌨️代码实现

下面是一个C++实现的插入排序算法示例，同时在每轮排序后打印出当前序列的状态，便于观察排序过程。

#include <iostream>  
#include <vector>  
using namespace std;  
  
// 插入排序函数模板  
template<class T>  
void insertionSort(T arr[], int n) {  
    for (int i = 1; i < n; i++) {  
        T temp = arr[i];  // 保存待插入元素  
        int j = i - 1;    // 从已排序序列的最后一个元素开始比较  
        while (j >= 0 && arr[j] > temp) {  
            arr[j + 1] = arr[j];  // 将大于temp的元素后移  
            j--;                  // 继续比较前一个元素  
        }  
        arr[j + 1] = temp;        // 找到合适位置插入temp  
  
        // 打印每轮排序结果  
        cout << "第" << i << "轮排序结果：";  
        for (int k = 0; k < n; k++) {  
            cout << arr[k] << " ";  
        }  
        cout << endl;  
    }  
}  
  
int main() {  
    int a[] = {49, 38, 65, 97, 76, 13, 27, 49};  
    int n = sizeof(a) / sizeof(a[0]);  // 计算数组长度  
    cout << "初始序列：";  
    for (int i = 0; i < n; i++) {  
        cout << a[i] << " ";  
    }  
    cout << endl;  
    insertionSort(a, n);  // 执行插入排序  
    return 0;  
}

📇执行结果

📇代码解释

插入排序算法在每一步将一个待排序的元素插入到已排序的序列中，直到所有元素都被插入。下面是这个过程的详细解释：

初始序列为：49 38 65 97 76 13 27 49。
第1轮：将38插入到49前面，因为38 < 49，结果变为38 49 65 97 76 13 27 49。
第2轮：65保持原位，因为它大于前面的所有元素。
第3轮：97同样保持原位。
第4轮：76需要插入到已排序的序列中，经过比较和移动，最终插入到65和97之间，结果变为38 49 65 76 97 13 27 49。

（后续轮次的排序过程依此类推，直到所有元素都被正确排序。）

🐋8.4.2 选择排序

选择排序的基本思想是每次从待排序的序列中选择最小（或最大）的一个元素，存放到序列的起始位置，直到全部待排序的数据元素排完。以下是选择排序的详细实现和解释。

⌨️代码实现

#include <iostream>  
#include <vector>  
using namespace std;

template <class T>
void mySwap(T& x, T& y) {
    T temp = x;
    x = y;
    y = temp;
}

template <class T>
void selectionSort(T a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int leastIndex = i;              // 保存最小值的下标
        for (int j = i + 1; j < n; j++)  // 从i+1开始向后找最小值
            if (a[j] < a[leastIndex])    // 如果找到比当前最小值还小的值
                leastIndex = j;	    	 // 保存最小值的下标
        mySwap(a[i], a[leastIndex]);	 // 将最小值与a[i]交换

        cout << "第" << i + 1 << "轮排序结果：";
        for (int k = 0; k < n; k++)
			cout << a[k] << " ";
        cout << endl;
    }
}

int main() {
	int a[] = { 49, 38, 65, 97, 76, 13, 27, 49 };
    int n = sizeof(a) / sizeof(a[0]);  // 计算数组长度  
    cout << "初始序列：";
    for (int i = 0; i < n; i++) 
		cout << a[i] << " ";
	cout << endl;
	selectionSort(a, n);
	return 0;
}

📇执行结果

📇代码解释

选择排序算法在每一轮将队列的一个最小的元素排到第i个位置，直到所有元素都被排序。下面是这个过程的详细解释：

初始序列为：49 38 65 97 76 13 27 49。
第1轮：队列里最小的元素是13，与第1个元素49交换位置，结果变为13 38 65 97 76 49 27 49；
第2轮：除去第1个元素，队列里最小的元素是27，与第2个元素38交换位置，结果变为13 27 65 97 76 49 38 49；
第3轮：除去前2个元素，队列里最小的元素是38，与第3个元素65交换位置，结果变为13 27 38 97 76 49 65 49；
第4轮：除去前3个元素，队列里最小的元素是49，与第4个元素97交换位置，结果变为13 27 38 49 76 97 65 49。

（后续轮次的排序过程依此类推，直到所有元素都被正确排序。）

🐋8.4.3 交换排序

交换排序的一种常见实现是冒泡排序，其基本思想是多次遍历待排序的序列，每次比较相邻的两个元素，如果它们的顺序错误就把它们交换过来。每一轮遍历都会将当前未排序部分的最大元素“冒泡”到序列的最后，因此每一轮遍历后，最大元素都会被放置在正确的位置。

⌨️代码实现

#include <iostream>  
#include <vector>  
using namespace std;

template <class T>
void mySwap(T& x, T& y) {
    T temp = x;
    x = y;
    y = temp;
}

template <class T>
void bubbleSort(T a[], int n) {
    int i = n - 1;
    while (i > 0) {
        int lastExchangeIndex = 0;      // 保存最后一次交换的位置
        for (int j = 0; j < i; j++)     // 从前往后冒泡
            if (a[j + 1] < a[j]) {	    // 如果后一个元素小于前一个元素
                mySwap(a[j], a[j + 1]); // 交换两个元素
                lastExchangeIndex = j;  // 保存最后一次交换的位置
            }
        i = lastExchangeIndex;	        // i之后的元素已经有序，无需再比较

        cout << "第" << n - i << "轮排序结果：";
        for (int k = 0; k < n; k++)
			cout << a[k] << " ";
        cout << endl;
    }
}

int main() {
	int a[] = { 49, 38, 65, 97, 76, 13, 27, 49 };
	int n = sizeof(a) / sizeof(a[0]);  // 计算数组长度  
	cout << "初始序列：";
	for (int i = 0; i < n; i++) 
		cout << a[i] << " ";
	cout << endl;
	bubbleSort(a, n);
	return 0;
}

📇执行结果

📇代码解释

冒泡排序算法的详细过程如下：

从序列的第一个元素开始，比较相邻的两个元素，如果前一个元素大于后一个元素，则交换它们的位置。
这样，一轮遍历后，最大的元素会被“冒泡”到序列的最后。
重复上述步骤，但是每一轮遍历可以少比较一次，因为最大的元素已经被放置在正确的位置。

根据初始序列49 38 65 97 76 13 27 49，冒泡排序的过程大致如下：

初始序列：49 38 65 97 76 13 27 49
第1轮排序后：38 49 65 76 13 27 49 97（最大的97沉底）。从初始序列开始，具体为：
- 49与38比较，49较大，49后移，变为38 49 65 97 76 13 27 49；
- 49与65比较，65较大，排列不变，变为38 49 65 97 76 13 27 49；
- 65与97比较，97较大，排列不变，变为38 49 65 97 76 13 27 49；
- 97与76比较，97较大，97后移，变为38 49 65 76 97 13 27 49；
- 97与13比较，97较大，97后移，变为38 49 65 76 13 97 27 49；
- 97与27比较，97较大，97后移，变为38 49 65 76 13 27 97 49；
- 97与49比较，97较大，97后移，变为38 49 65 76 13 27 49 97；
第2轮排序后：38 49 65 13 27 49 76 97（次大的76沉底）
...（依此类推）
最终排序结果：13 27 38 49 49 65 76 97

（后续轮次的排序过程依此类推，直到所有元素都被正确排序。）

🐋8.5 查找

查找，顾名思义，就是在大量的数据中搜索我们想要找的信息。其中，两种常见且基础的查找算法是顺序查找和折半查找。

需要说一下，这个部分仅列代码，有关查找的详细解释可以参考这里：

🌸数据结构07：查找[C++][顺序、分块、折半查找]_分块查找输出结果c++-CSDN博客

🐋8.5.1 顺序查找

顺序查找是最简单的查找方法，其基本思想是从列表的第一个元素开始，逐个比较，直到找到目标元素或遍历完整个列表。

⌨️代码实现

template <class T>
int seqSearch(const T list[], int n, const T& key) {
    for (int i = 0; i < n; i++)
        if (list[i] == key)
            return i;
    return -1;
}

🐋8.5.2 折半查找

折半查找，也称二分查找，是一种在有序列表中查找目标元素的高效方法。其基本思想是不断将列表划分为两半，并判断目标元素可能在哪一半中，直到找到目标或确定目标不存在于列表中。

⌨️代码实现

template <class T>
int binSearch(const T list[], int n, const T& key) {
    int low = 0;
    int high = n - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (key == list[mid])
            return mid;
        else if (key < list[mid])
            high = mid – 1;
        else
            low = mid + 1;
    }
    return -1;
}