Data Structures Part 1 Arrays

Data Structures Part 1 Arrays

Arrays
Arrays are very important in C.

Subscripts begin with 0
Character strings are implemented using arrays
There can be multiple dimensions
Initialization can be done with the declaration
Automatically pass addresses when passed as function arguments

/ double dTemperatureM[]
= {45.0, 48.3, 52.1, 54.5, 62.0. 66.0, 72.3, 71.0, 70.3
,68.3, 66.3};
char dayWeekM[7][10] = { "Sunday", "Monday", "Tuesday"
, "Wednesday", "Thursday", "Friday", "Saturday" };
// Using a typedef for the day of the week */
typedefcharDayOfWeek[10];
DayOfWeek dayWeekM[7] = { "Sunday", "Monday", "Tuesday"
, "Wednesday", "Thursday", "Friday", "Saturday" };
Exercise: Create and initialize and array named monthM which will contain the 3 character abbreviation for each month. / typedef char MonthAbbrev[4];
// Initialize that array
MonthAbbrev monthM[??] =
{ ?? };
iMonth = 1;
printf("%s\n", monthM[i-1]);
// suppose we don't want to do the -1; instead, we want to actually use 1
// as our subscript for Jan. What can we do?
MonthAbbrev monthM[??] =
{ ?? };
iMonth = 1;
printf("%s\n", monthM[i]);
Multi-dimensional Arrays
Arrays can have many dimensions. You will more likely hit a limit in addressable memory before you have too many dimensions.
C Arrays occupy contiguous memory and are stored in row-major order.
int iStuffM[3][2]
= { { 1, 2 }
, { 3, 4 }
, { 5, 6 } };
Showing it as two dimensional:
1 / 2
3 / 4
5 / 6
Showing it in contiguous memory:
1 / 2 / 3 / 4 / 5 / 6
/ int iA[4][3] =
{ {0,1,2}
, {10,11,12}
, {20,21,22}
, {30,31,32}};
Shown as two-dimensional:
Column 0 / Column 1 / Column 2
Row 0 / 0 / 1 / 2
Row 1 / 10 / 11 / 12
Row 2 / 20 / 21 / 22
Row 3 / 30 / 31 / 32
Shown it in contiguous memory:
0 / 1 / 2 / 10 / 11 / 12 / 20 / 21 / 22 / 30 / 31 / 32
[0][0] / [0][1] / [0][2] / [1][0] / [1][1] / [1][2] / [2][0] / [2][1] / [2][2] / [3][0] / [3][1] / [3][2]
first row
row 0 / second row
(row 1) / third row
(row 2) / fourth row
(row 3)
Three Dimensional Array Example
Suppose we want to represent a chess board where each piece is 2 characters (plus a zero byte):
WQ - White Queen
WK - White King
WR - White Rook
WP - White Pawn
WN - White Knight
WB - White Bishop / // Option 1
char chessBoard[8][8][3];
// Option 2
typedef char Piece[3];
Piece chessBoard[8][8];
// Option 3
typedef char Piece[3];
typedef Piece Board[8][8];
Board chessBoard;
How does a C compiler map an element reference to memory?
One dimensional:

referencing element array[i]
address of element array[i] =

addressOfFirstEntry + i * sizeof(anEntry)
Two dimensional:

referencing element array[i][j]
size of a row (we will call it rowSize) =

numberOfColumns * sizeof(anEntry)

address of element array[i][j] =

addressOfFirstEntry + i * rowSize
+ j * sizeof(anEntry) / // one dimensional
int iScoreM[5] = {80, 90, 75, 60, 95}
address 6800 / 80 / 90 / 75 / 60 / 95
Each element is 4 bytes (since int is 4 bytes)
Address of iScoreM[i] = addressOfFirstEntry + i * sizeof(anEntry)
iScoreM[3] = 6800 + 3 * 4 = 6812
// two dimensional
int iStuffM[3][2]
= { { 1, 2 }
, { 3, 4 }
, { 5, 6 } };
Showing it as two dimensional:
1 / 2
3 / 4
5 / 6
Showing it in contiguous memory:
address 6820 / 1 / 2 / 3 / 4 / 5 / 6
rowSize = numberOfColumns * sizeof(anEntry)
= 2 * 4 = 8
Address of iStuffM[2][1] = addressOfFirstEntry + i * rowSize
+ j * sizeof(anEntry)
= 6820 + 2 * 8 + 1 * 4
= 6820 + 16 + 4 = 6840
More Examples of Initialization
int iCubeM[2][2][3]
={
{{000,001,002},{010,011,012}}
,{{100,101,102},{110,111,112}}
};
The function, memset(address, char, repetition) can be used to set the contents of an array to a value.
char cDotM[20];
// option 1
memset(cDotM, '.', 19);
cDotM[19] = '\0';
// option 2
memset(cDotM, '.', sizeof(cDotM)); / /* iSampleM has 5 rows with 3 columns per row
** With this initialization, the first row is populated and
** then the second, and so on.
*/
int iSampleM[5][3]
= {10, 20, 30
,110, 120, 130
,210, 220, 230
,310, 320, 330
,410, 420, 430};
10 / 20 / 30
110 / 120
210 / 220 / 230
310 / 320 / 330
410 / 420 / 430
Since arrays are in contiguous memory, the array would look like this in memory:
10 / 20 / 30 / 110 / 120 / 130 / 210 / 220 / 230 / 310 / 320 / 330 / 410 / 420 / 430
/* Same array, but the initialization specifies what is
** populated per row by using inner braces.
*/
int iSampleM[5][3]
= {{10, 20, 30}
,{110, 120}
,{210, 220, 230}
,{310, 320, 330}
,{410, 420, 430}};
/* Using inner braces for each row, you don't have to populate
** the entire row.
*/
int iSampleM[5][3]
= {{10, 20, 30}
,{110, 120}
,{210, 220, 230}
,{310}
,{410, 420, 430}};
Does this initialize all elements of iSampleM to 0?
memset(iSampleM, 0, 15); // only initialized the first 15 bytes of 60
memset(iSampleM, 0, sizeof(iSampleM));
memset(iSampleM, 0, 15*sizeof(int));
Why do subscripts in C, C++, and Java begin with 0?
Look at how addresses are calculated for an array entry.
Functions and Arrays
Arrays are automatically passed by address. C does not provide a mechanism to allow a called function to know the dimensions of an array. / // Calling function
double dTemperatureM[]
= {45.0, 48.3, 52.1, 54.5, 62.0. 66.0, 72.3, 71.0, 70.3
,68.3, 66.3, 999};
double dAverage = calcAverage(dTemperatureM);
…
}
// Code for calcAverage function
double calcAverage(double dTemperatureM[])
{
int i;
double dSum = 0.0;
for (i = 0; dTemperatureM[i] != 999; i++)
{
dSum += dTemperatureM[i];
}
return dSum;
}
Passing Multi-Dimensional Arrays
Some languages (e.g., PL/I) can pass descriptors (which describe the dimensions of an array) to functions. C only passes the starting address of an array. For a two dimensional array, you must specify the number of columns. You can also specify the number of rows.
In the function, sum2Darray (see to the right), what would be the result of sizeof(iValueM) inside that function? At compile time, we don't know the size of each dimension of iValueM in sum2dArray.
I wish the compiler would give an error. Both gcc and M/S VS give 4 or 8 (depending on the size of a pointer). / // Calling function
int iValueM[10][5];
int iSum;
…
iSum = sum2dArray(iValueM, 10);
}
// code for sum2dArray function
int sum2dArray(int iValueM[][5], int iRowCnt)
{
int i;
int j;
int isum = 0;
for (i = 0; i < iRowCnt; i++)
{
for (j = 0; j 5; j++)
{
isum += iValueM[i][j];
}
}
return isum;
}
Using Typedefs for Multi-dimensional Arrays
For multi-dimensional arrays in C, we usually specify the size for each dimension by using typedefs. This lets the complier know exactly how big the array is.
Notice that bestMove (see example) returns a structure. In C, primitive types and structures can be returned as functional results. C does not allow functional results to be an array. / typedef char Piece[3];
typedef Piece Board[8][8];
typedef struct
{
int iFromRow;
int iFromCol;
int iToRow;
int iToCol;
} Move;
// code for bestMove function
Move bestMove(Board chessBoard, int bWhiteMoveInd)
{
int i, j;
Move move;
for (i = 0; i < 8; i ++)
for(j = 0; i < 8; j ++)
{
if (bWhiteMoveInd & chessBoard[i][j][0] == 'W')
// evaluate white piece
…
else
// evaluate black piece
…
}
return move;
}
Assigning From one Array into Another
C doesn't support assignments from arrays to arrays using the assignment operator "=".
Zero-Terminated strings use strcpy(szTo, szFrom). The number of bytes copied is dependent on the '\0'.
Any array can be copied using memcpy(pTo, pFrom, iSize). It copies iSize bytes from pFrom to pTo. / // Copy Employee Name to Manager Name
char szEmpNm[30] = "Sue Melater";
char szMgrNm[30];
szMgrNm = szEmpNm; // error
strcpy(szMgrNm, szEmpNm); // This copied 12 bytes including zero terminator
// Copy array of student grades to the best student grades array
int iGradeM[20];
int iBestGradeM[20];
int iNumGrades = 12;
memcpy(iBestGradeM, iGradeM, sizeof(iGradeM)); // copied 80 bytes
memcpy(iBestGradeM, iGradeM, iNumGrades*sizeof(int)); // copied 48 bytes
Warning
If you are using memcpy to copy data from one part of an array to another location in the same array, it may be necessary to use memmove() instead of memcpy(). memmove is guaranteed to handle overlapping values. memcpy() can be faster than memmove(). / typedef char Name[30];
Name waitingLineM[50];
…
// move 5 people from element j (and the next 4 elements) to
// element i.
memcpy(&waitingLineM[i], &waitingLineM[j], 5 * sizeof(Name));
// If the from and to overlap, use memmove()
memmove(&waitingLineM[i], &waitingLineM[j], 5 * sizeof(Name));