An array is a collection of data elements of the same data type. The data can be arranged in different number of dimensions depending on the problem being solved:
- For example, we can use a one-dimensional array to store and process a collection of integers.
- We can use a two-dimensional array to store the data that needs to be arranged as a matrix or table.
- We can have an array with a higher number of dimensions, too. For example, a three-dimensional array is used to store a colored image.
In this blog, we’ll focus on triangular arrays, which are a specialized implementation of two-dimensional arrays. Before moving to triangular arrays in C++, we’ll build a foundation by first exploring two-dimensional arrays.
Two-dimensional array#
Two-dimensional arrays are matrices of dimension , where is the number of rows and is the number of columns. In a two-dimensional array, the number of rows and columns is set at the time of creation of the array, defining the size of both dimensions. As a result, each row contains the same number of columns. For example, the following array represents a matrix of size 5 3:
Let’s see how you can create and use a triangular array in C++:
#include <iostream>using namespace std;int main() {int myData[5][3] = {{5, 2, 7}, {8, 8, 8}, {3, 2, 1}, {0, 9, 9}, {6, 4, 2}};for(int i=0;i<5;i++){for(int j=0;j<3;j++){cout<<" "<<myData[i][j];}cout<<"\n";}return 0;}
Let’s understand the implementation:
- We have created and initialized a two-dimensional array
myDataof size 5 3 in line 5. - In lines 7–14, we have used two nested
forloops to iterate over the rows and columns of the arraymyDataand display the data on the console.
Triangular array#
The triangular array is a two-dimensional array where the number of columns in each row is not fixed. One possible implementation could be that the first row has one column, the second row has two columns, and so on. One possibility could be to create a conventional two-dimensional array and use its cells on or below the diagonal, as shown below.
The shortcoming of this implementation would be the unused memory, which is almost half of the reserved memory. This implementation fixes the number of columns for each row. A good triangular array shouldn’t be using additional memory. Instead, it should create the required number of columns for each row. The following figure illustrates a triangular array:
Implementing a triangular array#
Let’s implement a triangular array in C++. In this two-dimensional array, we’ll keep the number of rows fixed, whereas the number of columns in each row will be dynamic. We’ll create a one-dimensional array of integer pointers to create a fixed number of rows. Each of these pointers can hold the address of an integer location. This individual integer location could be a stand-alone location or any (or starting) location of an array.
#include <iostream>using namespace std;int main() {int *myData[5];for(int i=0;i<5;i++){myData[i] = new int[i+1];}for(int i=0;i<5;i++){for(int j=0;j<=i;j++){myData[i][j] = i+1;}}for(int i=0;i<5;i++){for(int j=0;j<=i;j++){cout<<" "<<myData[i][j];}cout<<"\n";}return 0;}
Let’s understand the code:
- In line 5, we create an array
myDataof five pointers. - In lines 7–10, we run a loop and create an array of
i+1integers for eachiwhose address is held bymyData[i]. This results in the creation of our desired triangular array. - In lines 12–18, we initialize each element of the array with an example value.
- In lines 20–27, we display the array.
Example: A variation of Galton's board#
Galton’s board is a pyramid-like structure. A ball is dropped from the top of the pyramid. So, there is only one possible point in the pyramid where the ball can be dropped from as the first step. The ball is supposed to keep on rolling down stepwise. In the first step, it takes a random decision to either move to the left side or the right side. As a result of this random choice, it reaches the second row of the pyramid. The same process is repeated at each row. Finally, the ball hits one of the cells in the last row. This process can be repeated multiple times, and due to the random choice being made at each step, the path being followed by the ball may change. We maintain a counter against each cell of the last row to count how many times the ball hit the corresponding cell of the last row.
In our implementation, we initialize the triangular array with all zeros. As the ball hits a particular cell, it becomes . The following figure demonstrates the triangular array initialized with zeros depicting a variation of Galton’s board.
The following figure shows one possible path the ball will follow if we run the experiment once.
Let’s implement this variation of Galton’s board:
#include <iostream>using namespace std;int main() {int counter[5];srand(time(0));int direction, row, col;int *myData[5];for(int i=0;i<5;i++){myData[i] = new int[i+1];}for(int i=0;i<5;i++){counter[i] = 0;}//Let's run this experiment 10 timesfor(int w=1;w<=10;w++){//Re-initialise the array for each experimentfor(int i=0;i<5;i++){for(int j=0;j<=i;j++){myData[i][j] = 0;}}row = 0, col = 0;for(int x=1;x<=5;x++){myData[row][col] = 1;direction = random() % 2;if(direction == 1) //Go to right side of next row otherwise stay in the same column{col++;}row++;if(row == 4){counter[col]++;}}for(int i=0;i<5;i++){for(int k=5;k>=i;k--){cout<<" ";}for(int j=0;j<=i;j++){cout<<" "<<myData[i][j];}cout<<"\n";}cout<<" -----------------\n";cout<<" ";for(int i=0;i<5;i++){cout<<counter[i]<<" ";}cout<<"\n";cout<<" -----------------\n";}return 0;}
Let’s understand the code to simulate Galton’s board:
- In lines 8–12, we create the triangular array
myDatathat is being used as the primary data structure to simulate Galton’s board. - In lines 14–17, we initialize a one-dimensional array
counterto store the count of the number of hits against each column. - In line 19, we use the loop counter
wto count the number of experiments we run to drop the ball from the top of the triangular array. - In lines 22–28, we reset the triangular array each time the experiment runs.
- In line 30, we define the start point where the ball will be dropped from in each experiment.
- In line 32, we use the loop counter
xto repeat the process of moving the ball to the next row 5 times, as there are 5 rows in our array. - In line 34, we change the value of
myData[row][col]notating the hit of the ball at this particular cell. - In line 36,
0or1is generated as a random number and stored indirectionto take a random decision of dropping the ball to the left or right direction of the next row. - In lines 38-42, values
rowandcolare updated based on the value ofdirection. - In lines 44–47, the counter of the corresponding
colis updated when the ball reaches the lastrow. - In lines 50–69, we format the array contents and the counter and display them as a triangular array followed by the counter.
You may try using a specialized implementation of two-dimensional arrays to implement different strategy games like Ludo or Chess. Different mazes to solve a wide variety of puzzles can possibly be modeled as specialized implementations of two-dimensional arrays.
Arrays are one of the fundamental building blocks of computer programming. To dive deep into the programming journey, have a look at the following courses:
Learn C++: The Complete Course for Beginners
If you're a beginner and want to learn C++ to start your coding journey, you're in the right place. This comprehensive course starts from the absolute basics and gradually builds up to exciting real-life coding projects. The emphasis throughout is on practical lessons and analogies that you can relate to. As you learn, you'll work your way through dozens of coding exercises that you can run from right inside your browser. By the time you're done, you'll have a strong grasp of C++, one of the most in-demand programming languages in the world. You'll have gotten plenty of hands-on practice and will be able to confidently write your own applications.
Learn Object-Oriented Programming in C++
Object-oriented programming (OOP) has been around for decades. If you have a basic understanding of C++ and are interested in leveling up your skills, this class will help you do just that. Starting with an overview of the basics, you’ll dive into understanding the time-honored technique for implementing complex applications using user-defined classes. Followed up by discussing classes and objects, and then building up to the high-level topics including inheritance and polymorphism. Throughout the course, you’ll be fully immersed in OOP for C++, with illustrations, exercises, quizzes, and hands-on challenges every step of the way. You’ll walk away with an understanding of classes and objects behavior and be able to easily create simple, efficient, reusable and secure code.
C++ Programming for Experienced Engineers
If you’re looking to sharpen up your C++ programming skills, then you’re in the right place. You will start with learning about dynamic memory allocation, how to create classes, and constructors. In the latter half of the course, inheritance, functions, I/O, exception handling, and more. Throughout the course, you will study over 90 carefully designed examples aimed to enhance your understanding of the C++ language. By the time you finish this course, you will be able to use more advanced functionality in your C++ programs.
Free Resources
