编辑代码

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

#define OK              1
#define ERROR           0
#define INFEASIBLE        -1
#define OVERFLOW        -2
#define TRUE            1
#define FALSE            0

typedef int Status;
typedef int ElemType;
typedef struct LNode
{
    ElemType data;
    struct LNode* next;
}LNode,*LinkList;
/*定义了两种新的数据类型LNode和LinkList
显然各个结点是LNode类型的，头指针和结点的next成员是LinkList类型的,
L是LinkList这个新的结构体指针类型定义的头指针*/

Status InitList(LinkList &L)    //初始化
{
    L = (LinkList)malloc(sizeof(LNode));
    if (L == NULL)return ERROR;
    L->next = NULL;
    return OK;
}

Status ListEmpty(LinkList L)    //判空
{
    if (L->next == NULL) return TRUE;
    return FALSE;
}

Status ListInsert(LinkList &L, int i, ElemType e)    //插入
{
    int j = 0;
    LinkList p = L, s;    //指针p指向头指针
    if (i<1) return ERROR;
    while ((p != NULL) && (j<i - 1))
    {
        p = p->next;
        j++;
    }
    if(p==NULL)return ERROR;
    s = (LNode*)malloc(sizeof(LNode));    //生成新节点
    if (s == NULL) return ERROR;
    s->data = e;    //s结点存放e
    s->next = p->next;    //s结点指针指向第i个结点
    p->next = s;    //p指针指向s结点
    return OK;
}

Status ScanfList(LinkList &L)    //键盘输入
{
    printf("输入整数，以0结束:\n");
    ElemType e;
    int i = 1;
    scanf("%d", &e);
    while (e != 0)
    {
        if (!ListInsert(L, i, e)) return ERROR;
        i++;
        scanf("%d", &e);
    }
    return OK;
}

Status ListDelete(LinkList &L, int i, ElemType &e)    //删除
{
    int j = 0;
    LinkList p = L, q;
    if ((i<1) || (L->next == NULL)) return ERROR;
    while ((p != NULL) && (j<i - 1))
    {
        p = p->next;
        j++;
    }
    if (p == NULL) return ERROR;
    q = p->next;    //q暂存被删结点ai的地址
    p->next = q->next;    //p指针(也即是第i-1个结点的指针)指向第i+1个结点
    e = q->data;    //ai结点的数据赋值给e返回
    free(q);
    return OK;
}

Status GetElem(LinkList L, int i, ElemType &e)    //取值
{
    int j = 1;
    LinkList p = L->next;
    if (i<1) return ERROR;
    while ((p != NULL) && (j<i))
    {
        p = p->next;
        j++;
    }
    if (p == NULL) return ERROR;
    e = p->data;
    return OK;
}

int LocateElem(LinkList L, ElemType e)    //定位
{
    int i = 1;
    LinkList p = L;
    while (p->next != NULL)
    {
        p = p->next;
        if (p->data == e)return i;
            i++;
    }
    return i;
}

Status PriorElem(LinkList L, ElemType e, ElemType &pr_e)    //直接前驱
{
    LinkList p = L->next;
    if (p->data == e) return ERROR;    //首结点没有直接前驱
    while (p != NULL)
    {
        if (p->next->data == e) break;
        p = p->next;
    }
    if (p == NULL) return ERROR;    //p指针一直移到尾结点仍找不到e，返回错误
    pr_e = p->data;
    return OK;
}

int GetLength(LinkList L)    //求长度
{
    int i = 0;
    LinkList p = L;
    while (p->next != NULL)
    {
        p = p->next;
        i++;
    }
    return i;
}

void PrnList(LinkList L)    //遍历
{
    LinkList p = L->next;
    if (p == NULL) printf("NULL\n");
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

void NiList(LinkList &L)    //逆置
{
    LinkList p = L->next, q;    //p指针指向了首结点
    L->next = NULL;    //将头结点指针置空
    while (p != NULL)
    {
        q = p;    //q指针从指向第一个结点开始后移
        p = p->next;    //p指针从指向第二个结点开始后移
        q->next = L->next;    //q所指向结点的指针q->next指向其上一个结点
        L->next = q;    //头指针后移
    }
}

Status ClearList(LinkList &L)    //清空
{
    LinkList p = L->next, q;
    if (p == NULL) return OK;
    while (p != NULL)
    {
        q = p->next;
        free(p);
        p = q;
    }
    L->next = NULL;
    return OK;
}

Status Destroy(LinkList &L)    //销毁
{
    LinkList p = L->next, q;
    while (p != NULL)
    {
        q = p->next;
        free(p);
        p = q;
    }
    free(L);
    return OK;
}


int main()
{
    int i;
    ElemType e, e1;

    LinkList L;
    if (InitList(L)) printf("OK\n");
    ScanfList(L);
    PrnList(L);

    int k;
    printf("\n1.插入\n2:删除\n3:取值\n4:定位\n5:直接前驱\n");
    printf("6.求长度\n7:遍历\n8:逆置\n9:清空\n10:销毁\n\n0.退出\n");
    scanf("%d", &k);
    while (k != 0)
    {
        switch (k)
        {
        case 1:
            printf("在第几个位置插入何数：");
            scanf("%d%d", &i, &e);
            if (ListInsert(L, i, e)) printf("OK\n");
            break;
        case 2:
            printf("删除第几个数：");
            scanf("%d", &i);
            if (ListDelete(L, i, e))printf("删除数为：%d\n", e);
            break;
        case 3:
            printf("获取第几个数：");
            scanf("%d", &i);
            if (GetElem(L, i, e)) printf("数为：%d\n", e);
            break;
        case 4:
            printf("定位何数：");
            scanf("%d", &e);
            if (LocateElem(L, e)) printf("位序为：%d\n", LocateElem(L, e));
            break;
        case 5:
            printf("寻找何数直接前驱:");
            scanf("%d", &e);
            if (PriorElem(L, e, e1)) printf("前驱为:%d\n", e1);
            break;
        case 6:
            printf("表长为：");
            printf("%d\n", GetLength(L));
            break;
        case 7:
            printf("遍历：\n");
            PrnList(L);
            break;
        case 8:
            NiList(L);
            PrnList(L);
            printf("逆置成功\n");
            break;
        case 9:
            if (ClearList(L))printf("清空成功\n");
            break;
        case 10:
            if (Destroy(L))printf("销毁成功\n");
            break;
        default:
            printf("ERROR\n");
        }
        scanf("%d", &k);
    }
    return 0;
}