AB11-分别采用头插法和尾插法建立一个带头结点的单链表

代码实现

尾插法

/**
 * 采用尾插法建立带头结点的单链表
 * @return 指向链表头结点的指针
 */
LinkList create_tail() {
    // 创建头结点并初始化
    LinkList L = (LinkList)malloc(sizeof(LNode));
    if (L == NULL) {
        printf("内存分配失败\n");
        return NULL;
    }
    L->next = NULL;  // 头结点指针域初始化为空

    // r始终指向链表的尾结点，便于尾插操作
    LNode* r = L;

    // 读取数据
    int x;
    printf("请输入数据（输入9999结束）：");
    scanf("%d", &x);

    // 循环创建结点，直到输入结束标志
    while (x != 9999) {
        // 创建新结点
        LNode* s = (LinkList)malloc(sizeof(LNode));
        if (s == NULL) {
            printf("内存分配失败\n");
            return L;  // 返回已创建的部分链表
        }

        // 设置新结点数据
        s->data = x;
        s->next = NULL;  // 新结点插入到链表尾部

        // 尾插操作：将新结点链接到链表尾部
        r->next = s;
        r = s;  // 更新尾指针，指向新的尾结点

        // 读取下一个数据
        scanf("%d", &x);
    }

    return L;  // 返回链表头指针
}

头插法

/**
 * 采用头插法建立带头结点的单链表
 * @return 指向链表头结点的指针
 */
LinkList create_head() {
    // 创建头结点并初始化
    LinkList L = (LinkList)malloc(sizeof(LNode));
    if (L == NULL) {
        printf("内存分配失败\n");
        return NULL;
    }
    L->next = NULL;

    // 读取数据
    int x;
    printf("请输入数据（输入9999结束）：");
    scanf("%d", &x);

    // 循环创建结点，直到输入结束标志
    while (x != 9999) {
        // 创建新结点
        LNode* s = (LinkList)malloc(sizeof(LNode));
        if (s == NULL) {
            printf("内存分配失败\n");
            return L;
        }

        // 设置新结点数据
        s->data = x;

        // 头插操作：将新结点插入到头结点之后
        s->next = L->next;  // 新结点指向原第一个结点
        L->next = s;        // 头结点指向新结点

        // 读取下一个数据
        scanf("%d", &x);
    }

    return L;  // 返回链表头指针
}

算法执行流程图解

尾插法执行过程

输入序列：1 2 3 9999

初始状态：L → [ ]→NULL
          ↑
          r

输入1：   L → [ ]→[1]→NULL
          ↑      ↑
          头    r(尾)

输入2：   L → [ ]→[1]→[2]→NULL
          ↑           ↑
          头         r(尾)

输入3：   L → [ ]→[1]→[2]→[3]→NULL
          ↑                ↑
          头              r(尾)

头插法执行过程

输入序列：1 2 3 9999

初始状态：L → [ ]→NULL

输入1：   L → [ ]→[1]→NULL
                ↑
               新插入

输入2：   L → [ ]→[2]→[1]→NULL
                ↑    ↑
               新插入

输入3：   L → [ ]→[3]→[2]→[1]→NULL
                ↑    ↑    ↑
               新插入

头插法与尾插法对比图

输入序列：1 2 3

尾插法结果：L → [ ]→[1]→[2]→[3]→NULL
                    ↑    ↑    ↑
                  前   中   后(输入顺序)

头插法结果：L → [ ]→[3]→[2]→[1]→NULL
                    ↑    ↑    ↑
                  后   中   前(输入顺序相反)

复杂度分析

时间复杂度：O(n)

• 创建结点：n次malloc操作，每次O(1)，总计O(n)
• 链接操作：每次插入操作O(1)，总计O(n)
• 输入操作：n次scanf操作，总计O(n)
• 总体时间复杂度：O(n)

空间复杂度：O(n)

• 结点存储：n个结点，每个结点占用O(1)空间，总计O(n)
• 辅助变量：指针变量L、r、s等，O(1)
• 总体空间复杂度：O(n)

算法特点对比

特征	头插法	尾插法
实现难度	简单	需要维护尾指针
时间复杂度	O(n)	O(n)
空间复杂度	O(n)	O(n)
结果顺序	与输入相反	与输入相同
适用场景	不关心顺序或需要逆序	需要保持输入顺序

核心思想总结

头插法： - 每次将新结点插入到头结点之后 - 实现简单，但结果与输入顺序相反

尾插法： - 使用尾指针r始终指向链表尾结点 - 每次将新结点插入到尾结点之后 - 结果与输入顺序一致，但需要维护尾指针