C++

#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个元素单链表:1.头插法建单2.尾差法建单链表
    ~LinkList(); // 析构函数 链表的销毁
    int Length(); // 链表的长度
    DataType Get(int i); // 按位查找 查找第i个节点的元素值
    int Locate(DataType x); // 按值查找 查找值为x的元素序号
    void Insert(int i, DataType x); // 插入操作 第i个位置上插入值位x的结点
    DataType Delete(int i); // 删除操作 删除第i个结点
    void Empty(); // 判断线性表是否为空
    void PrintList(); // 遍历操作,按序号依次输出各元素
private:
    Node<DataType>* head;
};

// 初始化
template <typename DataType>
LinkList<DataType>:: LinkList()
{
    head = new Node<DataType>; // 生成头结点
    head->next = nullptr;
}

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

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

// 链表的长度
template <typename DataType>
int LinkList<DataType>:: Length()
{
    Node<DataType> *p = head->next; //初始化工作指针
    int count = 1;
    while (p != nullptr)
    {
        p = p->next;
        count ++;
    }
    return count;   
}

// 按位查找 
template <typename DataType>
DataType LinkList<DataType>:: Get(int i)
{
    Node<DataType> *p = head->next;
    int count = 1;
    while (p != nullptr && count < i)
    {
        p = p->next;
        count ++;
    }
    if (p == nullptr) throw "查找位置错误";
    else return p;
}

// 按值查找 
template <typename DataType>
int LinkList<DataType>:: Locate(DataType x)
{
    Node<DataType> *p = head->next;
    int count = 1;
    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 = head, *s;
    int count = 0;               //工作指针p应指向头结点
    while (p != NULL && count < i - 1)  //查找第i - 1个结点
    {
        p = p->next;                   //工作指针p后移
        count++;
    }
    if (p == nullptr) throw "插入位置错误";
    else
    {
        s = new Node<DataType>;
        s->data = x;
        s->next = p->next;
        p->next = s;
    }
}

// 删除操作 
template <typename DataType>
DataType LinkList<DataType>:: Delete(int i)
{
    DataType x;
    Node<DataType> *p, *q;
    int count = 0; 
    p = head;               //注意工作指针p要指向头结点
    while (p != NULL && count < i - 1)  //查找第i-1个结点
    {
        p = p->next;
        count++;
    }
    if (p == nullptr || p->next == nullptr) throw "删除位置错误";
    else
    {
        q = p->next;
        x = q->data;
        p->next = q->next;
        delete q;
        return x;
    }
}

// 判断线性表是否为空
template <typename DataType>
void LinkList<DataType>:: Empty()
{
    if (head->next == nullptr) cout << "为空" << endl;
    else cout << "不为空" << endl;
}

// 遍历操作
template <typename DataType>
void LinkList<DataType>:: PrintList()
{
    Node<DataType> *p = head->next;
    while (p != nullptr)
    {
        cout << p->data<<"\t";
        p = p->next;
    }
    cout << endl;
}


int main()
{
    int r[5]={1, 2, 3, 4, 5};
    LinkList<int> L(r, 5);
    //判空操作
    L.Empty(); 
    cout<<"执行插入操作前数据为："<<endl;
    // 打印遍历操作
    L.PrintList( ); //显示链表中所有元素
    try
    {
        L.Insert(2, 3);
    }
    catch (char *s)
    {
        cout<<s<<endl;
    }
    cout<<"执行插入操作后数据为："<<endl;
    L.PrintList( );     //显示链表中所有元素
    cout<<"值为5的元素位置为:";
    // 按值查找操作
    cout<<L.Locate(5)<<endl; //查找元素5，并返回在单链表中位置
    cout<<"执行删除操作前数据为："<<endl;     
    L.PrintList( );  //显示链表中所有元素
    // 删除操作
    try
    {
        L.Delete(1); //删除元素4
    }
    catch (char *s)
    {
        cout<<s<<endl;
    }
    cout<<"执行删除操作后数据为："<<endl;     
    L.PrintList( );  //显示链表中所有元素

    return 0;
}