C++实现线性表 - 01 数组

简介: 从今天开始,我将为大家用c++代码来实现常见数据结构与算法的代码,我们先从大家最熟悉的数组开始实现。

写在前面:
从今天开始,我将为大家用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();
}

image.png

如果大家有什么问题的话,欢迎在下方评论区进行讨论哦~

目录
相关文章
|
5月前
|
搜索推荐 编译器 C语言
【C++核心】特殊的元素集合-数组与字符串详解
这篇文章详细讲解了C++中数组和字符串的基本概念、操作和应用,包括一维数组、二维数组的定义和使用,以及C风格字符串和C++字符串类的对比。
116 4
|
1月前
|
存储 算法 测试技术
【C++数据结构——线性表】求集合的并、交和差运算(头歌实践教学平台习题)【合集】
本任务要求编写程序求两个集合的并集、交集和差集。主要内容包括: 1. **单链表表示集合**:使用单链表存储集合元素,确保元素唯一且无序。 2. **求并集**:遍历两个集合,将所有不同元素加入新链表。 3. **求交集**:遍历集合A,检查元素是否在集合B中存在,若存在则加入结果链表。 4. **求差集**:遍历集合A,检查元素是否不在集合B中,若满足条件则加入结果链表。 通过C++代码实现上述操作,并提供测试用例验证结果。测试输入为两个集合的元素,输出为有序集合A、B,以及它们的并集、交集和差集。 示例测试输入: ``` a c e f a b d e h i ``` 预期输出:
42 7
|
1月前
|
机器学习/深度学习 存储 C++
【C++数据结构——线性表】单链表的基本运算(头歌实践教学平台习题)【合集】
本内容介绍了单链表的基本运算任务,涵盖线性表的基本概念、初始化、销毁、判定是否为空表、求长度、输出、求元素值、按元素值查找、插入和删除数据元素等操作。通过C++代码示例详细解释了顺序表和链表的实现方法,并提供了测试说明、通 - **任务描述**:实现单链表的基本运算。 - **相关知识**:包括线性表的概念、初始化、销毁、判断空表、求长度、输出、求元素值、查找、插入和删除等操作。 - **测试说明**:平台会对你编写的代码进行测试,提供测试输入和预期输出。 - **通关代码**:给出了完整的C++代码实现。 - **测试结果**:展示了测试通过后的预期输出结果。 开始你的任务吧,祝你成功!
41 5
|
1月前
|
机器学习/深度学习 存储 C++
【C++数据结构——线性表】顺序表的基本运算(头歌实践教学平台习题)【合集】
本文档介绍了线性表的基本运算任务,涵盖顺序表和链表的初始化、销毁、判定是否为空、求长度、输出、查找元素、插入和删除元素等内容。通过C++代码示例详细展示了每一步骤的具体实现方法,并提供了测试说明和通关代码。 主要内容包括: - **任务描述**:实现顺序表的基本运算。 - **相关知识**:介绍线性表的基本概念及操作,如初始化、销毁、判定是否为空表等。 - **具体操作**:详述顺序表和链表的初始化、求长度、输出、查找、插入和删除元素的方法,并附有代码示例。 - **测试说明**:提供测试输入和预期输出,确保代码正确性。 - **通关代码**:给出完整的C++代码实现,帮助完成任务。 文档
41 5
|
1月前
|
存储 算法 搜索推荐
【C++面向对象——群体类和群体数据的组织】实现含排序功能的数组类(头歌实践教学平台习题)【合集】
1. **相关排序和查找算法的原理**:介绍直接插入排序、直接选择排序、冒泡排序和顺序查找的基本原理及其实现代码。 2. **C++ 类与成员函数的定义**:讲解如何定义`Array`类,包括类的声明和实现,以及成员函数的定义与调用。 3. **数组作为类的成员变量的处理**:探讨内存管理和正确访问数组元素的方法,确保在类中正确使用动态分配的数组。 4. **函数参数传递与返回值处理**:解释排序和查找函数的参数传递方式及返回值处理,确保函数功能正确实现。 通过掌握这些知识,可以顺利地将排序和查找算法封装到`Array`类中,并进行测试验证。编程要求是在右侧编辑器补充代码以实现三种排序算法
42 5
|
5月前
|
C++
C++(十一)对象数组
本文介绍了C++中对象数组的使用方法及其注意事项。通过示例展示了如何定义和初始化对象数组,并解释了栈对象数组与堆对象数组在初始化时的区别。重点强调了构造器设计时应考虑无参构造器的重要性,以及在需要进一步初始化的情况下采用二段式初始化策略的应用场景。
|
6月前
|
算法 C++
c++学习笔记04 数组
这篇文章是C++学习笔记4,主题是数组。
56 4
|
6月前
|
C++ 索引
C++数组、vector求最大值最小值及其下标
C++数组、vector求最大值最小值及其下标
223 0
|
7月前
|
C++ 索引 运维
开发与运维数组问题之在C++中数组名和指针是等价如何解决
开发与运维数组问题之在C++中数组名和指针是等价如何解决
47 6
|
7月前
|
存储 安全 C++
开发与运维数组问题之声明一个数组如何解决
开发与运维数组问题之声明一个数组如何解决
52 6