C语言单链表实现异常 按partNumber升序插入时第二次调用触发崩溃

问题说明 #

现有代码需实现按partNumber（零件编号）升序插入的零件库存链表，运行时存在以下异常：

• 第一次调用insertPart函数时，节点可正常插入到表头位置
• 第二次调用插入函数时，无法正常定位插入位置，输入完全部待插入数据后程序异常退出，报错为：Process exited after 8.277 seconds with return value 3221225477（Windows下的内存非法访问错误）

现有实现代码 #

typedef struct part {
    int partNumber;
    char partName[200];
    int partQuantity;
    struct part *nextPart;
} Part;
Part *inventory = NULL;

void insertPart();

int
main(int argc, char *argv[])
{
    insertPart();
    insertPart();
    insertPart();
    insertPart();
    return 0;
}

void
insertPart()
{
    Part *tempPart,
    *traversePart,
    *swapPart;
    int counter = 0;

    traversePart = inventory;
    tempPart = (Part *) malloc(sizeof(Part *));

    printf("Enter the Part Number\n");
    scanf("%d", &(tempPart->partNumber));
    getchar();

    printf("Enter the Part Name\n");
    fgets(tempPart->partName, 200, stdin);

    printf("Enter the Part Quantity\n");
    scanf("%d", &(tempPart->partQuantity));
    getchar();

    if (inventory == NULL) {
        inventory = tempPart;
        printf("Part added at the first position.\n");
    }
    else {

        while (traversePart->nextPart->partNumber < tempPart->partNumber) {
            counter++;
            traversePart = traversePart->nextPart;
            if (traversePart->nextPart == NULL) {
                break;
            }
        }
        if (counter == 0) {
            swapPart = inventory;
            inventory = tempPart;
            tempPart->nextPart = swapPart;
        }
        else if (traversePart->nextPart == NULL) {
            traversePart->nextPart = tempPart;
        }
        else {
            swapPart = traversePart->nextPart;
            traversePart->nextPart = tempPart;
            tempPart->nextPart = swapPart;
        }
    }
    printf("Element added at position : %d", counter);
}

问题根因 #

• 内存分配大小错误：代码中用malloc(sizeof(Part *))分配内存，实际只分配了一个指针的大小（通常4/8字节），远小于Part结构体本身的大小（约200多字节），写入零件名称等长字符串时会直接造成内存越界。
• 遍历逻辑未做空指针判断：进入非空链表的分支后，直接访问traversePart->nextPart->partNumber，如果当前链表只有1个节点，traversePart->nextPart本身就是NULL，访问空指针的成员会直接触发内存非法访问。
• 新节点指针未初始化：分配的tempPart的nextPart字段没有初始化为NULL，插入到尾节点时会残留野指针，后续遍历链表时会触发崩溃。

修复后的实现代码 #

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

typedef struct part {
    int partNumber;
    char partName[200];
    int partQuantity;
    struct part *nextPart;
} Part;
Part *inventory = NULL;

void insertPart();

int
main(int argc, char *argv[])
{
    insertPart();
    insertPart();
    insertPart();
    insertPart();
    return 0;
}

void
insertPart()
{
    Part *tempPart, *traversePart;
    int insertPos = 1;

    // 修正内存分配大小
    tempPart = (Part *)malloc(sizeof(Part));
    // 新节点next指针初始化为空，消除野指针
    tempPart->nextPart = NULL;

    printf("Enter the Part Number\n");
    scanf("%d", &(tempPart->partNumber));
    getchar();

    printf("Enter the Part Name\n");
    fgets(tempPart->partName, 200, stdin);

    printf("Enter the Part Quantity\n");
    scanf("%d", &(tempPart->partQuantity));
    getchar();

    // 空链表直接插表头
    if (inventory == NULL) {
        inventory = tempPart;
        printf("Part added at the first position.\n");
    } else {
        traversePart = inventory;
        // 处理待插入编号比头节点还小的场景，直接插在表头
        if (tempPart->partNumber < inventory->partNumber) {
            tempPart->nextPart = inventory;
            inventory = tempPart;
            printf("Part added at the first position.\n");
        } else {
            // 遍历找插入位置，先判断空指针再判断编号大小
            while (traversePart->nextPart != NULL && 
                   traversePart->nextPart->partNumber < tempPart->partNumber) {
                insertPos++;
                traversePart = traversePart->nextPart;
            }
            // 插入到当前节点的后方
            tempPart->nextPart = traversePart->nextPart;
            traversePart->nextPart = tempPart;
        }
    }
    printf("Element added at position : %d\n", insertPos);
}

修复点说明 #

• 内存分配大小从sizeof(Part *)改为sizeof(Part)，匹配结构体实际占用的内存大小
• 遍历前先判断待插入节点是否需要插在表头，避免直接访问头节点的空next指针
• 遍历循环先判断当前节点的next是否为空，再判断编号大小，彻底避免空指针访问
• 新节点分配完成后直接将next指针初始化为NULL，消除野指针风险
• 简化插入逻辑，取消多余的交换指针变量，只要定位到插入位置的前一个节点，直接修改指针指向即可

内容的提问来源于stack exchange，提问作者Ayush Narang