#include<stdio.h>
#include<malloc.h>

typedef int DataType;        /*宏定义DataType的类型为整型*/
typedef struct Node{        /*宏定义单链表的结点结构*/
    DataType data;            /*data域用于存放数据元素*/
    struct Node *next;        /*next域用于存放指向其后继的指针*/
}LNode, *PNode, *LinkList;    /*LinkList为头指针*/

/*
  函数名：Menu
  函数作用：书写菜单
  入口参数：无
  出口参数：无
  函数编写人：yyk
*/
void Menu(void)
{
    printf("\t\t\t\t单链表\n");
    printf("\t***************************************************\n");
    printf("\t本程序可用于单链表的各种操作——包含初始化单链表，求表长，插入，删除，查找和销毁单链表。\n");
    printf("\t输入数字，按下回车键，即可运行对应操作，若初次运行，请先运行操作1\n");
    printf("\t\t（1）输入数组（注意应当是整数）\n");
    printf("\t\t（2）输出单链表长度\n");
    printf("\t\t（3）插入数据（输入形式为：插入位置,插入数字数值）\n");
    printf("\t\t（4）删除数据（输入形式为：删除位置）\n");
    printf("\t\t（5）查找元素（输入待查找的数据元素即可）\n");
    printf("\t\t（6）销毁单链表。\n");
    printf("\t\t（7）退出系统。\n");
    printf("**************************************************************************\n");
}

/*
  函数名：InitList
  函数作用：初始化单链表
  入口参数：LinkList *h
  出口参数：0 1
*/
int InitList(LinkList *h)
{
    *h = (LinkList)malloc(sizeof(LNode));    /*生成头结点*/
    if(!h)
    {
        printf("初始化链表错误！\n");

        return 0;
    }
    (*h)->next = NULL;

    return 1;
}

/*
  函数名：ListLength
  函数作用：求表长
  入口参数：LinkList h
  出口参数：total
*/
int ListLength(LinkList h)
{
    int total = 0;
    PNode p = h->next;

    while(p)
    {
        total++;
        p = p->next;
    }

    return total;
}

/*
  函数名：ListEmpty
  函数作用：判空表
  入口参数：LinkList h
  出口参数：0 1
*/
int ListEmpty(LinkList h)
{
    if(h->next==NULL)
    {
        return 1;
    }
    return 0;
}

/*
  函数名：ListInsert
  函数作用：插入
  入口参数：LinkList h, int pos, DataType x
  出口参数：0 1
*/
int ListInsert(LinkList h, int pos, DataType x)
{
    PNode p = h,q;
    int i = 0;

    while(p && i<pos-1)
    {
        p = p->next;
        i++;
    }
    if(!p || i>pos-1)
    {
        printf("插入位置不合法！\n");

        return 0;
    }
    q = (PNode)malloc(sizeof(LNode));
    if(!q)
    {
        printf("无法生成新结点\n");

        return 0;
    }
    q->data = x;
    q->next = p->next;
    p->next = q;

    return 1;
}

/*
  函数名：ListDelete
  函数作用：删除
  入口参数：LinkList h, int pos, DataType *item
  出口参数：0 1
*/
int ListDelete(LinkList h, int pos, DataType *item)
{
    PNode p = h,q;
    int i = 0;

    while(p->next && i<pos-1)
    {
        p = p->next;
        i++;
    }
    if(!p->next || i>pos-1)
    {
        printf("删除位置不合法！\n");

        return 0;
    }
    q = p->next;
    p->next = q->next;
    *item = q->data;
    free(q);
    return 1;
}

/*
  函数名：Find
  函数作用：查找
  入口参数：LinkList h, DataType item
  出口参数：p
*/
PNode Find(LinkList h, DataType item)
{
    int i, flag = 0;

    PNode p = h->next;
    for(i=1; p; i++)
    {
        p = p->next;
        if(p->data == item)
        {
            printf("该元素的位置是：%d", i);
            flag = 1;
            break;
        }
    }
    if(flag==0)
    {
        printf("数组中没有此元素！");
    }

    return p;
}

/*
  函数名：DestroyList
  函数作用：销毁单链表
  入口参数：LinkList h  
  出口参数：0 1
*/
void DestroyList(LinkList h)
{
    PNode p = h->next;
    while(h)
    {
        p = h;
        h = h->next;
        free(p);
    }
}

/*
  函数名：TraverseList
  函数作用：遍历单链表
  入口参数：LinkList h
  出口参数：0 1
*/
void TraverseList(LinkList h)
{
    PNode p = h->next;
    while(p)
    {
        printf("%5d", p->data);
        p = p->next;
    }
    printf("\n");
}

/*
  函数名：Work
  函数作用：识别运行指令
  入口参数：输入值
  出口参数：无
  函数编写人：yyk
*/
void Work(int choice, LNode *h)
{
    int num = 0, flag = 0, pos = 0;
    PNode tail, p;

    switch(choice)
    {
    case 1:
        flag = InitList(&h);

        if(flag==0)
        {
            break;
        }
        tail = h;
        printf("\n请输入数组：\n");
        scanf("%d", &num);

        for(; num!=-1; )
        {
            p = (LNode*)malloc(sizeof(LNode));
            p->data = num;
            p->next = NULL;
            tail->next = p;
            tail = p;
            scanf("%d", &num);
        }

        break;
    case 2:
        flag = ListEmpty(h);
        if(flag==1)
        {
            printf("链表为空！");
            break;
        }
        
        num = ListLength(h);
        printf("表长为：%d", num);

        break;
    case 3:
        flag = ListEmpty(h);
        if(flag==1)
        {
            printf("链表为空！");
            break;
        }
        printf("插入数据（输入形式为：插入位置,插入数字数值）\n");
        scanf("%d,%d", &pos, &num);
        flag = ListInsert(h, pos, num);
        if(flag == 0)
        {
            break;
        }
        else
        {
            printf("插入成功！");
        }
        break;
    case 4:
        flag = ListEmpty(h);
        if(flag==1)
        {
            printf("链表为空！");
            break;
        }
        printf("删除数据（输入形式为：删除位置）\n");
        scanf("%d", &pos);
        flag = ListDelete(h, pos, &num);
        if(flag == 0)
        {
            break;
        }
        else
        {
            printf("删除成功！删除数据为：%d", num);
        }
        break;
    case 5:
        flag = ListEmpty(h);
        if(flag==1)
        {
            printf("链表为空！");
            break;
        }
        printf("查找元素（输入待查找的数据元素即可）\n");
        scanf("%d", &num);
        Find(h, num);

        break;
    case 6:
        flag = ListEmpty(h);
        if(flag==1)
        {
            printf("链表为空！");
            break;
        }

        DestroyList(h);
        printf("单链表已销毁。\n");
        break;
    case 7:
        break;
    default:
        printf("\n请确认你所输入的数字为有效作用数字：1 2 3 4 5 6 7\n");
        break;
        ;
    }
    TraverseList(h);
}

/*
  函数名：main
  函数作用：主函数
  入口参数：无
  出口参数：0
  函数编写人：yyk
*/
int main(void)
{
    int choice = 0;
    LNode LinkList;

    Menu();
   
    printf("请输入操作指令：（1 2 3 4 5 6 7）:\n");
    scanf("%d", &choice);

    while(choice!=7)
    {
                Work(choice, &LinkList);
        scanf("%d", &choice);
    }
    DestroyList(&LinkList);

    return 0;
}