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

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

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

#ifndef LSCC_H
#define LSCC_H
#include 

using namespace std;

//定义链表中的数据结点
typedef struct ListNode{
    int data;//数据域
    ListNode *next;//指针域
}ListNode,*linkList;
//第一个listNode指的是一个结点
/
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

lscc.cpp文件

#include "lscc.h"
#include 
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;
    
    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 <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
}

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