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

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

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);
}

You may also like...

发表评论

您的电子邮箱地址不会被公开。

46 − 43 =