#include<stdio.h>
#include<malloc.h> 
#define MAX 100
typedef int DataType; //数据元素的类型
typedef struct{
    DataType data[MAX];
    int len;//线性表中的元素个数 
}seqList; 

typedef struct node{
    DataType data;
    struct node *next;
}LinkList;
LinkList *head; 
//初始化
void initList(){
    head = (LinkList *)malloc(sizeof(LinkList));
    head->next=NULL;
} 
//尾插法
void createListL(){
    LinkList *tail,*p;
    int n,i;
    printf("请输入需要插入的节点个数：");
    scanf("%d",&n);
    tail=head;
    //尾插法
    for(i=0;i<n;i++){
        p=(LinkList *)malloc(sizeof(LinkList));
        scanf("%d",&p->data);
        p->next=NULL; 
        //第一步： 把新结点p放到tail的next
        tail->next = p;
        //第二步：tail往后移动
        tail=tail->next; 
    }   
} 
//头插法
void createListH(){
    int i,n;
    LinkList *p;
    printf("请输入需要插入的节点个数：");
    scanf("%d",&n);
    for(i=0;i<n;i++){   
        p=(LinkList *)malloc(sizeof(LinkList));
        scanf("%d",&p->data);
        //第一步：将head中的next值放到新节点p的next
        p->next = head->next;
        //第二步：将p放到head的next中
        head->next = p; 
    }
} 

//逆置 
LinkList* reverseList(){
    LinkList* p,*q;
    LinkList* head2 = (LinkList *)malloc(sizeof(LinkList));
    head2->next=NULL;
    p=head->next;
    while(p){
        q=p->next;
        p->next = head2->next;
        head2->next = p;
        p=q;
    }
    return head2;
} 

void printList(){
    LinkList* q;
    int j;
    j=1;
    q=head->next;
    while(q!=NULL){
        printf("a%d:%d ",j++,q->data);
        q=q->next;
    }
    printf("\n");
}
//求一个链表的元素个数
int linkListLen(){
    LinkList *p = head->next;
    int count=0;
    while(p){
        count++;
        p=p->next;
    }
    return count;
} 
//根据位置查找元素的值(从1开始计数） 
//查找成功返回1，否则返回0
int getElem( ){
    int n,len;
    LinkList *p=head;
    printf("请输入查找元素的位置：");
    scanf("%d",&n);
    len = linkListLen();
    if(n>len||n<1){
        printf("输入错误\n");
        return 0;
    }
    //输入数据合法
    while(n--){
        p=p->next;
    }
    printf("您要查的数据：%d\n",p->data); 
    return 1; 
}

//在某个位置n上插入一个节点
//插入成功返回1，否则返回0
int insertElem(int n,DataType x){
    LinkList *s,*p=head; 
    int b=0;
    int len = linkListLen();
    if(n>len+1||n<1){
        printf("参数错误\n");
        return 0;
    }
    s = (LinkList *)malloc(sizeof(LinkList));
    s->data = x;
    while(b+1<n){
        p=p->next;
        b++;
    }
    s->next = p->next;
    p->next = s;
    printf("插入成功");
    return 1;
} 
//删除位置n上的一个节点
//删除成功返回1，否则返回0
int delElem(int n) {
    int len = linkListLen();
    int i=0;
    LinkList *p=head,*s;//p移动（s前），s被删除 
    if(n>len||n<1){
        printf("参数错误\n");
        return 0;
    }
    while(p->next!=NULL) {
        if(i+1==n){
            s=p->next;
            p->next= s->next;
            free(s);
            printf("删除成功");
            return 1;
        }
        i++;
        p=p->next;
    }   
}

void menu(){
    printf("-----------单链表的增删改查系统---------\n");
    printf("-----------1.头插法创建单链表---------------\n");
    printf("-----------2.尾插法创建单链表-----------\n");
    printf("-----------3.逆置 ----------------------\n");
    printf("-----------4.求一个链表的元素个数 ------\n");
    printf("-----------5.根据位置查找元素的值 ------\n");
    printf("-----------6.在某个位置n上插入一个节点--\n");
    printf("-----------7.删除位置n上的一个节点------\n");
    printf("请选择功能(1~7),输入0退出系统\n");
}   

int main(){
    int n; //输入的功能数字 
    //调用初始哈
    initList();
    do{
        menu();//菜单
        scanf("%d",&n); 
        switch(n){
            case 1:
                //头插法 
                createListH(); 
                printList();//输出 
                break;
            case 2:
                createListL();
                printList();//输出
                break;
            case 3:
                reverseList();
                printList();//输出
            case 4:
                linkListLen();
                printList();//输出
            case 5:

            DataType x;
            scanf("%d%d",&n,&x);
                insertElem(n,x);
                printList();//输出
            case 6:
                getElem( );
                printList();//输出
            case 7:

            scanf("%d",&n);
                delElem(n );
                printList();//输出
            case 0:
                return 0;
                break;
        }
    }while(1);



    return 0; 
}