链式存储结构的线性表

单链表结构可用如下C语言代码描述

typedef struct Node
{
    ElemType data;
    struct Node *next;
} Node;

typedef struct Node *LinkList

建立链表操作

// 尾插法建立链表
// 操作结果：产生长度为size的正序链表并返回头指针
LinkList CreateListTail(int size)
{
    int count;
    // head为头节点，p为工作指针，q为临时指针
    LinkList head, p, q;
    // 先建立一个空的头节点
    head = (LinkList)malloc(sizeof(Node));
    head->data = 0;
    head->next = NULL;
    // 将工作指针指向头节点
    p = head;
    for (count = 0; count < size; count++)
    {
        // 临时指针创建节点
        LinkList q = (LinkList)malloc(sizeof(Node));
        q->data = count;
        // 工作指针连接新建节点
        p->next = q;
        // 工作指针后移
        p = q;
    }
    // 标识链表结束
    p->next = NULL;
    return head;
}

// 头插法建立链表
// 操作结果：产生长度为size的逆序链表并返回头指针
LinkList CreateListHead(int size)
{
    int count;
    // head为头节点，p为临时指针
    LinkList head, p;
    // 先建立一个空的头节点
    head = (LinkList)malloc(sizeof(Node));
    head->data = 0;
    head->next = NULL;
    for (count = 0; count < size; count++)
    {
        p = (LinkList)malloc(sizeof(Node));
        p->next = head->next;
        p->data = count;
        head->next = p;
    }
    return head;
}

读取操作

// 读取一个节点
// 操作结果：读取head指向的链表的第i个节点并赋值给e指向的内存
int GetNode(LinkList head, int i, int *e)
{
    LinkList p = head;
    int count;
    // 位置不合理
    if (i <= 0)
    {
        return ERROR;
    }
    // 寻找读取的位置
    for (count = 0; count < i; count++)
    {
        p = p->next;
        if (!p)
        {
            return ERROR;
        }
    }
    *e = p->data;
    return OK;
}

插入节点操作

// 插入一个节点
// 操作结果：在head指向的链表的第i个位置插入e
int InsertNode(LinkList head, int i, int e)
{
    LinkList p = head, q;
    // 插入位置不合理
    if (i <= 0)
    {
        return ERROR;
    }
    int count;
    // 移动到插入的位置
    for (count = 1; count < i; count++)
    {
        p = p->next;
        // 插入位置不合理
        if (!p)
        {
            return ERROR;
        }
    }
    q = (LinkList)malloc(sizeof(Node));
    q->data = e;
    q->next = p->next;
    p->next = q;
    return OK;
}

删除一个节点操作

// 删除一个节点
// 操作结果：删除head指向链表的第i个节点
int DeleteNode(LinkList head, int i)
{
    LinkList p = head, q;
    int count;
    // 删除位置不合理
    if (i <= 0)
    {
        return ERROR;
    }
    //  找到需要删除的节点的前一个节点
    for (count = 0; count < i - 1; count++)
    {
        p = p->next;
        if (!(p->next))
        {
            return ERROR;
        }
    }
    // 删除节点
    q = p->next;
    p->next = p->next->next;
    free(q);
    return OK;
}

遍历操作

// 遍历链表
// 操作结果：输出head指向的链表的所有节点的值
void Traversal(LinkList head)
{
    LinkList p = head->next;
    while (p)
    {
        printf("%d\n", p->data);
        p = p->next;
    }
}

链式存储结构线性表的优点：

1. 不用确定具体的大小
2. 插入与删除操作时间复杂度为O(1)

顺序存储结构线性表的缺点：

1. 访问操作的时间复杂度比较高
2. 需要为存储关系(next指针)消耗额外的存储空间