当前位置:   article > 正文

【C语言 数据结构】单链表的学习使用_首元节点

首元节点

本文借鉴点击跳转

链表的介绍

链表是什么

链表又称单链表、链式存储结构,用于存储逻辑关系为“一对一”的数据。

和顺序表不同,使用链表存储数据,不强制要求数据在内存中集中存储,各个元素可以分散存储在内存中。例如,使用链表存储 {1,2,3},各个元素在内存中的存储状态可能是:

image-20221029155013960

可以看到,数据不仅没有集中存放,在内存中的存储次序也是混乱的。那么,链表是如何存储数据间逻辑关系的呢?

链表存储数据间逻辑关系的实现方案是:为每一个元素配置一个指针,每个元素的指针都指向自己的直接后继元素,如下图所示:

image-20221029155043169

显然,我们只需要记住元素 1 的存储位置,通过它的指针就可以找到元素 2,通过元素 2 的指针就可以找到元素 3,以此类推,各个元素的先后次序一目了然。

像图 2 这样,数据元素随机存储在内存中,通过指针维系数据之间“一对一”的逻辑关系,这样的存储结构就是链表。


结点

很多教材中,也将“结点”写成“节点”,它们是一个意思。

在链表中,每个数据元素都配有一个指针,这意味着,链表上的每个“元素”都长下图这个样子:

image-20221029155148704

数据域用来存储元素的值,指针域用来存放指针。数据结构中,通常将图 3 这样的整体称为结点。

也就是说,链表中实际存放的是一个一个的结点,数据元素存放在各个结点的数据域中。举个简单的例子,图 2 中 {1,2,3} 的存储状态用链表表示,如下图所示:

image-20221029155208848


在 C 语言中,可以用结构体表示链表中的结点,例如:

typedef char ElemType;

typedef struct node {
    ElemType data;
    struct Node *link;
} Node;
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

我们习惯将结点中的指针命名为 next,因此指针域又常称为“Next 域”。


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

图 4 所示的链表并不完整,一个完整的链表应该由以下几部分构成:

  1. 头指针:一个和结点类型相同的指针,它的特点是:永远指向链表中的第一个结点。上文提到过,我们需要记录链表中第一个元素的存储位置,就是用头指针实现。
  2. 结点:链表中的节点又细分为头结点、首元结点和其它结点:
    • 头结点:某些场景中,为了方便解决问题,会故意在链表的开头放置一个空结点,这样的结点就称为头结点。也就是说,头结点是位于链表开头、数据域为空(不利用)的结点。
    • 首元结点:指的是链表开头第一个存有数据的结点。
    • 其他节点:链表中其他的节点。

也就是说,一个完整的链表是由头指针和诸多个结点构成的。每个链表都必须有头指针,但头结点不是必须的。

例如,创建一个包含头结点的链表存储 {1,2,3},如下图所示:

image-20221029155406257

再次强调,头指针永远指向链表中的第一个结点。换句话说,如果链表中包含头结点,那么头指针指向的是头结点,反之头指针指向首元结点。


链表的基本操作

插入

同顺序表一样,向链表中增添元素,根据添加位置不同,可分为以下 3 种情况:

  • 插入到链表的头部,作为首元节点;
  • 插入到链表中间的某个位置;
  • 插入到链表的最末端,作为链表中最后一个结点;

对于有头结点的链表,3 种插入元素的实现思想是相同的,具体步骤是:

  1. 将新结点的 next 指针指向插入位置后的结点;
  2. 将插入位置前结点的 next 指针指向插入结点;

例如,在链表 {1,2,3,4} 的基础上分别实现在头部、中间、尾部插入新元素 5,其实现过程如图1 所示:

image-20221029155611799

代码实现

// TODO 添加节点,在最后的位置插入
void appendTail(Node *list, ElemType data) {
//    Node* head=list;
    Node *node = (Node *) malloc(sizeof(Node));
    node->data = data;
    node->link = NULL;
    while (list->link) {
        list = list->link;
    }
    list->link = node;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

删除

从链表中删除指定数据元素时,实则就是将存有该数据元素的节点从链表中摘除。

对于有头结点的链表来说,无论删除头部(首元结点)、中部、尾部的结点,实现方式都一样,执行以下三步操作:

  1. 找到目标元素所在结点的直接前驱结点;
  2. 将目标结点从链表中摘下来;
  3. 手动释放结点占用的内存空间;

从链表上摘除目标节点,只需找到该节点的直接前驱节点 temp,执行如下操作:

temp->next=temp->next->next;
  • 1

例如,从存有 {1,2,3,4} 的链表中删除存储元素 3 的结点,则此代码的执行效果如图 3 所示:

image-20221029155825191


代码实现

//TODO 删除指定位置的节点
void delLink(Node *list, int loc) {
    if(loc<1){//判断和删除位置是否有误
        printf("删除位置错误!!!");
    }else{
        for (int i = 0; i < loc - 1; ++i) {
            list = list->link;//找到删除位置的前一个节点
        }
        Node *node = list->link;
        node = node->link;//删除位置的后一个节点
        free(list->link);//释放删除的节点
        list->link = node;//指向新的地址
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

完整代码如下所示

//
// Created by HR on 2022/9/27.
//
#include "stdio.h"
#include "windows.h"
#include "stdlib.h"

typedef char ElemType;

typedef struct node {
    ElemType data;
    struct Node *link;
} Node;

// TODO 初始化链表
Node *creatHead() {
    Node *head;
    head = (Node *) malloc(sizeof(Node));
    head->link = NULL;
    return head;
}

// TODO 添加节点,在最后的位置插入
void appendTail(Node *list, ElemType data) {
//    Node* head=list;
    Node *node = (Node *) malloc(sizeof(Node));
    node->data = data;
    node->link = NULL;
    while (list->link) {
        list = list->link;
    }
    list->link = node;
}

// TODO 打印输出
void printList(Node *list)//遍历操作
{
    list = list->link;//指向头节点
    while (list)//遍历打印
    {
        printf("%c", list->data);
        list = list->link;
    }
    printf("\n");
}

// TODO 删除指定值的节点
void deleteTail(Node *list, ElemType data)//删除
{
    Node *pre = list;
    Node *current = list->link;
    while (current) {
        if (current->data == data) {
            pre->link = current->link;
            free(current);
            break;//退出循环
        }
        pre = current;
        current = current->link;
    }
}

// TODO 在指定位置插入指定的值
void insertLink(Node *list, int loc, ElemType data) {
    if(loc<1){//判断插入位置是否有误
        printf("插入位置错误!!!");
    }else{
        Node *node = (Node *) malloc(sizeof(Node));// 需要插入的节点
        node->data = data;//修改数据域
        for (int i = 0; i < loc - 1; ++i) {
            list = list->link;//找到插入位置前一个节点
        }
        node->link = list->link;//为新建节点的指针域赋值
        list->link = node;//修改插入节点前一位的指针域地址
    }
}

//TODO 删除指定位置的节点
void delLink(Node *list, int loc) {
    if(loc<1){//判断和删除位置是否有误
        printf("删除位置错误!!!");
    }else{
        for (int i = 0; i < loc - 1; ++i) {
            list = list->link;//找到删除位置的前一个节点
        }
        Node *node = list->link;
        node = node->link;//删除位置的后一个节点
        free(list->link);//释放删除的节点
        list->link = node;//指向新的地址
    }
}

// TODO 有序链表合并
void MergeList(Node *a, Node *b, Node *c) {
    Node *aNext = a->link;
    Node *bNext = b->link;
    while (aNext && bNext) {
        Node *tmp = (Node *) malloc(sizeof(Node));
        if (aNext->data > bNext->data) {
            tmp->data = bNext->data;
            tmp->link = c->link;
            c->link = tmp;
            bNext = bNext->link;
        } else {
            tmp->data = aNext->data;
            tmp->link = c->link;
            c->link = tmp;
            aNext = aNext->link;
        }
    }
    while (aNext) {
        Node *tmp = (Node *) malloc(sizeof(Node));
        tmp->data = aNext->data;
        tmp->link = c->link;
        c->link = tmp;
        aNext = aNext->link;
    }
    while (bNext) {
        Node *tmp = (Node *) malloc(sizeof(Node));
        tmp->data = bNext->data;
        tmp->link = c->link;
        c->link = tmp;
        bNext = bNext->link;
    }
}

int main() {
    Node *head = creatHead();
    char arr[] = "asdfghjkl";
    for (int i = 0; i < strlen("asdfghjkl"); i++) {
        appendTail(head, arr[i]);
    }
    printList(head);
    deleteTail(head, 'b');
    printf("链表数据展示:");
    printList(head);
    insertLink(head, 4, 'z');
    printf("在第四个位置插入z:");
    printList(head);
    delLink(head, 4);
    printf("删除第四个位置的元素:");
    printList(head);

    // 合并
    Node *a = creatHead();
    char arr1[] = "3789";
    for (int i = 0; i < strlen("3789"); i++) {
        appendTail(a, arr1[i]);
    }
    Node *b = creatHead();
    char arr2[] = "257";
    for (int i = 0; i < strlen("257"); i++) {
        appendTail(b, arr2[i]);
    }
    printf("链表a的数据:");
    printList(a);
    printf("链表b的数据:");
    printList(b);
    Node *c = creatHead();
    MergeList(a, b, c);
    printf("合并后的链表数据:");
    printList(c);

    return 1;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165

运行结果展示

链表数据展示:asdfghjkl
在第四个位置插入z:asdzfghjkl
删除第四个位置的元素:asdfghjkl
链表a的数据:3789
链表b的数据:257
合并后的链表数据:9877532

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小丑西瓜9/article/detail/429840
推荐阅读
相关标签
  

闽ICP备14008679号