#include <string.h>
#include <ctype.h>
#include <malloc.h>
#include <limits.h> // INT_MAX等
#include <stdio.h>  // NULL等
#include <stdlib.h> // atoi( ), exit( )
#include <math.h> // floor( ), ceil( ), abs( ), OVERFLOW宏定义，其值为3。
 
// 函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW 3
 
typedef int Status;
typedef int ElemType;
typedef struct LNode
{
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;
 
//单链表的初始化
Status InitList(LinkList &L)
{ // 操作结果：构造一个空的线性表L
    L = (LinkList)malloc(sizeof(LNode));
    if (!L)
        return ERROR;
    L->next = NULL;
    return OK;
}
 
//单链表的销毁
Status DestroyList(LinkList &L)
{ // 初始条件：线性表L已存在。
  // 操作结果：销毁线性表L
    LinkList p, q;
    p = L->next;
    while (p)
    {
        q = p->next;
        free(p);
        p = q;
    }
    free(L);
    L = NULL;
    return OK;
}
 
//单链表的清空
void ClearList(LinkList L) // 不改变L
{                          // 初始条件：线性表L已存在。
  // 操作结果：将L重置为空表
    LinkList p, q;
    p = L->next;
    while (p)
    {
        q = p->next;
        free(p);
        p = q;
    }
    L->next = NULL;
}
 
//单链表的判空
Status ListEmpty(LinkList L)
{ // 初始条件：线性表L已存在。
  // 操作结果：若L为空表，则返回TRUE，否则返回FALSE
 
    return L->next == NULL ? TRUE : FALSE;
}
 
//求单链表长度
int ListLength(LinkList L)
{ // 初始条件：线性表L已存在。
    // 操作结果：返回L中数据元素个数
 
    int len = 0;
    LinkList p = L->next;
    while (p)
    {
        len++;
        p = p->next;
    }
    return len;
}
 
//头插法建立单链表
void CreateList_HeadInsert(LinkList &L, int n)
{ // 初始条件：线性表L已存在。
    // 操作结果：逆位序输入n个元素的值，建立带表头结构的单链线性表L
 
    LinkList p, q;
    int e;
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &e);
        p = (LinkList)malloc(sizeof(LNode));
        p->data = e;
        p->next = L->next;
        L->next = p;
    }
}
 
//尾插法建立单链表
void CreateList_TailInsert(LinkList &L, int n)
{ // 初始条件：线性表L已存在。
    // 操作结果：正位序输入n个元素的值，建立带表头结构的单链线性表L
 
    LinkList p, q;
    int e;
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &e);
        p = (LinkList)malloc(sizeof(LNode));
        p->data = e;
        p->next = NULL;
        if (L->next == NULL)
        {
            L->next = p;
        }
        else
        {
            q = L;
            while (q->next)
            {
                q = q->next;
            }
            q->next = p;
        }
    }
}
 
//单链表中按序号查找数据元素
Status GetElem(LinkList L, int i, ElemType &e)
{ // 当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR
    LinkList p = L->next;
    int j = 1;
    while (p && j < i)
    {
        p = p->next;
        j++;
    }
    if (!p || j > i)
        return ERROR;
    e = p->data;
    return OK;
}
 
//单链表中按值查找数据元素的位序
int LocateElem(LinkList L, ElemType e)
{ // 返回L中第1个值为e 的数据元素的位序，若这样的数据元素不存在,则返回值为0
 
    LinkList p = L->next;
    int i = 1;
    while (p)
    {
        if (p->data == e)
            return i;
        p = p->next;
        i++;
    }
    return 0;
}
 
//查找直接前驱
Status PriorElem(LinkList L, ElemType cur_e, ElemType &pre_e)
{ // 初始条件: 线性表L已存在
    // 操作结果: 若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，
    //           返回OK；否则操作失败，pre_e无定义，返回ERROR
 
    LinkList p = L;
    LinkList q = L->next;
    while (q != NULL && q->data != cur_e)
    {
        p = q;
        q = q->next;
    }
    if (q == NULL)
        return ERROR;
    if (p == L)
        return ERROR;
    pre_e = p->data;
    return OK;
}
 
//插入节点
Status ListInsert(LinkList L, int i, ElemType e)
{ // 在带头结点的单链线性表L中第i个位置之前插入元素e
 
    LinkList p = L;
    int j = 0;
    while (p && j < i - 1)
    {
        p = p->next;
        j++;
    }
    if (!p || j > i - 1)
        return ERROR;
    LinkList s = (LinkList)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}
 
//删除结点
Status ListDelete(LinkList L, int i, ElemType &e)
{ // 在带头结点的单链线性表L中，删除第i个元素，并由e返回其值
 
    LinkList p = L;
    int j = 0;
    while (p->next && j < i - 1)
    {
        p = p->next;
        j++;
    }
    if (!p->next || j > i - 1)
        return ERROR;
    LinkList q = p->next;
    p->next = q->next;
    e = q->data;
    free(q);
    return OK;
}
 
//单链表数据元素的输出
Status visit(LinkList L)
{ // 按序输出单链表的各个元素值
    LinkList p = L->next;
    while (p)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
    return OK;
}
 
int main()
{
    int n = 5;
    int index; // 位序
    Status s;  // 状态返回值
    ElemType cur_e;
    ElemType pre_e;
    int value, delvalue;
 
    LinkList La, Lb;
    InitList(La);
    InitList(Lb);
 
    printf("头插法建立单链表,请输入5个数据：");
    CreateList_HeadInsert(La, n);
    printf("链表的长度为%d\n", ListLength(La));
    printf("链表的内容为：");
    visit(La);
 
    // 按位置查找
    printf("输入待查找元素位置：");
    scanf("%d", &index);
    s = GetElem(La, index, cur_e);
    if (s == OK)
        printf("第%d个元素的值为:%d\n", index, cur_e);
    else
        printf("不存在第%d个元素！\n", index);
 
    // 找前驱
    printf("输入待查找前驱的数据元素值：");
    scanf("%d", &cur_e);
    s = PriorElem(La, cur_e, pre_e);
    if (s == OK)
        printf("数据元素%d的前驱为:%d\n", cur_e, pre_e);
    else
        printf("数据元素%d的前驱不存在！\n", cur_e);
 
    // 按值查找
    printf("输入待查找元素的值：");
    scanf("%d", &cur_e);
    index = LocateElem(La, cur_e);
    printf("值为%d的元素在链表中的位置是%d\n", cur_e, index);
 
    // 清空链表
    s = ListEmpty(La);
    if (s == TRUE)
        printf("该链表为空，该链表的长度为%d\n", ListLength(La));
    else
        printf("该链表非空，该链表的长度为%d\n", ListLength(La));
 
    printf("清空链表\n");
    ClearList(La);
    s = ListEmpty(La);
    if (s == TRUE)
        printf("该链表为空，该链表的长度为%d\n", ListLength(La));
    else
        printf("该链表非空，该链表的长度为%d\n", ListLength(La));
    printf("\n");
 
    printf("尾插法建立单链表,请输入5个数据：");
    CreateList_TailInsert(Lb, n);
    printf("链表的长度为%d\n", ListLength(Lb));
    printf("链表的内容为：");
    visit(Lb);
 
    // 按位置查找
    printf("输入待查找元素位置：");
    scanf("%d", &index);
    s = GetElem(Lb, index, cur_e);
    if (s == OK)
        printf("第%d个元素的值为:%d\n", index, cur_e);
    else
        printf("不存在第%d个元素！\n", index);
 
    // 按值查找
    printf("输入待查找元素的值：");
    scanf("%d", &cur_e);
    index = LocateElem(Lb, cur_e);
    printf("值为%d的元素在链表中的位置是%d\n", cur_e, index);
 
    // 插入元素
    printf("请输入插入元素的位置和内容：");
    scanf("%d%d", &index, &value);
    if (index > 0)
    { // 检查插入位置是否有效
        s = ListInsert(Lb, index, value);
        if (s == OK)
            printf("插入成功！\n");
        else
            printf("插入失败！\n");
    }
    else
    {
        printf("插入位置无效！\n");
    }
    printf("链表的内容为：");
    visit(Lb);
 
    // 删除元素
    printf("请输入要删除元素的位置：");
    scanf("%d", &index);
    if (index > 0)
    { // 检查删除位置是否有效
        s = ListDelete(Lb, index, delvalue);
        if (s == OK)
            printf("删除成功！\n");
        else
            printf("删除失败！\n");
    }
    else
    {
        printf("删除位置无效！\n");
    }
    printf("链表的内容为：");
    visit(Lb);
 
    int lengthBeforeDestroy = ListLength(Lb);
    DestroyList(Lb);
    printf("销毁链表，该链表的长度为0");
 
    return 0;
}