Swift教程

数据结构与算法-线性表-单链表

本文主要是介绍数据结构与算法-线性表-单链表，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这就意味着，这些数据元素可以存在内存未被占用的任意位置（如图所示）。

image-20200406095837446

以前在顺序结构中，每个数据元素只需要存数据元素信息就可以了。现在链式结构中，除了要存数据元素信息外，还要存储它的后继元素的存储地址。

我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素ai的存储映像，称为结点（Node）。

n个结点（ai的存储映像）链结成一个链表，即为线性表（a1,a2,...,an）的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。单链表正是通过每个结点的指针域将线性表的数据元素按其逻辑次序链接在一起，如图所示。

image-20200406100123274

对于线性表来说，总得有个头有个尾，链表也不例外。我们把链表中第一个结点的存储位置叫做头指针，那么整个链表的存取就必须是从头指针开始进行了。之后的每一个结点，其实就是上一个的后继指针指向的位置。想象一下，最后一个结点，它的指针指向哪里？

最后一个，当然就意味着直接后继不存在了，所以我们规定，线性链表的最后一个结点指针为“空”（通常用NULL或“^”符号表示，如图所示）。

image-20200406100220697

有时，我们为了更加方便地对链表进行操作，会在单链表的第一个结点前附设一个结点，称为头结点。头结点的数据域可以不存储任何信息，谁叫它是第一个呢，有这个特权。也可以存储如线性表的长度等附加信息，头结点的指针域存储指向第一个结点的指针，如图所示。

image-20200406100336833

头指针与头结点的异同

image-20200406100433443

线性表链式存储结构代码描述

若线性表为空，则头结点的指针域指为空，如图所示：

image-20200406100640158

单链表的存储示意图：

image-20200406100758516

带有头结点的单链表，如图所示：

image-20200406100840083

单链表中，我们在C语言中可用结构指针来描述。

// 存储空间初始分配量
#define MAXSIZE 20
// ElemtType类型根据实际情况而定，这里假设为int
typedef int ElemType;

typedef struct {
    // 数组存储数据的元素，最多为MAXSIZE个
    ElemType data[MAXSIZE];
    // 线性表当前的长度
    int length;
} SqList;


#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
// Status是函数的类型，其值是函数结果状态代码，如OK等
typedef int Status;

// 线性表的单链表存储结构
typedef struct NodeTag {
    ElemType data;
    struct NodeTag *next;
} Node;

typedef struct NodeTag *LinkList;
复制代码

从这个结构定义中，我们也就知道，结点由存放数据元素的数据域和存放后继结点地址的指针域组成。假设p是指向线性表第i个元素的指针，则该结点ai的数据域我们可以用p->data来表示，p->data的值是一个数据元素，结点ai的指针域可以用p->next来表示，p->next的值是一个指针。p->next指向谁呢？当然是指向第i+1个元素，即指向ai+1的指针。也就是说，如果p->data=ai，那么p->next->data=ai+1（如图所示）。

image-20200406101952234

单链表的读取

获得单链表第i个元素的思路：

  1. 声明一个指针p指向单链表的第一个结点，初始化j从1开始。
  2. 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点。j累加1。
  3. 如果到链表的末尾，p为空，则第i结点不存在。
  4. 否则查找成功，返回结点p的数据，也就是第i个结点的数据。

实现算法代码如下：

// 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
// 操作结果：用e返回L中第i个数据元素的值
Status GetElem(LinkList L, int i, ElemType *e) {
    LinkList p = NULL;
    int j = 1;
    while (p && j < i) {
        p = p->next;
        j++;
    }
    if (!p || j > i) {
        return ERROR;
    }
    *e = p->data;
    return OK;
}
复制代码

单链表的插入

先来看单链表的插入。假设存储元素e的结点为s，要实现结点p、p->next和s之间逻辑关系的变化，只需将结点s插入到结点p和p->next之间即可。可如何插入呢（如图所示）？

image-20200406181030715

根本用不着惊动其他结点，只需要让s->next和p->next的指针做一点改变即可。

s->next = p->next; p->next = s;
复制代码

也就是说让p的后继结点改成s的后继结点，再把结点s变成p的后继结点（如图所示）。

image-20200406181147218

这两句的顺序可不可以交换？

如果先p->next=s;再s->next=p->next;会怎么样？哈哈，因为此时第一句会使得将p->next给覆盖成s的地址了。那么s->next=p->next，其实就等于s->next=s，这样真正的拥有ai+1数据元素的结点就没了上级。这样的插入操作就是失败的，造成了临场掉链子的尴尬局面。所以这两句是无论如何不能反的，这点初学者一定要注意。

插入结点s后，链表如图所示。

image-20200406181318917

对于单链表的表头和表尾的特殊情况，操作是相同的，如图所示。

image-20200406181353005

单链表第i个数据插入结点的算法思路：

  1. 声明一指针p指向链表头结点，初始化j从1开始；
  2. 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1；
  3. 若到链表末尾p为空，则说明第i个结点不存在；
  4. 否则查找成功，在系统中生成一个空结点s；
  5. 将数据元素e赋值给s->data；
  6. 单链表的插入标准语句s->next=p->next;p->next=s；
  7. 返回成功。

代码实现：

// 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)，
// 操作结果：在L中第i个结点位置之前插入新的数据元素e，L的长度加1
Status ListInsert(LinkList *L, int i, ElemType e) {
    LinkList p = *L;//让p指向链表的头结点
    LinkList s;//新元素的结点
    int j = 1;//从第一个位置开始便利
    
    //寻找第i-1个结点
    while (p && j < i) {
        p = p->next;
        j++;
    }
  	//如果传入的i是0或者是负数，那么这个时候，这个i节点是不存在的
    if (!p || j > i) {
        return ERROR;
    }
    //创建新的结点
    s = (LinkList)malloc(sizeof(Node));
    s->data = e;
    //将p的后继结点赋值给s的后继
    s->next = p->next;
    //将s赋值给p的后继 
    p->next = s;
    
    return OK;
}
复制代码

单链表删除

设存储元素ai的结点为q，要实现将结点q删除单链表的操作，其实就是将它的前继结点的指针绕过，指向它的后继结点即可，如图所示。

image-20200406201624895

我们所要做的，实际上就是一步，p->next=p->next->next，用q来取代p->next，即是：

q=p->next; p->next=q->next;
复制代码

单链表第i个数据删除结点的算法思路：

  1. 声明一指针p指向链表头结点，初始化j从1开始；
  2. 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1；
  3. 若到链表末尾p为空，则说明第i个结点不存在；
  4. 否则查找成功，将欲删除的结点p->next赋值给q；
  5. 单链表的删除标准语句p->next=q->next；
  6. 将q结点中的数据赋值给e，作为返回；
  7. 释放q结点；
  8. 返回成功。

代码实现：

// 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
// 操作结果：删除L的第i个结点，并用e返回其值，L的长度减1
Status ListDelete(LinkList *L, int i, ElemType *e) {
    LinkList p = *L;
    // 要删除的结点
    LinkList q;
    int j = 1;
    // 找到要删除结点的前一个结点
    while (p && i > j) {
        p = p->next;
        j++;
    }
    //i应该大于等于1，为0或者负数时，节点不存在, 判断要删除的结点是否存在
    if (!(p->next) || j > i) {
        return ERROR;
    }
    q = p->next;
    p->next = q->next;
    *e = q->data;
    //释放q结点
    free(q);
    return OK;
}
复制代码

单链表的整表创建

单链表整表创建的算法思路：

  1. 声明一指针p和计数器变量i；
  2. 初始化一空链表L；
  3. 让L的头结点的指针指向NULL，即建立一个带头结点的单链表；
  4. 循环：

头插法

  • 随机生成一个新的结点赋值给p;
  • 随机生成一个数字赋值给p的数据域；
  • 将p插入到头结点与前一个新结点之间。

代码实现如下：

// 随机产生n个元素的值，建立带表头结点的单链线性表L（头插法
void CreateListHead(LinkList *L, int n) {
    LinkList p;
    //初始化头结点
    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;
    
    for (int i = 0; i < n; i++) {
        // 生成新的结点
        p = (LinkList)malloc(sizeof(Node));
        // 随机生成100以内的数字
        p->data = rand() % 100 + 1;
        p->next = (*L)->next;
        // 插入到表头
        (*L)->next = p;
    }
}
复制代码

这段算法代码里，我们其实用的是插队的办法，就是始终让新结点在第一的位置。我也可以把这种算法简称为头插法，如图所示：

image-20200406204250641

尾插法

可事实上，我们还是可以不这样干，为什么不把新结点都放到最后呢，这才是排队时的正常思维，所谓的先来后到。我们把每次新结点都插在终端结点的后面，这种算法称之为尾插法。

算法实现思路：

  • 声明一个指针r，用来记录尾结点；初始化时r指向头结点的位置；
  • 随机生成一个新的结点赋值给p；
  • 给p的数据域随机赋值；
  • 将r的后继赋值为p;
  • 这是p是尾结点，我们将p再赋值给r，以便于下次能够快速找到尾结点

实现代码算法如下：

// 随机产生n个元素的值，建立带表头结点的单链线性表L（尾插法）
void CreateListTail(LinkList *L, int n) {
    LinkList p,r;
    //初始化头结点
    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;
    //r为指向尾部的结点
    r = *L;
    for (int i = 0; i < n; i++) {
        // 生成新的结点
        p = (LinkList)malloc(sizeof(Node));
        // 随机生成100以内的数字
        p->data = rand() % 100 + 1;
        r->next = p;
        r = p;
    }
}
复制代码

这段代码里我们通过把新元素追加到尾部的方法，让新的元素始终维持在链表的末尾，我们称之为尾插法，如图所示：

image-20200406205459394

单链表的整表删除

当我们不打算使用这个单链表时，我们需要把它销毁，其实也就是在内存中将它释放掉，以便于留出空间给其他程序或软件使用。

单链表整表删除的算法思路如下：

  1. 声明指针p和q；
  2. 将第一个结点赋值给p;
  3. 循环：
  • 将p->next赋值给q;
  • 释放p结点；
  • 将q赋值给p；

代码实现如下：

// 初始条件：顺序线性表L已存在，操作结果：将L重置为空表
Status ClearList(LinkList *L) {
    LinkList p, q;
    p = (*L)->next;
    while (p) {
        q = p->next;
        free(p);
        p = q;
    }
    // 头结点的指针域为空
    p->next = NULL;
    return OK;
}
复制代码

”这段算法代码里，常见的错误就是觉得q变量没有存在的必要。在循环体内直接写free(p); p = p->next;即可。可这样会带来什么问题？

要知道p指向一个结点，它除了有数据域，还有指针域。你在做free(p);时，其实是在对它整个结点进行删除和内存释放的工作。这就好比皇帝快要病死了，却还没有册封太子，他儿子五六个，你说要是你脚一蹬倒是解脱了，这国家咋办，你那几个儿子咋办？这要是为了皇位，什么亲兄弟血肉情都成了浮云，一定会打起来。所以不行，皇帝不能马上死，得先把遗嘱写好，说清楚，哪个儿子做太子才行。而这个遗嘱就是变量q的作用，它使得下一个结点是谁得到了记录，以便于等当前结点释放后，把下一结点拿回来补充。“

摘录来自: 程杰. “大话数据结构。” Apple Books.

总结

简单地对单链表结构和顺序存储结构做对比：

image-20200406210458608

通过上面的对比，我们可以得出一些经验性的结论：

  • 若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。
  • 若需要频繁插入和删除时，宜采用单链表结构。
  • 当线性表中的元素个数变化较大或者根本不知道有多大时，最好用单链表结构，这样可以不需要考虑存储空间的大小问题。
  • 而如果事先知道线性表的大致长度，比如一年12个月，一周就是星期一至星期日共七天，这种用顺序存储结构效率会高很多。
这篇关于数据结构与算法-线性表-单链表的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航