/*
 双链表的实现
 */
#include <iostream>
using namespace std;
template<typename T>
struct DNode
{
    T data;                     //数据域
    DNode<T> *piror,*next;       //指针域 前驱 后继
};
template<typename T>
class LinkList
{
private:
    DNode<T>* first; //双链表头指针
public:
    LinkList();
    LinkList(T a[],int n);
    ~LinkList();
    int Length();
    T Get(int i);
    int Location(T x);
    void Insert(int i,T x);
    T Delete(int i);
    int Empty();
    void PrintList();
    T Front(int i);
};
template<typename T>
LinkList<T>::LinkList()
{
    first=new DNode<T>;          //生成头节点
    first->next=nullptr;         //头节点的指针域为空
    first->piror=nullptr;
}
template<typename T>
LinkList<T>::LinkList(T a[],int n)  //尾插法
{
    first=new DNode<T>;
    DNode<T>*r=first,*s=nullptr;
    for (int i=0; i<n; i++) {
        s=new DNode<T>;
        s->data=a[i];
        s->piror=r;
        r->next=s;
        r=s;
    }
    r->next=nullptr;
}
template<typename T>
LinkList<T>::~LinkList()
{
    DNode<T>* p=first;
    while (first!=nullptr)    //释放每一个节点的存储空间
    {
        first=first->next;    //first指向被释放节点的下一个节点
        delete p;
        p=first;              //工作指针p后移
    }
}
template<typename T>
int LinkList<T>::Length()
{
    DNode<T> *p=first->next;  //工作指针初始化
    int count=0;
    while (p!=nullptr)
    {
        p=p->next;
        count++;
    }
    return count;
}
template<typename T>
T LinkList<T>::Get(int i)
{
    DNode<T>* p=first->next;  //工作指针初始化
    int count =1;
    while (p!=nullptr&&count<i) {
        p=p->next;
        count++;
    }
    if(p==nullptr)throw "查找位置错误";
    else
        return p->data;
}
template<typename T>
int LinkList<T>::Location(T x)
{
    DNode<T>* p=first->next;
    int count = 1;
    while (p!=nullptr) {
        if(p->data==x)
            return count;
        p=p->next;
        count++;
    }
    return 0;
}
template<typename T>
void LinkList<T>::Insert(int i, T x)
{
    DNode<T>*p=first,*s=nullptr;
    int count = 0;
    while (p!=nullptr&&count<i-1)   //查找第i-1个节点
    {
        p=p->next;
        count++;
    }
    if(p==nullptr)throw "插入位置错误";
    else{
        s=new DNode<T>;
        s->data=x;
        s->piror=p;
        s->next=p->next;
        p->next->piror=s;
        p->next=s;
    }
    
}
template<typename T>
T LinkList<T>::Delete(int i)
{
    T x;
    DNode<T> *p=first;
    int count =0;
    while (p!=nullptr&&count<i) {
        p=p->next;
        count++;
    }
    if(p==nullptr)
        throw "删除位置错误";
    else
    {
        x=p->data;
        p->next->piror=p->piror;
        p->piror->next=p->next;
        return x;
    }
}
template<typename T>
void LinkList<T>::PrintList()
{
    DNode<T>*p=first->next;
    while (p!=nullptr) {
        cout<<p->data<<"\t";
        p=p->next;
    }
    cout<<endl;
}
template<typename T>
int LinkList<T>::Empty()
{
    if(first->next==nullptr)
        return 1;
    else
        return 0;
}
template<typename T>
T LinkList<T>::Front(int i)
{
    DNode<T>*p=first->next;
    int count =1;
    while (p!=nullptr&&count<i)
    {
        p=p->next;
        count++;
    }
    if(p==nullptr)throw "查找位置错误";
    else
        return p->piror->data;
}
int main()
{
    int r[5]= {1,2,3,4,5},i,x;
    LinkList<int> L{r,5};
    cout<<"当前线性表的数据为:";
    L.PrintList();
    try
    {
        L.Insert(2, 8);
        cout<<"插入后的线性表数据:";
        L.PrintList();
    } catch (char* str) {cout<<str<<endl;}
    cout<<"当前链表长度为"<<L.Length()<<endl;
    cout<<"请输入要查找的元素值:";
    cin>>x;
    i=L.Location(x);
    if(i>0)
        cout<<"元素"<<x<<"的位置: "<<i<<endl;
    else
        cout<<"单链表中没有元素"<<x<<endl;
    try {
        cout<<"请输入要删除第几个元素";
        cin>>i;
        x=L.Delete(i);
        cout<<"删除的元素值是"<<x<<",执行删除操作后数据为:";
        L.PrintList();
    } catch (char *str) {
        cout<<str<<endl;
    }
    cout<<"请输出第3个元素的前面的元素："<<endl;
    cout<<L.Front(3)<<endl;
    return 0;
}