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

#define STARS   "**************************"
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE 0
#define OVERFLOW -2
#define MAXSIZE 20
#define QUIT 13
typedef int Status;

typedef struct{
    int num;
    char name[20];
    int score;
}ElemType;
typedef struct Lnode{
    ElemType data;
    struct Lnode *next;
}Lnode,*LinkList;

int menu(void);
char *s_gets(char *st,int n);
Status InitList_L(LinkList &L);         //初始化链表 
void CreateList_H(LinkList &L,int n);   //头插法
void CreateList_R(LinkList &L,int n);   //尾插法 
int ListEmpty(LinkList &L);             //判断链表是否为空
Status DestroyList_L(LinkList &L);      //链表的销毁 
Status ClearList(LinkList &L);          //清空链表 
int ListLength_L(LinkList &L);          //求单链表的长度 
Status GetElem_L(LinkList &L,int i,ElemType &e);    //获取线性表L中的某个数据元素的内容，通过变量e返回。
Lnode *LocateElem_L(LinkList L,ElemType e);     //查找数据元素为e的元素返回地址
int LocateElem_L1(LinkList L,ElemType e);   //按照元素查找位置 
Status ListInsert_L(LinkList &L,int i,ElemType e);      //插入元素 
Status ListDelete_L(LinkList &L,int i,ElemType &e);     //删除元素 

int main(void)
{
    int code;
    LinkList H;
    LinkList R;
    while((code = menu())!=QUIT)
    {
        switch(code)
        {
            case 1:
                if(InitList_L(H)&&InitList_L(R))
                    printf("Init...OK!\n");
                else
                    printf("Init faillure...Please check the memory size...\n");      
                break;
            case 2:
                int n;
                printf("Use header inserts, and enter the number of elements you want to insert and their contents:\n");
                scanf("%d",&n);
                CreateList_H(H,n);
                printf("...Insert the complete...Ok!\n");
                break;
            case 3:
                printf("Use the tail plug method, and enter the number of elements you want to insert and their contents:\n");
                scanf("%d",&n);
                CreateList_R(R,n);
                printf("...Insert the complete...Ok!\n");
                break;
            case 4:
                if(ListEmpty(H))
                    printf("Lnode...H IS NOT Empty!\n"); 
                else
                    printf("Lnode...H is empty!\n");
                if(ListEmpty(R))
                    printf("Lnode...R IS NOT Empty!\n"); 
                else
                    printf("Lnode...R is empty!\n");
                break; 
            case 5:
                if(DestroyList_L(H)&&DestroyList_L(R))
                    printf("..Destroy all OK!\n");
                break;
            case 6:
                if(ClearList(H)&&ClearList(R))
                    printf("..Clear List OK!\n");
                break;
            case 7:
                printf("H Length %d,R Length %d.\n",ListLength_L(H),ListLength_L(R));
                break;
            case 8:
                printf("请输入你要查询的元素位置：\n");
                int i;
                scanf("%d",&i);
                ElemType e;
                if(GetElem_L(R,i,e))
                    {
                        fputs(e.name,stdout);
                        printf(" your number is %d\nYur score are %d\n",e.num,e.score);
                    }
                else
                    printf("%d is not exist",i);
                break;
            case 9:
                if(LocateElem_L(R,e))
                    printf("Find!\n");
                else
                    printf("Sorry!\n");
                break;
            case 10:
                ElemType a;
                i = LocateElem_L1(R,a);
                if(i)
                    printf("Thise is %d elem.\n",i);
                else
                    printf("Sorry!");
                break;
            case 11:
                printf("输入插入的位置以及元素（该处以尾插法的线性表为例子）:\n");
                scanf("%d",&i);
                ElemType c;
                printf("Please print the number\n");
                scanf("%d",&c.num);
                printf("please print the name\n"); 
                while(getchar()!='\n')
                    continue;
                s_gets(c.name,20);
                printf("please print score:\n");
                scanf("%d",&c.score);
                if(ListInsert_L(R,i,e))
                    printf("...Insert OK!\n");
                else
                    printf("ERROR\n");
                break;
            case 12:
                printf("输入删除元素的位置（该处以尾插法的线性表为例子）：\n");
                scanf("%d",&i);
                ElemType temp;
                if(ListDelete_L(R,i,temp))
                    printf("...Delete ok!\n");
                else
                    printf("ERROR!!!\n");
                break;
            case 13:
                printf("Bye!\n");
                break;

        }
    }
    return 0;
}

Status InitList_L(LinkList &L)
{
    L = (LinkList)malloc(sizeof(Lnode));
    L ->next = NULL;
    return OK;
 } 
void CreateList_H(LinkList &L,int n)
{
    Lnode *p;
    L = (LinkList)malloc(sizeof(Lnode));
    L -> next = NULL;
    for(int i = n; i> 0;--i)
    {
        p = (LinkList)malloc(sizeof(Lnode));
        printf("Please print the number\n");
        scanf("%d",&p->data.num);
        printf("please print the name\n"); 
        while(getchar()!='\n')
            continue;
        s_gets(p->data.name,20);
        printf("please print score:\n");
        scanf("%d",&p->data.score);
        p -> next = L -> next;
        L -> next = p;
    }
}
void CreateList_R(LinkList &L,int n)
{
    Lnode *p,*r;
    L = (LinkList)malloc(sizeof(Lnode));
    L -> next = NULL;
    r = L;          //尾指针r指向头结点
    for(int i=0;i<n;++i)
    {
        p = (LinkList)malloc(sizeof(Lnode));
        printf("Please print the number\n");
        scanf("%d",&p->data.num);
        printf("please print the name\n"); 
        while(getchar()!='\n')
            continue;
        s_gets(p->data.name,20);
        printf("please print score:\n");
        scanf("%d",&p->data.score);
        p -> next = NULL;
        r -> next = p;
        r = p;
    } 
} 
int ListEmpty(LinkList &L)
{
    if(L -> next==NULL)
        return 0;
    else
        return 1;
} 
Status DestroyList_L(LinkList &L)
{
    Lnode *p;
    while(L)
    {
        p = L;
        L = L->next;
        free(p);
    } 
    return OK;
} 
Status ClearList(LinkList &L)
{
    Lnode *p,*q;
    p =L->next; 
    while(p)
    {
        q = p->next;
        free(p);
        p = q;  
    } 
    L->next =NULL;
    return OK;
} 
int ListLength_L(LinkList &L)
{
    LinkList p;
    p = L->next;
    int i =0;
    while(p)
    {
        i++;
        p = p->next;
    } 
    return i;
}
Status GetElem_L(LinkList &L,int i,ElemType &e)
{
    LinkList p;
    p = L->next;
    int j=1;
    while(p&&j<i)
    {
        p = p->next;
        ++j;
    } 
    if(!p||j>i)
        return ERROR;   //第i个元素不存在
    e = p->data;
    return OK; 
} 
Lnode *LocateElem_L(LinkList L,ElemType e)
{
    LinkList p;
    p = L->next;
    printf("Please print the number\n");
    scanf("%d",&e.num);
    printf("please print the name\n"); 
    while(getchar()!='\n')
        continue;
    s_gets(e.name,20);
    printf("please print score:\n");
    scanf("%d",&e.score);
    while(p&&p->data.num!=e.num)
        p = p->next;
    return p; 
} 
int LocateElem_L1(LinkList L,ElemType e)
{
    LinkList p;
    p = L->next;
    int j = 1;
    printf("Please print the number\n");
    scanf("%d",&e.num);
    while(p && p->data.num!=e.num)
    {
        p = p->next;
        j++;
    }
    if(p)
        return j;
    else
        return 0;
}
Status ListInsert_L(LinkList &L,int i,ElemType e)
{
        LinkList p,s;
        s = (LinkList)malloc(sizeof(Lnode));
        p = L;
        int j = 0;
        while(p&&j<i-1)
        {
            p = p->next;
            ++j;
        }
        if(!p||j>i-1)
        {
            return ERROR;
        }
        s->next = p->next;
        p->next = s;
        return OK;
}
Status ListDelete_L(LinkList &L,int i,ElemType &e)
{
    LinkList p,q;
    int j=0;
    while(p->next&&j<i-1)
    {
        p = p->next;
        ++j;
     } 
    if(!(p->next)||j>i-1)
        return ERROR;
    q = p->next;
    p->next=q->next;
    e = q->data;
    free(q);
    return OK;
} 

int menu(void)
{
    int code;
    printf("\n%s%s\n",STARS,STARS);
    printf("请选择操作：\n1.单链表的初始化\n"
    "2.头插法创建链表(自带初始化)\n"
    "3.尾插法创建链表(自带初始化)\n"
    "4.判断链表是否为空\n"
    "5.单链表的销毁（销毁后的链表不存在）\n"
    "6.清空链表（清空后的链表只剩下头指针和头结点）\n"
    "7.求单链表的长度 \n"
    "8.查找第i个位置上的元素\n"
    "9.根据元素内容查找元素是否存在（这里是根据number）\n"
    "10:按值查找元素，返回元素位置\n"
    "11:单链表的插入\n"
    "12:单链表的删除\n"
    "13:退出\n");
    printf("\n%s%s\n",STARS,STARS);
    int status2;
    while((status2 = scanf("%d",&code))!=1||(code<1||code>13))
    {
        if(status2!=1)
            scanf("%*s");         //处理非整数输入
        printf("Enter an integer from 1 to 13 or 'q',please.\n");

    }
    return code;
}
char *s_gets(char *st,int n)
{
    char *ret_val;
    char *find;

    ret_val = fgets(st,n,stdin);
    if(ret_val)
    {
        find = strchr(st,'\n');
        if(find)
            *find = '\0';
        else
            while(getchar()!='\n')
                continue;
    }
    return ret_val;
}