笔触狂放9

这个屌丝很懒，什么也没留下！

热门标签

【数据结构】单链表的基本操作（C语言版）_单链表的创建:分配空间、参数初始化 (3)单链表的插入:创建新节点,在位置i-1和i之

作者：笔触狂放9 | 2024-05-28 08:32:04

踩

单链表的创建:分配空间、参数初始化 (3)单链表的插入:创建新节点,在位置i-1和i之

单链表的定义

单链表（Singly linked list）是一种常见的数据结构，它由一个结点（Node）的链表构成，每个结点包含两个域：数据域和指针域。数据域用于存储结点的数据，指针域用于存储下一个结点的地址。

单链表中的第一个结点被称为头结点（Head），它用来存放链表的基地址。头结点中的指针域指向链表的第一个结点，最后一个结点的指针域指向空地址，表示链表结束。

下面是一个单链表结点的定义：


typedef int DataType;
 
typedef struct ListNode
{
	DataType data;            // 数据域，存储结点的数据
	struct ListNode* next;    // 指针域，指向下一个结点
}ListNode;

值得注意的是，单链表是一种动态数据结构，可以在运行时动态添加或删除结点，也可以在任何位置插入或删除结点，因为每个结点的指针域储存的是下一个结点的地址，所以链表的结构是相对灵活的，有着较强的扩展性。

单链表的特点以及与顺序表的差别

链表是动态数据结构：链表的长度可以根据实际需要进行动态调整，可以在运行时添加或删除结点。
链表的插入和删除操作高效：在链表中插入或删除结点的操作时间复杂度为O(1)，只需要修改指针的指向即可，而不需要像数组那样需要移动其他元素。
链表对内存的利用率较低：链表中的结点是通过指针连接的，需要额外的内存空间来存储指针。
链表的访问操作相对较慢：由于链表中的结点不是连续存储的，因此无法像数组一样通过下标直接访问元素，需要从头结点开始遍历链表，直到找到目标结点。
链表的结构灵活：可以在链表中间插入或删除结点，只需修改指针的指向即可。而数组的长度是固定的，插入或删除元素需要移动其他元素。
链表适用于频繁插入和删除的场景：由于链表插入和删除的时间复杂度为O(1)，相比数组，链表更适合频繁插入和删除结点的情况。

需要注意的是，链表的访问操作时间复杂度为O(n)，其中n是链表的长度。因此，在需要频繁根据索引访问元素的情况下，数组可能更加合适。而链表适用于需要动态调整长度、频繁插入和删除元素的场景。

单链表的基本操作

1、单链表的初始化

单链表的初始化即构造一个仅包含头结点的空单链表。其过程是首先申请一个结点并让指针 head指向该结点，然后将它的指针域赋为空（NULL)，最后返回头指针 head。

首先我们先了解下什么是头节点以及为什么要设置头节点：

方便操作空链表：初始时，链表是空的，没有任何结点。如果没有头结点，链表的第一个结点就是空链表。通过设置头结点，即使链表为空，也有了一个起始的位置，可以方便地进行插入和删除操作。
简化插入和删除操作：有了头结点，插入和删除操作可以统一处理。无论在链表的头部、中间还是尾部插入或删除结点，操作逻辑都是一致的。通过将头结点作为起点，可以避免处理边界情况的复杂性。
方便获取链表长度：头结点为链表提供了一个便捷的起点，从头结点开始遍历链表，可以方便地计算链表的长度。
方便遍历操作：通过头结点，从链表的第一个结点开始遍历整个链表，可以避免操作和管理指针时的边界情况。

注意：头结点不存储实际的数据，仅作为链表的起点，其下一个结点指向链表的第一个有效节点。因此，在使用链表时，需要特别注意头结点的存在，并在涉及到插入、删除和遍历操作时进行处理。

由此可见，设置头节点可以简化部分操作。当然不设置头节点也是可以的，但是博主建议大家在学习单链表的初期尽量使用带头节点的单链表，等掌握熟练后自己再尝试不包含头节点的单链表。


// 初始化单链表
ListNode* InitList()
{
    // 创建头结点，并进行内存分配
    ListNode* head = (ListNode*)malloc(sizeof(ListNode));
   
    // 检查内存分配是否成功
    if (head == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
 
    // 将头结点的指针域置空
    head->next = NULL;
 
    return head;
}

2、头插法建立单链表

链表与顺序表不同，它是一种动态管理的存储结构，链表中的每个结点占用的存储空间不是预先分配，而是运行时系统根据需求生成的。因此，建立在初始化链表后，建立线性链表从空表开始，每读入有效的数据则申请一个结点s，并将读取的数据存放到新结点s的数据域中，然后将新结点插入到当前链表头结点head之后，直到循环结束为止。

注意：代码中head为二级指针，即链表头结点的地址。

*head 是一个解引用操作，意味着它获取了 head 指针所指向的值。在这种情况下，head 是一个指向链表头结点指针的指针，通过 *head 可以获取到链表头结点指针的值。

通过 *head 可以访问并修改链表的头指针。在 AddListHead 函数中，(*head)->next 用于获取头结点的下一个节点的指针，而 (*head)->next = newnode 则是将新节点的地址赋值给头结点的下一个节点指针，从而实现在链表头部插入新节点的操作。


void CreateListHead(ListNode** head)
{
    assert(head && *head);
    int i, n, val;
 
    // 获取要增加的节点数
    printf("需要增加多少个节点：");
    scanf("%d", &n);
 
    // 循环增加新节点
    for (i = 0; i < n; i++)
    {
        // 获取用户输入的节点值
        printf("请输入第 %d 个节点的数据：", i + 1);
        scanf("%d", &val);
 
        // 创建新节点，并进行内存分配检查
        ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
 
        // 检查内存分配是否成功
        if (newnode == NULL)
        {
            perror("malloc fail");
            exit(-1);
        }
 
        // 将节点值存储在新节点中
        newnode->data = val;
 
        // 将新节点插入到链表头部：将新节点的下一个节点指向当前头节点的下一个节点
        // 然后将新节点设为头节点的下一个节点
        newnode->next = (*head)->next;
        (*head)->next = newnode;
    }
}

3、尾插法建立单链表

头插法建立链表虽然算法简单易理解，但生成的链表中结点的次序和原输入的次序相反。而尾插法建立链表可实现次序的一致，该算法依旧从空表开始，但需增加一个尾指针last，使其指向当前链表的尾结点。其过程是：每读入有效的数据则申请一个结点s，并将读取的数据存放到新结点s的数据域中，将s的尾指针设为空指针(NULL），然后将新结点插入到当前链表尾部（last 指针所指的结点后面），直到循环结束为止。


void CreateListLast(ListNode** head)
{
    assert(head && *head);
 
    int i, n, val;
 
    // 获取要增加的节点数
    printf("需要增加多少个节点：");
    scanf("%d", &n);
 
    // 创建临时指针并指向链表的头节点
    ListNode* temp = *head;
 
    // 移动到链表的最后一个节点
    while (temp->next)
    {
        temp = temp->next;
    }
 
    // 循环增加新节点
    for (i = 0; i < n; i++)
    {
        // 获取用户输入的节点值
        printf("请输入第 %d 个节点的数据：", i + 1);
        scanf("%d", &val);
 
        // 创建新节点，并进行内存分配检查
        ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
 
        // 检查内存分配是否成功
        if (newnode == NULL)
        {
            perror("malloc fail");
            exit(-1);
        }
 
        // 将节点值存储在新节点中
        newnode->data = val;
        newnode->next = NULL;
 
        // 将新节点连接到链表的最后一个节点，并更新最后一个节点为新节点
        temp->next = newnode;
        temp = newnode;
    }
}