#include<iostream>
using namespace std;
#define ERROR 0;
#define OK    1;
 struct Student
 {
     int ID;
     int length;
     Student *next;
 };

Student *InitList()
{
    Student *p;
    p=new Student;
    if(!p) return ERROR;   //判错行，如果没成功生成节点则返回EREEOE。
    p->length=0;      //初始化头结点信息，注重length和next，其他信息弱化，掷空。
    p->ID=NULL;
    p->next=NULL;
    return p;
}

void AddList(Student *head)
{
    int i;      //循环控制变量。
    Student *p,*q;
    q=head;
    for(i=1;i<=5;i++)   //默认生成节点为1,2,3,4,5。   头结点为0节点。
    {
        p=new Student;
        if(!p) cout<<"未成功生成节点"<<endl;
        p->next=NULL;//初始化各节点，弱化length，注重next，其他信息先掷空，等待UpdateList函数更新这些信息。
        p->ID=NULL;
        q->next=p;
        q=p;    //偏移指针。
    }
    head->length+=5;
}

Student *Visit(Student *head,int n)  //返回第n个节点的地址，计数不包括头结点。
{
    if(n<0||n>head->length) cout<<"输入了错误的学生序号"; //验证接收数据的正确性。
    int i;  //循环控制变量。
    Student *p,*q;
    q=head;
    if(n=0) return head;   //若为第0节点，则返回头节点指针。
    for(i=1;i<=n+1;i++)    //i为当前指针所指向的第i个节点。   n为返回指针所指向的节点。
    {
        p=q->next;
        q=p;  //偏移指针。
    }
    return p;
}

void PrintList(Student *head)   //这里是逐个输出整个链表！
{
    Student *p,*r;
    int i,a;  //循环控制变量。
    p=head->next;
    if(p!=NULL)   //保护性代码行，如果为空表，则不执行输出信息。
    {
        for(i=1;i<=head->length;i++)
        {
            r=Visit(head,i);
            a=r->ID;
            cout<<"第"<<i<<"学生ID为:"<<a<<endl;//我们输出的是信息，并不关注链表的长度，所以不再输出length。
        }
    }
    else cout<<"此表为空表，无法再输出信息"<<endl;
}

void UpdateList(Student *head)
{
    int i;  //循环控制变量。
    Student *p;
    int a;
    for(i=1;i<=head->length;i++)   //逐个更新元素数据循环。
    {
        p=Visit(head,i);
        cout<<"第"<<i<<"位学生的ID"<<endl;
        cin>>a;
        p->ID=a;
    }
}

void InsirtList(Student *head,int x)
{
    Student *p,*r;
    r=Visit(head,x);
    p=new Student;
    if(!p) cout<<"插入节点生成失败"<<endl;
    p->next=r->next;
    r->next=p;
    cout<<"新学生的ID为:";
    cin>>p->ID;
    p->length=NULL;   //弱化数据节点的length，掷空即可。
    ++head->length;
}

void GetElem(Student *head,int y)
{
    Student *p;
    p=Visit(head,y);
    cout<<"第"<<y<<"位学生的ID为："<<p->ID<<endl;
}

void FrontElem(Student *head,int u)
{
    if(u<=1) cout<<"小于等于1的节点前驱不合法。"<<endl;
    Student*p;
    p=Visit(head,u-1);
    cout<<"第"<<u<<"个节点的前驱是："<<u-1<<"信息如下"<<endl;
    cout<<p->ID<<endl;

}

void BehindElem(Student *head,int v)
{
    if(v>=head->length) cout<<"大于等于末尾节点的后继不合法。"<<endl;
    Student*p;
    p=Visit(head,v+1);
    cout<<"第"<<v<<"个节点的后继是："<<v+1<<"信息如下"<<endl;
    cout<<p->ID<<endl;
}

void DeleElem(Student *head,int z)
{
    if(z<0||z>head->length)  cout<<"错误的位置"<<endl;   //保护性代码行。你懂得。
    Student *p,*q;
    p=Visit(head,z-1);   //得到所删除元素的前一个节点。这样就不可能得到最后一个节点。
    q=p->next;  //将q指向所删除节点。
    if(q->next!=NULL)    //如果为最后一个节点则不再连接。
    {
        p->next=q->next;//连接所删除节点后的其他节点。
    }
    delete q; //删除这个节点。
    --head->length;  //链表长度减一。
}

void FreeList(Student *head)
{
    Student *p;
    int i;  //循环控制变量。
    for(i=head->length;i<=1;--i)   //从最后逐个删除节点。
    {
        p=Visit(head,i);
        delete p;
    }
    head->length=0;  //只要执行完这个函数，链表长度必定为空。
}

int main()
{
    cout<<"创造头节点... ..."<<endl;
    Student *head;
    head=InitList();
    cout<<"完成创造！"<<endl;

    cout<<"以下是增加节点，我们默认生成5个节点"<<endl;
    AddList(head);
    cout<<"完成增加！"<<endl;

    cout<<"以下是更新5个节点信息："<<endl;
    UpdateList(head);
    cout<<"更新后链表信息为："<<endl;
    PrintList(head);

    cout<<"以下为插入节点操作："<<endl;
    int x;
    cout<<"请输入希望插入在第几个节点后："<<endl;
    cin>>x;
    InsirtList(head,x);
    cout<<"插入后链表信息为："<<endl;
    PrintList(head);

    cout<<"以下是得到节点信息："<<endl;
    int y;
    cout<<"现在链表共有节点："<<head->length<<"个。"<<endl;
    cout<<"请输入希望得到第几个节点:"<<endl;
    cin>>y;
    if(y!=0)
        GetElem(head,y);
    else
        cout<<"输入了错误节点"<<endl;

    cout<<"以下为得到节点前驱："<<endl;
    int u;
    cout<<"希望得到第几个节点的前驱:"<<endl;
    cin>>u;
    FrontElem(head,u);

    cout<<"以下为得到节点后继："<<endl;
    int v;
    cout<<"希望得到第几个节点的后继:"<<endl;
    cin>>v;
    BehindElem(head,v);

    cout<<"以下为删除节点操作："<<endl;
    int z;
    cout<<"请输入希望删除节点位置"<<endl;
    cin>>z;
    DeleElem(head,z);
    cout<<"删除后链表信息为："<<endl;
    PrintList(head);

    cout<<"以下为掷空这个链表操作："<<endl;
    FreeList(head);
    cout<<"掷空后链表为："<<endl;
    PrintList(head);

    return OK;
}

Student *Visit(Student *head,int n)  //返回第n个节点的地址，计数不包括头结点。
{
    if(n<0||n>head->length) cout<<"输入了错误的学生序号"; //验证接收数据的正确性。
    int i;  //循环控制变量。
    Student *p,*q;
    q=head;
    if(n==0) return head;   //若为第0节点，则返回头节点指针。
    for(i=1;i<n+1;i++)    //i为当前指针所指向的第i个节点。   n为返回指针所指向的节点。
    {
        p=q->next;
        q=p;  //偏移指针。
    }
    return p;
}