[数据结构与算法]数据结构—线性表的链式存储

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

typedef int tElem;
typedef struct List {
    tElem data;             // 数据域
    struct List * next;     // 指针域
} List, *pList;
typedef enum Status {
    ok = 1,Error = 0
} Status;


/*
 * 初始化
 * 步骤：
 *  为头结点申请一个内存空间。
 *  判断空间申请状态。
 *  让头结点的指针域指向 NULL。
*/
Status InitList(List * head)
{
    head = (pList) malloc(sizeof(List));
    if(head == NULL)
    {
        printf("空间申请失败！\n");
        return Error;
    }

    head->next = NULL;
    return ok;
}


/*
 * 获取线性表的长度
 * 步骤：
 *  定义一个计数器 count。
 *  定义一个临时变量 temp，初始值为头结点的下一个节点，因为计算链表长度时，是不计算头结点的，所以从头结点的下一个节点开始计数。
 *  遍历线性表，每遍历一次，计数器累加 1，同时让临时变量 temp 指向本身的下一个节点。
 *  最后输出 count 的值就是线性表当前的长度。
*/
Status ListEmpty(List * head)
{
    int count = 0;
    pList temp = head->next;
    while (temp != NULL)
    {
        count ++;
        temp = temp->next;
    }
    printf("线性表的长度为：%d\n",count);
}


/*
 * 头插入法插入一个元素
 * 步骤：
 *  判断头结点是否为空。
 *  定义一个临时变量 temp 并为其申请内存空间，用于存放插入的数据。
 *  令 temp 的数据域等于插入的数据 e。
 *  令 temp 的指针域指向头结点指针域指向的节点。
 *  最后，让头结点的指针域指向 temp。
 * 说明：
 *  利用头插入法插入的数据最后的顺序如下：
 *  初始化：head
 *  插入第一个元素 10：head -> 10 -> NULL
 *  插入第二个元素 20：head -> 20 -> 10 -> NULL
*/
Status ListHeadInsert(List * head,tElem e)
{
    if(head == NULL)
    {
        return Error;
    }

    pList temp = (pList) malloc(sizeof(List));
    temp->data = e;
    temp->next = head->next;
    head->next = temp;
    return ok;
}


/*
 * 尾插入法插入一个元素
 * 步骤：
 *  判断头结点是否为空。
 *  定义一个临时变量 item 用于遍历时接受线性表的每一个节点。
 *  定义一个临时变量 temp 并为其申请内存空间，用于存放插入的数据。
 *  令 item 等于头结点的下一个节点，因为在遍历时是从头结点的下一个节点开始的。
 *  令 temp 的数据域等于插入的数据 e。
 *  令 temp 的指针域指向 NULL。
 *  遍历线性表，当节点的指针域为 NULL 时，此时的 item 是离 head 最远的节点，也就是最后一个节点。
 *  最后令 item 的指针域指向 temp。
 * 说明：
 *  利用尾插入法插入的数据最后的顺序如下：
 *  初始化：head
 *  插入第一个数据 10：head -> 10 -> NULL
 *  插入第二个数据 20：head -> 10 -> 20 -> NULL
*/
Status ListTailInsert(List * head,tElem e)
{
    if(head == NULL)
    {
        return Error;
    }

    pList item = head->next;
    pList temp = (pList) malloc(sizeof(List));
    temp->data = e;
    temp->next = NULL;

    while (item->next != NULL)
    {
        item = item->next;
    }
    item->next = temp;
    return ok;
}


/*
 * 打印线性表
 * 步骤：
 *  定义一个计数器，用作节点的索引（可以不定义）
 *  定义一个临时变量 item，存入头结点的下一个节点，原因同上，打印时不打印头结点，从头结点的下一个节点开始打印。
 *  遍历线性表，当 item 的指针域为 NULL 时，item 已是线性表的最后一个元素了。
 *  循环体内对每个节点的数据与进行打印。
*/
void ListTraverse(List * head)
{
    int count = 0;
    pList temp = head->next;
    while (temp != NULL)
    {
        count ++;
        printf("线性表的第 %d 个元素是：%d\n",count,temp->data);
        temp = temp->next;
    }
}


/*
 * 判断元素 e 是否在线性表中
 * 步骤：
 *  定义一个临时变量 temp 初始值给头结点的下一个节点
 *  遍历线性表，判断元素 e 是否在线性表中出现。若在线性表内，返回 1，否则返回 0。
*/
Status ListIsIn(List * head,tElem e)
{
    pList temp = head->next;
    while (temp != NULL)
    {
        if(temp->data == e)
        {
            return ok;
        }
        temp = temp->next;
    }
    return Error;
}

/*
 * 获取元素 e 前一个元素
 * 步骤：
 *  判断元素 e 是否在列表中。
 *  定义一个临时变量 temp，值为头结点的下一个节点。
 *  判断 temp 的数据域是否等于元素 e，若相等则表示 temp 是线性表的第一个元素，无前一个元素。
 *  遍历线性表，若 item 下一个节点的数据域等于 e，表示此时的 item 是元素 e 的前一个元素，打印 item 的数据域即可。
*/
Status PriorElem(List * head,tElem e)
{
    if(!ListIsIn(head,e))
    {
        printf("元素 %d 不在线性表中！\n",e);
        return Error;
    }

    pList temp = head->next;
    if(temp->data == e)
    {
        printf("元素 %d 是线性表的第一个元素，无前一个元素。\n");
        return Error;
    }

    while (temp->next != NULL)
    {
        if(temp->next->data == e)
        {
            printf("元素 %d 的前一个元素是：%d\n",e,temp->data);
            return ok;
        }
        temp = temp->next;
    }
}


/*
 * 获取元素 e 后一个元素
 * 步骤：
 *  判断元素 e 是否在列表中。
 *  定义一个临时变量 temp，值为头结点的下一个节点。
 *  遍历线性表，如果 temp 的数据域等于 e，则此时 temp 的指针域表示元素 e 的后一个节点，打印这个节点的数据域即可。
 *  若果 temp 的指针域为空，则 temp 表示线性表的最后一个元素，无后一个元素。
*/
Status NextElem(List * head,tElem e)
{
    if(!ListIsIn(head,e))
    {
        printf("元素 %d 不在线性表中！\n",e);
        return Error;
    }

    pList temp = head->next;
    while (temp->next != NULL)
    {
        if(temp->data == e)
        {
            printf("元素 %d 的后一个元素是：%d\n",e,temp->next->data);
            return ok;
        }
        temp = temp->next;
    }
    if(temp->next == NULL && temp->data == e)
    {
        printf("元素 %d 是线性表的最后一个元素，没有后一个元素。\n",e);
    }
}


/*
 * 删除元素 e
 * 步骤：
 *  判断元素 e 是否在列表中。
 *  定义一个临时变量 temp，值为头结点的下一个节点。
 *  遍历线性表，第一次循环是，若 temp 的数据域等于 e，则让头结点指向 temp 的下一个节点，这样就把 temp 这个节点挤出去了。
 *  若 temp 的下一个节点的数据域等于 e，说明此时的 temp 是元素 e 的前一个节点，让这个节点的指针域直接指向元素 e 所在节点的下一个节点即可。
*/
Status ListDelete(List * head,tElem e)
{
    if(!ListIsIn(head,e))
    {
        printf("元素 %d 不在线性表中！\n",e);
        return Error;
    }

    pList temp = head->next;
    while (temp != NULL)
    {
        if(temp->data == e)
        {
            head->next = temp->next;
            return ok;
        }
        if(temp->next->data == e)
        {
            temp->next = temp->next->next;
            return ok;
        }
        temp = temp->next;
    }
}


/*
 * 清空线性表
 * 步骤：
 *  直接让头结点的指针域指向空即可。
*/
void ClearList(List * head)
{
    head->next = NULL;
}


/*
 * 摧毁线性表
 * 步骤：
 *  直接释放头结点即可
*/
void DestroyList(List * head)
{
    free(head);
    printf("销毁成功！\n");
}

int main() {
    List head;

    // 初始化
    InitList(&head);

    // 统计线性表长度
    printf("初始化后：");
    ListEmpty(&head);
    printf("\n");

    // 头插入元素
    ListHeadInsert(&head,10);
    ListHeadInsert(&head,20);

    // 尾插入元素
    ListTailInsert(&head,30);
    ListTailInsert(&head,40);

    // 打印线性表
    ListTraverse(&head);
    printf("\n");

    // 获取元素 e 的前一个元素
    PriorElem(&head,10);
    PriorElem(&head,20);
    PriorElem(&head,50);
    printf("\n");

    // 获取元素 e 的后一个元素
    NextElem(&head,10);
    NextElem(&head,40);
    NextElem(&head,50);
    printf("\n");

    // 删除元素
    ListDelete(&head,50);
    ListDelete(&head,30);
    ListTraverse(&head);
    printf("\n");

    // 清空线性表
    ClearList(&head);
    printf("清空线性表后：");
    ListEmpty(&head);

    // 销毁线性表
    DestroyList(&head);

    return 0;
}