#include <stdio.h>
#include <stdlib.h> //malloc free

// 定义链表的结构体
typedef struct LinkList{
    int item;
    struct LinkList* next;
}LinkList;
LinkList* init(){
    LinkList* node = (LinkList*)malloc(sizeof(LinkList));
    node->item=0;
    node->next=NULL;
}

void print(LinkList* H){
    LinkList* node=H->next;
    if(H->item==0){
        puts("没有元素!");
        return ;
    }
    while(node){
        printf("%d ",node->item);
        node=node->next;
    }
    puts("");

}

int insert(LinkList* H,int idx,int n){
    LinkList* n1,*node=H->next;
    int i=1;
    // 判断插入位置是否合法
    if(idx<=0 || idx>H->item+1)return 0;
    else if(idx==1){
        n1=(LinkList*)malloc(sizeof(LinkList));
        n1->item=n;
        n1->next = H->next;
        H->next = n1;
    }
    else{
        // 找被插入位置的前一个位置
        while(i<idx-1){
            node=node->next;
            i++;
        }
        n1=(LinkList*)malloc(sizeof(LinkList));
        n1->item=n;
        n1->next=node->next;
        node->next=n1;
    }

    H->item++;

    return 1;
}

int del(LinkList* H,int idx){
    LinkList* n1,*node=H->next;
    int i=1;
    // 判断删除位置是否合法
    if(idx<=0 || idx>H->item)return 0;
    else if(idx==1){
        n1 = H->next;
        H->next = n1->next;
        free(n1);
    }
    else{
        while(i<idx-1){
            node=node->next;
            i++;
        }
        n1=node->next;
        node->next=n1->next;
        free(n1);
    }

    H->item--;

    return 1;
}
int main(){
    
    int n;
    // 创建头结点，用头指针指向头结点
    /*
        Head-item:链表的长度
    */
    LinkList* Head=init();

    puts("1.输出链表中元素");
    puts("2.删除元素");
    puts("3.插入元素");
    puts("请选择功能(输入0结束程序):");

    while(scanf("%d",&n),n){
        switch(n){
            case 1:{
                print(Head);
                break;
            }
            case 2:{
                int i;
                puts("输入删除位置");
                scanf("%d",&i);
                if(del(Head,i)){
                    puts("删除成功!");
                    print(Head);
                }
                else{
                    puts("删除失败!请检查删除位置是否合法!");
                }
                break;
            }
            case 3:{
                int i,n;
                puts("输入插入位置和值");
                scanf("%d %d",&i,&n);
                if(insert(Head,i,n)){
                    puts("插入成功!");
                    print(Head);
                }
                else{
                    puts("插入失败！请检查插入位置是否合法!");
                }
                break;
            }
            default:{
                puts("功能尚未开发，敬请期待!");
                break;
            }
        }
        puts("1.输出链表中元素");
        puts("2.删除元素");
        puts("3.插入元素");
        puts("请选择功能(输入0结束程序):");
    }
    return 0;
}
