【C/C++】C语言实现单链表

简单描述

• 用codeblocks编译通过
• 源码参考连接

https://gitee.com/IUuaena/data-structures-c.git

代码

• common.h

#ifndef COMMON_H_INCLUDED
#define COMMON_H_INCLUDED

#define ELEM_TYPE   int //!< 链表元素类型

/*! @brief 返回值类型 */
typedef enum
{
    OK,             //!< 成功/正确
    NON_ALLOCATED,  //!< 内存分配失败
    NON_EXISTENT,   //!< 不存在
    ERROR           //!< 错误
} status_t;

#endif // COMMON_H_INCLUDED

• linked_list.h

#ifndef LINKED_LIST_H_INCLUDED
#define LINKED_LIST_H_INCLUDED


#include "common.h"


/*! @brief 链表结点 */
typedef struct linked_node
{
    ELEM_TYPE               data;   //!< 数据项
    struct linked_node*   next;   //!< 下一结点
} linked_node_t;

typedef linked_node_t* linked_list_t;   //!< 链表


status_t LinkedListCreate(linked_node_t** linked_list_head, ELEM_TYPE* elements, int elem_count);

status_t LinkedListGetElem(linked_node_t* linked_list_head, int pos, ELEM_TYPE* elem);

status_t LinkedListInsert(linked_node_t* linked_list_head, int pos, ELEM_TYPE elem);

status_t LinkedListDelete(linked_node_t* linked_list_head, int pos, ELEM_TYPE* elem);

status_t LinkedListMergeTwoSortedList(linked_node_t* list_a_head,linked_node_t* list_b_head,linked_node_t** merged_list_head);

void LinkedListPrint(linked_node_t* linked_list_head);

#endif // LINKED_LIST_H_INCLUDED

• linked_list.c

/*!
 * @file linked_list.c
 * @author CyberDash计算机考研, cyberdash@163.com(抖音id:cyberdash_yuan)
 * @brief 单链表头文件
 * @version 1.0.0
 * @date 2022-07-10
 * @copyright Copyright (c) 2021
 *  CyberDash计算机考研
 */

#include <stdlib.h>
#include <stdio.h>
#include "linked_list.h"


/*!
 * @brief **链表创建**
 * @param linked_list_head **链表头结点**(指针)
 * @param elements **数据项数组**
 * @param elem_count **数据项数量**
 * @return **执行结果**
 * @note
 *
 * 链表创建
 * -------
 * -------
 *
 * - 链表头结点分配内存 \n
 * &emsp; **if** 内存分配失败 : \n
 * &emsp;&emsp; 返回NON_ALLOCATED \n
 * - 链表头节点next设置为NULL \n
 * - 遍历数据项数组并插入链表结点 \n
 * &emsp; **for loop** 遍历数据项数组(从后向前) : \n
 * &emsp;&emsp; 分配当前链表结点内存 \n
 * &emsp;&emsp; **if** 内存分配失败 : \n
 * &emsp;&emsp;&emsp; 返回NON_ALLOCATED \n
 * &emsp;&emsp; 当前数据项elements[i]赋给当前链表结点的data \n
 * &emsp;&emsp; 链表头的next指向当前链表结点 \n
 */
status_t LinkedListCreate(linked_node_t** linked_list_head, ELEM_TYPE* elements, int elem_count)
{
    *linked_list_head = (linked_node_t*)malloc(sizeof(linked_node_t)); // 链表头结点分配内存
    if (!(*linked_list_head))
    {
        return NON_ALLOCATED;
    }

    (*linked_list_head)->next = NULL;

    for (int i = elem_count - 1; i >= 0; i--)
    {
        linked_node_t* linked_node = (linked_node_t*)malloc(sizeof(linked_node_t)); // 新结点分配内存
        if (!linked_node)
        {
            return NON_ALLOCATED;
        }

        linked_node->data = elements[i];            // elements[i]赋给新结点数据项
        linked_node->next = (*linked_list_head)->next; // 新结点next赋值
        (*linked_list_head)->next = linked_node;       // linked_list_head->next指向新结点
    }

    return OK;
}


/*!
 * @brief **链表获取某位置的结点数据**
 * @param linked_list_head **链表头结点**(指针)
 * @param pos **位置**
 * @param elem **保存结点数据项的变量**(指针)
 * @return **执行结果**
 * @note
 * 链表获取某位置的结点数据
 * ---------------------
 * ---------------------
 *
 * - 初始化遍历指针cur和起始位置cur_post(从1开始, 区别于数组的从0开始) \n
 * - 遍历链表至位置pos \n
 * &emsp; **while** 未遍历至位置pos : \n
 * &emsp;&emsp; cur指向后一个结点 \n
 * &emsp;&emsp; cur_pos加1 \n
 * - 边界条件判断 \n
 * **if** 遍历指针cur指向NULL 或者 cur_pos大于pos : \n
 * &emsp; 返回NON_EXISTENT(不存在该位置的元素) \n
 * - 将位置pos的元素的data赋给参数elem指向的变量
 */
status_t LinkedListGetElem(linked_node_t* linked_list_head, int pos, ELEM_TYPE* elem)
{
    linked_node_t* cur = linked_list_head->next;
    int cur_pos = 1;

    while (cur && cur_pos < pos)
    {
        cur = cur->next;
        cur_pos++;
    }

    // 位置pos的结点不存在, 返回NON_EXISTENT
    if (!cur || cur_pos > pos)
    {
        return NON_EXISTENT;
    }

    *elem = cur->data; // 将位置pos的数据项赋给*elem

    return OK;
}


/*!
 * @brief **链表插入**
 * @param linked_list_head **链表头结点**(指针)
 * @param pos **位置**(在这个位置前执行插入)
 * @param elem **待插入的数据项**
 * @return **执行结果**
 * @note
 * 链表插入
 * -------
 * -------
 *
 * - 初始化指针cur和insert_pos_predecessor \n
 * &emsp; cur用来遍历, 找到插入位置的前一节点, insert_pos_predecessor用来找该节点的位置 \n
 * - 找到插入位置 \n
 * &emsp; **while** cur不为NULL 或者 尚未遍历完整个链表 \n
 * &emsp;&emsp; cur指向下一个结点 \n
 * &emsp;&emsp; insert_pos_predecessor加1 \n
 * - 处理没有插入位置的情况 \n
 * &emsp; **if** 插入位置不存在 \n
 * &emsp;&emsp; 返回ERROR \n
 * - 执行插入 \n
 * &emsp; 分配结点内存 \n
 * &emsp; **if** 内存分配失败 : \n
 * &emsp;&emsp; 返回NON_ALLOCATED \n
 * &emsp; 插入节点设置data和next \n
 * &emsp; cur->next指向插入节点 \n
 */
status_t LinkedListInsert(linked_node_t* linked_list_head, int pos, ELEM_TYPE elem)
{
    linked_node_t* cur = linked_list_head;
    int insert_pos_predecessor = 0; // 插入位置的前一位置, 初始化为0

    // 遍历到插入位置的前一位置
    while(!cur || insert_pos_predecessor < pos - 1)
    {
        cur = cur->next;
        insert_pos_predecessor++;
    }

    // 如果插入位置不存在, 返回ERROR
    if (!cur || insert_pos_predecessor > pos - 1)
    {
        return ERROR;
    }

    // 插入结点分配内存
    linked_node_t* insert_node = (linked_node_t*)malloc(sizeof(linked_node_t));
    if (!insert_node)
    {
        return NON_ALLOCATED;
    }

    // 插入节点设置data和next
    insert_node->data = elem;
    insert_node->next = cur->next;

    // cur->next指向插入节点
    cur->next = insert_node;

    return OK;
}


/*!
 * @brief **链表删除结点**
 * @param linked_list_head **链表头结点**(指针)
 * @param pos **删除结点位置**
 * @param elem **被删除结点数据项的保存变量**(指针)
 * @return **执行结果**
 * @note
 * 链表删除结点
 * ----------
 * ----------
 * - 初始化变量delete_node_predecessor和delete_pos_predecessor \n
 * &emsp; delete_node_predecessor(删除节点的前一节点指针)指向表头 \n
 * &emsp; delete_pos_predecessor(删除节点的前一节点的位置)初始值为0 \n
 * - 遍历至被删除结点 \n
 * - 处理不存在删除结点的情况 \n
 * - 删除结点 \n
 * &emsp; 指针delete_node指向delete_node_predecessor->next(被删除结点) \n
 * &emsp; delete_node_predecessor->next指向被删除结点的next \n
 * &emsp; 被删除结点的数据项赋给item \n
 * &emsp; 调用free释放被删除结点 \n
 */
status_t LinkedListDelete(linked_node_t* linked_list_head, int pos, ELEM_TYPE* elem)
{
    linked_node_t* delete_node_predecessor = linked_list_head;    // 待删除结点前一结点(指针), 初始化指向链表头结点
    int delete_pos_predecessor = 0; // 待删除结点前一结点的位置, 初始化为0

    // 遍历到待删除结点的前一结点
    while(!(delete_node_predecessor->next) || delete_pos_predecessor < pos - 1)
    {
        delete_node_predecessor = delete_node_predecessor->next;
        delete_pos_predecessor++;
    }

    // 位置pos的结点不存在, 返回NON_EXISTENT
    if (!(delete_node_predecessor->next) || delete_pos_predecessor > pos - 1)
    {
        return NON_EXISTENT;
    }

    linked_node_t* delete_node = delete_node_predecessor->next; // delete_node指向待删除结点
    delete_node_predecessor->next = delete_node->next;
    *elem = delete_node->data;

    free(delete_node);  // 释放结点
    delete_node = NULL; // 避免野指针

    return OK;
}


/*!
 * @brief **链表合并两个有序链表**
 * @param list_a_head **a链表的头结点**(指针)
 * @param list_b_head **b链表的头结点**(指针)
 * @param merged_list_head **合并链表的头结点**(二级指针)
 * @return **执行结果**
 * @note
 * 链表合并两个有序链表
 * -----------------
 * -----------------
 * **注**: 有序链表a和有序链表b合并, 合并至a链表 \n
 * - 初始化链表a的遍历指针a_cur和链表b的遍历指针b_cur \n
 * &emsp; a_cur指向链表a首元素结点 \n
 * &emsp; b_cur指向链表b首元素结点 \n
 * - 初始化合并链表的遍历指针 \n
 * &emsp; cur指向链表a头结点 \n
 * - 执行合并 \n
 * &emsp; **while** 链表a和链表b都未合并完 : \n
 * &emsp;&emsp; **if** 链表a当前元素 <= 链表b当前元素 : \n
 * &emsp;&emsp;&emsp; 合并链表当前元素(cur)的next指向链表a当前元素 \n
 * &emsp;&emsp;&emsp; 合并链表当前元素(cur)更新为链表a当前元素 \n
 * &emsp;&emsp;&emsp; 链表a当前元素向后移动一位(next) \n
 * &emsp;&emsp; **else** (链表a当前元素 > 链表b当前元素) : \n
 * &emsp;&emsp;&emsp; 合并链表当前元素(cur)的next指向链表a当前元素 \n
 * &emsp;&emsp;&emsp; 合并链表当前元素(cur)更新为链表a当前元素 \n
 * &emsp;&emsp;&emsp; 链表a当前元素向后移动一位(next) \n
 * - 剩余链表处理 \n
 * &emsp; 如果链表a有剩余, 将链表a加到合并链表尾部 \n
 * &emsp; 如果链表b有剩余, 将链表b加到合并链表尾部 \n
 */
status_t LinkedListMergeTwoSortedList(linked_node_t* list_a_head,
                                      linked_node_t* list_b_head,
                                      linked_node_t** merged_list_head)
{
    linked_node_t* a_cur = list_a_head->next;
    linked_node_t* b_cur = list_b_head->next;

    *merged_list_head = list_a_head;
    linked_node_t* cur = list_a_head;

    while (a_cur && b_cur)
    {
        if (a_cur->data <= b_cur->data)
        {
            cur->next = a_cur;
            cur = a_cur;
            a_cur = a_cur->next;
        }
        else
        {
            cur->next = b_cur;
            cur = b_cur;
            b_cur = b_cur->next;
        }
    }

    if (a_cur)
    {
        cur->next = a_cur;
    }

    if (b_cur)
    {
        cur->next = b_cur;
    }

    return OK;
}

/*!
 * @brief **打印链表**
 * @param linked_list_head **链表头结点**
 * @note
 * 打印链表
 * -------
 * -------
 * 遍历链表, 打印每一结点的数据项data \n
 */
void LinkedListPrint(linked_node_t* linked_list_head)
{
    for (linked_node_t* cur = linked_list_head->next; cur != NULL; cur = cur->next)
    {
        printf("%d ", cur->data);
    }

    printf("\n");
}

• main.c

#include <stdio.h>
#include <stdlib.h>
#include "linked_list.h"

void TestLinkedListCreate() {
    printf("\n");
    printf("|------------------------ CyberDash ------------------------|\n");
    printf("|                       测试链表的创建                        |\n");

    ELEM_TYPE arr[6] = { 1, 4, 2, 8, 5, 7 };    // 数据项数组
    linked_node_t* linked_list_head = NULL;     // 链表头结点linked_list_head初始化为NULL

    printf("创建链表: ");

    // 调用LinkedListCreate创建链表
    LinkedListCreate(&linked_list_head, arr, sizeof(arr)/ sizeof(ELEM_TYPE));

    // 打印链表
    LinkedListPrint(linked_list_head);

    printf("\n-------------------------------------------------------------\n\n");
}

/*!
 * @brief **测试链表获取结点数据**
 * @note
 * 测试链表获取结点数据
 * -----------------
 * -----------------
 * - 创建链表 \n
 * &emsp; 使用数组[1, 4, 2, 8, 5, 7]创建链表 \n
 * - 获取某位置结点数据 \n
 * &emsp; 获取并打印 \n
 */
void TestLinkedListGetElem() {
    printf("\n");
    printf("|------------------------ CyberDash ------------------------|\n");
    printf("|                      测试链表的获取元素                      |\n");

    ELEM_TYPE arr[6] = { 1, 4, 2, 8, 5, 7 };    // 数据项数组
    linked_node_t* linked_list_head = NULL;     // 链表头结点linked_list_head初始化为NULL

    printf("创建链表: ");

    // 调用LinkedListCreate创建链表
    LinkedListCreate(&linked_list_head, arr, sizeof(arr) / sizeof(ELEM_TYPE));

    // 打印链表
    LinkedListPrint(linked_list_head);

    int pos = 3;
    ELEM_TYPE data;
    LinkedListGetElem(linked_list_head, pos, &data);

    printf("位置%d的结点, 数据项: %d\n", pos, data);

    printf("\n-------------------------------------------------------------\n\n");
}

/*!
 * @brief **测试链表删除结点**
 * @note
 * 测试链表删除结点
 * --------------
 * --------------
 * - 创建链表 \n
 * &emsp; 使用数组[1, 4, 2, 8, 5, 7]创建链表 \n
 * - 删除结点 \n
 * - 打印链表 \n
 */
void TestLinkedListDelete() {
    printf("\n");
    printf("|------------------------ CyberDash ------------------------|\n");
    printf("|                      测试链表的删除结点                      |\n");

    ELEM_TYPE arr[6] = { 1, 4, 2, 8, 5, 7 };    // 数据项数组
    linked_node_t* linked_list_head = NULL;     // 链表头结点linked_list_head初始化为NULL

    // 调用LinkedListCreate创建链表
    printf("创建链表: ");
    LinkedListCreate(&linked_list_head, arr, sizeof(arr) / sizeof(ELEM_TYPE));

    // 打印链表
    LinkedListPrint(linked_list_head);

    int delete_pos = 4;             // 删除结点位置
    ELEM_TYPE delete_node_elem = 0; // 被删除结点数据项的保存变量

    printf("\n删除位置%d的结点(从1开始计数)\n\n", delete_pos);
    LinkedListDelete(linked_list_head, delete_pos, &delete_node_elem);

    // 打印链表
    printf("删除结点后的链表: ");
    LinkedListPrint(linked_list_head);

    printf("\n-------------------------------------------------------------\n\n");
}

/*!
 * @brief **测试链表插入结点**
 * @note
 * 测试链表插入结点
 * --------------
 * --------------
 * - 创建链表 \n
 * &emsp; 使用数组[1, 4, 2, 8, 5, 7]创建链表 \n
 * - 插入结点 \n
 * - 打印链表 \n
 */
void TestLinkedListInsert() {
    printf("\n");
    printf("|------------------------ CyberDash ------------------------|\n");
    printf("|                      测试链表的插入结点                      |\n");

    ELEM_TYPE arr[6] = { 1, 4, 2, 8, 5, 7 };    // 数据项数组
    linked_node_t* linked_list_head = NULL;     // 链表头结点linked_list_head初始化为NULL

    // 调用LinkedListCreate创建链表
    printf("创建链表: ");
    LinkedListCreate(&linked_list_head, arr, sizeof(arr) / sizeof(ELEM_TYPE));

    // 打印链表
    LinkedListPrint(linked_list_head);

    // 插入新元素
    LinkedListInsert(linked_list_head, 2, 9);
    LinkedListInsert(linked_list_head, 2, 10);
    LinkedListInsert(linked_list_head, 2, 11);

    // 打印链表
    printf("插入3个新结点后的链表: ");
    LinkedListPrint(linked_list_head);

    printf("\n-------------------------------------------------------------\n\n");
}


/*!
 * @brief **测试链表有序链表合并**
 * @note
 *
 * (有序)链表合并
 * ------------
 * ------------
 * - 创建链表1 \n
 * &emsp; 2 --> 4 --> 6 --> 8 \n
 * - 创建链表2 \n
 * &emsp; 1 --> 3 --> 5 --> 7 --> 9 --> 10 \n
 * - 合并链表 \n
 * &emsp; 1 --> 2 --> 3 --> 4 --> 5 --> 6 --> 7 --> 8 --> 9 --> 10 \n
 */
void TestLinkedListMerge() {
    printf("\n");
    printf("|------------------------ CyberDash ------------------------|\n");
    printf("|                      测试有序链表的合并                      |\n");

    ELEM_TYPE elements1[4] = { 2, 4, 6, 8 };
    ELEM_TYPE elements2[6] = { 1, 3, 5, 7 , 9, 10};

    linked_node_t* linked_list_head1 = NULL;
    linked_node_t* linked_list_head2 = NULL;
    linked_node_t* merged_linked_list_head = NULL;

    printf("创建链表1:\n");
    LinkedListCreate(&linked_list_head1, elements1, sizeof(elements1) / sizeof(ELEM_TYPE));
    LinkedListPrint(linked_list_head1);

    printf("创建链表2:\n");
    LinkedListCreate(&linked_list_head2, elements2, sizeof(elements2) / sizeof(ELEM_TYPE));
    LinkedListPrint(linked_list_head2);

    printf("合并链表:\n");
    LinkedListMergeTwoSortedList(linked_list_head1, linked_list_head2, &merged_linked_list_head);
    LinkedListPrint(merged_linked_list_head);

    printf("\n-------------------------------------------------------------\n\n");
}

int main()
{
    printf("你好!\n");
    TestLinkedListCreate();
    TestLinkedListGetElem();
    TestLinkedListDelete();
    TestLinkedListInsert();
    TestLinkedListMerge();
    return 0;
}

运行结果

你好!

|------------------------ CyberDash ------------------------|
|                       测试链表的创建                        |
创建链表: 1 4 2 8 5 7

-------------------------------------------------------------


|------------------------ CyberDash ------------------------|
|                      测试链表的获取元素                      |
创建链表: 1 4 2 8 5 7
位置3的结点, 数据项: 2

-------------------------------------------------------------


|------------------------ CyberDash ------------------------|
|                      测试链表的删除结点                      |
创建链表: 1 4 2 8 5 7

删除位置4的结点(从1开始计数)

删除结点后的链表: 1 4 2 5 7

-------------------------------------------------------------


|------------------------ CyberDash ------------------------|
|                      测试链表的插入结点                      |
创建链表: 1 4 2 8 5 7
插入3个新结点后的链表: 1 11 10 9 4 2 8 5 7

-------------------------------------------------------------


|------------------------ CyberDash ------------------------|
|                      测试有序链表的合并                      |
创建链表1:
2 4 6 8
创建链表2:
1 3 5 7 9 10
合并链表:
1 2 3 4 5 6 7 8 9 10

-------------------------------------------------------------