#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct Link{
    int base;
    struct Link *next;
}Link; 

void createLink(Link **LN,int A[],int n){//创建链表 
    Link *node,*end,*first;
    *LN =  (Link *)malloc(sizeof(Link));
    first = end =*LN;
    int i= 0 ;
    for(i;i<n;i++){
        node = (Link *)malloc(sizeof(Link));
        node->base=A[i];
        end->next = node;
        end = node;
    } 
    end->next=NULL;
}

void traversal(Link *LN){//遍历链表 
    Link *Node;
    Node =LN->next;
    while(Node->next!=NULL){
        printf("%d\n",Node->base);
        Node=Node->next;
    }
    printf("%d\n",Node->base);
}

int getLength(Link *LN){//获取链表长度 
    int length=0;
    Link *Node;
    Node =LN->next;
    while(Node->next!=NULL){
        length++;
        Node=Node->next;
    }
    length++;
    return length;
}

int insert(Link **LN,int index,int val){//插入元素 
    Link *Node;
    Link *end;
    end = *LN;
    int j=1;
    int length=getLength(*LN);
    if(index>length+1){
        printf("删除位置不合法请重新选择！\n");
    }else if(index==length+1){//插入末尾的情况 
        Node = (Link*)malloc(sizeof(Link));
        Node->base=val;
        Node->next=NULL;
        end = end->next;
        for(j;j<length;j++){
            end=end->next;
        }
        
        end->next=Node;
    
    }else if(index<=length){//插入中间的情况 
        for(j;j<index;j++){
            end=end->next;
        }
        Node = (Link*)malloc(sizeof(Link));
        Node->base=val;
        printf("second\n");
        Link *record;
        record = end->next;
        end->next=Node;
        printf("third\n");
        Node->next=record;
        
    }
} 
void deleteNode(Link **LN,int index){//删除元素 
    Link *end;
    end = *LN;
    int j=1;
    int length=getLength(*LN);
    if(index>length){
        printf("删除位置不合法请重新选择！\n");
    }else if(index==length){//删除末尾的情况 
        for(j;j<length;j++){
            end=end->next;
        }
        printf("second\n");
        end->next=NULL;
        printf("third\n");
    }else if(index<length){//删除中间的情况 
        for(j;j<index;j++){
            end=end->next;
        }
        Link *record;
        record = end->next;
        end->next=record->next;
    }
} 

int main(int argc, char *argv[]) {
    Link L;
    Link *LN;//头指针 
    int i;
    printf("1.向链表中添加元素！\n");
    printf("2.遍历链表!\n");
    printf("3.获得链表长度!\n");
    printf("4.向链表中插入元素!\n");
    printf("5.删除链表中的元素!\n");
    printf("********************************************\n"); 
    while(1){
        printf("请输入要进行的操作！\n");
        scanf("%d",&i);
        switch(i){
            case 5:
                printf("请输入要删除元素的位置！\n");
                int index;
                scanf("%d",&index);
                deleteNode(&LN,index);
                break;
            case 4:{
                printf("请输入想要插入的位置！\n");
                int index,val;
                scanf("%d",&index);
                printf("请输入插入的元素！\n");
                scanf("%d",&val);
                insert(&LN,index,val);
                break;
                } 
            case 3:
                printf("链表的长度为%d\n",getLength(LN));
                break;
            case 2:
                printf("链表中含有的元素：\n");
                traversal(LN);
                break;  
            case 1:
                printf("请输入链表的长度！\n");
                int n;
                scanf("%d",&n);
                int A[n];
                printf("请输入要加入到链表的数据！\n");  
                int j=0;
                for(j;j<n;j++){
                    scanf("%d",&A[j]);
                }
                createLink(&LN,A,n);
                break;

        }
    }
    return 0;
}