#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;

typedef struct Lnode {
    int data;
    Lnode *next;
}Lnode,*Linklist;


//初始化链表

bool iniLinklist(Linklist &l)
{
    l=(Lnode *)malloc(sizeof(Lnode));
    if(l == NULL)
        {
            printf("内存不足,创建头节点失败\n\n");
            return false;
        }
    l->next=NULL;
    printf("创建头节点成功\n\n");
    return true;

}


//判断链表是否为空

bool emptyLinklist(Linklist l)
{
    if(l->next==NULL)
        return true;
    return false;
}



//定位
Lnode *Getnodebyi(Linklist l,int i)
{   
    if(i<0)
    return NULL;
    Linklist p;
    p=l;
    int j=0;
    while(p!=NULL && j<i)
        {
            p=p->next;
            j++;
        }
    return p;
}


//按值
bool Getnodebyvalue(Linklist l,int value)
{   
    int j=1;
    Lnode *p=l->next;
    while(p!=NULL && p->data!=value)
        {
            p=p->next;
            j++;
        }
    if(p== NULL)
       
       {
        printf("链表为空\n");
        return false;
       }
    printf("值为%d的节点的位序为%d\n",value,j);
    return true;
    
} 


//前插
bool nodeinsertprior(Lnode *p,int value)
{
    if(p == NULL)
        return false;
    Lnode *s=(Lnode *)malloc(sizeof(Lnode));
    if(s == NULL)
        return false;
    s->next=p->next;
    p->next=s;
    s->data=p->data;
    p->data=value;
    printf("前插法插入节点成功\n\n");
    return true;
}



//后插
bool nodeinsertnext(Lnode *p,int value)
{
    if(p == NULL)
        return false;
    Lnode *s=(Lnode *)malloc(sizeof(Lnode));
    if(s == NULL)
        return false;
    s->data=value;
    s->next=p->next;
    p->next=s;
    printf("后插法插入节点成功\n\n");
    return true;
}



//插入节点

bool insertLinklist(Linklist &l,int i,int value)
{
    if(i<1)
        return false;
    Lnode *p=Getnodebyi(l,i-1);
    printf("1:选择前插法\n");
    printf("2:选择后插法\n");
    int choice= 0;
    scanf("%d",&choice);
    if(choice == 2)
        return nodeinsertnext(p,value);     
    else if(choice == 1)
        return nodeinsertprior(p,value);
} 


//删除节点

bool Linklistdelete(Linklist &l,int i ,int &value)
{
    if (i < 1)
        return false;
    Lnode *p=Getnodebyi(l,i-1);
    if(p == NULL)
        return false;
    if(p->next== NULL)
        return false;
    Linklist q = p->next;
    value=q->data;
    p->next=q->next;
    free(q);
    q=NULL;
    
    return true;
}

bool Linklistlength(Linklist l)
{
    int length =  0;
    Lnode *q = l;
    int i=0;
    while(q->next!=NULL)
    {
        q=q->next;
        length++;
    }
    // for(;q->next!=NULL;i++)
    // {
    //     q=q->next;
    // }
    printf("单链表的长度为%d\n",length);
    return true;
}




void menu()
{
    printf("请选择功能\n");
    printf("1:退出\n");
    printf("2:插入节点\n");
    printf("3:删除节点\n");
    printf("4:按位查找\n");
    printf("5:按值查找\n");
    printf("6:求表的长度\n");
    printf("7:打印出链表\n");
}


int main()
{   
    Linklist l;
    iniLinklist(l);
    int option,i,value=0;
    int j=1;
    Lnode *p=NULL;
    if(emptyLinklist(l))
    {
        printf("单链表目前为空\n\n");
    }

    while(1){
        menu();
        scanf("%d",&option);
        if(option == 1)
        {
            printf("退出\n\n");
            break;
        }
        switch(option)
        {
            case 2:
            
             
                printf("请输入节点位序以及值\n");
                scanf("%d %d",&i,&value);
                insertLinklist(l,i,value);
                break;
             

            case 3:
                
                
                printf("请输入要删除的节点位序\n");
                scanf("%d",&i);
                if(Linklistdelete(l,i,value))
                    {
                        printf("删除节点成功\n\n");
                    }
                else

                    printf("删除节点失败\n\n");
                break;
                
                
            case 4:
             
                printf("请输入节点的位序\n");
                scanf("%d",&i);
                p=Getnodebyi(l,i);
                printf("第%d个节点的值为%d\n\n",i,p->data);
              
                break;
                
            

            case 5:
            
                printf("请输入值来查找位序\n");
                scanf("%d",&value);
                Getnodebyvalue(l,value);
                break;
            

            case 6:
             
             
                Linklistlength(l);
                break;

            case 7:
                while(Getnodebyi(l,j)!=NULL)
                    {   
                        
                        printf("位序为%d的值为%d\n",j,Getnodebyi(l,j)->data);
                        j++;
                    }
                j=1;
                break;
        }
    }
        
    
    

    system("pause");
    return 0;
}