声明：仅供留档查阅，仅用作起到提示引导性作用，仅用作学习交流，切勿直接照搬

代码主体

以下是一个简单的C++实现，用于维护单链表：

来自bing ai

#include <iostream>
using namespace std;

template <typename DataType>
struct Node
{
    DataType data;        // 数据域
    Node<DataType>* next; // 指针域
};

template <typename DataType>
class LinkList
{
public:
    LinkList();                    // 无参构造函数，建立只有头结点的空链表
    LinkList(DataType a[], int n); // 有参构造函数，建立有n个元素的单链表
    ~LinkList();                   // 析构函数
    int Length();                  // 求单链表的长度
    int Empety();
    DataType Get(int i);            // 按位查找。查找第i个结点的元素值
    int Locate(DataType x);         // 按值查找。查找值为x的元素序号
    void Insert(int i, DataType x); // 插入操作，第i个位置插入值为x的结点
    DataType Delete(int i);         // 删除操作，删除第i个结点
    void PrintList();               // 遍历操作，按序号依次输出各元素
private:
    Node<DataType>* first; // 单链表的头指针
};

template <typename DataType>
LinkList<DataType>::LinkList()
{
    first = new Node<DataType>; // 生成头结点
    first->next = nullptr;      // 头结点的指针域置空
}

template <typename DataType>
int LinkList<DataType>::Empety()
{
    if (first->next == nullptr)
        return 1;
    else
        return 0;
}

template <typename DataType>
void LinkList<DataType>::PrintList()
{
    Node<DataType>* p = first->next; // 工作指针p初始化
    while (p != nullptr)
    {
        cout << p->data << "\t";
        p = p->next; // 工作指针p后移，注意不能写作p++
    }
}

template <typename DataType>
int LinkList<DataType>::Length()
{
    Node<DataType>* p = first->next; // 工作指针p初始化为开始接点
    int count = 0;                   // 累加器count初始化
    while (p != nullptr)
    {
        p = p->next;
        count++;
    }
    return count; // 注意count的初始化和返回值之间的关系
}

template <typename DataType>
DataType LinkList<DataType>::Get(int i)
{
    Node<DataType>* p = first->next; // 工作指针p初始化
    int count = 1;                   // 累加器count初始化
    while (p != nullptr && count < i)
    {
        p = p->next; // 工作指针p后移
        count++;
    }
    if (p == nullptr)
        throw "位置";
    else
        return p->data;
}

template <typename DataType>
int LinkList<DataType>::Locate(DataType x)
{
    Node<DataType>* p = first->next; // 工作指针p初始化
    int count = 1;                   // 累加器count初始化
    while (p != nullptr)
    {
        if (p->data == x)
            return count; // 查找成功，结束函数并返回序号
        p = p->next;
        count++;
    }
    return 0; // 退出循环表明查找失败
}

template <typename DataType>
void LinkList<DataType>::Insert(int i, DataType x)
{
    Node<DataType>* p = first, * s = nullptr; // 工作指针p初始化
    int count = 0;
    while (p != nullptr && count < i - 1) // 查找第i – 1个结点
    {
        p = p->next; // 工作指针p后移
        count++;
    }
    if (p == nullptr)
        throw "位置"; // 没有找到第i – 1个结点
    else
    {
        s = new Node<DataType>;
        s->data = x; // 申请结点s，数据域为x
        s->next = p->next;
        p->next = s; // 将结点s插入到结点p之后
    }
}

template <typename DataType>
LinkList<DataType>::LinkList(DataType a[], int n)
{
    first = new Node<DataType>;              // 生成头结点
    Node<DataType>* r = first, * s = nullptr; // 尾指针初始化
    for (int i = 0; i < n; i++)
    {
        s = new Node<DataType>;
        s->data = a[i];
        r->next = s;
        r = s; // 将结点s插入到终端结点之后
    }
    r->next = nullptr; // 单链表建立完毕，将终端结点的指针域置空
}

template <typename DataType>
DataType LinkList<DataType>::Delete(int i)
{
    DataType x;
    Node<DataType>* p = first, * q = nullptr; // 工作指针p指向头结点
    int count = 0;
    while (p != nullptr && count < i - 1) // 查找第i-1个结点
    {
        p = p->next;
        count++;
    }
    if (p == nullptr || p->next == nullptr) // 结点p不存在或p的后继结点不存在
        throw "位置";
    else
    {
        q = p->next;
        x = q->data;       // 暂存被删结点
        p->next = q->next; // 摘链
        delete q;
        return x;
    }
}

template <class DataType>
LinkList<DataType>::~LinkList()
{
    Node<DataType>* q = NULL;
    while (first != NULL) // 释放单链表的每一个结点的存储空间
    {
        q = first;           // 暂存被释放结点
        first = first->next; // first指向被释放结点的下一个结点
        delete q;
    }
}

int main()
{
    int maxsize;
    cout << "请输入你要创建数组的大小" << endl;
    cin >> maxsize;
    int* a = new int[maxsize];
    for (int i = 0; i < maxsize; i++)
    {
        a[i] = i+1;
        cout << " " << endl;
    }
    cout << "已创建一个最大长度"<<maxsize<<"的随机数链表" << endl;
    LinkList<int> L{ a, maxsize };
    cout << "执行遍历链表" << endl;
    L.PrintList();
    cout << endl;
    cout << "请输入一个最大长度内的数字查找元素" << endl;
    int i;
    cin >> i;
    cout << L.Locate(i) << endl;
    cout << "请插入一个新数字元素，请依次输入位置和数据" << endl;
    int j, k;
    cin >> j >> k;
    L.Insert(j, k);
    cout << "执行遍历链表" << endl;
    L.PrintList();
    cout << endl;
    cout << "请删除一个新数字元素，请输入位置" << endl;
    int l;
    cin >> l;
    cout << "删除的元素位置是" << l << "数据是" << L.Get(l) << endl;
    L.Delete(l);
    cout << "执行遍历链表" << endl;
    L.PrintList();
    cout << endl;
    return 0;
}

这个程序首先创建了一个空的单链表，然后向其中添加了一些节点。然后，它遍历了整个列表，查找了一个元素，插入了一个新的元素，删除了一个元素，然后再次遍历了整个列表。希望这个示例能对你有所帮助！

两个有序单链表合并为一个有序单链表

当然，这是一个包含main函数的完整程序，它创建了两个有序链表，并将它们合并为一个有序链表：

#include <iostream>

// 定义链表节点
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

// 合并两个有序链表
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if (l1 == NULL) {
        return l2;
    }
    if (l2 == NULL) {
        return l1;
    }
    if (l1->val < l2->val) {
        l1->next = mergeTwoLists(l1->next, l2);
        return l1;
    } else {
        l2->next = mergeTwoLists(l1, l2->next);
        return l2;
    }
}

int main() {
    // 创建第一个有序链表：1 -> 3 -> 5
    ListNode *l1 = new ListNode(1);
    l1->next = new ListNode(3);
    l1->next->next = new ListNode(5);

    // 创建第二个有序链表：2 -> 4 -> 6
    ListNode *l2 = new ListNode(2);
    l2->next = new ListNode(4);
    l2->next->next = new ListNode(6);

    // 合并两个有序链表
    ListNode *merged = mergeTwoLists(l1, l2);

    // 打印合并后的链表
    while (merged != NULL) {
        std::cout << merged->val << " ";
        merged = merged->next;
    }

    return 0;
}

这个程序首先创建了两个有序链表l1和l2，然后调用mergeTwoLists函数将它们合并为一个新的有序链表。最后，它遍历新的链表并打印出每个节点的值。

请注意，这个程序没有释放分配给链表节点的内存。在实际使用中，你应该在不再需要节点时释放它们的内存，以防止内存泄漏。此外，这个程序假设输入的链表已经排序。如果输入的链表没有排序，你需要先对它们进行排序。

双链表

双链表是一种更复杂的线性数据结构，它的每个节点都有两个链接，一个指向前一个节点，另一个指向后一个节点。以下是一个使用C++实现的双链表的基本设计：

#include <iostream>

// 定义双链表节点
struct ListNode {
    int val;
    ListNode *prev;
    ListNode *next;
    ListNode(int x) : val(x), prev(NULL), next(NULL) {}
};

// 添加节点到双链表的末尾
void addNode(ListNode* &head, int val) {
    ListNode* newNode = new ListNode(val);
    if (head == NULL) {
        head = newNode;
    } else {
        ListNode* temp = head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
        newNode->prev = temp;
    }
}

// 打印双链表
void printList(ListNode* head) {
    ListNode* temp = head;
    while (temp != NULL) {
        std::cout << temp->val << " ";
        temp = temp->next;
    }
    std::cout << std::endl;
}

int main() {
    // 创建一个空的双链表
    ListNode* head = NULL;

    // 添加节点到双链表
    addNode(head, 1);
    addNode(head, 2);
    addNode(head, 3);

    // 打印双链表
    printList(head);

    return 0;
}

这个程序首先定义了一个双链表节点的结构，然后定义了两个函数：addNode用于向双链表的末尾添加新的节点，printList用于打印双链表的所有节点。在main函数中，它创建了一个空的双链表，然后添加了几个节点，并打印出了这个双链表。

请注意，这个程序没有释放分配给链表节点的内存。在实际使用中，你应该在不再需要节点时释放它们的内存，以防止内存泄漏。此外，你可能还需要实现其他操作，如删除节点、查找节点等。这取决于你的具体需求。如果你需要帮助实现这些操作，请随时向我询问！

循环链表

循环链表是一种特殊的链表，其中最后一个元素指向链表的第一个元素。这种类型的数据结构可以用于实现需要循环或重复的算法。以下是一个使用C++实现的循环链表的基本设计：

#include <iostream>

// 定义链表节点
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

// 添加节点到循环链表的末尾
void addNode(ListNode* &head, int val) {
    ListNode* newNode = new ListNode(val);
    if (head == NULL) {
        head = newNode;
        newNode->next = head;
    } else {
        ListNode* temp = head;
        while (temp->next != head) {
            temp = temp->next;
        }
        temp->next = newNode;
        newNode->next = head;
    }
}

// 打印循环链表
void printList(ListNode* head) {
    if (head == NULL) return;
    ListNode* temp = head;
    do {
        std::cout << temp->val << " ";
        temp = temp->next;
    } while (temp != head);
    std::cout << std::endl;
}

int main() {
    // 创建一个空的循环链表
    ListNode* head = NULL;

    // 添加节点到循环链表
    addNode(head, 1);
    addNode(head, 2);
    addNode(head, 3);

    // 打印循环链表
    printList(head);

    return 0;
}