链表练习题c++代码实现(一)：头插法，尾插法，删除指定结点

lscc.h文件
头插法和尾插法都代码实现都有。
采用面向对象的方法实现，第一个文件是.h文件，是对方法的初步定义，
具体实现在lscc.cpp文件里(往下滑就能看见啦)。

/*
 *文件名：lscc.h
 *作  者：辛伯达
 *描  述：链表的基本操作和4个习题
 */

#ifndef LSCC_H
#define LSCC_H
#include <iostream>

using namespace std;

//定义链表中的数据结点
typedef struct ListNode{
    int data;//数据域
    ListNode *next;//指针域
}ListNode,*LinkList;
//第一个listNode指的是一个结点
//*LinkList指的是一个指向listNode数据类型的指针的指针
/*有点类似于int *pr;这是一个指向int类型的指针
如果不定义*LinkList的话，后面再建立链表的时候
就要先
ListNode *LinkList;
像上面那样定义一个指向链表的指针。
*/
class lscc
{
    public:
        lscc();
        ~lscc();
        //定义：生成链表的函数
        //头插法：
        LinkList List_HeadInsert();
        //尾插法:
        LinkList List_TailInsert();

        //定义一个输出单链表的函数
        void printLink(LinkList &);

        //1.设计一个算法，删除不带头结点的单链表L中所有值为x的结点
        void del_x(LinkList &, int);

        //2.删除带头结点的元素,并返回删除后的链表
        LinkList removeElements(LinkList &, int);

        //3.丛尾到头反向输出链表的值
        //法一：用栈  法二：用递归(这里用递归实现)
        void R_Print(LinkList &);

        //4.删除链表中值最小的结点(最小的结点唯一)
        LinkList Delete_Min (LinkList&);

};

#endif // LSCC_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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

lscc.cpp文件

/*
 *文件名：
 *作  者：辛伯达
 *描  述：王道考研链式存储代码题实现
 *
 */
#include "lscc.h"
#include <iostream>
using namespace std;


lscc::lscc()
{
    //ctor
}

//头插法建立链表
LinkList lscc::List_HeadInsert(){
    ListNode *s;
    LinkList L = new ListNode;//新建一个结点，并让指针L指向这个结点
    L->next = NULL;
    int x;
    cin >> x;
    while (x != 9999) {//输入9999表示插入结束
        s = new ListNode;//新建一个结点，并让指针s指向这个结点
        s->data = x;
        s->next = L->next;
        L->next = s;
        cin >> x;
    }
    return L;
}

//尾插法建立链表
LinkList lscc::List_TailInsert() {
    ListNode *s, *r;
    /*这里定义两个指针
      指针s指向新建的结点new ListNode,用来操作新的结点。
      指针r永远指向最后一个结点，方便在末尾插入。
    */
    LinkList L = new ListNode;
    r = L;
    L->next = NULL;
    int x;
    cin >> x;
    while (x!=9999) {
        s = new ListNode;//new一个新的结点，让指针s指向这个结点
        s->data = x;
        r->next = s;
        r = s;//指针r往后移动一位，让其始终指向刚插入的新结点
        cin >> x;
    }
    r->next = NULL;//最后一定不要忘记让最后一个结点指向NULL
    return L;
}

//定义一个输出单链表的函数
void lscc:: printLink(LinkList &L) {
    ListNode *q;//这里也是要定义一个指向linkNode数据类型的指针
    q = L->next;
    while (q) {
        cout << q->data << " ";
        q = q->next;
    }
    cout << endl;
}

//1.递归删除(不使用while循环)链表中指定的元素x
void lscc::del_x(LinkList &L, int x) {
    ListNode *s;
    if (L==NULL) {
        return;//如果是空表，则直接返回
    }
    if (L->data == x) {
        s = L;
        L = L->next;//注意这里是L往后移动一个结点
        delete s;//然后再删除s指向的结点
        del_x(L,x);
    }else{
        del_x(L->next,x);
    }
}
//2.删除带头结点链表中的指定元素（不用递归的方法）
LinkList lscc::removeElements(LinkList &L, int val) {
    ListNode * dummyHead = new ListNode;//设置一个虚拟头结点
    dummyHead->next = L;//让虚拟头结点指向L
    ListNode* cur = dummyHead;//再来一个临时指针指向虚拟头结点
    while (cur->next != NULL) {
        if (cur->next->data == val) {
            ListNode* tmp = cur->next;//设置临时指针指向符合删除条件的结点
            cur->next = cur->next->next;
            delete tmp;//释放符合删除条件的元素
        }else {
            cur = cur->next;
            //如果当前结点不符合删除条件，cur指针往后移动一个结点
        }
    }
    L = dummyHead->next;
    //删除完以后，再把虚拟头结点删除了
    delete dummyHead;
    return L;//返回删除的结点
}

//3.丛尾到头反向输出链表的值
//法一：用栈  法二：用递归(这里用递归实现)
void lscc::R_Print(LinkList &L) {
    //每当访问一个结点的时候，先递归访问输出其后面的结点，在访问输出自身结点
    if (L->next != NULL) {
        R_Print(L->next);
    }
    if (L != NULL) {
        cout << L->data <<endl;
    }
}


//4.删除链表中值最小的结点(最小的结点唯一)
LinkList lscc::Delete_Min(LinkList &L) {
    /*思路：
     *指针minp指向检测过程中值最小的结点
     *指针p为工作指针，每次往后移动一个单位
     *p每移动一个单位，就比较p->data 和 minp->data值的大小
     *若：minp->data小，则p往后移动一个单位继续比较
     *若:p->data小，则minp=p,让minp指向当前p指向的结点。
     *注意：工作指针p和最小值指针minp都应该定义前驱指针，pre和minpre，方便删除
     */
     //定义虚拟头结点
     ListNode* dummyNode = new ListNode;
     dummyNode->next = L;//把虚拟头结点放在L前面

     //定义要使用的指针
     //工作指针的前驱指针:pre
     //工作指针:p
     ListNode* pre = dummyNode, *p = dummyNode->next;
     //最小值指针的前驱指针：minpre
     //最小值指针：minp
     ListNode* minpre = dummyNode, *minp = dummyNode->next;

     //开始while循环
     while (p != NULL) {
        if (p->data < minp->data) {
            //如果此时工作指针指向的结点小，则刷新minp
            minp = p;
            minpre = pre;
        }
        //继续扫描下一个结点
        pre = p;
        p = p->next;
     }
     //删除最小结点
     minpre->next = minp->next;
     delete minp;
     return L;
}

lscc::~lscc()
{
    //dtor
}

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160

main.cpp

int main() {
	//链表的操作
    //使用头插法新建一个链表
    lscc list1;
    ListNode *L;
    L = list1.List_TailInsert();
    list1.printLink(L);
    list1.del_x(L, 3);//用递归删除指定元素
    
    cout << "------------------------------" << endl;

    //用带头结点指针删除指定元素
    L = list1.removeElements(L, 3);
    list1.printLink(L);
    cout << "------------------------------" << endl;

    //3.逆序输出链表的值
    list1.R_Print(L);
    cout << "------------------------------" << endl;
    
    //4.删除链表中最小值结点(最小值结点唯一)
    list1.Delete_Min(L);
    list1.printLink(L);
    cout << "------------------------------" << endl;

	return 0;
}
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