LV050-单链表简介

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

一、存储结构

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

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

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

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

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

二、优缺点

• 优点

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

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

• 缺点

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

三、结构体实现

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

/* 自定义数据类型 */
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

/** ==== ==== ==== ==== ==== ==== ==== ==== ==== ==== ==== ==== ==== =
 * 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

/** ==== ==== ==== ==== ==== ==== ==== ==== ==== ==== ==== ==== ==== =
 * 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

#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

##============================================================================#
# 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.编译测试

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

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

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