愿你坚持不懈,努力进步,进阶成自己理想的人

—— 2017.09, 写给3年后的自己

PAT-课后练习2-(D)单向链表的删除操作

定义单向链表struct Node并实现:输入若干个学生信息(包括学号、姓名和成绩),输入学号为0时输入结束,再输入一个成绩值,将成绩小于该值的学生信息删除,并将成绩大于等于该值的学生信息输出。

输入输出示例:括号内为说明
输入:
1 zhang 78
2 wang 80
3 li 75
4 zhao 85

输出:
2 wang 80
4 zhao 85

#include <iostream>
using namespace std;
struct Node {
    int num;
    string name;
    int score;
    Node * next;
};

Node * create() {
    Node *p1=NULL, *p2=NULL, *head=NULL;
    p1 = new Node;
    cin >> p1->num;
    while(p1->num != 0) {
        cin >> p1->name >> p1->score;
        if(head==NULL) head = p1;
        else p2->next = p1;
        p2 = p1;
        p1 = new Node;
        cin >> p1->num;
    }
    if(head) p2->next = NULL;
    return head;
}

Node * delNode(Node * head, int score) {
    Node *cur=head, *pre=NULL;
    if(head!=NULL) {
        do {
            if(cur->score < score) {
                if(pre!=NULL) {
                    pre->next = cur->next;
                } else {
                    head = cur->next;
                }
            }
            pre = cur;
            cur = cur->next;
        } while(cur!=NULL);
    }
    return head;
}

void print(Node *head) {
    Node *p = head;
    if(head!=NULL) {
        do {
            cout << p->num << " " << p->name << " " << p->score << endl;
            p = p->next;
        } while(p!=NULL);
    }
}

int main() {
    int min;
    Node * p = create();
    cin >> min;
    p = delNode(p, min);
    print(p);
    return 0;
}

以此为背景,总结一下:
要实现一个链表的删除操作,比如对于一个存放学生成绩的链表,它的每个节点的结构体定义为:
struct Node {
int num;
int score;
Node * next;
};
如果我们要删除其中一些节点,比如成绩不足60分的节点删掉,那该怎么办?假设我们有一个这样子的链表:
head->[59]->[60]->[55]->[70]->[45]->NULL
这个链表就包括了要处理的三个情形:删除首端的、中间的、末尾的节点。分别就这三种情形做下分析:
1、 删除首端的。就把head节点指向当前节点的下一节点
2、 删除中间的。就把当前节点的前一个节点的下一个节点指向当前这个节点的下一个节点
3、 删除末尾的和删除中间的并没有区别,所以不用单独处理

代码实现思路:
定义指针变量pre、cur分别保存前一个节点和当前节点。一开始的时候,cur自然是取head的值,pre一开始为NULL。
然后用do…while循环,在每次循环都判断当前的cur->score是否小于60,如果小于60的话,就要执行删除操作,即:
1、若pre=NULL时,说明当前节点并没有前一个节点,它是首端的节点,要删除当前节点,就把head指向当前节点的下一个节点即head=cur->next就可以了
2、如果pre!=NULL,说明当前节点是有前一个节点的,要删除当前节点,要让前一个节点的下一节点为当前节点的下一节点,即pre->next=cur->next
每次循环的最后,都要为下一次循环做好准备,即保存好当前节点,以便作为下一节点的pre节点。然后再把当前节点换为下一节点就可以了。即为pre=cur; cur=cur->next,最终,我们可以用一个函数实现整个功能:

Node * delNode(Node * head, int score) {
    Node *cur=head, *pre=NULL;
    if(head!=NULL) {
        do {
            if(cur->score < score) {
                if(pre!=NULL) pre->next = cur->next;
                else head = cur->next;
            }
            pre = cur;
            cur = cur->next;
        } while(cur!=NULL);
    }
    return head;
}