【奇妙的数据结构世界】 用经典例题对数组进行全面分析 | C++

简介: 简单来说,数据结构是一种辅助程序设计并且进行优化的方法论,它不仅讨论数据的存储与处理的方法,同时也考虑到了数据彼此之间的关系与运算,从而极大程度的提高程序执行的效率,减少对内存空间的占用等。不同种类的数据结构适用于不同的程序应用,选择合适正确的数据结构,可以让算法发挥出更大的性能,给设计的程序带来更高效率的算法。

前言

       简单来说,数据结构是一种辅助程序设计并且进行优化的方法论,它不仅讨论数据的存储与处理的方法,同时也考虑到了数据彼此之间的关系与运算,从而极大程度的提高程序执行的效率,减少对内存空间的占用等。不同种类的数据结构适用于不同的程序应用,选择合适正确的数据结构,可以让算法发挥出更大的性能,给设计的程序带来更高效率的算法。

一、数组是什么?

1.简要介绍

  数组类型是一种典型的静态数据结构,它使用了连续分配的内存空间去存储数据内容。静态数据结构是在编译时就给其变量分配好一定大小的内存空间。在建立静态数据结构的初期,必须事先去声明可能要占用多大的固定内存空间,因此这样可能造成一定的内存浪费或是经过后续操作出现数据溢出的现象。当对于简单的程序设计问题时,我们可以利用其下标,充分的对每一个位置上的数据进行修改、读取和使用,但是如果进行删除或插入数据的操作时将会移动大量的数据元素。

2.具体情况

   数组是具有相同和数据类型的变量的集合,它们在内存中占有一块连续的内存空间。数组可以分为一维数组、二维数组和多维数组,平时的学习中一维和二维是常用的,多维数组的话一般就会涉及到一些复杂的空间问题。在如下的图一中,是一个一维数组array_1[7],它是拥有6个相同数据类型的数组。

二维数组可以视为一维数组的扩展,它与一维数组差别只在于维数的声明。在如下的图二中,是一个二维数组array_2[4][5]在直观平面上的具体排列方式。

  三维数组的表示法和二维数组一样,都可以视作一维数组的扩展。在如下的图三中,是一个三维数组array_3[2][3][4]将它想象成空间上的立方体的情况。

二、数组典型例题——一维&二维&三维

1.一维数组(校门外的树

①例题:


       某校大门外长度为 l 的马路上有一排树,每两棵相邻的树之间的间隔都是 1 米。我们可以把马路看成一个数轴,马路的一端在数轴 0 的位置,另一端在 l 的位置;数轴上的每个整数点,即 0、1、2、...、l,都种有一棵树。

       由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数,区域之间可能有重合的部分。现在要把这些区域中的树(包括区域端点处的两棵树)移走。你的任务是计算将这些树都移走后,马路上还有多少棵树。


       输入要求:分析后可知需要输入马路的长度l,区域的数目m。m行的两个整数u和v,分别来表示一个区域的起点和终点坐标;


       输出要求:输出一个整数,表示移走每个区域上的树后剩余的树的数目;

   数据要求:1≤l≤10000、1≤m≤100、0≤u≤v≤l;

②代码展示:

#include<iostream>
using namespace std;
int tree_num[10001];
class tree {
public:
  int l,m;
  int u[101], v[101];
  void calculator()
  {
  for (int i = 0; i < m; i++)
  {
    for (int j = u[i]; j <= v[i]; j++)
    {
    tree_num[j] = 1;
    }
  }
  int count = 0;
  for (int k = 0; k <= l; k++)
  {
    if (tree_num[k] == 0)
    count++;
  }
  cout << "剩余" << count << "棵树" << endl;
  }
};
void text()
{
  tree t;
  cout << "请输入马路的长度:";
  cin >> t.l; 
  cout << "请输入区域的个数:";
  cin >> t.m;
  cout << "请开始分别输入" << t.m << "个区域的始点和终点坐标" << endl;
  for (int i = 0; i < t.m; i++)
  {
  cin >> t.u[i] >> t.v[i];
  }
  t.calculator();
}
int main()
{
  text();
}

③代码结果展示:

2.二维数组(彩票摇奖)

①例题:


       为了丰富人民群众的生活、支持某些社会公益事业,北塔市设置了一项彩票。该彩票的规则是:


1. 每张彩票上印有 7 个各不相同的号码,且这些号码的取值范围为 1~33。

2. 每次在兑奖前都会公布一个由七个各不相同的号码构成的中奖号码。

3. 共设置 7 个奖项,特等奖和一等奖至六等奖。


兑奖规则如下:

       - 特等奖:要求彩票上 7 个号码都出现在中奖号码中。

       - 一等奖:要求彩票上有 6 个号码出现在中奖号码中。

       - 二等奖:要求彩票上有 5 个号码出现在中奖号码中。

       - 三等奖:要求彩票上有 4 个号码出现在中奖号码中。

       - 四等奖:要求彩票上有 3 个号码出现在中奖号码中。

       - 五等奖:要求彩票上有 2 个号码出现在中奖号码中。

       - 六等奖:要求彩票上有 1 个号码出现在中奖号码中。


注:兑奖时并不考虑彩票上的号码和中奖号码中的各个号码出现的位置。例如,中奖号码为 23、31、1、14、19、17、18,则彩票 12、8、9、23、1、16、7由于其中有两个号码(23和1)出现在中奖号码中,所以该彩票中了五等奖。现已知中奖号码和小明买的若干张彩票的号码,请你写一个程序帮助小明判断他买的彩票的中奖情况。


       输入要求:输入的第一行只有一个自然数 n,表示小明买的彩票张数;第二行存放了 7 个介于 1 和 33 之间的自然数,表示中奖号码;在随后的 n 行中每行都有 7 个介于 1 和 33 之间的自然数,分别表示小明所买的 n 张彩票;


       输出要求:依次输出小明所买的彩票的中奖情况(中奖的张数),首先输出特等奖的中奖张数,然后依次输出一等奖至六等奖的中奖张数。

数据要求:1≤n<1000

②代码展示:

#include<iostream>
using namespace std;
int number[1001];
class lottery {
public:
  int n;
  int arr_1[7];
  int arr_2[1001][7];
  void calculator_1()
  {
  for (int i = 0; i < n; i++)
  {
    int count = 0;
    int ans = 0;
    while (ans < 7)
    {
    for (int j = 0; j < 7; j++)
    {
      if (arr_2[i][j] == arr_1[ans])
      count++;
    }
    ans++;
    }
    number[i] = count;
  }
  }
  void calculator_2()
  {
  int a = 0, b = 0, c = 0, d = 0, e = 0, f = 0, g = 0;
  for (int i = 0; i < n; i++)
  {
    switch (number[i])
    {
    case 1:
    g++;
    break;
    case 2:
    f++;
    break;
    case 3:
    e++;
    break;
    case 4:
    d++;
    break;
    case 5:
    c++;
    break;
    case 6:
    b++;
    break;
    case 7:
    a++;
    break;
    }
  }
  cout << "分别对应中奖情况如下:(特等-一等-二等-三等-四等-五等-六等)" << endl;
  cout << a << " " << b << " " << c << " " << d << " " << e << " " << f << " " << g << endl;
  }
};
void text()
{
  lottery l;
  cout << "请输入购买彩票的张数:";
  cin >> l.n;
  cout << "请输入彩票的7位中奖号码:";
  for (int i = 0; i < 7; i++)
  {
  cin >> l.arr_1[i];
  }
  cout << "请输入购买彩票的号码:" << endl;
  for (int i = 0; i < l.n; i++)
  {
  for (int j = 0; j < 7; j++)
  {
    cin >> l.arr_2[i][j];
  }
  }
  l.calculator_1();
  l.calculator_2();
}
int main()
{
  text();
}

③代码结果展示:

3.三维数组(工艺品制作)

①例题:


       现有一个长宽高分别为 w,x,h 组成的实心玻璃立方体,可以认为是由 1✖1✖1 的数个小方块组成的,每个小方块都有一个坐标( i,j,k )。现在需要进行q次切割。每次切割给出 (x1,y1,z1),(x2,y2,z2)这6个参数,保证 x1<=x2,y1<=y2,z1<=z2;每次切割时,使用激光工具切出一个立方体空洞,空洞的壁平行于立方体的面,空洞的对角点就是给出的切割参数的两个点。


       换句话说,所有满足 x1<=i<=x2 , y1<=j<=y2 , z1<=k<=z2 的小方块(i,j,k)的点都会被激光蒸发。例如有一个 4✖4✖4 的大方块,其体积为64;给出参数(1,1,1),(2,2,2)时,中间的8块小方块就会被蒸发,剩下56个小方块。现在想知道经过所有切割操作后,剩下的工艺品还剩下多少格小方块的体积。


       输入要求:分别输入长宽高三个正整数w、x、h。一个整数q,然后在接下来的q行,每行6个整数(x1,y1,z1),(x2,y2,z2)分别表示对角的两个顶点坐标;


       输出要求:输出一个整数表示切割后还剩余多少个小立方体;

  数据要求:1≤w,x,h≤20、1≤q≤100、1≤x1≤x2≤w、1≤y1≤y2≤x、1≤z1≤z2≤h;

②代码展示:

#include<iostream>
using namespace std;
#define max 21
int sq[max][max][max] = {0};
class art {
public:
  int w, x, h;
  int x1, y1, z1;
  int x2, y2, z2;
  void calculator_1()
  {
  for (int i = x1; i <= x2; i++)
    for (int j = y1; j <= y2; j++)
    for (int k = z1; k <= z2; k++)
      sq[i][j][k] = 1;
  }
  void calculator_2()
  {
  int count=0;
  for (int i = 1; i <= w; i++)
    for (int j = 1; j <= x; j++)
    for (int k = 1; k <= h; k++)
      if (sq[i][j][k] == 0)
      count++;
  cout << "剩余" << count << "个小方块" << endl;
  }
};
void text()
{
  art a;
  cout << "请输入长宽高:";
  cin >> a.w >> a.x >> a.h;
  cout << "请输入q的值:";
  int q; cin >> q;
  cout << "请分别输入两组对角点的坐标值" << endl;
  for (int num = 1; num <= q; num++)
  {
   cin >> a.x1 >>a.y1 >> a.z1;
   cin >> a.x2 >>a.y2>> a.z2;
   a.calculator_1();
  }
  a.calculator_2();
}
int main()
{
  text();
}

③代码结果展示:

总结

  以上就是我们第八章的全部讲解与典型例题,因为上面这三个例题更大程度上是数组和算法的结合应用,所以对于C++的一些初学者来说,上面的三个例题是有一定难度和挑战性的。但是如果可以独立且正确的去完成,那么你在数据结构数组这一块就可以打个对勾了。

目录
相关文章
|
16天前
|
存储 人工智能 算法
C 408—《数据结构》算法题基础篇—数组(通俗易懂)
408考研——《数据结构》算法题基础篇之数组。(408算法题的入门)
58 23
|
1月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
142 77
|
1月前
|
存储 人工智能 算法
【C++数据结构——图】最短路径(头歌教学实验平台习题) 【合集】
任务描述 本关任务:编写一个程序,利用Dijkstra算法,实现带权有向图的最短路径。 相关知识 为了完成本关任务,你需要掌握:Dijkst本关任务:编写一个程序,利用Dijkstra算法,实现带权有向图的最短路径。为了完成本关任务,你需要掌握:Dijkstra算法。带权有向图:该图对应的二维数组如下所示:Dijkstra算法:Dijkstra算法是指给定一个带权有向图G与源点v,求从v到G中其他顶点的最短路径。Dijkstra算法的具体步骤如下:(1)初始时,S只包含源点,即S={v},v的距离为0。
61 15
|
1月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
46 10
|
1月前
|
存储 C++
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
【数据结构——树】哈夫曼树(头歌实践教学平台习题)【合集】目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:任务描述 本关任务:编写一个程序构建哈夫曼树和生成哈夫曼编码。 相关知识 为了完成本关任务,你需要掌握: 1.如何构建哈夫曼树, 2.如何生成哈夫曼编码。 测试说明 平台会对你编写的代码进行测试: 测试输入: 1192677541518462450242195190181174157138124123 (用户分别输入所列单词的频度) 预
61 14
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
|
1月前
|
Java C++
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
48 12
|
1月前
|
算法 C++
【C++数据结构——图】最小生成树(头歌实践教学平台习题) 【合集】
【数据结构——图】最小生成树(头歌实践教学平台习题)目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:【合集】任务描述 本关任务:编写一个程序求图的最小生成树。相关知识 为了完成本关任务,你需要掌握:1.建立邻接矩阵,2.Prim算法。建立邻接矩阵 上述带权无向图对应的二维数组,根据它建立邻接矩阵,如图1建立下列邻接矩阵。注意:INF表示无穷大,表示整数:32767 intA[MAXV][MAXV];Prim算法 普里姆(Prim)算法是一种构造性算法,从候选边中挑
44 10
|
1月前
|
存储 算法 C++
【C++数据结构——图】图的邻接矩阵和邻接表的存储(头歌实践教学平台习题)【合集】
本任务要求编写程序实现图的邻接矩阵和邻接表的存储。需掌握带权有向图、图的邻接矩阵及邻接表的概念。邻接矩阵用于表示顶点间的连接关系,邻接表则通过链表结构存储图信息。测试输入为图的顶点数、边数及邻接矩阵,预期输出为Prim算法求解结果。通关代码提供了完整的C++实现,包括输入、构建和打印邻接矩阵与邻接表的功能。
49 10
|
1月前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
38 7
|
1月前
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
44 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】