LinkList.h

#pragma once
#include<iostream>
using namespace std;

class LNode {
    friend class LinkList;
public:
    int data;
    LNode* next;

};

class LinkList {
public:
    LNode* first;

    LinkList() {
        first = new LNode();
        first->data = 666;
        first->next = nullptr;
    }

    void creatH(int arr[], int n) {
        LNode* p;
        LNode* s;
        p = first;
        for (int i = 0; i < n; i++) {
            s = new LNode();
            s->data = arr[i];
            s->next = p->next;
            p->next = s;
        }
    }

    void creatE(int arr[], int n) {
        LNode* p;
        LNode* s;
        p = first;
        for (int i = 0; i < n; i++) {
            s = new LNode();
            s->data = arr[i];
            p->next = s;
            p = s;
        }
    }


    void show() {
        LNode* p;
        p = first->next;
        while (p != nullptr) {
            cout << p->data << " ";
            p = p->next;
        }
        cout << endl;
    }

    /**
    （1）定位函数Locate：在单链表中寻找第i个结点。若找到 ，则返回第i个结点的地址；
    若找不到，则返回NULL。
    */
    LNode* Locate(int i) {
        LNode* p = first;
        LNode* res = NULL;
        int flag = 1;
        for (int index = 0; index < i; index++) {
            if (p->next != nullptr) {
                p = p->next;
            }
            else {
                flag = 0;
                break;
            }
        }
        if (flag == 1) {
            res = p;
        }
        return res;
        
    }

    /**
    （2）求最大值函数max：通过一趟遍历在单链表中确定值最大的点。
    */
    LNode* max() {
        LNode* p;
        LNode* res;
        p = first->next;
        res = p;
        while (p != nullptr) {
            if (p->data > res->data) {
                res = p;
            }
            p = p->next;
        }
        return res;
    }

    /**
    （3）统计函数number：统计单链表中具有给定值x的所有元素。
    */
    int number(int x) {
        int n = 0;
        LNode* p;
        p = first->next;
        while (p != nullptr) {
            if (p->data == x) {
                n++;
            }
            p = p->next;
        }
        return n;
    }
    
    /**
    (4)建立函数creat：根据一维数组a[n]建立一个单链表，使单链表中各元素的次序与
    a[n]中各元素的次序相同，要求改程序的时间复杂度为O(n)。
    */
    void creat(int a[], int n) {
        //与creatE()是等价函数
        creatE(a, n);
    }

    /**
    （5）整理函数tidyup：在非递减有序的单链表中删除值相同的多余结点。
    */
    void tidyup() {
        LNode* p;
        LNode* s;
        p = first;
        while (p->next->next != nullptr) {
            if (p->next->data == p->next->next->data) {
                s = p->next;
                p->next = p->next->next;
                delete s;
            }
            else {
                p = p->next;
            }
            //易错点：删除以后不能直接跳转下一个结点，需要清除干净以后才能跳转
        }
    }

};

main.cpp

#include"LinkList.h"

int main() {
    cout << "Test Creator Function:" << endl;
    int creatFunction[] = { 1,2,3,4,5,6,7,8,9 };
    LinkList LC1,LC2;
    cout << "Creat linklist from the head:" << endl;
    LC1.creatH(creatFunction, 9);
    LC1.show();
    cout << "Creat linklist from the ending:" << endl;
    LC2.creatE(creatFunction, 9);
    LC2.show();

    cout << "---------------------------------" << endl;

    cout << "Test 01:" << endl;
    LinkList T1_1;
    int t1_1[] = { 1,5,9,4,1,6,85,12,56,5,12,52 };
    T1_1.creatE(t1_1, 12);
    T1_1.show();
    LNode* T1_res;
    T1_res = T1_1.Locate(5);
    if (T1_res != NULL) {
        cout << "The 5th elem is " << T1_res->data << endl;
    }
    else {
        cout << "NULL" << endl;
    }

    cout << "---------------------------------" << endl;

    cout << "Test 02:" << endl;
    LinkList T2_1;
    int t2_1[] = { 56,8,9,56,15,38,41,94,456,462,2 };
    T2_1.creatH(t2_1, 11);
    T2_1.show();
    LNode* res;
    res = T2_1.max();
    cout << "The max node's data is " << res->data << endl;

    cout << "---------------------------------" << endl;

    cout << "Test 03:" << endl;
    LinkList T3_1;
    int t3_1[] = { 1,9,1,8,1,6,1,5,1,4,1,1,2,3,1 };
    T3_1.creatH(t3_1, 15);
    T3_1.show();
    int num = T3_1.number(1);
    cout << "The number of 1 in this array is " << num << endl;

    cout << "---------------------------------" << endl;

    cout << "Test 04:" << endl;
    LinkList T4_1;
    int t4_1[] = { 1,2,3,4,5,6,7,8,9 };
    T4_1.creat(t4_1, 9);
    T4_1.show();

    cout << "---------------------------------" << endl;

    cout << "Test 05:" << endl;
    LinkList T5_1;
    int t5_1[] = { 1,1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,6,6,6,6,6,7,7,7,8,8,9,9,9,9,9 };
    T5_1.creat(t5_1, 31);
    T5_1.show();
    T5_1.tidyup();
    T5_1.show();

    return 0;
}