#include <iostream.h>
#include <string.h>
#include<stdlib.h>




struct Student
{
    char number[10];
    char name[20];
    char sex[2];
    int age;
    char place[20];
};

typedef Student EType;



struct DoubleNode
{
    EType data;
    DoubleNode *plink;
    DoubleNode *nlink;
};

typedef double HeadEType;
struct HeadNode
{
    HeadEType    Hdata;
    DoubleNode   * first;
};
typedef HeadNode  *DoubleChainList;

void CreatDoubleChainList(DoubleChainList &L)
{//构造一个空链表
    L=new  HeadNode ;
    L->first=NULL;
    //L->Hdata=199
}


void OutPutDoubleChainList(DoubleChainList &L)
{//逐个输出链表L中的数据元素
    DoubleNode *current;
    current=L->first;
    cout<<"L->first--->";
    while(current)
    {
        current=current->nlink;
        cout<<"link"<<"<--->";
    }
    cout<<"NULL"<<endl;
   
    current=L->first;
    cout<<"                  ";
    while(current)
    {
        cout<<current--->data.place<<"  ";
        current=current--->nlink;
    }
    cout<<endl;
   
    current=L->first;
    cout<<"                 ";
    while(current)
    {
        cout<<current->data.place<<"  ";
        current=current->nlink;
    }
    cout<<endl;
   
}



int LengthDoubleChainList(DoubleChainList  &L)
{//返回链表L中数据元素节点数
    DoubleNode  *current;
    current=L->first;
    int length=0;
    while(current)
    {
        length++;
        current=current->nlink;
    }
    return length;
}



void EraseDoubleChainList(DoubleChainList &L)
{//删除链表L中全部数据，并释放节点空间
    DoubleNode * current ;
    current =L->first;
    while(L->first)
    {
        current =current->nlink;
        delete L->first;
        L->first =current;
    }
}



bool GetElemChainList(DoubleChainList &L,int i,EType &result)
{//L中第i个元素取至x中，如不存在返回false，找到返回true
    if(i<1) return false;
    DoubleNode *current=L->first;
    int index=1;
    while(index<i && current)
    {
        current=current->nlink;
        index++;
    }
    if(current)
    {
        result=current->data;
        return true ;
    }
    return false ;
    //i 值太大  不存在第i个节点
}



DoubleNode * SearchDoubleChainList(DoubleChainList  &L,EType  &x)
{//查找x，如果找到返回x所在的地址，如果未找到返回NULL
    DoubleNode *current =L->first;
    while(current && current->data.age!=x.age)
        current=current->nlink;
    if(current)
        return current;
    return NULL ;
}



bool InsertDoubleChainList(DoubleChainList  &L,int k,EType &x)
{//在链表中第k个数据元素忠厚中插入元素x运算，如果不存在第k个元素或线性表空间已满，则返回出错状态
    if(k<0)
        return false;
    int index=1;
    DoubleNode  *current=L->first;
    while (index<k && current)
    {//找第k个节点
        index++;
        current=current->nlink;
    }
    if(k>0 && !current)
        return false ;
    DoubleNode *q=new DoubleNode;
    q->data=x;
    if(k)
    {//插入在current之后
        q->nlink=current->nlink;
        q->plink=current;
        DoubleNode *p=current->nlink;
        if(p)
            p->plink=q;
        current->nlink=q;
    }
   
   
    else
    {//作为第一个元素节点插入
        q->nlink=L->first;
        q->plink=NULL;
        DoubleNode * p=L->first;
        if(p)
            p->plink=q;
        L->first=q;
    }
    return true;
}

bool EraseDoubleChainList(DoubleChainList &L,int k)
{//在双向链L中删除第k个数据元素，如果不存在第k个元素返回出错状态
    if(k<1 || !L->first)
        return false;
    DoubleNode  *current=L->first;
    DoubleNode *p;
    if(k==1)
    {
        p=current->nlink;
        if(p)
            p->plink=NULL;
        L->first=p;
    }
    else
    {
        DoubleNode  *q=L->first;
        for(int index=1;index< k && q;index++)
            q=q->nlink;
        if(!q)
            return false;
        current=q;
        q=current->plink;
        p=current->nlink;
        q->nlink=p;
        if(p)
            p->plink=q;
    }
    delete current  ;   //释放被删除节点current的空间
        return true;
}






//下面是双向链表的主程序
int main ()
{
    DoubleNode  *p,*q;
    DoubleChainList  L;
    EType    x,result;
    int  k,choice;
    int  start,end;
   
    //构造链表
    CreatDoubleChainList(L);
        
        
        //链表初始化
        
    char  number[][20]={"  ","1209030101","1209030102","1209030103","1209030104","1209030105","1209030106","1209030107","1209030108"};
    char  name[][20]={"  ","我是胖子1","嗯给","我是新手叫祭狼","夜半轻叩寡妇门","醉扭貔","夜未央","恩给是傻叉1","柳叶飞絮"};
    char  sex[][4]={"  ","男","女","女","男","男","男","女","男"};
    char  place[][10]={"  ","守望之海","战争学院","征服之海","诺克萨斯","怒瑞玛","德玛西亚","黑色玫瑰","艾欧尼亚"};
   
    for(int i;i<10;i++)
    {
        p=new DoubleNode;
        strcpy(p->data.number,number[10-i]);
        strcpy(p->data.name,name[10-i]);
        strcpy(p->data.sex,sex[10-i]);
        p->data.age=19;
        strcpy(p->data.place,place[10-i]);
        p->nlink=L->first;
        if(i!=1)
        {
            q=L->first;
            q->plink=p;
        }
        L->first=p;
    }
    q=L->first;
    q->plink=NULL;
   
   
   
    while(true)
    {
        cout<<endl;
        cout<<"******************************双向链表存储的运算******************************"<<endl;
        cout<<"*   1---输出双向链表中所有的元素                                             *"<<endl;
        cout<<"*   2---计算链表长度                                                         *"<<endl;
        cout<<"*   3---在链表中查找第k个元素                                                *"<<endl;
        cout<<"*   4---在链表中插入新元素到第k个元素后面                                    *"<<endl;
        cout<<"*   5---在链表中删除第k个元素                                                *"<<endl;
        cout<<"*   6---在链表中删除第i到第j个节点                                           *"<<endl;
        cout<<"*   7---删除链表中所有节点                                                   *"<<endl;
        cout<<"*   0---推出                                                                 *"<<endl;
        cout<<"******************************************************************************"<<endl;
        cout<<"请选择处理功能:  ";
        cin>>choice;
        cout<<endl;
        
        
        system("cls");
            switch(choice)
        {
    case 1 :
        {//输出双向链表中的所有元素
            cout<<"***********************输出双向链表中所有元素************************"<<endl;
            cout<<endl;
            OutPutDoubleChainList(L);
            cout<<endl;
            break;
        }
        
        
        
    case 2:
        {//计算链表长度
            cout<<"***********************计算链表长度************************"<<endl<<endl;
            cout<<"此操作前链表状态："<<endl<<endl;
            OutPutDoubleChainList(L);
            cout<<endl;
            cout<<"双向链表长度="<<LengthDoubleChainList(L)<<endl<<endl;
            break;
        }
        
        
    case 3:
        {//查找第k个节点
            cout<<"***********************在链表中查找第k个元素************************"<<endl<<endl;
            cout<<"此操作前链表状态："<<endl<<endl;
            OutPutDoubleChainList(L);
            cout<<endl;
            
            
            cout<<"输入查找第k个记录的K值： ";
            cin>>k;
            cout<<endl;
            if(GetElemChainList(L,k,result))
            {
                cout<<"第"<<k<<"个元素的值"<<endl<<endl;
                cout<<"学号: "<<result.number<<endl;
                cout<<"姓名: "<<result.name<<endl;
                cout<<"性别: "<<result.sex<<endl;
                cout<<"年龄: "<<result.age<<endl;
                cout<<"地址: "<<result.place<<endl<<endl;
            }
            else
            {
                cout<<"k值范围不正确!"<<endl<<endl;
                break;
            }
        }
        
    case 4:
        {//在链表中插入新元素到第k个元素后面
            cout<<"***********************在链表中插入新元素到第k个元素后面************************"<<endl<<endl;
            cout<<"此操作前链表状态："<<endl<<endl;
            OutPutDoubleChainList(L);
            cout<<endl;
            
            
            cout<<"输入插入点k值：";
            cin>>k;
            cout<<"输入要插入的数据值x ："<<endl<<endl;
            strcpy(x.number,"1209030109");
            strcpy(x.name,"啊马上把你叫法师");
            strcpy(x.sex,"男");
            x.age=18;
            strcpy(x.place,"扭曲丛林");
            
            cout<<"学号："<<x.number<<endl;
            cout<<"姓名："<<x.name<<endl;
            cout<<"性别："<<x.sex<<endl;
            cout<<"年龄："<<x.age<<endl;
            cout<<"住址："<<x.place<<endl<<endl;
            
            cout<<"插入数据x 到 第"<<k<<"个记录后面的结果："<<endl<<endl;
            if(InsertDoubleChainList(L,k,x))
                OutPutDoubleChainList(L);
            else
                cout<<"K值范围不正确!"<<endl<<endl;
            break;
        }
        
        
        
    case 5:
        {//在链表中删除第k个元素
            cout<<"***********************在链表中删除第k个元素************************"<<endl<<endl;
            cout<<"此操作前链表状态："<<endl<<endl;
            OutPutDoubleChainList(L);
            cout<<endl;
            
            
            cout<<"删除第几个节点";
            cin>>k;
            cout<<"删除第"<<k<<"个节点后的结果: "<<endl<<endl;
            if(EraseDoubleChainList(L,k))
                OutPutDoubleChainList(L);
            else
                cout<<"K值范围不正确!"<<endl<<endl;
            break;
        }
        
        
        
    case 6:
        {//删除第i到第j个节点
            cout<<"***********************删除第i到第j个节点************************"<<endl<<endl;
            cout<<"此操作前链表状态："<<endl<<endl;
            OutPutDoubleChainList(L);
            cout<<endl;
            
            
            cout<<"输人起点i 值：";
            cin>>start;
            cout<<"输人终点j 值：";
            cin>>end;
            cout<<endl<<endl;
            
            int length=LengthDoubleChainList(L);
            cout<<endl<<"删除第"<<start<<"到第"<<end<<"个节点后的结果"<<endl;
            if(L->first && (start>0 && start<=length) && (end>0 && end<=length) && (start<=end))
            {
                k=start;
                for(i=1;i<end-start+1;i++)
                {
                    EraseDoubleChainList(L,k);
                }
                OutPutDoubleChainList(L);
            }
            else
                cout<<"起点或终点值不对！"<<endl;
            break;
        }
        
        
        
    case 7:
        {//删除链表中的所有元素
            cout<<"***********************删除链表中的所有元素************************"<<endl<<endl;
            cout<<"此操作前链表状态："<<endl<<endl;
            OutPutDoubleChainList(L);
            cout<<endl;
            
            
            cout<<"删除整个链表中的节点后的结果："<<endl<<endl;
            EraseDoubleChainList(L);
            OutPutDoubleChainList(L);
            break;
        }
        
        
        
        
        
    case 0:
        {//退出链表操作
            cout<<endl<<"***********************退出链表操作************************"<<endl;
            delete L;
            return 0;
            break;
        }
}
            
            
            system("pause");
            system("cls");
            }
}

表示相当的长