逻辑结构上一个挨一个的数据,在实际存储时,并没有像顺序表那样也相互紧挨着。恰恰相反,数据随机分布在内存中的各个位置,这种存储结构称为线性表的链式存储
(本文转载自 biancheng.net,原文作者解学武)。

由于分散存储,为了能够体现出数据元素之间的逻辑关系,每个数据元素在存储的同时,要配备一个指针,用于指向它的直接后继元素,即每一个数据元素都指向下一个数据元素(最后一个指向 NULL)。

如图 1 所示,当每一个数据元素都和它下一个数据元素用指针链接在一起时,就形成了一个链,这个链子的头就位于第一个数据元素,这样的存储方式就是链式存储。

线性表的链式存储结构生成的表,称作链表

链表中数据元素的构成

每个元素本身由两部分组成:

  • 本身的信息,称为数据域
  • 指向直接后继的指针,称为指针域

这两部分信息组成数据元素的存储结构,称之为结点。n 个结点通过指针域相互链接,组成一个链表。

图 3 中,由于每个结点中只包含一个指针域,生成的链表又被称为线性链表单链表

链表中存放的不是基本数据类型,需要用结构体实现自定义:

typedef struct Link
{
    int elem;         //代表数据域
    struct Link *next; //代表指针域,指向直接后继元素
} link;

头结点、头指针和首元结点

  • 头结点:有时,在链表的第一个结点之前会额外增设一个结点,结点的数据域一般不存放数据(有些情况下也可以存放链表的长度等信息),此结点被称为头结点。若头结点的指针域为空(NULL),表明链表是空表。头结点对于链表来说,不是必须的,在处理某些问题时,给链表添加头结点会使问题变得简单。
  • 首元结点:链表中第一个元素所在的结点,它是头结点后边的第一个结点。
  • 头指针:永远指向链表中第一个结点的位置(如果链表有头结点,头指针指向头结点;否则,头指针指向首元结点)。

头结点和头指针的区别:头指针是一个指针,头指针指向链表的头结点或者首元结点;头结点是一个实际存在的结点,它包含有数据域和指针域。两者在程序中的直接体现就是:头指针只声明而没有分配存储空间,头结点进行了声明并分配了一个结点的实际物理内存。

单链表中可以没有头结点,但是不能没有头指针!

链表的创建和遍历

万事开头难,初始化链表首先要做的就是创建链表的头结点或者首元结点。创建的同时,要保证有一个指针永远指向的是链表的表头,这样做不至于丢失链表。

例如创建一个链表(1、2、3、4):

link *initLink()
{
    link *p = (link *)malloc(sizeof(link)); //创建一个头结点
    link *temp = p;                         //声明一个指针指向头结点,用于遍历链表
    //生成链表
    for (int i = 1; i < 5; i++)
    {
        link *a = (link *)malloc(sizeof(link));
        a->elem = i;
        a->next = NULL;
        temp->next = a;
        temp = temp->next;
    }
    return p;
}

链表中查找某结点

一般情况下,链表只能通过头结点或者头指针进行访问,所以实现查找某结点最常用的方法就是对链表中的结点进行逐个遍历。

int selectElem(link *p, int elem)
{
    link *t = p;
    int i = 1;
    while (t->next)
    {
        t = t->next;
        if (t->elem == elem)
        {
            return i;
        }
        i++;
    }
    return -1;
}

链表中更改某结点的数据域

链表中修改结点的数据域,通过遍历的方法找到该结点,然后直接更改数据域的值。

//更新函数,其中,add 表示更改结点在链表中的位置,newElem 为新的数据域的值
link *amendElem(link *p, int add, int newElem)
{
    link *temp = p;
    temp = temp->next; //在遍历之前,temp 指向首元结点
    //遍历到被删除结点
    for (int i = 1; i < add; i++)
    {
        temp = temp->next;
    }
    temp->elem = newElem;
    return p;
}

向链表中插入结点

链表中插入头结点,根据插入位置的不同,分为 3 种:

  • 插入到链表的首部,也就是头结点和首元结点中间。
  • 插入到链表中间的某个位置。
  • 插入到链表最末端。

虽然插入位置有区别,都使用相同的插入手法。分为两步,如图 5 所示。

  • 将新结点的 next 指针指向插入位置后的结点。
  • 将插入位置前的结点的 next 指针指向插入结点。

提示:在做插入操作时,首先要找到插入位置的上一个结点,图 4 中,也就是找到结点 1,相应的结点 2 可通过结点 1 的 next 指针表示,这样,先进行步骤 1,后进行步骤 2,实现过程中不需要添加其他辅助指针。

link *insertElem(link *p, int elem, int add)
{
    link *temp = p; //创建临时结点 temp
    //首先找到要插入位置的上一个结点
    for (int i = 1; i < add; i++)
    {
        if (temp == NULL)
        {
            printf("插入位置无效\n");
            return p;
        }
        temp = temp->next;
    }
    //创建插入结点 c
    link *c = (link *)malloc(sizeof(link));
    c->elem = elem;
    //向链表中插入结点
    c->next = temp->next;
    temp->next = c;
    return p;
}

注意:首先要保证插入位置的可行性,例如图 5 中,原本只有 5 个结点,插入位置可选择的范围为:1-6,如果超过 6,本身不具备任何意义,程序提示插入位置无效。

从链表中删除节点

当需要从链表中删除某个结点时,需要进行两步操作:

  • 将结点从链表中摘下来。
  • 手动释放掉结点,回收被结点占用的内存空间。

使用 malloc 函数申请的空间,一定要注意手动 free 掉。否则在程序运行的整个过程中,申请的内存空间不会自己释放(只有当整个程序运行完了以后,这块内存才会被回收),造成内存泄漏,别把它当成是小问题。

link *delElem(link *p, int add)
{
    link *temp = p;
    //temp 指向被删除结点的上一个结点
    for (int i = 1; i < add; i++)
    {
        temp = temp->next;
    }
    link *del = temp->next;        //单独设置一个指针指向被删除结点,以防丢失
    temp->next = temp->next->next; //删除某个结点的方法就是更改前一个结点的指针域
    free(del);                     //手动释放该结点,防止内存泄漏
    return p;
}
最后修改:2019 年 11 月 09 日 09 : 06 PM
如果觉得我的文章对你有用,请随意赞赏