写在前面:
从今天开始,我将为大家用c++代码来实现常见数据结构与算法的代码,我们先从大家最熟悉的数组开始实现。
由于数组用的比较多,这里我会将 c++ 中 STL 里的 vector 一起介绍,因为使用起来 vector 会更加方便,大家可以尝试着去代替数组。当然之后的代码我仍然会用正常的数组来写,方便大家理解。
后续代码实现的大部分地方其实还是用 c 来实现,只不过我利用了 c++ 的一些特性,比如 cin 和 cout,又比如 c++ 中指针的运用,用这些都是为了方便而且也不难理解。
一维数组的创建
#include<bits/stdc++.h>
using namespace std;
//创建一维静态数组
void CreatArray01()
{
const int N = 100;
//int arr[]={1,2,3,4,5,6,7,8,9};//可以直接赋值
int Array01[N] = { 0 }; //可以将数组中所有元素赋值为0,其他值不可以这样操作
for (int i = 0; i < N; i++) cin >> Array01[i];
}
//用new创建一维动态数组
void CreatArray02()
{
int num; //表示数组元素的数量
cin >> num;
int* Array02 = new int[num];
for (int i = 0; i < num; i++) cin >> Array02[i];
}
//用vector创建一维数组
void CreatArray03()
{
vector<int> Array03;
int num;
cin >> num;
for (int i = 0; i < num; i++) cin >> Array03[i];
}
二维数组的创建
#include<bits/stdc++.h>
using namespace std;
//创建二维静态数组
void CreatArray01()
{
int Array01[3][4] = { 0,1,2,3,4,5,6,7,8,9,10,1 };
}
//用new创建二维动态数组
void CreatArray02()
{
int row, col; //设置行数和列数
cin >> row >> col;
int** Array02 = new int* [row];
for (int i = 0; i < row; i++) Array02[i] = new int[col];
for (int i = 0; i < row; i++)
for (int j = 0; j < col; j++)
cin >> Array02[i][j];
}
//用vector创建二维数组(方法一)
void CreatArray03()
{
int row, col;
cin >> row >> col;
vector<vector<int> > Array03(row); //注意内层的vector后面要有一个空格
for (int i = 0; i < row; i++) Array03[i].resize(col);
for (int i = 0; i < row; i++)
{
for (int j = 0; j < col; j++)
{
cin >> Array03[i][j];
}
}
}
//用vector创建二维数组(方法二)
void CreatArray04()
{
int row, col;
cin >> row >> col;
vector<vector<int> >Array04(row, vector<int>(col));
for (int i = 0; i < row; i++)
{
for (int j = 0; j < col; j++)
{
cin >> Array04[i][j];
}
}
}
二维数组作为函数的参数
#include<bits/stdc++.h>
using namespace std;
//方法一:指明参数
void print1(int a[3][4])
{
for (int i = 0; i < 3; i++)
for (int j = 0; j < 4; j++)
cout << a[i][j] << " ";
cout << endl;
}
//方法二:省略一个高维参数
void print2(int a[][4], int lines)
{
for (int i = 0; i < 3; i++)
for (int j = 0; j < 4; j++)
cout << a[i][j] << " ";
cout << endl;
}
int main()
{
int a[3][4] = { 0 };
for (int i = 0; i < 3; i++)
for (int j = 0; j < 4; j++)
a[i][j] = 4 * i + j;
print1(a);
print2(a, 3);
return 0;
}
数组的插入
接下来我们来讲讲数组常规的一些操作,为了方便理解,我们就用最原始的方法来做,不涉及STL的内容。数组的插入分为直接插入与指定位置插入,后者操作起来比前者步骤多一点点。
//插入元素
void push_key(int key)
{
if (cnt == N)
{
cout << "容器已满!" << endl;
return;
}
res[++cnt] = key;
}
//在指定位置前插入元素
void insert_key(int idx, int key)
{
if (cnt == N)
{
cout << "容器已满!" << endl;
return;
}
//判断指定的位置下标是否超出范围或数组越界
if (idx<1 || idx>N)
{
cout << "下标不满足要求!" << endl;
return;
}
for (int i = cnt; i >= idx; i--)
res[i + 1] = res[i]; //将插入位置的后面所有元素都后移一位
res[idx] = key;
cnt++;
}
数组的删除
删除操作相对于插入操作,会多一个查找操作。
//找到指定元素
int find(int key)
{
for (int i = 1; i <= cnt; i++)
if (res[i] == key)
return i;
return -1;
}
//删除指定元素
void delete_key(int key)
{
if (cnt == 0)
{
cout << "容器为空!" << endl;
return;
}
int idx = find(key); //找到该元素的位置
if (idx == -1)
{
cout << "不存在该元素!" << endl;
return;
}
for (int i = idx; i <= cnt; i++)
res[i] = res[i + 1]; //让删除元素后面的所有元素向前移一位就可以覆盖掉删除元素
cnt--;
}
全部代码
#include<bits/stdc++.h>
using namespace std;
const int N = 10; //最大容量为10
int res[N + 1]; //存储元素,下标从1开始
int cnt = 0; //数组指针,也表示当前元素数量
//插入元素
void push_key(int key)
{
if (cnt == N)
{
cout << "容器已满!" << endl;
return;
}
res[++cnt] = key;
}
//在指定位置前插入元素
void insert_key(int idx, int key)
{
if (cnt == N)
{
cout << "容器已满!" << endl;
return;
}
//判断指定的位置下标是否超出范围或数组越界
if (idx<1 || idx>N)
{
cout << "下标不满足要求!" << endl;
return;
}
for (int i = cnt; i >= idx; i--)
res[i + 1] = res[i]; //将插入位置的后面所有元素都后移一位
res[idx] = key;
cnt++;
}
//找到指定元素
int find(int key)
{
for (int i = 1; i <= cnt; i++)
if (res[i] == key)
return i;
return -1;
}
//删除指定元素
void delete_key(int key)
{
if (cnt == 0)
{
cout << "容器为空!" << endl;
return;
}
int idx = find(key); //找到该元素的位置
if (idx == -1)
{
cout << "不存在该元素!" << endl;
return;
}
for (int i = idx; i <= cnt; i++)
res[i] = res[i + 1]; //让删除元素后面的所有元素向前移一位就可以覆盖掉删除元素
cnt--;
}
//展示容器中元素
void show()
{
if (cnt == 0)
{
cout << "容器为空!" << endl;
return;
}
for (int i = 1; i <= cnt; i++)
cout << res[i] << " ";
cout << endl;
}
int main()
{
//初始化数组
for (int i = 1; i <= 5; i++)
push_key(i);
show();
insert_key(3, 9);
insert_key(5, 7);
show();
delete_key(3);
delete_key(10);
show();
}
如果大家有什么问题的话,欢迎在下方评论区进行讨论哦~