1.线性表的链式存储

顺序表由于逻辑上相邻的元素物理位置上也相邻，所以它的的插入、删除操作需要移动大量的元素，影响了运行效率，由此引入线性表的链式存储，它是通过“链”建立起元素之间的逻辑关系，对其进行插入、删除操作只需要修改指针。

2.单链表

1.单链表的定义

概述

线性表的链式存储又称为单链表，他是通过一组任意的存储单元来存储线性表中的数据元素。为了建立起数据元素之间的线性关系，对每个链表结点，除了存放元素的自身信息之外，还要存放一个指向其后继的指针。

结点结构如上图，其中data为数据域，存放数据元素，next为指针域，存放其后继结点的指针。

头结点:链表中第一个结点我们叫做头结点,数据域默认不使用，只是用指针域。
首结点:链表中头结点的下一个节点。空的带头结点的单链表没有首结点
尾结点:链表中最后一个结点我们叫做尾结点,尾结点的指针域为NULL。

单链表中节点类型描述

typedef struct LNode
{
    ElemType data;
    struct LNode *next;

} LinkNode, *LinkList;

2.单链表上基本操作的实现

1.创建

就是创建一个头结点，将next域设为空

LinkList CreateList()
{
    LinkList L = (LinkList)malloc(sizeof(LinkNode));
    L->next = NULL;
    return L;
}

2.插入（*）

插入统一的操作就是创建新结点病将值赋给新节点的data域

头插法

直接在头结点后面插入

void InsertHeadList(LinkList L, ElemType e)
{
    LinkList p = L; //指向头结点
    LinkList temp = (LinkList)malloc(sizeof(LinkNode));
    temp->data = e;

    temp->next = p->next;
    p->next = temp;
}

尾插法

遍历链表直到尾结点（指针域为NULL），再后插

void InsertTailList(LinkList L, ElemType e)
{
    LinkList p = L; //指向tou结点
    LinkList temp = (LinkList)malloc(sizeof(LinkNode));
    temp->data = e;
    while (p->next != NULL)
    {
        p = p->next;
    }
    temp->next = p->next;
    p->next = temp;
}

按序插入

下面代码是按照从大到小的顺序插入

void InsertOrderList(LinkList L, ElemType e)
{
    LinkList p = L; //指向tou结点
    LinkList temp = (LinkList)malloc(sizeof(LinkNode));
    temp->data = e;
    while (p->next != NULL && temp->data < p->next->data)
    {
        p = p->next;
    }
    temp->next = p->next;
    p->next = temp;
}

指定位置插入

找到第i-1位置 向后插入

int InsertList(LinkList L, int i, ElemType e)
{
    if (i <= 0)
        return 0;
    int j = 0;
    LinkList p = L, temp; //p指向tou结点

    while (p != NULL && j < i - 1)
    {
        j++;
        p = p->next;
    }
    if (NULL == p)
        return 0;
    else
    {
        temp = (LinkList)malloc(sizeof(LinkNode));
        temp->data = e;
        temp->next = p->next;
        p->next = temp;
        return 1;
    }
}

3.输出

从首结点开始扫描单链表，输出各节点data域值

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