C + +那年那些事

前言

本篇blog是读者所总结（cv大法均有包含出处，笔者水平有限，如果错误请指出（主要期末考总结了一下方便考前再次复习

理论基础

在protected保护继承中，对于垂直访问等同于公有继承，对于水平访问等同于私有继承。

动态绑定是在运行时选定调用的成员函数的。

对于从基类继承的虚函数，派生类也可以不进行重定义。

类A是类B的友元，说明类A是友元类

友元不能传递也不能继承：破坏封装性

class ClassB;

class ClassA {
public:
    void display(const ClassB& b);
};

class ClassB {
    friend class ClassA;  // 声明ClassA为友元类

private:
    int privateData = 10;

protected:
    int protectedData = 20;
};

void ClassA::display(const ClassB& b) {
    std::cout << "Private Data: " << b.privateData << std::endl;
    std::cout << "Protected Data: " << b.protectedData << std::endl;
}

在销毁派生类对象时，先调用基类的析构函数，再调用派生类的析构函数

new

new出来的对象仅仅是调用对象的构造函数，new之后要显示的调用delete函数

palcement new的主要用途就是反复使用一块较大的动态分配的内存来构造不同类型的对象或者他们的数组。placement new构造起来的对象或其数组，要显示的调用他们的析构函数来销毁，千万不要使用delete。

static修饰的对象时，只有在程序结束时才会调用析构函数，位于main函数中定义的对象之后

友元

友元的关键字为 friend
友元的三种实现

1. 类做友元
2. 成员函数做友元
3. 全局函数做友元

• friend修饰别的类

  • 友元类可以声明在类中任意位置。friend class 类名

  • 声明友元类之后，友元类中的所有成员函数都是该类的友元函数，能够访问该类的所有成员。

• friend修饰成员函数

  • 友元成员函数声明语法：friend 函数返回值类型 类名::函数名();

  • 注意定义的先后，建议在前面进行声明，后面进行函数的同一定义，防止出现问题。

• friend修饰类外定义的函数

  • 将类外部的普通函数作为类的友元函数，在类中使用friend关键字声明该普通函数就可以实现，友元函数可以在类中任意位置声明。

  • 普通函数作为友元函数的声明形式如下所示： friend 函数返回值类型 友元函数名（形参列表）

链表

链表确实是一种重要的动态数据结构，它在许多情况下非常有用，但您的描述中有几点需要澄清和修正：

1. 动态内存分配： 链表确实根据需要动态地开辟内存空间。每个新元素（通常称为节点）都是在需要时创建的，这使得链表在内存使用方面非常灵活。
2. 插入和删除的灵活性： 链表可以在几乎任何位置轻松地插入或删除节点。由于不需要像数组那样移动元素，这些操作通常很高效，尤其是当你可以直接访问到要操作的节点的前一个节点时。
3. 不支持随机访问： 链表不支持随机访问。数组支持高效的随机访问，即可以直接通过索引在常数时间内访问任何元素。而链表则需要从头开始遍历，直到到达所需的元素，这使得访问特定元素是线性时间的操作。
4. 内存和操作效率：
   • 内存使用：相比于数组，链表的内存使用通常更高，因为每个节点不仅要存储数据，还需要存储至少一个指向列表中下一个节点的指针。在双向链表中，还需要存储指向前一个节点的指针。
   • 操作效率：链表的操作效率依赖于具体操作。对于在链表头部或已知位置插入和删除操作，链表非常高效。然而，对于需要搜索特定元素的操作，链表的效率通常低于数组，因为需要遍历链表元素。
5. 节省内存： 链表不一定能节省内存，特别是当节点包含的数据较小时，额外的指针所需的内存可能会使得链表的总内存占用实际上高于同等数量的数组元素。

运算符重载

在C++中，大多数运算符可以被重载为成员函数或非成员函数（包括友元函数），但并非所有运算符都可以用这三种方式重载。以下是一些关键点和例外：

成员函数和非成员函数

• 成员函数：当一个运算符被重载为成员函数时，它的第一个操作数必须是调用该成员函数的对象本身。这意味着，对于二元运算符，左操作数是对象本身，右操作数是作为参数传递的。
• 非成员函数：这些通常被实现为普通函数或友元函数。友元函数虽然定义在类的外部，但它可以访问类的所有私有和保护成员。

友元函数

• 友元函数：不是类的成员，但有权访问类的私有和保护成员。友元函数通常用于那些需要访问两个不同类对象的私有数据的运算符重载。

特殊运算符重载

• 赋值运算符（=）：只能作为成员函数重载。这是因为赋值运算符需要改变对象自身的状态，且左侧操作数必须是类类型的对象。
• 下标运算符（[]）、函数调用运算符（()）和箭头运算符（->）：也只能作为成员函数重载。
• 递增（++）和递减（--）运算符：可以作为成员函数或非成员函数重载，但通常作为成员函数重载，以便可以直接修改对象的状态。

示例

举个例子，考虑一个简单的类Vector，我们可以重载加法运算符+：

class Vector {
public:
    int x, y;

    // 成员函数重载
    Vector operator+(const Vector& other) {
        return {x + other.x, y + other.y};
    }

    // 友元函数重载
    friend Vector operator+(const Vector& lhs, const Vector& rhs) {
        return {lhs.x + rhs.x, lhs.y + rhs.y};
    }
};

在这个例子中，加法运算符可以作为成员函数或非成员友元函数重载。选择哪种方式取决于具体需求，例如，如果需要访问两个不同对象的私有成员，则可能需要使用友元函数。

结论

虽然很多运算符可以以不同方式重载，但并非所有运算符都可以通过所有三种方式（成员、非成员、友元）重载。选择合适的重载方式取决于特定的需求和设计目标。

实践实例

vector使用

下面是一些vector的用法示例：

**创建和初始化vector**：

#include <vector>
#include <iostream>

int main() {
    // 创建一个空的vector
    std::vector<int> numbers;

    // 创建一个具有初始值的vector
    std::vector<int> numbers = {1, 2, 3, 4, 5};

    // 使用push_back()逐个添加元素
    std::vector<int> numbers;
    numbers.push_back(1);
    numbers.push_back(2);
    numbers.push_back(3);

    // 使用指定大小和初始值创建vector
    std::vector<int> numbers(5, 0);  // 包含5个初始值为0的元素

    return 0;
}

访问和修改vector中的元素：

#include <vector>
#include <iostream>

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};

    // 通过下标访问元素
    std::cout << numbers[0] << std::endl;  // 输出：1

    // 使用at()函数访问元素（提供边界检查）
    std::cout << numbers.at(2) << std::endl;  // 输出：3

    // 修改元素的值
    numbers[3] = 10;

    return 0;
}

获取vector的大小和迭代访问：

#include <vector>
#include <iostream>

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};

    // 获取vector的大小
    std::cout << "Size: " << numbers.size() << std::endl;

    // 使用迭代器遍历vector
    for (std::vector<int>::iterator it = numbers.begin(); it != numbers.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // 使用范围-based for循环遍历vector（C++11及以上版本）
    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

插入和删除元素：

#include <vector>
#include <iostream>

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};

    // 在指定位置插入元素
    numbers.insert(numbers.begin() + 2, 10);  // 在索引为2的位置插入10

    // 在末尾添加元素
    numbers.push_back(6);

    // 删除指定位置的元素
    numbers.erase(numbers.begin() + 1);  // 删除索引为1的元素

    // 删除末尾的元素
    numbers.pop_back();

    return 0;
}

输出

#include<iostream>
#include<string>
#include<string.h>
#include<vector>
using namespace std;

int main()
{

        std::vector<int> numbers = { 1, 2, 3, 4, 5 };

        // 在指定位置插入元素
        numbers.insert(numbers.begin() + 2, 10);  // 在索引为2的位置插入10

        // 在末尾添加元素
        numbers.push_back(6);

        // 删除指定位置的元素
        numbers.erase(numbers.begin() + 1);  // 删除索引为1的元素

        // 删除末尾的元素
        numbers.pop_back();
        for (int num : numbers) {
            std::cout << num << " ";
        }
        std::cout << std::endl;

        return 0;
}

公倍数以及公约数

#include <iostream>

// 求最大公约数
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

// 求最小公倍数
int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}

重载格式

在C++中，运算符重载是一种允许为已有的运算符提供用户定义的实现的语言特性。这使得开发者可以对自定义数据类型使用标准运算符。下面提供了一些常见运算符的重载格式，包括成员函数和非成员函数（包括友元函数）的重载方式。

1. 加法运算符（+）

成员函数形式：

class MyClass {
public:
    MyClass operator+(const MyClass& rhs) const {
        // 返回一个新对象，是当前对象和rhs的和
        return MyClass(/* 构造逻辑 */);
    }
};

非成员（友元）函数形式：

class MyClass {
public:
    friend MyClass operator+(const MyClass& lhs, const MyClass& rhs) {
        // 返回lhs和rhs的和
        return MyClass(/* 构造逻辑 */);
    }
};

2. 赋值运算符（=）

成员函数形式（只能是成员函数）：

class MyClass {
public:
    MyClass& operator=(const MyClass& rhs) {
        // 赋值逻辑
        return *this;  // 返回当前对象的引用
    }
};

3. 下标运算符（[]）

成员函数形式（只能是成员函数）：

class MyClass {
public:
    ElementType& operator[](int index) {
        // 返回对应索引的元素的引用
        return elements[index];
    }
};

4. 递增运算符（++）

前缀递增：

class MyClass {
public:
    MyClass& operator++() {
        // 递增逻辑
        return *this;
    }
};

后缀递增：

class MyClass {
public:
    MyClass operator++(int) {
        MyClass temp = *this;
        // 递增逻辑
        return temp;
    }
};

5. 输出运算符（<<）常用于输出流重载

非成员（友元）函数形式：

class MyClass {
public:
    friend std::ostream& operator<<(std::ostream& os, const MyClass& obj) {
        // 输出obj的信息到os
        return os;
    }
};

6. 比较运算符（==）

成员函数形式：

class MyClass {
public:
    bool operator==(const MyClass& rhs) const {
        // 返回比较结果
        return /* 比较逻辑 */;
    }
};

非成员（友元）函数形式：

class MyClass {
public:
    friend bool operator==(const MyClass& lhs, const MyClass& rhs) {
        // 返回比较结果
        return /* 比较逻辑 */;
    }
};

这些示例展示了如何重载常见运算符。在实际使用中，选择成员函数还是友元函数形式，通常取决于是否需要访问私有成员，以及是否希望第一个操作数是类类型的对象。总的来说，运算符重载应该谨慎使用，以保持代码的直观和易于理解。

问题

为什么选择 int 作为参数？（后置++）

1. 语法规定：C++语言规范定义了后缀递增运算符的重载必须使用一个int类型的参数。这个参数的存在是为了语法上的需要，以便编译器能够区分后缀递增（operator++(int)）和前缀递增（operator++()）。
2. 占位符用途：这个int参数实际上是一个占位符，它不需要被赋予任何实际的值。在调用后缀递增时，通常传递的是一个字面值0，但这个值在实际的运算符实现中通常是被忽略的。

为什么MyClass&是&？

在C++中，使用引用返回类型（例如 MyClass&）在运算符重载和其他方法中是一种常见的做法，尤其是在赋值运算符和前缀递增/递减运算符中。这样做有几个重要的原因和优势：

1. 避免不必要的对象复制

当函数返回类型是一个对象而不是引用时，C++标准通常要求返回值被复制或移动到调用方的变量中。如果返回类型是一个引用，这种复制可以被避免。对于包含大量数据或复杂资源管理的类来说，避免这种复制是提高性能的关键。

2. 允许链式调用

返回对象的引用允许方法调用可以被链式连接起来。这是因为返回的引用指向调用对象本身，所以可以继续在同一个表达式中对其进行操作。例如：

myObject.Increment().SetSomething(5).DoAnotherThing();

在这个示例中，Increment、SetSomething 和 DoAnotherThing 都可能返回 MyClass&，允许连续调用。

3. 保持操作符的预期行为

对于某些操作符，如赋值 (=)、前缀递增 (++) 和前缀递减 (--)，按照惯例和预期，这些操作应该修改原始对象，并返回修改后的对象的引用。这样，操作的结果可以直接用于其他操作，模仿了内置类型的行为。例如：

++(++myObject);

在这个表达式中，第一个 ++ 操作修改了 myObject 并返回了它的引用，第二个 ++ 立即作用于同一个对象。

4. 实现符合直觉的语义

通过返回引用，你确保了操作符或方法的行为符合使用者的直觉。例如，赋值运算符通常预期能直接在赋值后使用对象，如在表达式或条件中：

if ((a = b) == c) {
    // do something
}

在这里，a = b 赋值并测试与 c 是否相等，这种行为是通过返回 a 的引用来实现的。

总结

使用 MyClass& 作为返回类型提供了性能优势，允许链式调用，保持了操作符的预期行为，并实现了符合直觉的语义。这些都是在设计类接口时考虑使用引用作为返回类型的重要因素。

抽象类and接口

以下是一个简单的抽象类示例：

class Shape {
public:
    virtual void draw() const = 0;  // 纯虚函数
    virtual double area() const = 0;  // 纯虚函数
};

class Circle : public Shape {
private:
    double radius;
public:
    Circle(double r) : radius(r) {}
    void draw() const override {
        std::cout << "Drawing a circle." << std::endl;
    }
    double area() const override {
        return 3.14159 * radius * radius;
    }
};

类的引用重写

在C++中，如果类A公有地继承自类B，那么类B的指针或引用可以指向类A的对象，但反过来不行。这是因为类B只是类A的一部分，而类A包含了类B的所有特性以及额外的特性。让我们通过一个例子来更清楚地解释这一点。

示例说明

假设我们有一个基类 Base 和一个从 Base 公有继承的派生类 Derived：

class Base {
public:
    void baseMethod() {
        std::cout << "Base method" << std::endl;
    }
};

class Derived : public Base {
public:
    void derivedMethod() {
        std::cout << "Derived method" << std::endl;
    }
};

在这种情况下，我们可以使用 Derived 类的对象来初始化 Base 类的引用或指针，因为每个 Derived 对象都是一个 Base 对象。这是多态的基础，允许 Base 类型的引用或指针调用在 Derived 类中重写的方法。

Derived derivedObj;
Base &baseRef = derivedObj;  // 正确：Derived 对象可以被看作是 Base 对象
baseRef.baseMethod();        // 调用 Base 的方法

然而，反过来不行：

Base baseObj;
Derived &derivedRef = baseObj;  // 错误：不能将 Base 对象的引用转换为 Derived 引用
derivedRef.derivedMethod();     // 这行代码是无效的，因为上一行已经是编译错误

这里的错误发生是因为 baseObj 只是一个 Base 类型的对象，它可能没有 Derived 类中定义的额外成员和方法。尝试将一个 Base 类型的对象的引用转换为 Derived 类型的引用是不安全的，因为 Derived 可能有更多的数据成员或方法，这在 Base 对象中并不存在。

结论

因此，公有继承允许基类的指针或引用指向派生类的对象，但不能使用基类对象来初始化派生类的引用。这种类型的引用或指针转换是单向的，只能从派生类到基类，而不是反过来。这是面向对象设计中的一个重要安全特性，它保护了程序的类型安全性。

algorithm头文件

#include <algorithm> 是C++标准库中的一个头文件，它提供了大量的函数模板，用于处理各种算法操作，包括排序、搜索、合并、替换、旋转、反转等。以下是一些常用的函数和它们的用途：

• 排序：

  • sort(first, last)：对范围内的元素进行排序。
  • stable_sort(first, last)：对范围内的元素进行稳定排序。

• 搜索：

  • find(first, last, value)：在范围内查找特定值的第一个出现位置。

  • binary_search(first, last, value)：在已排序的范围内执行二分查找。

• 合并：

  • merge(first1, last1, first2, last2, result)：合并两个已排序的范围到一个新的范围。

• 替换：

  • replace(first, last, old_value, new_value)：将范围内的所有旧值替换为新值。

• 旋转：

  • rotate(first, middle, last)：将范围内的元素旋转，使得中间元素成为新的第一个元素。

• 反转：

  • reverse(first, last)：反转范围内元素的顺序。

补充：

result.back()是result的末尾

result.pop_back();移除最后一位

stoi(result);转换为int型（老pwn了）

result.substr(7)将提取从指定位置开始到字符串末尾的所有字符

result.substr(7,5)从指定位置开始读取5个字符

在使用 <algorithm> 头文件中的函数时，对类型的要求主要涉及以下几个方面：

1. 迭代器要求：
   • 大多数算法函数需要至少是输入迭代器（Input Iterator）的迭代器类型。这意味着你可以使用这些函数来处理任何支持输入迭代器的容器，如std::vector、std::list、std::deque、std::array等，以及普通数组。
   • 某些算法可能需要更高级的迭代器类型，如前向迭代器（Forward Iterator）、双向迭代器（Bidirectional Iterator）或随机访问迭代器（Random Access Iterator）。例如，sort() 函数通常需要随机访问迭代器。
2. 等等（还有很多的要求主要涉及自定义类在此不过多赘述

algorithm 头文件是C++标准库中的一个重要组成部分，它提供了大量的算法，用于处理和操作容器（如数组、std::vector、std::list、std::set、std::map 等）中的元素。以下是一些 algorithm 头文件中常用函数的使用示例：

std::sort：对容器中的元素进行排序。

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
   std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
   std::sort(v.begin(), v.end()); // 对整个向量进行排序

   for (int i : v) {
       std::cout << i << ' ';
   }
   std::cout << std::endl;

   return 0;
}

std::find：在容器中查找特定元素。

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
   std::vector<int> v = {1, 2, 3, 4, 5};
   int target = 3;
   auto it = std::find(v.begin(), v.end(), target); // 查找元素3

   if (it != v.end()) {
       std::cout << "Element found at position: " << (it - v.begin()) << std::endl;
   } else {
       std::cout << "Element not found" << std::endl;
   }

   return 0;
}

std::reverse：反转容器中的元素顺序。

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
   std::vector<int> v = {1, 2, 3, 4, 5};
   std::reverse(v.begin(), v.end()); // 反转整个向量

   for (int i : v) {
       std::cout << i << ' ';
   }
   std::cout << std::endl;

   return 0;
}

std::max_element 和 std::min_element：找到容器中的最大和最小元素。

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
   std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
   auto max_it = std::max_element(v.begin(), v.end()); // 找到最大元素
   auto min_it = std::min_element(v.begin(), v.end()); // 找到最小元素

   std::cout << "Max element: " << *max_it << std::endl;
   std::cout << "Min element: " << *min_it << std::endl;

   return 0;
}

这些只是 algorithm 头文件中提供的众多算法的一小部分。使用这些算法可以大大简化对容器中元素的操作，提高代码的效率和可读性。

链表

C++单链表的操作
2017-12-25


 // 单链表.cpp: 定义控制台应用程序的入口点。
 //Author:kgvito 
 //Date: 2017.12.25
 
 
 #include "stdafx.h"
 #include<iostream>
 using namespace std;
 
 typedef int DataType;
 #define Node ElemType
 #define ERROR NULL
 
 //构建一个节点类
 class Node                          
 {
 public:
     int data;     //数据域
     Node * next;  //指针域
 };
 
 //构建一个单链表类
 class LinkList                      
 {
 public:
     LinkList();                      //构建一个单链表;
     ~LinkList();                  //销毁一个单链表;
     void CreateLinkList(int n);   //创建一个单链表
     void TravalLinkList();        //遍历线性表
     int GetLength();              //获取线性表长度
     bool IsEmpty();               //判断单链表是否为空
     ElemType * Find(DataType data); //查找节点
     void InsertElemAtEnd(DataType data);            //在尾部插入指定的元素
     void InsertElemAtIndex(DataType data,int n);    //在指定位置插入指定元素
     void InsertElemAtHead(DataType data);           //在头部插入指定元素
     void DeleteElemAtEnd();       //在尾部删除元素
     void DeleteAll();             //删除所有数据
     void DeleteElemAtPoint(DataType data);     //删除指定的数据
     void DeleteElemAtHead();      //在头部删除节点
 private:
     ElemType * head;              //头结点
 };
 
 //初始化单链表
 LinkList::LinkList()                  
 {
     head = new ElemType;            
     head->data = 0;               //将头结点的数据域定义为0
     head->next = NULL;            //头结点的下一个定义为NULL
 }     
 
 //销毁单链表
 LinkList::~LinkList()
 {
     delete head;                 //删除头结点
 } 
 
 //创建一个单链表
 void LinkList::CreateLinkList(int n)
 {
     ElemType *pnew, *ptemp;
     ptemp = head;
     if (n < 0) {       //当输入的值有误时，处理异常
         cout << "输入的节点个数有误" << endl;
         exit(EXIT_FAILURE);
     }
     for (int i = 0; i < n;i++) {        //将值一个一个插入单链表中
         pnew = new ElemType;
         cout << "请输入第" << i + 1 << "个值: " ;
         cin >> pnew->data;
         pnew->next = NULL;          //新节点的下一个地址为NULL
         ptemp->next = pnew;         //当前结点的下一个地址设为新节点
         ptemp = pnew;               //将当前结点设为新节点
     }
 }
 
 //遍历单链表
 void LinkList::TravalLinkList()
 {
     if (head == NULL || head->next ==NULL) {
         cout << "链表为空表" << endl;
     }
     ElemType *p = head;                 //另指针指向头结点
     while (p->next != NULL)        //当指针的下一个地址不为空时，循环输出p的数据域
     {
         p = p->next;               //p指向p的下一个地址
         cout << p->data << " ";
     }
 }
 
 //获取单链表的长度
 int LinkList::GetLength()
 {
     int count = 0;                  //定义count计数
     ElemType *p = head->next;           //定义p指向头结点
     while (p != NULL)                //当指针的下一个地址不为空时，count+1
     {
         count++;                  
         p = p->next;                //p指向p的下一个地址
     }
     return count;                   //返回count的数据
 }
 
 //判断单链表是否为空
 bool LinkList::IsEmpty()
 {
     if (head->next == NULL) {                 
         return true;
     }
     return false;
 }
 
 //查找节点
 ElemType * LinkList::Find(DataType data)
 {
     ElemType * p = head;
     if (p == NULL) {                           //当为空表时，报异常
         cout << "此链表为空链表" << endl;
         return ERROR;
     }
     else
     {
         while (p->next != NULL)               //循环每一个节点
         {
             if (p->data == data) {
                 return p;                     //返回指针域
             }
             p = p->next;
         }
         return NULL;                           //未查询到结果
     }
 }
 
 //在尾部插入指定的元素
 void LinkList::InsertElemAtEnd(DataType data)
 {
     ElemType * newNode = new ElemType;    //定义一个Node结点指针newNode
     newNode->next = NULL;         //定义newNode的数据域和指针域
     newNode->data = data;
     ElemType * p = head;              //定义指针p指向头结点
     if (head == NULL) {           //当头结点为空时，设置newNode为头结点
         head = newNode;
     }
     else                          //循环知道最后一个节点，将newNode放置在最后
     {
         while (p->next != NULL)
         {
             p = p->next;
         }
         p->next = newNode;
     }
 }
 
 //在指定位置插入指定元素
 void LinkList::InsertElemAtIndex(DataType data,int n)
 {
     if (n<1 || n>GetLength())                   //输入有误报异常
         cout << "输入的值错误" << endl;
     else
     {
         ElemType * ptemp = new ElemType;        //创建一个新的节点
         ptemp->data = data;                     //定义数据域
         ElemType * p = head;                    //创建一个指针指向头结点
         int i = 1;
         while (n > i)                           //遍历到指定的位置
         {
             p = p->next;
             i++;
         }
         ptemp->next = p->next;                 //将新节点插入到指定位置
         p->next = ptemp;
     }
 }
 
 //在头部插入指定元素
 void LinkList::InsertElemAtHead(DataType data)
 {
     ElemType * newNode = new ElemType;    //定义一个Node结点指针newNode
     newNode->data = data;
     ElemType * p = head;              //定义指针p指向头结点
     if (head == NULL) {           //当头结点为空时，设置newNode为头结点
         head = newNode;
     }
     newNode->next = p->next;          //将新节点插入到指定位置
     p->next = newNode;
 }
 
 //在尾部删除元素
 void LinkList::DeleteElemAtEnd()
 {
     ElemType * p = head;          //创建一个指针指向头结点
     ElemType * ptemp = NULL;      //创建一个占位节点
     if (p->next == NULL) {        //判断链表是否为空
         cout << "单链表空" << endl;
     }
     else
     {
         while (p->next != NULL)   //循环到尾部的前一个
         {
             ptemp = p;            //将ptemp指向尾部的前一个节点
             p = p->next;          //p指向最后一个节点
         }
         delete p;                //删除尾部节点
         p = NULL;
         ptemp->next = NULL;
     }
 }
 
 //删除所有数据
 void LinkList::DeleteAll()
 {
     ElemType * p = head->next;
     ElemType * ptemp = new ElemType;
     while (p != NULL)                    //在头结点的下一个节点逐个删除节点
     {
         ptemp = p;
         p = p->next;
         head->next = p;
         ptemp->next = NULL;
         delete ptemp;
     }
     head->next = NULL;                 //头结点的下一个节点指向NULL
 }
 
 //删除指定的数据
 void LinkList::DeleteElemAtPoint(DataType data)
 {
     ElemType * ptemp = Find(data);    //查找到指定数据的节点位置
     if (ptemp == head->next) {        //判断是不是头结点的下一个节点，如果是就从头部删了它
         DeleteElemAtHead();
     }
     else
     {
         ElemType * p = head;          //p指向头结点
         while (p->next != ptemp)      //p循环到指定位置的前一个节点
         {
             p = p->next;
         }
         p->next = ptemp->next;         //删除指定位置的节点
         delete ptemp;
         ptemp = NULL;               
     }
 
 }
 
 //在头部删除节点
 void LinkList::DeleteElemAtHead()
 {
     ElemType * p = head;
     if (p == NULL || p->next == NULL) {   //判断是否为空表，报异常
         cout << "该链表为空表" << endl;
     }
     else
     {
         ElemType * ptemp = NULL;      //创建一个占位节点
         p = p->next;
         ptemp = p->next;              //将头结点的下下个节点指向占位节点
         delete p;                     //删除头结点的下一个节点
         p = NULL;
         head->next = ptemp;           //头结点的指针更换
     }
 }
 
 //测试函数
 int main()
 {
     LinkList l;
     int i;
     cout << "1.创建单链表   2.遍历单链表   3.获取单链表的长度   4.判断单链表是否为空   5.获取节点\n";
     cout << "6.在尾部插入指定元素   7.在指定位置插入指定元素   8.在头部插入指定元素\n";
     cout<<"9.在尾部删除元素   10.删除所有元素   11.删除指定元素   12.在头部删除元素   0.退出" << endl;
     do
     {
         cout << "请输入要执行的操作: ";
         cin >> i;
         switch (i)
         {
         case 1:
             int n;
             cout << "请输入单链表的长度: ";
             cin >> n;
             l.CreateLinkList(n);
             break;
         case 2:
             l.TravalLinkList();
             break;
         case 3:
             cout << "该单链表的长度为" << l.GetLength() << endl;
             break;
         case 4:
             if (l.IsEmpty() == 1)
                 cout << "该单链表是空表" << endl;
             else
             {
                 cout << "该单链表不是空表" << endl;
             }
             break;
         case 5:
             DataType data;
             cout << "请输入要获取节点的值: ";
             cin >> data;
             cout << "该节点的值为" << l.Find(data)->data << endl;
             break;
         case 6:
             DataType endData;
             cout << "请输入要在尾部插入的值: ";
             cin >> endData;
             l.InsertElemAtEnd(endData);
             break;
         case 7:
             DataType pointData;
             int index;
             cout << "请输入要插入的数据: ";
             cin >> pointData;
             cout << "请输入要插入数据的位置: ";
             cin >> index;
             l.InsertElemAtIndex(pointData, index);
             break;
         case 8:
             DataType headData;
             cout << "请输入要在头部插入的值: ";
             cin >> headData;
             l.InsertElemAtHead(headData);
             break;
         case 9:
             l.DeleteElemAtEnd();
             break;
         case 10:
             l.DeleteAll();
             break;
         case 11:
             DataType pointDeleteData;
             cout << "请输入要删除的数据: ";
             cin >> pointDeleteData;
             l.DeleteElemAtPoint(pointDeleteData);
             break;
         case 12:
             l.DeleteElemAtHead();
             break;
         default:
             break;
         }
     }while (i != 0);
 
     system("pause");
     return 0;
 }

模板

在C++中，模板是一种强大的特性，它允许你编写与类型无关的代码。模板可以用于函数（函数模板）和类（类模板）。下面是一些函数模板和类模板的示例。

函数模板示例

#include <iostream>

// 函数模板，用于交换两个值
template <typename T>
void swapValues(T& a, T& b) {
    T temp = a;
    a = b;
    b = temp;
}

int main() {
    int a = 5, b = 10;
    std::cout << "Before swap: a = " << a << ", b = " << b << std::endl;
    swapValues(a, b);
    std::cout << "After swap: a = " << a << ", b = " << b << std::endl;

    double x = 3.14, y = 6.28;
    std::cout << "Before swap: x = " << x << ", y = " << y << std::endl;
    swapValues(x, y);
    std::cout << "After swap: x = " << x << ", y = " << y << std::endl;

    return 0;
}

在这个示例中，swapValues 是一个函数模板，它可以用来交换任何类型的两个值。

类模板示例

#include <iostream>
#include <vector>
#include <algorithm>

// 类模板，用于存储和打印元素
template <typename T>
class Printer {
private:
    std::vector<T> elements;

public:
    void addElement(const T& element) {
        elements.push_back(element);
    }

    void printElements() {
        for (const auto& element : elements) {
            std::cout << element << " ";
        }
        std::cout << std::endl;
    }
};

int main() {
    Printer<int> intPrinter;
    intPrinter.addElement(1);
    intPrinter.addElement(2);
    intPrinter.addElement(3);
    intPrinter.printElements();

    Printer<std::string> stringPrinter;
    stringPrinter.addElement("Hello");
    stringPrinter.addElement("World");
    stringPrinter.printElements();

    return 0;
}

在这个示例中，Printer 是一个类模板，它可以用来存储和打印任何类型的元素。

模板特化示例

#include <iostream>

// 通用函数模板
template <typename T>
T max(T a, T b) {
    std::cout << "General template" << std::endl;
    return (a > b) ? a : b;
}

// 特化函数模板，用于比较 const char* 类型
template <>
const char* max(const char* a, const char* b) {
    std::cout << "Specialized template" << std::endl;
    return (std::strcmp(a, b) > 0) ? a : b;
}

int main() {
    int a = 5, b = 10;
    std::cout << "Max of " << a << " and " << b << " is " << max(a, b) << std::endl;

    const char* x = "apple";
    const char* y = "banana";
    std::cout << "Max of " << x << " and " << y << " is " << max(x, y) << std::endl;

    return 0;
}

在这个示例中，我们为 max 函数模板提供了一个特化版本，专门用于比较 const char* 类型的字符串。

这些示例展示了C++模板的基本用法，包括函数模板、类模板和模板特化。模板是C++中实现泛型编程的关键特性，它允许你编写高度可重用的代码。