数据结构与算法2 -- 链表

前言

上一篇文章讲了，数据结构包括四大逻辑结构和两大物理结构，如下：

逻辑结构
- 集合结构
- 线性结构
- 树形结构
- 图形结构
物理结构
- 顺序存储结构
- 链式存储结构

集合结构没有太多的东西，以后需要的时候再提一下就好。我们知道线性结构有数组、链表、队列等，那么本篇文章就来针对链表进行讲解。

链表

链表在逻辑上是线性的，但是在物理存储上却是链式存储的。因此也就被称为线性表的链式存储。
从名字上看就可以知道，这家伙应该是像铁链一样，一环扣一环的，而事实上也正是如此。

话不多说，链表主要有以下四种：

单向链表。
单向循环链表。单向链表首尾相连。
双向链表。
双向循环链表。

节点

节点是链表中具体存储数据的地方，可以看成是铁链上的环。
节点主要分为两块，数据域和指针域。

单向链表

下面是使用C语言实现的单向链表，以及对应的一些常用方法。
.h文件

#import <Foundation/Foundation.h>

#define ERROR 0
#define SUCCESS 1
typedef int hyStatus;

// 定义 节点 结构体类型
typedef struct Node {
    int data;               // 数据域
    struct Node *next;      // 指针域
}Node;
// 定义 链表 类型
typedef Node* LinkList;

// 创建一个链表
LinkList InitLinkList(void);

// 头插法添加一个节点
hyStatus addNodeToHeader(LinkList *ll, int data);
// 尾插法添加一个节点
hyStatus addNodeToFooter(LinkList ll, int data);
// 指定位置插入一个节点
hyStatus addNodeToCustom(LinkList *ll, int data, int index);

// 删除指定位置的节点
hyStatus delNodeWithIndex(int index, LinkList *ll);

// 查找某个数据第一次出现在哪个节点
int checkIndexInLinkList(LinkList ll, int data);
// 查找指定index处的节点的data值
int checkDataInLinkList(LinkList ll, int index);

// 遍历链表打印其中的data
void foreachLinkList(LinkList ll);

// 销毁一个节点变量
hyStatus freeNode(Node *node);
// 销毁一个链表
hyStatus freeLinkList(LinkList *ll);

.m文件（为了方便就直接使用.m文件写了，反正OC完全支持C语言）

#import "LinkList.h"

// 创建一个节点
Node * InitNode(int data) {
    Node *node = malloc(sizeof(Node));
    if (!node) {
        printf("创建Node失败\n");
        return NULL;
    }
    node->data = data;
    node->next = NULL;
    return node;
}

// 头插法添加一个节点
hyStatus addToHeader(LinkList *ll, Node *node)
{
    node->next = *ll;
    *ll = node;
    return SUCCESS;
}

// 尾插法添加一个节点
hyStatus addToFooter(LinkList ll, Node *node)
{
    LinkList p = ll;
    while (p->next) {
        p = p->next;
    }
    p->next = node;
    return SUCCESS;
}

// 指定位置插入一个节点
hyStatus addToCustom(LinkList *ll, Node *node, int index)
{
    if (index < 1) {
        printf("index最小要为1，表示插入到第一个位置\n");
        return ERROR;
    }
    // 如果要插入的位置是第一个
    if (index == 1) {
        node->next = *ll;
        *ll = node;
    }
    else {
        LinkList p = *ll;
        // 要插入的位置是第2到最后，找到要插入位置的前一个位置
        for (int i = 1; i < index - 1; i++) {
            if (p->next) {
                // 2----length - 1
                p = p->next;
            }
            else {
                // other
                printf("要插入的位置比链表长度还大\n");
                return ERROR;
            }
        }
        node->next = p->next;
        p->next = node;
    }
    return SUCCESS;
}

// 创建一个链表
LinkList InitLinkList() {
    // 开辟一块可以存放一个Node类型变量的堆空间，并且把这块空间的地址返回
    LinkList ll = malloc(sizeof(Node));
    if (!ll) {
        printf("开辟Node空间失败\n");
        return NULL;
    }
    ll->data = 0;
    ll->next = NULL;
    return ll;
}

// 头插法添加一个节点
hyStatus addNodeToHeader(LinkList *ll, int data)
{
    Node *node = InitNode(data);
    if (node) {
        return addToHeader(ll, node);
    }
    return ERROR;
}

// 尾插法添加一个节点
hyStatus addNodeToFooter(LinkList ll, int data)
{
    Node *node = InitNode(data);
    if (node) {
        return addToFooter(ll, node);
    }
    return ERROR;
}

// 指定位置插入一个节点
hyStatus addNodeToCustom(LinkList *ll, int data, int index)
{
    Node *node = InitNode(data);
    if (node) {
        return addToCustom(ll, node, index);
    }
    return ERROR;
}

// 删除指定位置的节点
hyStatus delNodeWithIndex(int index, LinkList *ll)
{
    if (index < 1) {
        printf("节点的最小位置是1, index < 1");
        return ERROR;
    }
    Node *node;
    if (index == 1) {
        if ((*ll)->next) {
            node = *ll;
            *ll = (*ll)->next;
            return freeNode(node);
        }
        else {
            return freeNode(*ll);
        }
    }
    else {
        // 不改动第一个节点，则不需要使用*ll
        /*
         node\*ll-->1-->2-->3
         */
        node = *ll;
        Node *p = NULL;
        for (int i = 1; i < index; i++) {
            if (node->next) {
                p = node;
                node = node->next;
            }
            else {
                printf("要删除的index比链表的长度还大\n");
                return ERROR;
            }
        }
        // 删除中间节点
        p->next = node->next;
        return freeNode(node);
    }
}

// 查找某个数据第一次出现在哪个节点
int checkDataInLinkList(LinkList ll, int data)
{
    int i = 1;
    do {
        if (ll->data == data) {
            return i;
        }
        ll = ll->next;
        i++;
    } while (ll);
    return ERROR;
}

int checkIndexInLinkList(LinkList ll, int index)
{
    if (index < 1) {
        printf("index不能小于1\n");
        return ERROR;
    }
    /*
     ll-->1-->2-->3-->4
     */
    for (int i = 1; i < index; i++) {
        if (ll->next) {
            ll = ll->next;
        }
        else {
            printf("index不能大于链表的总长度\n");
            return ERROR;
        }
    }
    return ll->data;
}

// 遍历链表打印data
void foreachLinkList(LinkList ll)
{
    do {
        printf("--------%d---------\n", ll->data);
        ll = ll->next;
    } while (ll);
}

// 销毁一个节点变量
hyStatus freeNode(Node *node) {
    node->data = 0;
    node->next = NULL;
    free(node);
    node = NULL;
    return SUCCESS;
}

// 销毁一个链表
hyStatus freeLinkList(LinkList *ll) {
    Node *node;
    while ((*ll)->next) {
        // node保存当前节点，*ll指向下一个节点
        node = *ll;
        *ll = (*ll)->next;
        // 释放node节点
        freeNode(node);
    }
    // 释放*ll中next为空的最后一个节点
    return freeNode(*ll);
}

调用，在main.m中调用的。

#import "LinkList.h"

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        // 创建一个链表
        LinkList ll = InitLinkList();
        // 循环添加几个节点
        for (int i = 1; i <= 10; i++) {
            // 头插法
//            addNodeToHeader(&ll, i);
            // 尾插法
            addNodeToFooter(ll, i);
        }
        // 遍历链表
        foreachLinkList(ll);
        
        // 任意插入
        printf("=========================\n");
        addNodeToCustom(&ll, 28, 12);
        foreachLinkList(ll);
        
        // 删除指定位置的节点
        printf("++++++++++++++++++++++++++\n");
        delNodeWithIndex(5, &ll);
        foreachLinkList(ll);
        
        // 查询节点
        int index = checkDataInLinkList(ll, 4);
        printf("查找到的位置是：%d\n", index);
        
        int data = checkIndexInLinkList(ll, 5);
        printf("查找到的数据是：%d\n", data);
    }
    return 0;
}

注释写的很明确，应该就不需要过多的解释了。
需要注意的是，单向链表和单向循环链表都没有使用head节点。

单向循环链表

前面已经说了，单向循环链表就是在单向链表的基础上首尾相连。如下图：

从上图可以看到，单向循环链表的最后一个节点的指针域不再是NULL了，而是保存了这个链表首节点的地址，即指向了链表的首节点。

代码实现：
分文件写有点麻烦，就全部写到main.m文件中了。

#import <Foundation/Foundation.h>

#define ERROR 0
#define SUCCESS 1
typedef int hyStatus;

// 定义 节点 结构体类型
typedef struct Node {
    int data;               // 数据域
    struct Node *next;      // 指针域
}Node;
// 定义 链表 类型
typedef Node* LinkList;

// 创建循环链表
LinkList createLoopLinkList(void) {
    LinkList ll = NULL;     // 始终指向链表头
    LinkList r  = NULL;     // 始终指向链表尾
    int data;
    printf("输入非负整数向链表创建节点数据，输入负数结束创建\nlinklist = ");
    while (1) {
        scanf("%d", &data);
        if (data < 0) {
            break;
        }
        // 第一次输入
        if (ll == NULL) {
            ll = malloc(sizeof(Node));
            // 增加程序健壮性
            if (ll == NULL) {
                exit(0);
            }
            // 赋值，改指针
            ll->data = data;
            ll->next = ll;
            r = ll;
        }
        else {
            Node *node = malloc(sizeof(Node));
            if (node == NULL) {
                break;
            }
            node->data = data;      // 数据
            node->next = r->next;   // r是尾节点，r->next指向头节点，，，这一步是把头节点的地址给node->next，把node的next指向头节点
            r->next = node;         // 把node的地址给r->next，这一步是把node连到了链表的最后，此时node就是尾节点，r是倒数第二个节点
            r = r->next;            // 将r重新改到尾节点
        }
    }
    
    return ll;
}
// 指定位置插入一个节点
hyStatus insertNode(LinkList *ll, int data, int index) {
    if (index < 1) {
        printf("插入位置非法\n");
        return ERROR;
    }
    // 要插入的节点
    Node *node = malloc(sizeof(Node));
    if (node == NULL) {
        exit(0);
    }
    node->data = data;
    // 插入在第一个位置和插入在最后一个位置，链表的结构相同，但意义不同
    // 在最后一个位置插入时，*ll指针指向的仍是头节点
    // 在第一个位置插入时，*ll要修改指向为当前插入的节点，此时新插入的节点是头节点，原本的头节点现在已经是第二个了，这也是为什么参数要传*ll的原因
    if (index == 1) {
        // 首先，要找到最后一个节点
        Node *lastNode = *ll;
        while (lastNode->next != *ll) {
            lastNode = lastNode->next;
        }
        // 找到了最后一个节点，开始插入
        node->next = *ll;
        lastNode->next = node;
        // 改变头节点的位置，为新插入的node
        *ll = node;
    }
    else {
        // 如果要插入第3个位置，则需要找到第2个位置
        // 因为tNode默认就在第1个位置，所以只需要循环index-2次就可找到index前一个位置
        Node *tNode = *ll;
        for (int i = 1; i < index - 1; i++) {
            if (tNode->next == *ll) {
                printf("插入的位置比链表长度还大\n");
                return ERROR;
            }
            tNode = tNode->next;
        }
        node->next = tNode->next;
        tNode->next = node;
    }
    return SUCCESS;
}
// 删除指定位置的节点
hyStatus deleteNode(LinkList *ll, int index) {
    if (index < 1) {
        printf("删除位置非法\n");
        return ERROR;
    }
    // 删除第一个节点
    if (index == 1) {
        // 首先，要找到最后一个节点
        Node *lastNode = *ll;
        while (lastNode->next != *ll) {
            lastNode = lastNode->next;
        }
        // 找到了最后一个节点，开始删除第一个
        lastNode->next = (*ll)->next;
        (*ll)->data = 0;
        (*ll)->next = NULL;
        free(*ll);
        // 改变头节点的位置，为原本的第二个节点
        *ll = lastNode->next;
    }
    else {
        // 如果要删除第3个位置，则需要找到第2个位置
        // 因为tNode默认就在第1个位置，所以只需要循环index-2次就可找到index前一个位置
        Node *tNode = *ll;
        for (int i = 1; i < index - 1; i++) {
            tNode = tNode->next;
            if (tNode->next == *ll) {
                printf("删除的位置比链表长度还大\n");
                return ERROR;
            }
        }
        // 开始删除
        Node *delNode = tNode->next;
        tNode->next = delNode->next;
        delNode->data = 0;
        delNode->next = NULL;
        free(delNode);
    }
    return SUCCESS;
}
// 查询某值在链表中的位置
int findNode(LinkList ll, int data) {
    Node *p = ll;
    int index = 1;
    do {
        if (p->data == data) {
            return index;
        }
        p = p->next;
        index++;
    } while (p != ll);
    printf("没有找到此节点\n");
    return ERROR;
}
// 遍历循环链表
void foreachLinkList(LinkList ll) {
    Node *p = ll;
    do {
        printf("%-5d", p->data);
        p = p->next;
    } while (p != ll);
    printf("\n");
}


int main(int argc, const char * argv[]) {
    @autoreleasepool {
        // 创建链表
        LinkList ll = createLoopLinkList();
        foreachLinkList(ll);
        // 插入节点
        printf("++++++++++++++++++++++++++\n");
        insertNode(&ll, 0, 1);
        foreachLinkList(ll);
        // 删除节点
        printf("--------------------------\n");
        deleteNode(&ll, 1);
        foreachLinkList(ll);
        // 查询节点
        printf("==========================\n");
        printf("查找到的位置是：%d\n", findNode(ll, 10));
    }
    return 0;
}

双向链表

在上面的单向链表中可以发现一个问题，就是如果想要知道某个节点的地址，那么就必须先找到它的前一个节点，通过前一个节点的next才能获取这个节点的地址。同时我们也不能通过当前节点获得前一个节点的地址，在操作过程中就会感觉很麻烦。

而接下来要说的双向链表就很好的解决了这种问题，单向链表的节点是只保存了数据和下一个节点的地址，那么能不能把前一个节点的地址也保存起来呢？答案是肯定的。具体样式如下图：

节点结构不再是只有两部分了，而是有了三部分：数据域、前驱、后继。

数据域用来存储数据。
前驱保存前一个节点的地址。
后继保存下一个节点的地址。

head节点

在贴代码之前先说一下head节点，通过上面的单向链表代码可以知道，无论是在插入节点还是删除节点，都不可避免的需要判断要插入的位置是不是第一个？要删除的节点是不是第一个节点？因为在进行插入和删除时，第一个节点和其他的节点需要进行不同的操作。

那么如何让第一个节点和其他节点操作相同呢？这里就引入了头节点(head节点)的概念。其实头节点应该在链表创建的时候默认创建好，但是不让它存储数据。这时第一个节点实质上是第二个节点，因为真正的第一个节点是head节点，这样就保证了插入和删除节点的时候第一个节点和其他节点进行的操作相同。

光说不练假把式，看代码：

#import <Foundation/Foundation.h>

#define ERROR 0
#define SUCCESS 1
typedef int hyStatus;

typedef struct _Node {
    int data;
    struct _Node *frontNode;     // 前驱
    struct _Node *nextNode;      // 后继
} Node;

typedef Node* LinkList;         // 双向链表

// 单向链表中没有使用`head`节点，在这个双向链表中就使用一次`head`节点吧
// 创建一个链表
LinkList createLinkList() {
    // 新创建的这个节点就是`head`节点
    LinkList ll = malloc(sizeof(Node));
    // 默认创建成功了，就不考虑开辟空间失败了😄
    ll->data = 0;       // 这里就用来保存节点的数量好了，反正闲着也是闲着
    ll->frontNode = NULL;
    ll->nextNode  = NULL;
    
    // 添加节点
    Node *lastNode = ll;      // 记录最后一个节点
    int data = 0;
    printf("请输入节点数据，负数表示输入结束:\n");
    while (1) {
        scanf("%d", &data);
        if (data < 0) {
            break;
        }
        // 创建节点
        Node *node = malloc(sizeof(Node));
        node->data = data;
        node->nextNode  = NULL;
        // 将节点添加到链表后面
        node->frontNode = lastNode;
        lastNode->nextNode = node;
        lastNode = node;
        // 链表的节点数量++
        ll->data++;
    }
    
    return ll;
}
// 插入一个节点
hyStatus insertNode(LinkList *ll, int data, int index) {
    if (index < 1 || index > (*ll)->data + 1) {
        printf("插入的位置不合法\n");
        return ERROR;
    }
    // 创建一个节点
    Node *node = malloc(sizeof(Node));
    node->data = data;
    node->frontNode = NULL;
    node->nextNode  = NULL;
    
    // 开始插入，因为有head节点的存在，插入第1个位置和其他位置没太大区别
    Node *p = *ll;
    for (int i = 1; i < index; i++) {
        // 为了保险起见，还是加上这个判断吧
        if (p->nextNode) {
            p = p->nextNode;
        }
    }
    // 开始插入节点
    if (p->nextNode) {
        node->nextNode = p->nextNode;
        p->nextNode->frontNode = node;
    }
    p->nextNode = node;
    node->frontNode = p;
    // 链表长度++
    (*ll)->data++;
    
    return SUCCESS;
}
// 删除一个节点
hyStatus deleteNode(LinkList *ll, int index) {
    if (index < 1 || index > (*ll)->data) {
        printf("删除的位置不合法\n");
        return ERROR;
    }
    Node *p = *ll;
    for (int i = 1; i < index; i++) {
        if (p->nextNode) {
            p = p->nextNode;
        }
    }
    // 开始删除
    Node *delNode = p->nextNode;        // 保存要删除的那个节点
    p->nextNode = delNode->nextNode;
    // 若删除的是最后一个节点，是没有nextNode的
    if (delNode->nextNode) {
        delNode->nextNode->frontNode = p;
    }
    
    // 开始释放要删除的节点
    delNode->data = 0;
    delNode->nextNode = NULL;
    delNode->frontNode = NULL;
    // 链表长度--
    (*ll)->data--;
    
    return SUCCESS;
}
// 查询节点
int findNode(LinkList ll, int data) {
    Node *p = ll;
    for (int i = 1; i <= ll->data; i++) {
        // 因为p最开始是指向header节点的，先向后移一个节点
        if((p = p->nextNode)) {
            // 判断是否找到
            if (p->data == data) {
                return i;
            }
        }
        else {
            printf("没有找到\n");
            return 0;
        }
    }
    printf("没有找到\n");
    return 0;
}
// 遍历链表
void foreachLinkList(LinkList ll) {
    Node *p = ll->nextNode;     // 第一个节点
    while (p) {
        printf("%-5d", p->data);
        p = p->nextNode;
    }
    printf("\n");
}


int main(int argc, const char * argv[]) {
    @autoreleasepool {
        // 创建链表
        LinkList ll = createLinkList();
        foreachLinkList(ll);        // 遍历链表
        
        // 插入节点
        printf("+++++++++++++++++++++++++++++++++++\n");
        insertNode(&ll, 0, 4);
        foreachLinkList(ll);
        
        // 删除节点
        printf("-----------------------------------\n");
        deleteNode(&ll, 4);
        foreachLinkList(ll);
        
        // 查询节点
        printf("===================================\n");
        printf("查询的位置是：%d\n", findNode(ll, 7));
    }
    return 0;
}

双向循环链表

图有点丑，但是相信看完了上面那些，理解这个还是很轻松的。

简而言之，首节点的前驱保存了尾节点的地址。尾节点的后继保存了首节点的地址。这样就构成了双向循环。

对于使用了head节点来说，上图中的第一个节点就是head节点，第二个节点才是需求上需要使用的第一个节点。

双向循环链表代码实现：

#import <Foundation/Foundation.h>

#define ERROR 0
#define SUCCESS 1
typedef int hyStatus;

typedef struct _Node {
    int data;
    struct _Node *frontNode;     // 前驱
    struct _Node *nextNode;      // 后继
} Node;

typedef Node* LinkList;         // 双向链表

// MARK: - 单向链表和单向循环链表都没有使用head，那么在双向链表和双向循环链表中就都使用head好了，😂
// 创建链表
LinkList createLinkList() {
    // MARK: - 全部复制过来，把首尾相连就好了
    // 新创建的这个节点就是`head`节点
    LinkList ll = malloc(sizeof(Node));
    // 默认创建成功了，就不考虑开辟空间失败了😄
    ll->data = 0;       // 这里就用来保存节点的数量好了，反正闲着也是闲着
    ll->frontNode = NULL;
    ll->nextNode  = NULL;
    
    // 添加节点
    Node *lastNode = ll;      // 记录最后一个节点
    int data = 0;
    printf("请输入节点数据，负数表示输入结束:\n");
    while (1) {
        scanf("%d", &data);
        if (data < 0) {
            break;
        }
        // 创建节点
        Node *node = malloc(sizeof(Node));
        node->data = data;
        node->nextNode  = NULL;
        // 将节点添加到链表后面
        node->frontNode = lastNode;
        lastNode->nextNode = node;
        lastNode = node;
        // 链表的节点数量++
        ll->data++;
    }
    
    // 首尾相连
    lastNode->nextNode = ll;
    ll->frontNode = lastNode;
    
    return ll;
}
// 插入一个节点
hyStatus insertNode(LinkList *ll) {
    int data = 0, index = 0;
    // 输入位置
    printf("请输入插入节点的位置：");
    scanf("%d", &index);
    printf("\n");
    // 判断输入的位置是否合法
    if (index < 1 || index > (*ll)->data + 1) {
        printf("插入的位置不合法\n");
        return ERROR;
    }
    // 输入数据
    printf("请输入插入节点的数据：");
    scanf("%d", &data);
    printf("\n");
    
    // 创建节点
    Node *node = malloc(sizeof(Node));
    node->data = data;
    node->nextNode = NULL;
    node->frontNode = NULL;
    
    // 找位置
    Node *p = *ll;
    for (int i = 1; i < index; i++) {
        // 因为index经过判断，是合法的，所以不用考虑p->nextNode循环的问题
        p = p->nextNode;
    }
    // 开始插入
    node->nextNode = p->nextNode;
    p->nextNode->frontNode = node;
    p->nextNode = node;
    node->frontNode = p;
    // 长度++
    (*ll)->data++;
    
    return SUCCESS;
}
// 删除一个节点
hyStatus deleteNode(LinkList *ll) {
    int index = 0;
    printf("请输入要删除节点的位置：");
    scanf("%d", &index);
    printf("\n");
    // 判断输入的位置是否合法
    if (index < 1 || index > (*ll)->data) {
        printf("删除的位置不合法\n");
        return ERROR;
    }
    // 开始删除节点
    Node *p = *ll;
    for (int i = 1; i < index; i++) {
        // 因为index经过判断，是合法的，所以不用考虑p->nextNode循环的问题
        p = p->nextNode;
    }
    // 开始删除
    Node *delNode = p->nextNode;
    p->nextNode = delNode->nextNode;
    delNode->nextNode->frontNode = p;
    
    // 释放删除的节点
    delNode->data = 0;
    delNode->frontNode = NULL;
    delNode->nextNode  = NULL;
    free(delNode);
    
    // 链表长度--
    (*ll)->data--;
    return SUCCESS;
}
// 查询循环链表
int findNode(LinkList ll) {
    int data = 0;
    printf("请输入要查询的数据：");
    scanf("%d", &data);
    printf("\n");
    
    // 开始查询
    Node *p = ll->nextNode;
    int index = 1;
    while (p != ll) {
        if (p->data == data) {
            return index;
        }
        p = p->nextNode;
        index++;
    }
    printf("没有找到这个节点\n");
    return ERROR;
}
// 遍历循环链表
void foreachLinkList(LinkList ll) {
    Node *p = ll->nextNode;
    int index = 1;
    while (p != ll) {
        printf("%-5d", p->data);
        p = p->nextNode;
        index++;
    }
    printf("\n");
}


int main(int argc, const char * argv[]) {
    @autoreleasepool {
        // 创建链表
        LinkList ll = createLinkList();
        foreachLinkList(ll);
        
        // 插入节点
        printf("++++++++++++++++++++++++++++\n");
        insertNode(&ll);
        foreachLinkList(ll);
        
        // 删除节点
        printf("----------------------------\n");
        deleteNode(&ll);
        foreachLinkList(ll);
        
        // 查找节点
        printf("============================\n");
        printf("查找数据的位置是：%d\n", findNode(ll));
        
    }
    return 0;
}

好了双向循环链表到这也已经说完了，可能会感觉这篇文章草草了事，但是我实在是觉得这些没什么东西，细心思考应该都能实现这些功能。所以大部分文字都是用来解释一些名词，概念等。

至于逻辑思路，一切尽在代码中，一切尽在注释中。

总结

这篇文章主要讲了线性表的链式存储结构------链表。包括了单向链表、单向循环链表、双向链表、双向循环链表以及他们对应的创建链表、插入节点、删除节点、查询数据等功能。

C语言函数------传值和传地址

之所以说这个，是因为我突然想到了代码中用到了一些传地址的地方，可能对于一些C语言基础不是太好的读者来说有点迷茫。

首先我相信大家应该都知道C语言函数的传参，实质是把变量的空间拷贝一份传进函数实现。如：

// 将传进来的参数+1
void sumOne(int a) {
    a = a + 1;
}

int x = 10;
// 在调用这个方法的时候，实质是把x拷贝一份，然后把拷贝的变量传进函数实现
sumOne(x);

因为是把变量拷贝了一份传到方法实现，并且这个拷贝出来的变量的作用域就只在sumOne函数内。因此在sunOne函数内的a = a + 1;并不会改变函数外部的x的值。

如果我想让函数改变外部变量的值怎么办？很简单，传地址。如下：

// 将传进来的参数+1
void sumOne(int *a) {
    // a是地址，*a代表通过地址a找到对应的那块空间
    *a = *a + 1;
}

int x = 10;
int *x1 = &x;       // 将x的地址赋值给指针变量x1
// 这里调用方法的时候会将指针变量x1拷贝一份传进函数实现
// 即将x的地址拷贝一份传进函数实现
sumOne(x1);

这样，就可以达到在函数内部修改外部变量值的效果了。

传地址的用法可不仅仅是这样，我们知道在OC中有block的存在来解决回调的需求，那么C语言的回调函数需要怎么搞？
没错，就是使用这个传地址，只不过传的地址是回调函数的函数地址，就这么简单。

本文地址https://juejin.cn/post/6844904118130065422