University of Washington Computer Programming ISlide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30R-1University of WashingtonComputer Programming ILecture 17:Multidimensional Arrays© 2000 UW CSER-3OverviewReview1-D arraysConcepts this lecture:2-D arrays2-D arrays as parametersLayout of 2-D arrays in memoryR-4Arrays as Data StructuresReview: An array is an ordered collection of values of identical typeName the collection; number the elementsArrays are the natural choice for organizing a large number of values, all of identical typeR-5Beyond Simple ArraysSometimes the collection of values has some additional regular pattern or structureOne common such structure is the matrix or tableIn C, we can express this as a two-dimensional arrayHigher-dimensional arrays (3-D, 4-D, …) are possible, but we won’t use them in this courseR-62-Dimensional ArraysAn ordered collection of values of identical typeName the collection; number the elementsLike 1-D arrays, but a different numbering schemeExample: scores for 7 students on 4 homeworksC expressions:score[0][0] is 22score[6][3] is 122*score[3][0] is 3025202413252112student 0student 1student 2student 3student 4student 5student 62212515225815121719022425252525252425hw 0 1 2 3scoreR-7Declaring a 2-D Arrayint score [MAX_STUDENTS] [MAX_HWS] ;#define MAX_STUDENTS 80#define MAX_HWS 6...R-82-D Arrays: Terminologytype name[#rows][#columns]int score[80][6];score is a two-dimensional array of int of size 80 by 6score[0][0], score[0][1], .... , score[79][5] are the elements of the arrayR-9An Alternate Viewint score[80][6];We could also view each row as an element:“score is an array of size 80” With this view, each element (row) is a 1-D array,of type “array of size 6 of int”R-10BookkeepingAs with 1-D arrays, often we only use part of the space available in a 2-D arrayDeclared size of the array specifies its maximum capacity. The current size (# of rows and columns currently in use) needs to be kept track of in separate variablesR-11Reading in DataProblem: Read in data for student assignmentsInput data format: The number of students, then the number of assignments, followed by the data per studentA nested loop is the right program structure for reading in the data detailsint score [MAX_STUDENTS] [MAX_HWS] ;int nstudents, nhws, i, j ;R-12Reading a 2-D Array: Code/* Read the number of students and assignments, then loop to read detailed data */scanf (“%d %d”, &nstudents, &nhws) ;if (nstudents <= MAX_STUDENTS && nhws <= MAX_HWS) {for ( i = 0 ; i < nstudents ; i = i + 1 ) for ( j = 0 ; j < nhws ; j = j + 1 ) scanf(“%d”, &score [i] [j]) ;}Part of the array is unused; which part?R-13Array Input Tracescore j= 0 1 2 3 4 5 ... i=0 i=1 i=2 ... i=6i=7Input: 7 4 0 1 2 3 4 5 6 7 8 9 ...0 1 2 3 ? ? ... 4 5 6 7 ? ? ... 8 9 ... ... …? ? ? ? ...R-14Printing a 2-D Arrayif (nstudents <= MAX_STUDENTS && nhws <= MAX_HWS) {for ( i = 0 ; i < nstudents ; i = i + 1 ) { for ( j = 0 ; j < nhws ; j = j + 1 ) printf(“%d”, score [i] [j]) ; printf(“\n”) ;}}R-152-D Arrays as ParametersSame as 1-D arrays (almost): Individual array elements can be either value or pointer parametersEntire arrays are always passed as pointer parameters - never copiedDon’t use & and * with entire array parametersDifference:No empty brackets [ ] in formal parametersActually, [ ] allowed sometimes; we won’t use in this courseR-162-D Array As ParameterA function to read into array a the grade information for the given number of students and assignmentsvoid read_2D ( int a [MAX_STUDENTS] [MAX_HWS], int nstudents, int nhws){...R-172-D Array As Parameter/* Read into array a the grade information for *//* the given number of students and assignments */void read_2D ( int a [MAX_STUDENTS] [MAX_HWS] , int nstudents, int nhws){ int i, j ; for ( i = 0 ; i < nstudents ; i = i + 1 )for ( j = 0 ; j < nhws ; j = j + 1 ) scanf(“%d”, &a[i][j]) ;}R-18Array Function Argumentsint main(void){ int score [MAX_STUDENTS] [MAX_HWS] ; int nstudents, nhws ; scanf (“%d %d”, &nstudents, &nhws) ; if ( nstudents <= MAX_STUDENTS && nhws <= MAX_HWS) read_2D (score, nstudents, nhws) ;...} no &R-19Example - Digital ImageA digital image is a rectangular grid of pixelsPixel representation: integer value giving brightness from 0 (off) to 255 (full on) Black & White: one int per pixelColor: 3 ints per pixel - one each for red, green, and blueAn image is normally stored as a 2D arrayR-20Problem - Shift ImageWrite a function that shifts a B&W image right one pixelStrategy: shift columns one at a timeTo shift a column, shift the pixels 1 row at a time0 1 2 3 4 5 6 7 801234567891011R-21A couple of definitions/* Number of rows and columns in image */#define NROWS 768#define NCOLS 1024/* Representation of a white pixel */#define WHITE 255R-22Code/* Shift image right one column */void shift_right(int image[NROWS][NCOLS]) { int row, col; /* shift all columns */ for (col = … ) { /* shift column col one space to the right */ for (row = 0; row < NROWS; row++) image[row][col+1] = image[row][col]; } /* set leftmost column to white */ for (row = 0; row < NROWS; row++) image[row][0] = WHITE;}R-23Column SequenceQuestion: Does it matter if we shift from left to right vs right to left?Question: What are the correct loop bounds for col?0 to NCOLS-1? 0 to NCOLS-2? 1 to NCOLS-1? Something else? /* shift all columns */ for (col = … ) { /* shift column col one space to the rigtht */ for (row = 0; row < NROWS; row++) image[row][col+1] = image[row][col]; }R-240 1 2 3 4 5 6 7 801234567891011R-25OrderAnswer: Yes it does. If we shift from left to right, we wind up making copies of column 0 in every column of the image. Correct code looks like this. /* shift all columns */ for (col = NCOLS - 2; col >= 0; col-- ) { /* shift column col one space to the rigtht */ for (row = 0; row < NROWS; row++) image[row][col+1] = image[row][col]; }R-26Column SequenceQuestion: Does it matter if we shift from left to right vs right to left?Question: What are the correct loop bounds for col?0 to NCOLS-1? 0 to NCOLS-2? 1 to NCOLS-1? Something else? /* shift all columns */ for (col = … ) { /* shift
View Full Document
Unlocking...