简介

此模块为学校数据结构必修课学习内容的记录与分享

全文大体分为一下几个部分

• 模块解释
• 可视化GIF合集
• 整体复现
• 最终结果

模块解释

* 单链表的空间储存方式

这里的头节点还存在一些问题待修改

创建单链表

typedef struct LinkNode {
    char data;
    struct LinkNode *next;
} LNode, *LinkList, *NodePtr;

为什么定义这么多的别名？每个别名是什么意思

作用：提高代码的可读性，使代码便于理解

LNode：链表节点，用于sizeof函数求得结构体大小

NodePtr：指向链表节点的指针

LinkList：这里用来创建单链表头节点【为什么不直接使用NodePtr别名？】【进行实验发现可以使用NodePtr，这里使用LinkList是为了方便代码理解】

初始化单链表头节点

NodePtr IniLinkList() {
    NodePtr tempHeader = (NodePtr)malloc(sizeof(LNode));
    tempHeader->data = '0';
    tempHeader->next = NULL;
    return tempHeader;
}

这里使用 LNode 获得结构体空间大小

不能使用 NodePtr 这只会获取指针的空间大小

打印链表内容

void PrintList(NodePtr paraHeader) {
    NodePtr p = paraHeader->next;
    while(p!=NULL) {
        printf("%c", p->data);
        p = p->next;
    }
    printf("\n");
}

打印单链表节点内数据地址【包括头节点】

void PrintListMemory(NodePtr paraHeader) {
    printf("The position of each node is :%d\n (The line above is help to realize the way the Single Link List store the data.)\n",sizeof(LNode));
    NodePtr p = paraHeader;
    while(p!=NULL) {
        printf("At address %ld, data = %c, next = %ld \r\n", p, p->data, p->next);
        p = p->next;
    }
    printf("\n");
}

在链表末尾插入元素

void AppendElement(NodePtr paraHeader, char paraData) {
    NodePtr q,p;

    q = (NodePtr)malloc(sizeof(LNode));
    q->data = paraData;
    q->next = NULL;

    p = paraHeader;
    while(p->next!=NULL) {
        p = p->next;
    }

    p->next = q;
}

在指定位置插入元素

void InsertElement(NodePtr paraHeader, char paraData, int paraIndex) {
    NodePtr q,p;

    p = paraHeader;
    for(int i = 0 ; i < paraIndex; i++) {
        p = p->next;
        if(p == NULL) {  // 这里忘记添加边界检查判断了
            printf("Index out of range!\r\n");
            return;
        }
    }

    q = (NodePtr)malloc(sizeof(LNode));
    q->data = paraData;

    printf("Linking~\n");
    q->next = p->next;
    p->next = q;
}

先移动到指定节点，然后再添加内容

删除指定内容的节点

void DeleteElement(NodePtr paraHeader, char paraData) {
    NodePtr p,q;

    p = paraHeader;
    while(p->next!=NULL && p->next->data!=paraData) {
        p = p->next;
    }

    if(p->next==NULL) {
        printf("Cannot delete %c\n", paraData);
        return;
    }

    q = p->next;
    p->next = q->next;

    free(q);
}

通过指针移动的方式删除指定内容的节点

不要忘记用q指向需要删除的节点然后free掉，避免野指针出现

测试函数

void TestAll() {
    NodePtr TempList = IniLinkList();
    PrintList(TempList);

    AppendElement(TempList, 'H');
    AppendElement(TempList, 'E');
    AppendElement(TempList, 'L');
    AppendElement(TempList, 'L');
    AppendElement(TempList, 'O');
    AppendElement(TempList, '!');
    printf("After appendElement:\n");
    PrintList(TempList);
    printf("The position of each element:\n");
    PrintListMemory(TempList);

    DeleteElement(TempList, 'E');
    DeleteElement(TempList, 'A');
    DeleteElement(TempList, 'O');
    printf("After deleteElement:\n");
    PrintList(TempList);
    printf("The position of each element:\n");
    PrintListMemory(TempList);

    InsertElement(TempList, 'O', 1);
    printf("After insertElement\n");
    PrintList(TempList);
    printf("The position of each element:\n");
    PrintListMemory(TempList);

}

Main函数

int main() {
    // printf("%d\n",sizeof(LNode));
    // printf("%d\n",sizeof(*NodePtr));
    // 这只是一个指针别名，因此不能进行解指针操作
    // 下来看下为什么内存会不一样
    TestAll();
}

可视化GIF合集

尾插法

在单链表尾部插入新节点

插入指定元素

在第二个节点插入存储数据值为12的节点：

元素查找

在单链表中查找数值为38的节点并且返回节点序号（这里是3）

元素删除

删除数值为38的节点

注意，不能直接free掉指定节点，否则会丢失后面的数据

整体代码复现

#include<stdio.h>
#include<malloc.h>

typedef struct LinkNode {
    char data;
    struct LinkNode *next;
} LNode, *LinkList, *NodePtr;
// 为什么定义这么多的别名？每个别名是什么意思
// 作用：提高代码的可读性，使代码便于理解
// LNode：链表节点，用于sizeof函数求得结构体大小
// NodePtr：指向链表节点的指针
// LinkList：这里用来创建单链表头节点【为什么不直接使用NodePtr别名？】【进行实验发现可以使用NodePtr，这里使用LinkList是为了方便代码理解】

// 初始化单链表头节点
NodePtr IniLinkList() {
    NodePtr tempHeader = (NodePtr)malloc(sizeof(LNode));
    tempHeader->data = '0';
    tempHeader->next = NULL;
    return tempHeader;
}

// 打印链表内容
void PrintList(NodePtr paraHeader) {
    NodePtr p = paraHeader->next;
    while(p!=NULL) {
        printf("%c", p->data);
        p = p->next;
    }
    printf("\n");
}

// 打印单链表节点内数据地址【包括头节点】
void PrintListMemory(NodePtr paraHeader) {
    printf("The position of each node is :%d\n (The line above is help to realize the way the Single Link List stores the data.)\n",sizeof(LNode));
    NodePtr p = paraHeader;
    while(p!=NULL) {
        printf("At address %ld, data = %c, next = %ld\n", p, p->data, p->next);
        p = p->next;
    }
    printf("----------------------------------------\n");
}

// 在链表末尾插入元素
void AppendElement(NodePtr paraHeader, char paraData) {
    NodePtr q,p;

    q = (NodePtr)malloc(sizeof(LNode));
    q->data = paraData;
    q->next = NULL;

    p = paraHeader;
    while(p->next!=NULL) {
        p = p->next;
    }

    p->next = q;
}

// 在指定位置插入元素
void InsertElement(NodePtr paraHeader, char paraData, int paraIndex) {
    NodePtr q,p;

    p = paraHeader;
    for(int i = 0 ; i < paraIndex; i++) {
        p = p->next;
        if(p == NULL) {  // 这里忘记添加边界检查判断了
            printf("Index out of range!\r\n");
            return;
        }
    }

    q = (NodePtr)malloc(sizeof(LNode));
    q->data = paraData;

    printf("Insert the data %c in the position %d\n",paraData,paraIndex);
    q->next = p->next;
    p->next = q;
}
// 先移动到指定节点，然后再添加内容

// 删除指定内容的节点
void DeleteElement(NodePtr paraHeader, char paraData) {
    NodePtr p,q;

    p = paraHeader;
    while(p->next!=NULL && p->next->data!=paraData) {
        p = p->next;
    }

    if(p->next==NULL) {
        printf("Cannot delete %c\n", paraData);
        return;
    }

    q = p->next;
    p->next = q->next;

    free(q);
}
// 通过指针移动的方式删除指定内容的节点
// 不要忘记用q指向需要删除的节点然后free掉，避免野指针出现

void TestAll() {
    NodePtr TempList = IniLinkList();

    printf("Before appendElement:\n");
    PrintList(TempList);
    printf("----------------------------------------\n");

    AppendElement(TempList, 'H');
    AppendElement(TempList, 'E');
    AppendElement(TempList, 'L');
    AppendElement(TempList, 'L');
    AppendElement(TempList, 'O');
    AppendElement(TempList, '!');
    printf("After appendElement:\n");
    PrintList(TempList);
    printf("----------------------------------------\n");
    printf("The position of each element:\n");
    PrintListMemory(TempList);

    printf("Begin deleteElement:\n");
    DeleteElement(TempList, 'E');
    DeleteElement(TempList, 'A');
    DeleteElement(TempList, 'O');
    printf("After deleteElement:\n");
    PrintList(TempList);
    printf("----------------------------------------\n");
    printf("The position of each element:\n");
    PrintListMemory(TempList);

    InsertElement(TempList, 'O', 1);
    printf("After insertElement\n");
    PrintList(TempList);
    printf("----------------------------------------\n");
    printf("The position of each element:\n");
    PrintListMemory(TempList);

}
int main() {
    // printf("%d\n",sizeof(LNode));
    // printf("%d\n",sizeof(*NodePtr));
    // 这只是一个指针别名，所以不能进行解指针操作
    // 下来看下为什么内存会不一样
    TestAll();
}

输出结果

PS D:\a_study\code_vs\DataStructure\SingleList> gcc -o kernel code.cpp
PS D:\a_study\code_vs\DataStructure\SingleList> ./kernel
Before appendElement:

----------------------------------------
After appendElement:
HELLO!
----------------------------------------
The position of each element:
The position of each node is :16
 (The line above is help to realize the way the Single Link List stores the data.)
At address 12131072, data = 0, next = 12135216
At address 12135216, data = H, next = 12135248
At address 12135248, data = E, next = 12156880
At address 12156880, data = L, next = 12156912
At address 12156912, data = L, next = 12156944
At address 12156944, data = O, next = 12156976
At address 12156976, data = !, next = 0
----------------------------------------
Begin deleteElement:
Cannot delete A
After deleteElement:
HLL!
----------------------------------------
The position of each element:
The position of each node is :16
 (The line above is help to realize the way the Single Link List stores the data.)
At address 12131072, data = 0, next = 12135216
At address 12135216, data = H, next = 12156880
At address 12156880, data = L, next = 12156912
At address 12156912, data = L, next = 12156976
At address 12156976, data = !, next = 0
----------------------------------------
Insert the data O in the position 1
After insertElement
HOLL!
----------------------------------------
The position of each element:
The position of each node is :16
 (The line above is help to realize the way the Single Link List stores the data.)
At address 12131072, data = 0, next = 12135216
At address 12135216, data = H, next = 12156944
At address 12156944, data = O, next = 12156880
At address 12156880, data = L, next = 12156912
At address 12156912, data = L, next = 12156976
At address 12156976, data = !, next = 0
----------------------------------------
PS D:\a_study\code_vs\DataStructure\SingleList>

过程记录

1. 复现代码
2. 发现并解决问题【结构体别名问题】
3. 迁移博客文章
4. 优化输出内容

Points

多个别名的用处

1. 实现不同的功能

例如在本代码单链表结构体的别名中，*NodePtr 可以指向单链表的节点，而 LNode 则用于反馈结构体空间大小信息【二者各司其职，均有功用】

2. 方便代码理解

有时候一个结构体在一个程序中被不同模块使用，每次使用的环境不一样，多种别名能够区分不同环境

指针别名

指针别名可以创建一个指向该结构体的指针，方便进行结构体空间分配、赋值等操作

但是要注意，不能对指针别名进行解指针

Delete 函数最后的 free 操作

通过 q 指针指向被删除的节点，free q，避免野指针出现【不要忘记这一点】

Thinking

what – 什么是单链表, 在现实世界中有哪些单链表的例子？

通过 next 指针连接节点的另类”数组“

1. 打印队列
2. 歌单切换
3. 文本编辑器中的撤销操作

why – 有了顺序表, 为什么还要引入单链表

单链表能够进行灵活的内存分配以及高效的插入删除操作

内存的非连续性能够更好利用碎片内存

how – 在现实世界中, 如何管理、操纵这些单链表?

按照需求进行单链表的结构体设置以及基本操作

单链表的基本操作有：定义、初始化、插入、删除、查找