删除链表中所有值为x的元素

1.不带头结点

（1）不带头结点递归删除

  1. 递归算法
  2. 删除不带头结点的单链表 L 中所有值为 x 的结点
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
#include "presetNoHead.h"

//利用递归 删除指定元素
void recursiveDelete(Node *&L, int x) {
    Node *p = L;
    if (L == NULL) return;//递归出口
    if (L->data == x) {
        L = L->next;//L->next = L->next->next;
        free(p);
        recursiveDelete(L, x);
    } else {
        recursiveDelete(L->next, x);//L = L->next;
    }
}

int main() {
    int n;
    Node list;
    Node *L = &list;
    cout << "enter the length of this linklist : "; cin >> n;
    createLinkList(L, n);
    cout << "current linklist: " << endl; print(L);
    int x;
    cout << "enter the target : "; cin >> x;
    recursiveDelete(L, x);
    cout << "after the deletion : "; print(L);
    return 0;
}

（2）不带头结点非递归删除

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
33
34
35
36
37
38
39
40
41
42
43
// while循环非递归删除
void whileDelete(LinkList& L, int x) {
    if (L == NULL)
        return;
    Node* p = L;
    while (p->next != NULL) {
        if (p->next->data == x) {
            Node* q = p->next;
            p->next = q->next;
            delete q;
        }
        if (p->next != NULL)
            p = p->next; // 若p指针已指向尾元素则不进行自增操作（否则将p指针置空导致访问p->next非法空间）
    }
}
void whileDelete(LinkList& L, int x) {
    if (L == NULL)
        return;
    Node* p = L;
    while (p->next != NULL) {
        if (p->next->data == x) {
            Node* q = p->next;
            p->next = q->next;
            delete q;
        } else {
            p = p->next;
        }
    }
}
void whileDelete(LinkList& L, int x) {
    if (L == NULL)
        return;
    Node* p = L;
    while (p->next != NULL) {
        if (p->next->data != x) {
            p = p->next;
        } else {
            Node* q = p->next;
            p->next = q->next;
            delete q;
        }
    }
}

2.带头结点

（1）带头结点非递归删除

删除带头结点的单链表 L 中所有值为 x 的结点

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
#include "presetHead.h"

void whileDelete(LinkList &L, int x) {
    if (L == NULL) return;
    Node *p = L;
    while (p->next != NULL) {
        if (p->next->data != x) {
            p = p->next;
        } else {
            Node *q = p->next;
            p->next = q->next;
            delete q;
        }
    }
}

int main() {
    int n;
    cout << "enter the length of this linklist : "; cin >> n;
    LinkList L; createLinkList(L, n);
    cout << "current linklist: " << endl; print(L);
    int x;
    cout << "enter the target : "; cin >> x;
    whileDelete(L, x);
    cout << "after the deletion : "; print(L);
    return 0;
}

3.单链表有无头结点的区别

  1. 头结点：在单链表第一个元素结点之前设置的一个结点， 数据域可以不存任何信息，指针域指向单链表第一个元素的结点。

    image-20230703093814284

  2. 头指针：指向单链表的第一个结点的指针， 如果单链表有头结点，则头指针指向头结点 ，如果单链表没有头结点，则头指针指向第一个首元结点。

  3. 首元结点：单链表中第一个有数据元素的结点。如果单链表有头结点，则首元结点为头结点的下一个结点，如果单链表没有头结点，则首元结点就是单链表的第一个结点。

  4. 设置头结点的优点：

    • 减少了单链表添加与删除时特殊情况的判断，减少程序的复杂性。

    • 主要是添加和删除在第一个有元素的结点（首元结点）上有区别，如果链表没有头结点，则删除或添加时都得需要判断一次首元结点，有头结点以后，首元结点实际为链表的第二个结点，使得所有的元素结点的添加删除更具有统一性。便于空表和非空表的统一处理，

    • 无论链表是否为空，头指针都是指向头结点的非空指针。

presethead.h

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
33
34
35
36
37
38
#ifndef _PRESETHEAD_H
#define _PRESETHEAD_H

#include <iostream>
using namespace std;

typedef struct Node {
    int data;
    struct Node *next;
} Node, *LinkList;

//链表数据插入（有头结点）
void createLinkList(LinkList &L, int n) {
    L = new Node;//链表初始化
    L->next = NULL;
    Node *r = L;//创建尾指针初始时指向头结点
    for (int i = 0; i < n; ++i) {
        Node *p = (Node *)malloc(sizeof(Node));
        cin >> p->data;
        p->next = NULL;
        
        r->next = p;
        r = p;
    }
}

//链表数据打印
void print(LinkList L) {
    Node *p = L->next;
    while (p != NULL) {
        //cout << p->data << ":" << p->next << " ";
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

#endif

presetnohead.h

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
33
34
35
36
37
38
#ifndef _PRESETNOHEAD_H
#define _PRESETNOHEAD_H

#include <iostream>
using namespace std;

typedef struct Node {
    int data;
    struct Node *next;
} Node;

//尾插法建立链表（无头结点）
void createLinkList(Node *L, int n) {
    cin >> L->data;//初始化首元结点
    L->next = NULL;
    Node *r = L;//创建尾指针初始时指向头结点
    for (int i = 0; i < n-1; ++i) {
        Node *p = (Node *)malloc(sizeof(Node));
        cin >> p->data;
        p->next = NULL;
        
        r->next = p;
        r = p;
    }
}

//链表数据打印
void print(Node *L) {
    Node *p = L;
    while (p != NULL) {
        //cout << p->data << ":" << p->next << " ";
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

#endif