LV03-05-数据结构-线性表-单链表基础

发表于 分类于 ， ， 本文字数： 1.7k 阅读时长 ≈ 6 分钟

本文主要是数据结构——单链表的基础知识相关笔记，若笔记中有错误或者不合适的地方，欢迎批评指正😃。

点击查看使用工具及版本
Windows windows11
Ubuntu Ubuntu16.04的64位版本
VMware® Workstation 16 Pro 16.2.3 build-19376536
SecureCRT Version 8.7.2 (x64 build 2214) - 正式版-2020年5月14日
开发板 正点原子 i.MX6ULL Linux阿尔法开发板
uboot NXP官方提供的uboot，NXP提供的版本为uboot-imx-rel_imx_4.1.15_2.1.0_ga(使用的uboot版本为U-Boot 2016.03)
linux内核 linux-4.15(NXP官方提供)
STM32开发板 正点原子战舰V3(STM32F103ZET6)
点击查看本文参考资料
参考方向 参考原文
------
点击查看相关文件下载
--- ---

链表，也可以说是链式存储结构，用于存储逻辑关系为 “一对一” 的数据。它与顺序表一样，都是线性表，但是与顺序表不同，链表不限制数据的物理存储状态，也就是说使用链表存储的数据元素，其物理存储位置是随机的。

一、存储结构

  • 数据域：数据元素本身所在的位置。

  • 指针域：指向直接后继元素的指针所在的位置。

  • 节点：每个数据包含数据本身和指向后继元素的指针，叫做节点。

  • 头节点：作为链表的第一个节点，它内部不存放数据，数据一般初始化为 0 ，对于链表，头节点不是必须的。

  • 头指针：就是一个指针，它永远指向链表第一个节点的位置，主要用于指明链表的位置，便于后期找到链表并使用表中的数据。

image-20221021073953722

二、优缺点

  • 优点

（1）任意位置插入删除时间复杂度为O(1)。

（2）动态数据结构，可以根据需要申请空间而不需要提前给出大小。

  • 缺点

（1）以节点为单位存储，不支持随机访问，访问时效率低下。

三、结构体实现

从存储结构来看，单链表的结构的结构体应该包含数据和指针，所以实现的结构体可以像这样定义：

image-20221021074739902 
1
2
3
4
5
6
7
8
/* 自定义数据类型 */
typedef int data_t;

typedef struct __node
{
    data_t data;
    struct node *next;
} _slinkednode, *_slinkedlink;

当我们为创建的结构体类型进行重命名之后，我们就可以简化结构体变量的定义了。

常规写法 等价写法
struct __node H; _slinkednode H;
struct __node * p; _slinkedlink p;

【说明】单链表英文名称为 single linked list ，这里就用 slinked 代表单链表啦。

四、框架实现

接下来我们需要搭建一个单链表的实现框架，它一共需要三个文件： slinkedlist.c 、 slinkedlist.h 和 main.c 。

1. slinkedlist.c

点击查看详情 
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
/** =====================================================
 * Copyright © hk. 2022-2025. All rights reserved.
 * File name  : slinkedlist.c
 * Author     : qidaink
 * Date       : 2022-10-21
 * Version    : 
 * Description: 
 * Others     : 
 * Log        : 
 * ======================================================
 */

#include <stdio.h>
#include "slinkedlist.h"

/**
 * @Function   : slinkedlist_create
 * @brief      : 单链表创建
 * @param arg  : none
 * @return     : none
 * @Description: 
 */
_slinkedlink slinkedlist_create(void)
{
    return NULL;
}

2. slinkedlist.h

点击查看详情 
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
/** =====================================================
 * Copyright © hk. 2022-2025. All rights reserved.
 * File name  : slinkedlist.h
 * Author     : qidaink
 * Date       : 2022-10-21
 * Version    :
 * Description:
 * Others     :
 * Log        :
 * ======================================================
 */
#ifndef __SLINKEDLIST_H__
#define __SLINKEDLIST_H__

/* 自定义数据类型 */
typedef int data_t;

typedef struct __node
{
    data_t data;
    struct node *next;
} _slinkednode, *_slinkedlink;

/* 函数声明 */

_slinkedlink slinkedlist_create(void); /* 单链表创建 */

#endif

3. main.c

点击查看详情 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
#include "slinkedlist.h"

void test_slinkedlist_create() 
{
	_slinkedlink L;
	L = slinkedlist_create();
}

int main(int argc, char *argv[])
{
	test_slinkedlist_create();
    return 0;
}

4. Makefile

点击查看详情 
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
##============================================================================#
# Copyright © hk. 2022-2025. All rights reserved.
# File name  : Makefile
# Author     : qidaink
# Date       : 2022-09-29
# Version    : 
# Description: 
# Others     : 
# Log        : 
##============================================================================#
##

TARGET          := main
#============================================================================#
## 工具设置
# 设置交叉编译器名称
CROSS_COMPILE   :=
# 设置交叉编译器
CC              := $(CROSS_COMPILE)gcc
# 编译选项
CFLAGS          += -g -Wall
#============================================================================#
## 目录路径设置
# 头文件路径设置(.h)
INCDIRS 		:= .

# 源文件路径设置(.S .C)
SRCDIRS			:= .

# 生成的中间 .o 文件的位置
OBJDIRS         := .
#============================================================================#
# 生成编译器的 -I dir_path 参数 
INCLUDE			:= $(patsubst %, -I %, $(INCDIRS))

# 获取所有的 .C 文件名称(包含路径)
CFILES			:= $(foreach dir, $(SRCDIRS), $(wildcard $(dir)/*.c))

# 获取所有的 .C 文件名称(不包含路径)
CFILENDIR		:= $(notdir  $(CFILES))

# 指定所有的 .C 生成的 .o 文件名(包含将要存放的路径)
COBJS			:= $(patsubst %, $(OBJDIRS)/%, $(CFILENDIR:.c=.o))

# 将所有要生成的 .o 文件合并到一个变量中(都包含路径)
OBJS			:= $(COBJS)

# 设置源文件路径
VPATH			:= $(SRCDIRS)

#============================================================================#			
# 生成目标文件	   
$(TARGET): $(OBJS)
	$(CC) $(CFLAGS) $^ -o $(TARGET)

# 隐含规则推导相关中间文件
$(COBJS) : $(OBJDIRS)/%.o : %.c
	$(CC) $(CFLAGS) -c $(INCLUDE) $<  -o $@ 
	
#============================================================================#	
.PHONY: clean clean_o
# 删除所有编译链接生成的文件命令
clean: clean_o
	@rm -vf $(TARGET)

# 删除所有的 .o 文件命令
clean_o:
	@rm -vf $(COBJS)

printf:
	@echo "CFLAGS    = $(CFLAGS)"
	@echo "INCDIRS   = $(INCDIRS)"
	@echo "SRCDIRS   = $(SRCDIRS)"
	@echo "INCLUDE   = $(INCLUDE)"
	@echo "CFILES    = $(CFILES)"
	@echo "CFILENDIR = $(CFILENDIR)"
	@echo "COBJS     = $(COBJS)"
	@echo "OBJS      = $(OBJS)"
	@echo "VPATH     = $(VPATH)"

5.编译测试

框架创建完毕后，可以在命令行输入以下命令进行测试，观察是否有报错，保证没有错误以便于后边相关操作的实现。

1
2
make          # 编译程序
./main        # 执行可执行程序

上边的程序中由于功能还没实现，所以可能会有警告。