数据结构——单链表（定义）

前言

数据结构是计算机专业中的一门专业基础必修课，学好常见的数据结构可以为后续课程的学习打下良好的基础,也是学习计算机专业其他课程的必备条件

1.线性表的链式表示

1.1单链表的定义

定义： 线性表的链式存储又称单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。

typedef struct LNode{  // 定义单链表结点类型
    ElemType data;  // 数据域 每个节点存放一个元素
    struct LNode *next; // 指针域  指向下一个节点
}LNode,*LinkList;
1
2
3
4

可以利用typedef关键字——数据类型重命名：type<数据类型><别名>

单链表两种实现方式：

1.11 不带头结点的单链表

#include
#define ElemType int
typedef struct LNode{  // 定义单链表结点类型
    ElemType data;  // 每个节点存放一个元素
    struct LNode *next; // 指针域  指向下一个节点
}LNode,*LinkList;

// 初始化一个空的单链表（不带头结点的单链表）

bool InitList(LinkList &L) { // 注意这里要用'&'
    L = NULL;  // 空表，暂时无任何结点  （NULL 防止脏数据）
    return true;
}

//判断单链表是否为空
bool Empty(LinkList L) {
    if(L == NULL) return true;
    else return false;
}

void text() {
    LinkList L; // 声明一个指向单链表的指针
    
    InitList(L); //初始化单链表
    
    //······ 后续代码实现
}
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

头结点：代表链表上头指针指向的第一个结点，不带有任何数据

1.12 带头结点的单链表

#include
#include // malloc  要包含的头文件
#define ElemType int
typedef struct LNode{  // 定义单链表结点类型
    ElemType data;  // 数据域 每个节点存放一个元素
    struct LNode *next; // 指针域  指向下一个节点
}LNode,*LinkList;

// 初始化一个空的单链表（带头结点）

bool InitList(LinkList &L) {
    L = (LNode *) malloc(sizeof(LNode)); // 分配一个头结点
    if(L = NULL) return false;   // 内存不足 分配空间失败
    L->next = NULL;   //头结点之后暂时没有结点
    return true;
}

//判断单链表是否为空
bool Empty(LinkList L) {
    if(L->next == NULL) return true;
    else return false;
}

void text() {
    LinkList L; // 声明一个指向单链表的指针

    InitList(L); //初始化单链表

    //······ 后续代码实现
}
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

1.13 带头结点和不带头结点的比较

不带头结点： 对第一个数据节点和后续数据节点的处理需要用不同的代码逻辑，对空表和非空表的处理也需要用不同的代码逻辑; 头指针指向的结点用于存放实际数据;
带头结点： 头指针指向的头结点不存放实际数据,头结点指向的下一个结点才存放实际数据;

总结

本节就介绍单链表的定义，下节继续单链表的基本操作。
如果感觉对你有用的话，点个关注吧！