数据结构简单入门/复习（一）-线性链表（C语言）（2020/11/18更新）

MWHLS • • C, 数据结构, 计算机语言
已阅： 73

这个系列是为了简单入门与复习而作的，因此内容并不完全，如本篇的线性链表除了创建、插入、删除外，还有一些较为复杂的操作，并且，本篇内容提到的也不涉及任何判断成功与否的代码，但个人认为，只要这三个部分掌握了，剩余的基础用法都能很快解决。

2020/11/18：
更新了较完整的链表代码。
文章排版美化。

2022/1/23：修改为Markdown格式。

目录
基础知识
定义与创建
链表的创建及结点添加
插入结点
删除结点
一份迟来的完整代码

基础知识

指针的基本使用。

结构体的定义。

分配内存：
使用 待分配变量 = (分配变量数据类型)malloc(分配大小)；
其中，分配大小一般用 sizeof(数据类型) 获得，如果需要分配N倍的空间，使用sizeof(数据类型)*N
假设要给 指针node 分配五个 Node*类型 的空间，就应该

node = (Node*)malloc(sizeof(Node)*5);

释放指针内存：
即时释放，可以防止过多过期数据占据内存。free(指针名称)
例如

int *node;
node = (int*)malloc(sizeof(int));
free(node); //这样就释放掉了上一行分配的内存。

free()是用来释放内存的，一个单纯指向性的指针并不需要释放，但如果这个指向性的指针 被分配了内存 来存储临时数据，则应该释放。（这里入门搞不懂，问题不大，多写点就有感觉了。）

定义与创建

线性链表的存取必须由头指针开始，头指针仅用来指向第一个数据结点的位置。
线性链表包括两个域，数据域与指针域，数据域用来存储数据，而指针域用来指向链表的下一个结点（Node）。
且因为线性链表的最后结点没有后继结点，因此其指针域为空（NULL）。

即，对于一个有三个数据的链表结构 |data - next|，它的形式应该是这样的：
|empty - first| -> |data1 - second| -> |data2 - third| -> |data3 - NULL|

#define ElemType int      //元素类型设置为int
typedef struct LNode{    //链表结构定义
    ElemType data;       //数据域
    struct LNode *next;  //指针域
}LNode;

链表的创建及结点添加

#include <stdio.h>
#include <stdlib.h>

#define ElemType int      //元素类型设置为int
typedef struct LNode{    //链表结构定义
    ElemType data;       //数据域
    struct LNode *next;  //指针域
}LNode;

int main(){

    //链表头结点创建
    LNode *LHead;
    LHead = (LNode*)malloc(sizeof(LNode));    //使用malloc为头结点分配内存空间
    LHead->next = (LNode*)malloc(sizeof(LNode));    //为头结点的下一个结点，即第一个数据结点分配内存。

    //设置一个临时变量存储当前结点所在的位置。
    LNode *LTemp;

    //将临时变量调整到第一个数据结点。
    LTemp = LHead->next;

    //通过临时变量  对第一个数据结点赋值，及下一个结点的创建。
    LTemp->data = 1;     //等效为 LHead->next->data = 1;
    LTemp->next = (LNode*)malloc(sizeof(LNode));    //同上等效

    //将临时变量设置为第二个数据结点。
    LTemp = LTemp->next;

    //通过临时变量  为第二个数据结点赋值，且第二个结点为最后一个结点。
    LTemp->data = 22;
    LTemp->next = NULL;    //表示第二个结点的下一个结点地址是NULL，即没有下一个结点

    system(PAUSE);      //在运行结束后停留
    return 0;
}

通过这个方法，即可创建一个
|empty - first| -> |1 - second| ->|22 - NULL|
的线性链表。

插入结点

目的：只知道A地址，结点B需要插入到A与C当中，此时A的下一个结点是C（A->next == C;）

原理：先将B的next设置为C，再将A的next设置为B
原因：这样可以在 不加入临时变量 记录C的地址 的前提下，将B插入。

B->next = A->next;
A->next = B;

删除结点

目的：只知道A地址，A的下一个是B，B的下一个是C，需要删除B

原理：添加临时变量记录C的地址，将B先释放，再设置C。或记录B，先设置C再释放B。

LNode *temp;
temp = A->next->next;    //将temp设置成A的下一个的下一个，即C
free(A->next);    //释放B结点
A->next = temp;    //将A的下一个设置为C

这样不释放temp，因为此时temp存储的是C的内存，不是新增加的临时内存，这个temp只是指示器，不需要释放。

一份迟来的完整代码

这篇文章写完后的第三个月，在做题的时候，用到了链表，于是就写了下完整的单链表代码，
然后发现之前因为用不习惯wordpress，排版有点丑，改了下。

#include <stdio.h>
#include <stdlib.h>

typedef struct lNode{
    int data;
    struct lNode *next;
}lNode;

lNode *createLink();
void insertLNode(lNode *node, int newData);
void deleteLNode(lNode *node);
void printLink(lNode *head);

int main() {
    lNode *head = createLink();
    printf(输出链表内容：);
    printLink(head);

    system(PAUSE);
    return 0;
}

lNode *createLink() {       //创建链表，并返回一个带头结点的链表。
    lNode *head = (lNode*)malloc(sizeof(lNode));
    lNode *node = head;
    head->next = NULL;
    int i = 0;
    for (i = 1; i <= 5; i++) {   //链表结点自动生成，用作测试
        insertLNode(node, i);
        node = node->next;
    }
    return head;
}

void insertLNode(lNode *node, int newData) {    //插入结点
    if (node->next == NULL) {
        node->next = (lNode*)malloc(sizeof(lNode));
        node->next->next = NULL;
        node->next->data = newData;
    }
    else {
        lNode *temp = (lNode*)malloc(sizeof(lNode));
        temp->next = node->next;
        temp->data = newData;
        node->next = temp;
    }
}

void deleteLNode(lNode *node) {     //删除结点
    if (node->next == NULL) {
        free(node);
    }
    else {
        lNode *temp;
        temp = node->next;
        node->data = temp->data;
        node->next = temp->next;
        free(temp);
    }
}

void printLink(lNode *head) {       //打印带头结点的链表，若不带头结点，将第一行head->next改为head即可。
    lNode *node = head->next;
    while (node) {
        printf(%d , node->data);
        node = node->next;
    }
    printf(\n);
}

版权声明：
作者：MWHLS
链接：https://mwhls.top/324.html
来源：无镣之涯
文章版权归作者所有，未经允许请勿转载。

THE END
分享
二维码
打赏
< <上一篇
下一篇>>