线性存储的链式存储

链式存储又叫链表，分可以分为单链表 双链表，循环链表，静态链表。

单链表

何为单链表：使用链式存储的结构实现线性存储（逻辑结构）。顺序表在物理上是连续存放的，单链表无需这样，原因就是 每个简单除了存放数据元素之外，还存储了指向下一个节点的指针

优点： 不要求大片连续存储空间，改变容量方便。

缺点： 不可以随机读取，要花费一定的空间存储指针。

单链表有两种实现方式，带头节点和不带头节点的。

实现单链表

typedef struct
{
    int data;           //数据域
    struct LNode *next; //指针域
} LNode;

增加一个新的结点：在内存中申请空间，并用指针p指向这个节点

LNode *P = (LNode *)malloc(sizeof(struct LNode));

typedef 的使用

基本语法: typedef <数据类型> <别名> 。

使用typedef 我们可以简化很多。

typedef struct LNode
{
    int data;           //数据域
    struct LNode *next; //指针域
} LNode, *LinkList;

其实 只要把 struct LNode{} 看出一个整体就好理解了，结合 typedef <数据类型> <别名> ，是不用一目了然。

等价于 typedef struct LNode LNode; typedef struct LNode* linkList;

我们就可 声明 LinkList 声明头指针， LNode 声明结构体。

初始化单链表 和判断是否为空

不带头节点

不带头节点其实非常好理解

bool InitList(LinkList &L)//无比传入引用，要不然操作的就是局部变量
{
    L = NULL;
    return true;
}
//判断是否为空
bool Empty(LinkList L)
{
    return (L==NULL);
}

使用话 用 LinkList 开辟头指针就好了。

void test()
{
    LinkList L; //声明指向单链表的指针
    InitList(L);
}
带头节点

其实带头节点有一点点不好理解。

bool InitList(LinkList &L)
{
    //开辟头节点，并且是头指针指向头节点
    L = (LNode *)malloc(sizeof(LNode));
    //开辟空间失败retrun flase
    if (L == NULL)
    {
        return false;
    }
    L->next = NULL;
    return true;
}
bool Empty(LinkList L)
{
    return (L->next == NULL);
}

void test()
{
    LinkList L; //声明指向单链表的指针
    InitList(L);
}
image-20210210152210283

首先加了头节点是为了实现某些操作方便，头节点不存储数据。

image-20210210153422747

带头节点和不带头节点有何区别

不带头节点，写代码比较麻烦，因为第一个数据点和后续数据不一样，所以需要不同的代码逻辑，并且对空表和非空表的处理也需要不同的逻辑。

结论：我们使用带头节点的，不适用不带头节点的。

单链表插入

带头节点

插入操作，在第i个位置上出入指定元素e。头节点可以作为第零个节点。

其实我们要做的事情就是

  1. 判断 i是否合法
  2. 在 i处 插入节点，就获取它前面一个节点 i-1
  3. 判断找到的i-1个节点是否存在
  4. 开辟新的节点并 连接到链表中
bool ListInsert(LinkList &L, int i, int e)
{
    if (i < 1)//i表示为序 不允许小于1
        return false;
    LNode *p = L; //p 指向当前扫描到的节点
    int j = 0;    //当前p指向的是那个节点
    //循环时为了获取 i-1节点
    while (p != NULL && j < i - 1) //扫描到 第i-1节点 当p == NULL说明到了表尾
    {
        p = p->next;
        j++;
    }
    // 如果在大于表尾的地方插入数据，那节点存在 ，那么插入失败
    if (p == NULL)
        return false;
    //开始新的节点，并存储数据 e
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    // 将s指向下一个节点，并且p（第i-1）节点的next指向 s
    s->next = p->next;
    p->next = s;
    return true;
}
不带头节点

其实就多了一个处理插入第一个位置的特殊情况 ，由于没有头节点 ，那么就要改 头地址LinkList的指向，

if(i==1)
{
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    // 将s指向原来的下一个节点，并且头指针指向 s
    s->next = L->next;
    L->next = s;
    return true;
}

所以不带头节点就有点麻烦,以后的情况就说明有头节点。

任意节点后插操作

bool InsertNextNode(LNode* p,int e)
{
    //传入节点不存在 失败
    if(p==NULL)
        return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if(s==NULL)//开辟空间失败
        return false;
    s->data=e;
    s->next = p->next;
    p->next = s;
    return true;
}

前插操作

由于我们单链表，知道某一个节点就可以知道它后面的所有节点，但是在他之前的呢，就单单这个条件的话无法知道的。

所以还要传入参数 头指针 LinkList，通过它来找到它前面节点，但是这样的算法时间复杂度无疑是 O(n);没有更简单的方法呢？

偷天换日

虽然节点是死的，但是数据是活的。找不到前驱节点就创造节点

  1. 我们继续指向后插操作
  2. 插入的节点覆盖插入节点的数据
  3. 原来的节点覆盖新数据。
bool InsertPriorNode(LNode *p, int e)
{
    //传入节点不存在 失败
    if (p == NULL)
        return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL) //开辟空间失败
        return false;
    // 继续查到后面
    s->next = p->next;
    p->next = s;
    s->data = p->data;
    p->data = e;
    return true;
}

很妙。

删除节点

删除操作,我们就需要进行如下几步

  1. 找到删除节点的前驱节点
  2. 让前驱节点的next指针跳过删除节点指向下一个节点。
  3. 释放删除节点的空间
按位序删除
// 按序位删除
bool ListDelete(LinkList &L, int i, int &e)
{
    if (i < 1)
        return false;
    LNode *p;
    int j = 0;
    p = L;
    // 扫描它前面一个节点
    while (p != NULL && j < i - 1)
    {
        p = p->next;
        j++;
    }
    if (p == NULL)
        return false;
    if (p->next == NULL) //发现i-1节点是 尾巴 就失败
        return false;
    //删除节点i
    LNode *q = p->next; //q是被删除节点
    e = q->data;//e是返回删除节点的值
    p->next = q->next;
    free(q);
    return true;
}
删除指定节点

和前插操作一样，我们这样进行

  1. 让它的后驱节点和自己交换数据域data 和指针域
  2. 释放后驱节点
bool DeleteNode(LNode *p)
{
    if (p == NULL)
        return false;
    LNode *q = p->next;
    p->data = q->data;
    p->next = q->next;
    free(q);
    return true;
}

但是这样是有bug的时候，假如删除最后一个节点就无法后驱节点（此时后驱节点是NULL）和自己交换数据域data 和指针域。

所以当时最后一个节点的时候，就要扫描到它的前驱节点

查找

按位查找

其实这个就简单多了，一个循环就可以解决

LNode *GetElem(LinkList L, int i)
{
    if (i < 0)
        return NULL;
    LNode *p = L;
    int j = 0;
    while (p != NULL && j < i)
    {
        p = p->next;
        j++;
    }
    return p;
}
按元素查找
LNode *LocaleElem(LinkList L, int e)
{
    LNode *p = L->next;
    while (p != NULL && p->data != e)
        p = p->next;
    return p;
}

求表的长度

int Length(LinkList L)
{
    int len = 0;
    LNode *p = L;
    while (p->next != NULL)
    {
        p = p->next;
        len++;
    }
    return len;
}

建立单链表

尾插法

所谓尾插法就是在链表的后面的节点插入数据。

LinkList List_TailInsert(LinkList &L)
{
    int x;
    L = (LinkList)malloc(sizeof(LNode));
    LNode *s, *r = L; //s表示开创的节点,r 为尾指针
    scanf("%d", &x);
    while (x != 9999) //9999 作为退出标志
    {
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        r->next = s; //新开辟的节点接入s 链表
        r = s;       //r有和新开创的节点重合
        scanf("%d", &x);
    }
    r->next = NULL;
    return L;
}
头插法

所谓头插法就是 一致在头节点插入数据

我们使用头插法，插入数据的话，插入数据是输入数据的逆序。

输入的数据是 1 2 3 那么存储数据恰好是 3 2 1, 这就叫逆置

LinkList List_HeadInsert(LinkList &L)
{
    int x;
    L = (LinkList)malloc(sizeof(LNode));
    LNode *s;
    L->next = NULL;
    scanf("%x", &x);
    while (x != 9999)
    {
        s = (LNode *)malloc(sizeof(LNode));
        //头插入操作
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%x", &x);
    }
    return L;
}

我们就可以更具这个写出一个逆置的函数, 其实就把后一个元素前插到前一个元素

void Inverse(LinkList &L)
{
    LNode *p, *q;
    p = L->next;
    L->next = NULL; //初始化空表
    while (p != NULL)
    {
        q = p; //p,q同时指向next结点
        p = p->next;//p为下一个指针。

        //头插操作
        q->next = L->next; //第一次执行时L->next为NULL
        L->next = q;
    }
}

总结

其实获取单链表这么多运算离不开，前插，后插操作，扫描节点的这几个操作。

Q.E.D.

努力学习的小菜鸟