以下是实现带头结点的单链表 LinkList 的代码：

template <class ElemType>
struct Node{
    ElemType data;
    Node<ElemType> *next;
};

template <class ElemType>
class LinkList{
public:
    LinkList() {
        first = new Node<ElemType>;
        first->next = nullptr;
    }
    LinkList(ElemType a[], int n);
    ~LinkList();
    int len();
    ElemType getElem(int i);
    int locate(ElemType x);
    void insert(int i, ElemType x);
    ElemType deleteElem(int i);
    void dispList();

private:
    Node<ElemType> *first;
};

template <class ElemType>
LinkList<ElemType>::LinkList(ElemType a[], int n) {
    first = new Node<ElemType>;
    first->next = nullptr;

    for (int i = n - 1; i >= 0; i--) {
        Node<ElemType> *newNode = new Node<ElemType>;
        newNode->data = a[i];
        newNode->next = first->next;
        first->next = newNode;
    }
}

template <class ElemType>
LinkList<ElemType>::~LinkList() {
    Node<ElemType> *p, *q;
    
    p = first;
    
    while (p != nullptr) {
        q = p;
        p = p->next;
        delete q;
   }
}

template <class ElemType>
int LinkList<ElemType>::len() {
   int count = 0;

   Node<ElemType> *p = first->next;

   while (p != nullptr) {
       count++;
       p = p->next;
   }

   return count;
}

template <class ElemType>
ElemTyple LinkList<ElemType>::getElem(int i) {
    if (i < 1 || i > len()) {
        throw "索引越界";
    }

    Node<ElemType> *p = first->next;
    
    int count = 1;

    while (count < i) {
        p = p->next;
        count++;
   }

   return p->data;
}

template <class ElemType>
int LinkList<ElemType>::locate(ElemType x) {
   int index = 1;

   Node<ElemType> *p = first->next;

   while (p != nullptr && p->data != x) {
       p = p->next;
       index++;
   }

   if (p == nullptr) {
       return -1; // 没找到
   } else {
       return index;
   }
}

template <class ElemType>
void LinkList<ElemType>::insert(int i, ElemType x) {
    if (i < 1 || i > len() + 1) {
        throw "插入位置非法";
    }

    Node<ElemType> *p = first;

    int count = 0;

    while (count < i - 1) { // 找到插入位置的前一个结点
        p = p->next;
        count++;
    }

    Node<ElemType> *newNode = new Node<ElemType>;
   
    newNode->data = x;
    
    newNode->next = p->next;
    
    p->next = newNode; 
}

template <class ElemType>
ElemTyple LinkList<ElemType>::deleteElem(int i) {
     if (i < 1 || i > len()) {
         throw "删除位置非法";
     }

     Node<ElemType> *p = first;

     int count = 0;

     while (count < i - 1) { // 找到待删除结点的前一个结点
         p = p->next;
         count++;
     }

     Node<ElemType> *q = p->next; // 待删除的结点
     
     ElemType x = q->data; // 保存待删除结点的数据

     p->next = q->next; // 将待删除结点从链表中摘下来
    
     delete q; // 释放内存

     return x;
}

template <class ElemType>
void LinkList<ElemType>::dispList() {
    Node<ElemType> *p = first->next;

    while (p != nullptr) {
        cout << p->data << " ";
        p = p->next;
    }

    cout << endl;
}

然后使用以下代码进行验证：

#include <iostream>
using namespace std;

int main() {
    int r[10] = { 4, 2, 6, 8, 12, 10, 14, 16, 19, 18 };
    LinkList<int> L(r, 10);
    
    cout << "执行插入操作前数据为：" << endl;
    L.dispList();
    
    L.insert(6, 11); 
    
    cout << "执行插入操作后数据为：" << endl;
    L.dispList(); 
    
    cout << "值为16的元素位置为:";
    cout << L.locate(16) << endl; 
    
    cout << "执行删除第7个元素操作，删除前数据为：" << endl;
    
    L.dispList(); 
     
   L.deleteElem(7); 
   
    cout << "删除后数据为：" << endl;
    
    L.dispList(); 
    
    return 0;
}

这段代码将创建一个包含初始元素的链表，并进行插入、查找和删除操作，最后输出结果。


内容由零声教学AI助手提供，问题来源于学员提问