6-5链式表操作集

题目描述

实现链表的操作集，也就是对链表进行增删改查。

题目地址为:https://pintia.cn/problem-sets/15/problems/728

List结构定义 

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct LNode *PtrToLNode;

struct LNode {

    ElementType Data;

    PtrToLNode Next;

};

typedef PtrToLNode Position;

typedef PtrToLNode List;

查询元素

要求

返回线性表中首次出现X的位置。若找不到则返回ERROR

具体代码

1
2
3
4
5
6
7
8
9
10
Position Find( List L, ElementType X ) {
    Position p = L;
    while(p) {
        if(p->Data == X) {
            return p;
        }
        p = p->Next;
    }
    return ERROR;
}

插入元素

要求

将X插入在位置P指向的结点之前，返回链表的表头。如果参数P指向非法位置，则打印“Wrong Position for Insertion”，返回ERROR

先找到P结点就需要先循环，但是又要有一个插入操作，同时就需要保留P结点之前的一个结点

非法位置指的是没有P结点就是这样

之后就是常规的插入操作了

具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
List Insert( List L, ElementType X, Position P ) {
    Position prev = NULL;
    Position next = L;

    PtrToLNode node = (PtrToLNode)malloc(sizeof(struct LNode));
    node->Data = X;
    node->Next = NULL;

    if (next == P) {
        node->Next = next;
        return node;
    }
    do {
        if(!next) {
            break;
        }
        prev = next;
        next = next->Next;
        if(next == P) {
            node->Next = next;
            if(!prev) {
                return node;
            } else {
                prev->Next = node;
                return L;
            }
        }
    } while(next);

    printf("Wrong Position for Insertion\n");
    return ERROR;
}

思考

在上述代码中存在着一系列问题。虽然能通过Test，但是有着太多的判断和处理

空链表插入，单结点尾部插入。。。。。。

当我把函数划分为多个部分的时候已经违背了简洁的初衷，而不是把问题简单化来处理

仔细思考，插入的关键不就是有无之前结点存在嘛！就两种情况，然后面对需要对比的判断不需要先移动，这样就避免了Segment fault。

具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
List Insert( List L, ElementType X, Position P ) {
    List head = L;
    PtrToLNode node = (PtrToLNode)malloc(sizeof(struct LNode));
    node->Data = X;
    node->Next = NULL;

    //无前结点的情况
    if (L == P) {
        node->Next = L;
        return node;
    }

    //有前结点的情况
    while(L) {
        if(L->Next == P) {
            node->Next = L->Next;
            L->Next = node;
            return head;
        }
        L = L->Next;
    }

    printf("Wrong Position for Insertion\n");
    return ERROR;
}

删除元素

要求

将位置P的元素删除并返回链表的表头。若参数P指向非法位置，则打印“Wrong Position for Deletion”并返回ERROR。

就是循环找到之后删除，同样也需要保留两个结点。同上解决方案，不实际移动，仅比较。

具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
List Delete( List L, Position P ) {
    List head = L;

    if(P == L) {
        return L->Next;
    }

    while(L) {
        if (L->Next == P) {
            L->Next = P->Next;
            return head;
        }
        L = L->Next;
    }

    printf("Wrong Position for Deletion\n");
    return ERROR;
}