admin管理员组文章数量:1611960
一、动态数组类
成员变量，包括数组的容量（引入容量的完全是为了避免频繁的new申请内存，造成的内存浪费）、数组元素个数和数组变量；
成员函数，包括默认、有参构造函数、析构函数以及重载[]运算符、重载=运算符；获取容量、大小以及判断数组是否为空；添加元素（尾插、任意位置插入）、删除指定位置的元素；最后就是私有的resize()函数，用来根据m_size与m_capacity，通过申请新的内存空间来调整容量；
主函数：测试动态数组类的各种接口函数；
1、MyArray.h
#pragma once
#include <iostream>
using namespace std;
#ifndef MYARRAY
#define MYARRAY
class MyArray
{
public:
MyArray(); // 默认构函数
MyArray(int capacity); // 有参构函数
MyArray(const MyArray &arr); // 拷贝构造函数
int operator[](int i) const;
int& operator[](int i);
MyArray& operator=(const MyArray &arr); // 重载赋值运算符
MyArray& operator+(const MyArray &temp);
virtual ~MyArray(); // 虚析构函数
bool empty();
int len() const;
int capacity() const;
void push_back(int val);
void insert(int pos, int val);//在pos索引位置添加元素
int Delete(int pos);//删除pos位置元素,返回该位置被删的值
private:
int *arr;
int m_size; // 数组当前元素个数
int m_capacity; // 数组容量
void resize(const int &newCapacity); // 实现动态变长数组，当size超过容量的时候不报错，而是调用该函数，改变容量
};
#endif
2、MyArray.cpp
#include "MyArray.h"
// size为数组当前元素个数，capacity为数组最大容量：
// 当size == capacity时，将capacity扩大两倍
// 当size == capacity / 4时，将capacity缩小两倍
MyArray::MyArray()
{
// 默认构造函数
}
MyArray::MyArray(int capacity) : m_capacity(capacity), m_size(0)
{
// 用一维指针数组定义的data
arr = new int[capacity];
}
MyArray::MyArray(const MyArray &temp)
{
// 判断是否是将自己拷贝给自己
if (this != &temp)
{
this->m_capacity = temp.m_capacity;
this->m_size = temp.m_size;
arr = new int[this->m_capacity];
for (int i = 0; i < this->m_size; i++)
{
this->arr[i] = temp.arr[i];
}
}
}
int MyArray::operator[](int i) const // 获取元素（读取）
{
return arr[i];
}
// 必须引用的返回形式int &，因为等号左边必须是左值
int& MyArray::operator[](int i) // 获取元素（写入；修改元素）
{
if (i == m_size) // 给数组尾部写入一个元素
{
m_size++;
}
return arr[i];
}
// Array &：不但能够避免在返回数据时调用拷贝构造函数，还能够达到连续赋值的目的
// 赋值运算符重载函数，除了能有对象引用这样的参数之外，也能有其它参数；但是其它参数必须给出默认值
MyArray& MyArray::operator=(const MyArray &temp) // 重载赋值运算符
{
// 判断是否是给自己赋值
if (this != &temp)
{
this->m_size = temp.m_size;
this->m_capacity = temp.m_capacity;
arr = new int[this->m_capacity];
for (int i = 0; i < m_size; i++)
{
this->arr[i] = temp.arr[i];
}
}
return *this;
}
MyArray& MyArray::operator+(const MyArray &temp)
{
for (int i = 0; i < temp.size(); i++)
{
this->push_back(temp[i]);
}
return *this;
}
MyArray::~MyArray()
{
delete[] arr;
arr = nullptr;
// nullptr和任何指针类型以及类成员指针类型的空值之间可以发生隐式类型转换
// 不存在到布尔型/整型的隐式类型转换(bool a = NULL，此时的a是false;bool b = nullptr不成立)(int a = NULL，此时的a为0；int a = nullptr不成立)
}
bool MyArray::empty()
{
return m_size == 0;
}
int MyArray::len() const
{
return m_size;
}
int MyArray::capacity() const
{
return m_capacity;
}
void MyArray::resize(const int &newCapacity) // 实现动态变长数组，当size超过容量的时候不报错，而是调用该函数，改变容量
{
// 按照新的容量申请新的内存空间，并将原内存空间中的元素拷贝到新的内存空间
m_capacity = newCapacity;
int *newArr = new int[m_capacity];
for (int i = 0; i < m_size; ++i)
{
newArr[i] = arr[i];
}
// 先释放掉原内存空间，然后让arr指向新的内存空间的首地址
delete[] arr;
arr = newArr;
}
void MyArray::push_back(int val) //在末尾添加元素
{
if (m_size == m_capacity)
{
resize(m_capacity * 2);
}
arr[m_size++] = val; // 先对m_size的位置进行赋值，再改变m_size的大小
}
void MyArray::insert(int pos, int val) // 在pos索引位置添加元素
{
if (m_size == m_capacity)
{
resize(m_capacity *= 2);
}
if (pos >= 0 && pos <= m_size)
{
// 将pos位置之后的元素，向后移动一个位置
for (int i = m_size; i > pos; i--)
{
arr[i] = arr[i - 1];
}
arr[pos] = val;
m_size++; // 调整size的大小
}
else
{
cout << "pos is out of the range" << endl;
}
}
int MyArray::Delete(int pos) // 删除pos位置元素
{
if (m_size == m_capacity / 4) // 当删除元素，使得size == 1/4 * capacity时，改变容量capacity *= 1/2
{
resize(m_capacity = m_capacity / 2);
}
if (pos >= 0 && pos < m_size)
{
// 将pos位置之后的元素，向前移动一个位置
int ret = arr[pos];
for (int i = pos + 1; i < m_size; i++)
{
arr[i - 1] = arr[i];
}
m_size--; // 更新size的大小
return ret;
}
else
{
cout << "pos is out of the range" << endl;
}
}3、main.cpp
#include "MyArray.h"
void PrintData(const MyArray &arr) // 打印数组
{
const int size = arr.len();
for (int i = 0; i < size; i++)
{
cout << arr[i] << " "; // 调用了重载[]运算符int operator[](int i) const，从而实现对数组元素的访问
}
cout << endl;
}
int main()
{
MyArray arr1(10);
for (int i = 0; i < 5; i++)
{
arr1[i] = i; // 调用了重载[]运算符int& operator[](int i)，从而实现对数组添加元素
}
MyArray arr2(arr1); // 调用了拷贝构造函数，实现了数组对象之间的深拷贝
if (!arr2.empty())
{
cout << "arr2 = ";
PrintData(arr2);
}
MyArray arr3;
arr3 = arr1; // 调用了重载赋值运算符MyArray &operator=(const MyArray &arr)，实现了数组对象之间的深拷贝
if (!arr3.empty())
{
cout << "arr3 = ";
PrintData(arr3);
}
arr1[1] = 2; // 调用了重载[]运算符int& operator[](int i)，从而实现对数组已有元素的修改
arr1.push_back(1); // 用push_back()成员函数，实现尾插
arr1.push_back(1);
arr1.push_back(1);
arr1.push_back(1);
arr1.push_back(1);
arr1.push_back(1); // 当arr1数组的m_size==m_capacity时，将容量m_capacity扩大为原来的2
arr1.insert(1, -1);
arr1.insert(arr1.len(), -1); // 用insert()成员函数，实现尾插
if (!arr1.empty())
{
cout << "arr1 = ";
PrintData(arr1);
}
arr2.Delete(0);
arr2.Delete(3);
arr2.Delete(4); // 越界处理，报错
arr2.Delete(0);
arr2.Delete(0); // 当删除元素，使得size == 1/4 * capacity时，改变容量capacity *= 1/2
if (!arr2.empty())
{
cout << "arr2 = ";
PrintData(arr2);
}
MyArray arr4 = arr1 + arr3; // 调用了MyArray& operator+(const MyArray &temp)重载的+号运算符、拷贝构造函数
if (!arr4.empty())
{
cout << "arr4 = ";
PrintData(arr4);
}
return 0;
}二、动态内存分配数组
1、一维数组的动态分配和使用
#include<iostream>
using namespace std;
int main()
{
int *arr = new int[10];
for (int i = 0; i < 10; i++)
{
arr[i] = i; // 相当于*(arr + i) = i;
}
for (int i = 0; i < 10; i++)
{
cout << arr[i] << " ";
}
cout << endl;
delete[] arr;
arr = nullptr;
return 0;
}2、二维数组的动态分配和使用
1） 法一：开辟一大块空间存放二维数组当成一维数组，且数组元素的存储在内存中是连续的；
#include<iostream>
using namespace std;
#define ROW 3
#define COL 3
int size = ROW * COL
int main()
{
int *arr = new int[size];
// 创建全是1的二位数组，且在内存中是连续存储的，行优先
for (int i = 0; i < ROW; i++)
{
for (int j = 0; j < COL; j++)
{
arr[i * COL + j] = 1;
}
}
for (int i = 0; i < size; i++)
{
cout << arr[i] << " ";
if ((i + 1) % COL == 0)
{
cout << endl;
}
}
delete[] arr;
arr = nullptr;
return 0;
}
2）法二：开辟一个指针数组，每个元素存放的是一个指针，每个指针都指向一个一维数组，再分别对每个一维数组分配空间
#include<iostream>
using namespace std;
#define ROW 3
#define COL 3
int main()
{
int **arr = new int*[ROW];
for (int i = 0; i < ROW; i++)
{
arr[i] = new int[COL];
}
for (int i = 0; i < ROW; i++)
{
for (int j = 0; j < COL; j++)
{
arr[i][j] = 1;
}
}
for (int i = 0; i < ROW; i++)
{
for (int j = 0; j < COL; j++)
{
cout << arr[i][j] << " ";
}
cout << endl;
}
delete[] arr;
arr = nullptr;
return 0;
}3）法三：借用数组指针，通过对数组指针访问到数组元素与第一种方法类似，也是连续存储的；
#include<iostream>
using namespace std;
int main()
{
// 用数组指针形式申请一个ROW行COL列的二维数组
int(*arr)[COL] = (int(*)[COL])malloc(sizeof(int) * ROW * COL);
for (int i = 0; i < ROW; i++)
{
for (int j = 0; j < COL; j++)
{
arr[i][j] = 1;
}
}
for (int i = 0; i < ROW; i++)
{
for (int j = 0; j < COL; j++)
{
cout << arr[i][j] << " ";
}
cout << endl;
}
free(arr);
arr = nullptr;
}
第二部分，借鉴(38条消息) 【C语言进阶篇】动态内存分配和数组的动态内存分配_LeePlace的博客-CSDN博客
版权声明：本文标题：数据结构与算法学习笔记（二）动态数组 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://m.elefans.com/dianzi/1728622474a1166529.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论