PTA数据结构题目：链表操作集合

寻找结点

插入结点

错误分析

while (prev != NULL && prev->Next != P)
为什么我写成
while (prev->Next != P && prev != NULL)
的时候会发生段错误，这两种写法逻辑上不是一样的吗？

野指针

逻辑顺序导致的潜在风险
在 C 语言中，逻辑与（&&）运算符是短路求值的。这意味着当计算A && B时，如果A为假，就不会再计算B了，因为整个表达式已经确定为假。
当你写成while (prev->Next!= P && prev!= NULL)时，如果prev是NULL，那么prev->Next这个操作会导致段错误。因为NULL指针是不能进行成员访问操作（->）的。而while (prev!= NULL && prev->Next!= P)这种写法先判断prev是否为NULL，只有当prev不为NULL时，才会去访问prev->Next，这样就避免了空指针访问的问题，是一种更安全的写法。

删除结点

代码

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

#define ERROR NULL
typedef int ElementType;
typedef struct LNode *PtrToLNode;
struct LNode
{
    ElementType Data;
    PtrToLNode Next;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;

Position Find(List L, ElementType X);
List Insert(List L, ElementType X, Position P);
List Delete(List L, Position P);

int main()
{
    List L;
    ElementType X;
    Position P, tmp;
    int N;

    L = NULL;
    scanf("%d", &N);
    while (N--)
    {
        scanf("%d", &X);
        L = Insert(L, X, L);
        if (L == ERROR)
            printf("Wrong Answer\n");
    }
    scanf("%d", &N);
    while (N--)
    {
        scanf("%d", &X);
        P = Find(L, X);
        if (P == ERROR)
            printf("Finding Error: %d is not in.\n", X);
        else
        {
            L = Delete(L, P);
            printf("%d is found and deleted.\n", X);
            if (L == ERROR)
                printf("Wrong Answer or Empty List.\n");
        }
    }
    L = Insert(L, X, NULL);
    if (L == ERROR)
        printf("Wrong Answer\n");
    else
        printf("%d is inserted as the last element.\n", X);
    P = (Position)malloc(sizeof(struct LNode));
    tmp = Insert(L, X, P);
    if (tmp != ERROR)
        printf("Wrong Answer\n");
    tmp = Delete(L, P);
    if (tmp != ERROR)
        printf("Wrong Answer\n");
    for (P = L; P; P = P->Next)
        printf("%d ", P->Data);
    return 0;
}

Position Find(List L, ElementType X)
{
    while (L != NULL)
    {
        if (L->Data == X)
        {
            return L;
        }
        L = L->Next;
    }
    return ERROR;
}
List Insert(List L, ElementType X, Position P)
{
    Position new = (Position)malloc(sizeof(struct LNode));
    if (new == NULL)
    {
        return ERROR;
    }
    new->Data = X;
    new->Next = NULL;
    if (P == NULL)
    {
        if (L == NULL)
        {
            return new;
        }
        Position last = L;
        while (last->Next != NULL)
        {
            last = last->Next;
        }
        last->Next = new;
        return L;
    }
    if (P == L)
    {
        new->Next = L;
        return new;
    }
    Position prev = L;
    //反过来写会造成野指针错误，访问空指针
    while (prev != NULL && prev->Next != P) // 这里不同
    {
        prev = prev->Next;
    }
    if (prev == NULL)
    {
        free(new);
        printf("Wrong Position for Insertion\n");
        return ERROR;
    }
    new->Next = prev->Next;
    prev->Next = new;
    return L;
}
List Delete(List L, Position P)
{
    if (P == NULL)
    {
        printf("Wrong Position for Deletion\n");
        return ERROR;
    }
    if (P == L)
    {
        List tmp = L; // 不同
        L = L->Next;
        free(tmp);
        return L;
    }
    Position prev = L;
    while (prev != NULL && prev->Next != P)
    {
        prev = prev->Next;
    }
    if (prev == NULL)
    {
        printf("Wrong Position for Deletion\n");
        return ERROR;
    }
    prev->Next = P->Next;
    free(P);
    return L;
}