1.数组的C++实现及相关知识

(1)C++实现

        C++是一门面向对象编程的语言，对于数组的实现我们就是要将数组这个对象的方法和属性写到数组类当中，程序如下：

//数组实现
class Array
{
    public:
    //构造
    Array(int size = 10):mCap(size)
    {
        mpArr = new int[size];
        mCur = 0;   //当不小心将mCur写成了mCap时，添加数量超过了最开始的的数组容量，在显示时数组成功扩容了但是mCap显示
    }               //的是0，是因为其实其并没有成功扩容而是数组进行了越界访问。
    //析构
    ~Array()
    {
        delete []mpArr;
        mpArr = nullptr;
    }
    //末尾位置增加元素
    void push_back(int val)
    {
        if(mCur == mCap)
        {
            explend(2*mCap);
        }
        mpArr[mCur++] = val;
    }
    //末尾位置删除元素
    void pop_back()
    {
        mCur--;
    }
    //指定位置插入元素
    void insert(int pos,int val)
    {
        if(pos < 0 || pos > mCur)
        {
            return;
        }
        if(mCur == mCap)
        {
            explend(2*mCap);
        }
        for(int i = mCur-1;i>=pos;i--)
        {
            mpArr[i+1] = mpArr[i]; //在数组里面对下标进行增加减小操作时不能使用自增自减 
        }
        mpArr[pos] = val;
        mCur ++;
    }
    //指定元素删除
    void erase(int val)
    {
        int pos = find(val);
        if(pos != -1)
        {
            for(;pos<mCur;pos++)
            {
                mpArr[pos] = mpArr[pos+1];
            }
        }
        mCur--;
    }
    //查找指定元素
    int find(int val)
    {
        int pos;
        for(pos=0;pos<mCur;pos++)
        {
            if(mpArr[pos] == val)
            {
                return pos;
            }
        }
        return -1;
    }
    //显示数组元素
    void show()
    {
        for(int i = 0;i<mCur;i++)
        {
            cout << mpArr[i] << " ";
        }
        cout << endl;
    }
    //获取有效元素个数
    int getmCur()
    {
        return mCur;
    }
    //获取数组容量
    int getmCap()
    {
        return mCap;
    }

    private:
    int *mpArr;  //指向创建的那块堆上的数组空间
    int mCap;    //数组空间大小
    int mCur;    //数组有效元素个数

    //数组内部扩展空间
    void explend(int size)
    {
        int* p = new int[size];
        memcpy(p,mpArr,sizeof(int)*mCur);
        delete[]mpArr; //注意扩容后该指针要指向新开辟的内存所以原来的内存空间要释放
        mCap = size;
        mpArr = p;
    }
};

在编写该类中的一些注意事项：1.当在进行构造函数编写时，我们肯定是要将数组的有效元素个数成员变量置为0的，但是若不小心将其写成了数组容量为0，在我们使用该类时是注意不到的。而且在对该类进行添加成员数组扩容时，数组也是会正常输出，但是这里的数组时进行了越界访问的，因为当数组的容量不小心被设置成0时，并不满足我们所设置的扩容条件，所以需要注意不要写错了。2.在数组进行下标访问来获取数组的前后元素时，下标注意不要写成自增和自减，只能进行加减操作，只能改变访问的位置不要改变了i的大小。3.在扩容函数中我们要注意在指向新扩容的数组空间之前我们要先将原来指向的那块数组空间进行一个释放。

(2)相关知识

        数组的特点：内存是连续的。

        数组的优点：1.下标访问（随机访问）的时间复杂度是O(1)

                              2.末尾位置增加和删除元素时间复杂度是O(1)

                              3.访问元素的前后元素非常方便

        数组的缺点：1.非末尾位置增加和删除元素要进行大量的数组移动时间复杂度是O(n)

                              2.搜索的时间复杂度，无序数组是O(n)，有序数组用二分查找是O(logn)

                              3.数组扩容消耗较大

下面来看一下与数组相关的一些其他知识：

数组逆序的实现：

void MyReverse(char arr[],int size)
{
    char* p = arr;
    char* q = arr+size-1;
    while(p<q) //指针可以直接进行大小比较
    {
        char ch = *p;
        *p = *q;
        *q = ch;
        p++;
        q--;
    }
}

注意的是指针是可以进行大小比较的，相当于地址值之间大小的比较，指针之间的加减特别是指向同类型存储数据的加减得到的是两指针之间元素的个数。

数组内的分类(奇偶分类)：

void AdjustArray(int arr[],int size)
{
    int *p = arr;
    int *q = arr+size-1;
    while(p<q)
    {
        while(p<q)
        {
            if((*p & 0x1) == 1) //位运算符的优先级低于该判断逻辑运算符，要加上小括号
            {
                break;
            }
            p++;
        }
        while(p<q)
        {
            if((*q & 0x1 )== 0)
            {
                break;
            }
            q--;
        }
        if(p<q)
        {
            int tmp = *p;
            *p = *q;
            *q = tmp;
            p++;
            q--;
        }
    }
}

数组除去指定值：

int Test(int arr[],int size,int val)
{
    int *p = arr;
    int *q = arr+size-1;
    while(p<=q)
    {
        while(p<=q)
        {
            if(*p == val)
            {
                break;
            }
            p++;
        }
        while(p<=q)
        {
            if(*q != val)
            {
                break;
            }
            q--;
        }
        if(p<=q)
        {
            *p = *q;
            p++;
            q--;
        }
    }
    return p-arr;
}

2.单链表的C++实现及相关知识

(1)C++实现

        同样我们将关于单链表的成员方法和成员变量都放在一个类中，程序如下：

// 节点类
struct Node
{
    Node(int data = 0) : _data(data), _next(nullptr) {}
    int _data;
    Node *_next;
};

// 链表类
class List
{
public:
    List()
    {
        _head = new Node();
    }
    ~List()//注意链表的析构要将链表在堆中new出的所有节点都要释放
    {
        Node *p = _head;
        while(p != nullptr)
        {
            _head = _head->_next;
            delete p;
            p = _head;
        }
    }                   
    // 尾插法
    void InsertTail(int val)
    {
        Node *p = _head;
        while (p->_next != nullptr)
        {
            p = p->_next;
        }
        p->_next = new Node(val);
    }
    // 头插法
    void InsertHead(int val)
    {
        Node *p = new Node(val);
        p->_next = _head->_next;
        _head->_next = p;
    }
    // 删除链表中指定元素的第一个元素
    void Remove(int val)
    {
        Node *q = _head;
        Node *p = _head->_next;
        while (p != nullptr)
        {
            if (p->_data == val)
            {
                q->_next = p->_next;
                delete p;
                return; // 找到并删除该节点后要return退出
            }
            else
            {
                q = p;
                p = p->_next;
            }
        }
    }
    // 删除链表中指定元素的所有元素
    void RemoveAll(int val)
    {
        Node *q = _head;
        Node *p = _head->_next;
        while (p != nullptr)
        {
            if (p->_data == val)
            {
                q->_next = p->_next;
                delete p;
                p = q->_next;
            }
            else
            {
                q = p;
                p = p->_next;
            }
        }
    }
    // 显示
    void show(void)
    {
        Node *p = _head->_next;
        while (p != nullptr)
        {
            cout << p->_data << " ";
            p = p->_next;
        }
        cout << endl;
    }

private:
    Node *_head;
};

注意点：1.对于链表来说每一个节点都是在堆上new出来的，在实现其析构函数时我们也要将其所有的节点进行释放。2.在实现删除对应元素值的第一个元素方法时，在删除完成后我们就要进行return返回了。

(2)相关知识

        单链表的特点：每一个节点都是在堆上new出来的，节点内存不连续

        单链表的优点：1.内存利用率高不需要大块连续内存

                                  2.插入和删除节点不需要移动其他节点，时间复杂度为O(1)

                                  3.不需要专门进行扩容

        单链表的缺点：1.内存占用量大，每一个节点都要多出内存来存放地址

                                  2.内存不连续无法进行内存的随机访问

                                  3.链表搜索效率不高，只能从头节点开始往后搜索，时间复杂度为O(n)

单链表的相关知识点：

单链表的逆序：

void ReserveList(List &list) // 单链表逆序可以采用头插法
{
    Node *p = list.head_->next_;
    list.head_->next_ = nullptr;
    while (p != nullptr)
    {
        Node *q = p->next_;
        p->next_ = list.head_->next_;
        list.head_->next_ = p;
        p = q;
    }
}

单链表的逆序可以采用头插法的思想实现。

在单链表中找到其倒数第k个节点：

bool GetNode(List &list,int k)
{
    if(k<=0) //参数有效性判断
    {
        return false;
    }
    Node *p = list.head_;
    Node *q = list.head_;
    for(int i = 0;i<k;i++)
    {
        p = p->next_;
        if(p == nullptr)
            return false;
    }
    while(p != nullptr)
    {
        p = p->next_;
        q = q->next_;
    }
        cout << q->data_ << endl;
    return true;
}

一般在有参数传递的函数中可以先进行参数的有效性判断。

合并两个有序的链表：

//合并两个有序链表
void MergeList(List &list1 ,List &list2)
{
    Node *p = list1.head_->next_;
    Node *q = list2.head_->next_;
    Node *last = list1.head_;
    while(p != nullptr && q != nullptr)
    {
        if(p->data_ < q->data_)
        {
            last->next_ = p;
            p = p->next_;
            last = last->next_;
        }
        else
        {
            last->next_ = q;
            q = q->next_;
            last = last->next_;
        }
    }
    if(p != nullptr)
    {
        last->next_ = p;
    }
    else if(q != nullptr)
    {
        last->next_ = q;        
    }
    list2.head_->next_ = nullptr;
}