個人博客的PAT題解

題目

OJ平臺

題目詳解

就是一個靜態(tài)鏈表刪除元素的數(shù)據(jù)結(jié)構(gòu)類型題目，這題最坑的地方在于輸出的時候需要地址五位數(shù)補(bǔ)0，如果是-1則不用補(bǔ)，導(dǎo)致你明明是對的，還以為是錯誤的。。???♂?

• 我用隊列存儲刪除的結(jié)點的地址，然后后面再進(jìn)行連接即可。

解題代碼

基本變量

int head, rm_head = -1; //分別用于存儲兩個鏈表的頭結(jié)點地址
int N;

struct node {
    int val;
    int next;

    node() : val(0), next(-1) {}
} linklist[MaxN];

queue<int> St; //存儲被刪除結(jié)點的地址
bitset<MaxN> check(0); //用于查重

Input函數(shù)

//輸入和構(gòu)建鏈表
void Input() {
    scanf("%d%d", &head, &N);
    int c = N;
    while (c--) {
        int addr, val, next;
        scanf("%d%d%d", &addr, &val, &next);
        linklist[addr].val = val;
        linklist[addr].next = next;
    }
}

handle函數(shù)

//處理鏈表的去重問題
void handle() {
    //正常刪除鏈表結(jié)點的處理方式
    int pre = head;
    check[abs(linklist[head].val)] = 1;
    for (int i = linklist[pre].next; i != -1; i = linklist[i].next) {
        int val = abs(linklist[i].val);
        if (!check[val]) {
            check[val] = 1;
            pre = i;
        }//一旦出現(xiàn)重復(fù)結(jié)點，把這個結(jié)點刪除就行，刪除結(jié)點的操作需要雙指針輔助
        else {
            linklist[pre].next = linklist[i].next;
            St.push(i);
        }
    }
    if (St.empty())
        return;
    //根據(jù)隊列進(jìn)行正確連接
    int num = St.front();
    St.pop();
    rm_head = num;
    while (!St.empty()) {
        linklist[num].next = St.front();
        num = linklist[num].next;
        St.pop();
    }
    linklist[num].next = -1;
}

print函數(shù)

//打印鏈表即可---注意小坑--(地址打印五位數(shù)字，少了補(bǔ)0,-1時不能打印五位數(shù))
void print() {
    handle();
    for (int i = head; i != -1; i = linklist[i].next) {
        if (linklist[i].next != -1)
            printf("%05d %d %05d\n", i, linklist[i].val, linklist[i].next);
        else {
            printf("%05d %d %d", i, linklist[i].val, linklist[i].next);
        }
    }
    if (rm_head == -1)
        return;
    printf("\n");
    for (int i = rm_head; i != -1; i = linklist[i].next) {
        if (linklist[i].next != -1)
            printf("%05d %d %05d\n", i, linklist[i].val, linklist[i].next);
        else {
            printf("%05d %d %d", i, linklist[i].val, linklist[i].next);
        }
    }
}

整合代碼提交

效率還行

#include<bits/stdc++.h>
#define MaxN 100000
using namespace std;
int head, rm_head = -1; //分別用于存儲兩個鏈表的頭結(jié)點地址
int N;

struct node {
    int val;
    int next;

    node() : val(0), next(-1) {}
} linklist[MaxN];

queue<int> St; //存儲被刪除結(jié)點的地址
bitset<MaxN> check(0); //用于查重

//輸入和構(gòu)建鏈表
void Input() {
    scanf("%d%d", &head, &N);
    int c = N;
    while (c--) {
        int addr, val, next;
        scanf("%d%d%d", &addr, &val, &next);
        linklist[addr].val = val;
        linklist[addr].next = next;
    }
}

//處理鏈表的去重問題
void handle() {
    //正常刪除鏈表結(jié)點的處理方式
    int pre = head;
    check[abs(linklist[head].val)] = 1;
    for (int i = linklist[pre].next; i != -1; i = linklist[i].next) {
        int val = abs(linklist[i].val);
        if (!check[val]) {
            check[val] = 1;
            pre = i;
        }//一旦出現(xiàn)重復(fù)結(jié)點，把這個結(jié)點刪除就行，刪除結(jié)點的操作需要雙指針輔助
        else {
            linklist[pre].next = linklist[i].next;
            St.push(i);
        }
    }
    if (St.empty())
        return;
    //根據(jù)隊列進(jìn)行正確連接
    int num = St.front();
    St.pop();
    rm_head = num;
    while (!St.empty()) {
        linklist[num].next = St.front();
        num = linklist[num].next;
        St.pop();
    }
    linklist[num].next = -1;
}

//打印鏈表即可---注意小坑--(地址打印五位數(shù)字，少了補(bǔ)0,-1時不能打印五位數(shù))
void print() {
    handle();
    for (int i = head; i != -1; i = linklist[i].next) {
        if (linklist[i].next != -1)
            printf("%05d %d %05d\n", i, linklist[i].val, linklist[i].next);
        else {
            printf("%05d %d %d", i, linklist[i].val, linklist[i].next);
        }
    }
    if (rm_head == -1)
        return;
    printf("\n");
    for (int i = rm_head; i != -1; i = linklist[i].next) {
        if (linklist[i].next != -1)
            printf("%05d %d %05d\n", i, linklist[i].val, linklist[i].next);
        else {
            printf("%05d %d %d", i, linklist[i].val, linklist[i].next);
        }
    }
}

int main() {
    Input();
    print();
    return 0;
}