单向链表的C语言实现_单向链表c语言实现

引言

        单向链表是一种重要的数据结构，由一系列结点组成，每个结点包含数据域和指向下一个结点的指针。由于其灵活的内存使用和动态扩展特性，单向链表在很多场景中得到了广泛应用。本文将详细介绍单向链表的实现，包括创建、插入、删除、查找、修改和打印操作，并给出完整的C语言代码示例。

一、单向链表的结点和结构定义

首先，我们需要定义单向链表的结点和链表本身的结构

#include <stdio.h>
#include <stdlib.h>
 
#define eleType int
 
// 单向链表的结点定义
typedef struct Listnode
 
{
 
         eleType data;            // 数据域
         struct Listnode* next;   // 指针域，指向后继结点
} Listnode;
 
// 单向链表的定义
typedef struct
 
{
 
        struct Listnode* head;   // 头结点
        size_t size;             // 整个链表的元素个数
} LinkedList;

• #include <stdio.h> 和 #include <stdlib.h>：包含标准输入输出和标准库函数。
• #define eleType int：定义链表中数据的类型为 int，可以根据需要更改。
• typedef struct Listnode：定义链表结点结构体，包含数据域 data 和指向后继结点的指针 next。
• typedef struct LinkedList：定义链表结构体，包含指向头结点的指针 head 和链表的元素个数 size。

二、单向链表的基本操作 

1.创建链表

链表的创建需要初始化头指针和元素个数。

void LinkedListCreat(LinkedList* list)
 
{
 
        list->head = NULL;   // 初始化链表头为NULL
        list->size = 0;      // 初始化链表大小为0
}

• void LinkedListCreat(LinkedList* list)：定义创建链表的函数，参数为指向链表的指针。
• list->head = NULL：将链表的头结点初始化为 NULL，表示链表为空。
• list->size = 0：将链表的大小初始化为0。

2. 销毁链表

销毁链表时，需要遍历链表并释放每个结点的内存。

void LinkedListDestory(LinkedList* list)
 
{
 
        while (list->head)
 
        {
                Listnode* temp = list->head;
                list->head = list->head->next;
                free(temp);
 
        }
 
        list->size = 0; // 将链表大小重置为0
}

• void LinkedListDestory(LinkedList* list)：定义销毁链表的函数，参数为指向链表的指针。
• while (list->head)：循环遍历链表直到头结点为 NULL。
• Listnode* temp = list->head：临时保存当前头结点的指针。
• list->head = list->head->next：将头结点指向下一个结点。
• free(temp)：释放当前头结点的内存。
• list->size = 0：将链表的大小重置为0。

3. 插入元素

在链表的第 i 个位置插入一个新结点。

void LinkedListInsert(LinkedList* list, int i, eleType value)
{//在链表的第i个位置插入一个值为value的结点
    if (i<0 || i>list->size)
    {
        printf("Invalid index\n");
        return;
    }
    Listnode* newNode = (Listnode*)malloc(sizeof(Listnode));
    newNode->data = value;//
    if (i == 0)//
    {
        newNode->next = list->head;//
        list->head = newNode;//
    }
    else
    {
        Listnode* current = list->head;//
        for (int j = 0;j < i - 1;j++)
        {
            current = current->next;//
        }
        newNode->next = current->next;//
        current->next = newNode;//
    }
 
    list->size++;//
}

• void LinkedListInsert(LinkedList* list, int i, eleType value)：定义插入元素的函数，参数为指向链表的指针，插入位置 i 和插入值 value。
• if (i < 0 || i > list->size)：检查插入位置是否合法，如果不合法则打印错误信息并返回。
• Listnode* newNode = (Listnode*)malloc(sizeof(Listnode))：分配新结点的内存。
• newNode->data = value：设置新结点的数据域。
• if (i == 0)：如果插入位置是头部。
  • newNode->next = list->head：新结点的指针域指向当前头结点。
  • list->head = newNode：将新结点设置为头结点。
• else：如果插入位置不是头部。
  • Listnode* current = list->head：临时变量 current 指向头结点。
  • for (int j = 0; j < i - 1; j++) { current = current->next; }：遍历链表直到找到插入位置的前一个结点。
  • newNode->next = current->next：新结点的指针域指向当前结点的下一个结点。
  • current->next = newNode：将当前结点的指针域指向新结点。
• list->size++：链表大小加1。

4. 删除元素

从链表中删除第 i 个结点。

void LinkedListRemove(LinkedList* list, int i)
{
    if (i<0 || i>list->size)
    {
        printf("Invalid index\n");
        return;
    }
    if (i == 0)
    {
        Listnode* next = list->head->next;
        free(list->head);
        list->head = next;
    }
    else
    {
        Listnode* current = list->head;
        for (int j = 0;j < i - 1;j++)
        {
            current = current->next;//
        }
        Listnode* next = current->next->next;
        free(current->next);
        current->next->next;
    }
 
    list->size--;//
}

• void LinkedListRemove(LinkedList* list, int i)：定义删除元素的函数，参数为指向链表的指针和删除位置 i。
• if (i < 0 || i >= list->size)：检查删除位置是否合法，如果不合法则打印错误信息并返回。
• if (i == 0)：如果删除位置是头部。
  • Listnode* next = list->head->next：临时变量 next 保存头结点的下一个结点。
  • free(list->head)：释放头结点的内存。
  • list->head = next：将头结点指向下一个结点。
• else：如果删除位置不是头部。
  • Listnode* current = list->head：临时变量 current 指向头结点。
  • for (int j = 0; j < i - 1; j++) { current = current->next; }：遍历链表直到找到删除位置的前一个结点。
  • Listnode* next = current->next->next：临时变量 next 保存当前结点的下下个结点。
  • free(current->next)：释放当前结点的下一个结点的内存。
  • current->next = next：将当前结点的指针域指向下下个结点。
• list->size--：链表大小减1。

5. 查找元素

查找链表中值为 value 的结点并返回该结点的指针。

Listnode* LinkedListFind(LinkedList* list, eleType value)
{//查找链表中值为value的结点并返回
    Listnode* current = list->head;
    while (current)
    {
        if (current->data == value)
            return current;//
        current = current->next;//
    }
    return NULL;//
}

• Listnode* LinkedListFind(LinkedList* list, eleType value)：定义查找元素的函数，参数为指向链表的指针和查找值 value。
• Listnode* current = list->head：临时变量 current 指向头结点。
• while (current)：循环遍历链表直到 current 为 NULL。
• if (current->data == value)：如果当前结点的数据域等于 value。
  • return current：返回当前结点的指针。
• current = current->next：将 current 指向下一个结点。
• return NULL：如果遍历完链表未找到匹配的结点，返回 NULL。

6. 获取索引元素

获取链表中第 i 个结点的指针。

Listnode* LinikedListGet(LinkedList* list, int i)
 
{
 
        if (i < 0 || i >= list->size)
 
        {
                printf("Invalid index\n");
                return NULL;
        }
 
        Listnode* current = list->head;
        for (int j = 0; j < i; j++)
 
        {
                current = current->next;
        }
 
        return current;
}

• Listnode* LinikedListGet(LinkedList* list, int i)：定义获取索引元素的函数，参数为指向链表的指针和索引位置 i。
• if (i < 0 || i >= list->size)：检查索引位置是否合法，如果不合法则打印错误信息并返回 NULL。
• Listnode* current = list->head：临时变量 current 指向头结点。
• for (int j = 0; j < i; j++) { current = current->next; }：遍历链表直到找到第 i 个结点。
• return current：返回第 i 个结点的指针。

7. 修改元素

更新链表中第 i 个结点的值为 value。

void LinkedListUpdate(LinkedList* list, int i, eleType value)
 
{
 
        Listnode* node = LinikedListGet(list, i);
 
        if (node != NULL)
 
        {
 
                node->data = value;
         }
 
        else
 
        {
                printf("Invalid index\n");
 
        }
}

• void LinkedListUpdate(LinkedList* list, int i, eleType value)：定义修改元素的函数，参数为指向链表的指针、索引位置 i 和新值 value。
• Listnode* node = LinikedListGet(list, i)：获取第 i 个结点的指针。
• if (node != NULL)：如果结点存在。
  • node->data = value：更新结点的数据域为 value。
• else：如果结点不存在。
  • printf("Invalid index\n")：打印错误信息

8. 打印链表

遍历并打印链表中的所有结点。

void LinkedListPrint(LinkedList* list)
 
{
 
        Listnode* current = list->head;
        while (current)
 
        {
                printf("%d -> ", current->data);
                current = current->next;
 
        }
 
        printf("NULL\n");
}

• void LinkedListPrint(LinkedList* list)：定义打印链表的函数，参数为指向链表的指针。
• Listnode* current = list->head：临时变量 current 指向头结点。
• while (current)：循环遍历链表直到 current 为 NULL。
• printf("%d -> ", current->data)：打印当前结点的数据域。
• current = current->next：将 current 指向下一个结点。
• printf("NULL\n")：遍历完链表后打印 NULL，表示链表结束。

三、总结

        以上是单向链表的完整实现，包括创建、销毁、插入、删除、查找、获取、修改和打印操作。每个操作都提供了详细的代码和解释，便于理解和学习。通过这些操作，我们可以有效地管理链表中的数据，实现灵活的动态内存操作。

四、示例代码

        最后，我们提供一个完整的示例代码，演示如何使用上述操作管理单向链表。

int main()
 
{
    LinkedList list;
    LinkedListCreat(&list);
 
    LinkedListInsert(&list, 0, 10);  // 插入10到第0个位置
    LinkedListInsert(&list, 1, 20);  // 插入20到第1个位置
    LinkedListInsert(&list, 2, 30);  // 插入30到第2个位置
    LinkedListPrint(&list);          // 打印链表: 10 -> 20 -> 30 -> NULL
 
    LinkedListRemove(&list, 1);      // 删除第1个位置的元素
    LinkedListPrint(&list);          // 打印链表: 10 -> 30 -> NULL
 
    Listnode* node = LinkedListFind(&list, 30);
    if (node) {
        printf("Found node with value: %d\n", node->data);
    } else {
        printf("Node not found\n");
    }
 
    LinkedListUpdate(&list, 1, 50);  // 更新第1个位置的元素值为50
    LinkedListPrint(&list);          // 打印链表: 10 -> 50 -> NULL
 
    LinkedListDestory(&list);        // 销毁链表
    return 0;
}

        通过这个示例代码，可以看到如何创建链表、插入元素、删除元素、查找元素、修改元素以及打印链表的全部过程，这些操作展示了单向链表的基本功能。

 五、总结

• 灵活性：单向链表的动态内存分配使其能够灵活应对大小变化，插入和删除操作效率较高。
• 实现细节：通过详细的代码实现和解释，理解了链表操作的内部机制。
• 应用场景：链表在需要频繁插入和删除操作的场景中表现优越，例如实现栈、队列等数据结构。

 （都看到这里了，点个赞支持一下吧，/(ㄒoㄒ)/~~）