英格兰萨里大学：《C语言》课程教学资源（讲义）Lecture 9 - Arrays

BLecture9Arrays:atandoto:Forthe lasttwo lectures wehave looked atalgorithms.Weshallnowreturntodatastructures..Sofarwehave onlylooked at simplevariables, integerscharacters floating point numbers (real numbers).But often wegetdata in sets of like'objects,e.g. images - 2D array of pixelsnttndstrings - 1D array of charactersFle.TheorderofthedataisimportantDaaSuctreCaesiyloeytgmeDeclaringArraysDeclaringArrays.We can assign initial values to any array,.C provides a simple data structure,applicableint a[3]-{10,11,12];to all datatypes:the arrayor int a[]-[10,11,12]:- int teleph[100], 7- 100 telephone numbers*/C counts the numberof items in theinitialisation list.-float marks[115]; /-115 exam marks -]The above declaration assigns values to the individualchar text[20]; /+a string 20 characters long +]arrayelementsas follows:Wecanuseany constant integerexpressiona[0]-10,a[1]-11,a[2]-12todeclarethesizeofanarray:Each a[...J is an integer variable. They are identified bysubscripts in square brackets []#define CLASS SIZE 108/.number of students+/.InC,subscripts alwaysbeginat Zero i.e.a[0]floatmarks[CLASS_SIZE] ; Well see why in the next lectureint thing[2*3+5] :SubscriptsandloopsArrayStorage.Itisverycommontouseaforlooptoaccess:Array elements are stored sequentially in memory,eachelementofanarrayinturnstarting with the [0] element/* F..PxansAoclade.catdso.h>array1.carray2.cT1724129218243msox[0]x[1]x[2]x[3]x[4]X (S)x [6]epp-eetomcmg papa peaot te-/intx[7]-[17,24,3,12,92,18,24]. /-initialierrayt_"/:Notethatalthoughwedeclare x[7] (7elements),the104851PatarYhighest subscript is 6. If we try toaccess x[7] thecomputer will let us but the result will be rubbish orJ-perint-/may result in the programming crashingorsIs(PaEot171s)n*,u,pa[u]]

1 1. Introduction 2. Binary Representation 3. Hardware and Software 4. High Level Languages 5. Standard input and output 6. Operators, expression and statements 7. Making Decisions 8. Looping 9. Arrays 10. Basics of pointers 11. Strings 12. Basics of functions 13. More about functions 14. Files 14. Data Structures 16. Case study: lottery number generator Lecture 9 Lecture 9 Arrays • For the last two lectures we have looked at algorithms. We shall now return to data structures. • So far we have only looked at simple variables, – integers – characters – floating point numbers (real numbers) • But often we get data in sets of ‘like’ objects, e.g. – images - 2D array of pixels – strings - 1D array of characters • The order of the data is important Declaring Arrays • C provides a simple data structure, applicable to all data types: the array – int teleph[100]; /* 100 telephone numbers*/ – float marks[115]; /* 115 exam marks */ – char text[20]; /* a string 20 characters long */ • We can use any constant integer expression to declare the size of an array: #define CLASS_SIZE 108 /* number of students*/ - float marks[CLASS_SIZE]; int thing[2*3+5]; Declaring Arrays • We can assign initial values to any array, int a[3]={10,11,12}; or int a[]={10,11,12}; • C counts the number of items in the initialisation list • The above declaration assigns values to the individual array elements as follows: a[0]=10, a[1]=11, a[2]=12 • Each a[.] is an integer variable. They are identified by subscripts in square brackets [ ] • In C, subscripts always begin at Zero i.e. a[0] – Well see why in the next lecture Array Storage • Array elements are stored sequentially in memory, starting with the [0] element int x[7]={17,24,3,12,92,18,24}; • Note that although we declare x[7] (7 elements), the highest subscript is 6. If we try to access x[7] the computer will let us but the result will be rubbish or may result in the programming crashing 17 24 3 12 92 18 24 X[0] X[1] X[2] X[3] X[4] X[5] X[6] low memory address low memory address Subscripts and loops • It is very common to use a for loop to access each element of an array in turn. /* Example: arrays */ #include #define MAX 21 main() { int u; long p2[MAX]; /* powers of two */ /* initialise array: */ p2[0] = 1; for (u = 1; u #define MAX 21 main() { int u; long p2[MAX]; /* powers of two */ /* initialise array: */ p2[0] = 1; for (u = 1; u main() { int u; long p2[21] = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576 }; for (u = 0; u main() { int u; long p2[21] = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576 }; for (u = 0; u < 21; u++) printf("2 to the power %2i = %7li\n", u, p2[u]); } array1.c array1.c array2.c array2.c

VectorsasArraysStrings as Arrays:We'll lookatthisinmoredetail laterbutnoteA vector in 3-spacethat strings areordered sets ofcharactershas three componentsarray3.c(x,y,zforapositionmlie(3,4,vector).,:Itcanberepresented,,bya3elementarrayanalyse.ceeringSorting an Array:Very often we would like to sort an array into order.lem(edeae.There are many ways to do this, but the simplest is"wmeI+++LEEEEEthebubblesorte+ +111+ Ps*1+- 1) 0]TAAbubblesortuses2nestedloops Values in the array are compared in pairs and swappedif410necessary so the larger value is in the higher position./ N This continues until no more swaps are neededea910心1_The valuebubbles up'to thetop'of the array:/--1201)33DEImemes.nanTOTPE>3D.sen131E".ado3:T.E5woeTwodimensionalArraysTwodimensionalArrays·Sometimes thedatahasa2D structure.Twodimensionalarraysareactuallystoredine.g.atableorimagealinearfashion,rowbyrowint table [2] [3]ROW1ROWOunsigned char image[640] [480].Thearray can be initialisedby a arrayof1724129210arraysx[0] [2]x[1][1]x [0] [0]x[1] [2]x[01 [1]X [1]1 [0]x[0] [0]x[0] [1]ROWOx[0] [2]1xi][]int x[2] [3]=((27,19,53],(14,41,59]];x [1] [2]ROW1x[1] [0]x [1] [1]camnCOLOCOL1COL22

2 Vectors as Arrays • A vector in 3-space has three components ( x,y,z for a position vector). • It can be represented by a 3 element array. /* Example: vectors represented by arrays */ #include main() { int i; int a[3] = {2, 4, 6}; int b[3] = {-5, 1, -9}; int c[3], d[3]; puts("Vectors in 3-space:\n"); printf("a = [%2i %2i %2i]\n\n", a[0], a[1], a[2]); printf("b = [%2i %2i %2i]\n\n", b[0], b[1], b[2]); /* form vector sum: */ for (i = 0; i main() { int i; int a[3] = {2, 4, 6}; int b[3] = {-5, 1, -9}; int c[3], d[3]; puts("Vectors in 3-space:\n"); printf("a = [%2i %2i %2i]\n\n", a[0], a[1], a[2]); printf("b = [%2i %2i %2i]\n\n", b[0], b[1], b[2]); /* form vector sum: */ for (i = 0; i #define MAX 1000 /* The maximum number of characters */ main() { char text[MAX], c; int i, lc, uc, dig, oth; puts("Type some text (then ENTER):"); /* Save typed characters in text[]: */ for (i = 0; i #define MAX 1000 /* The maximum number of characters */ main() { char text[MAX], c; int i, lc, uc, dig, oth; puts("Type some text (then ENTER):"); /* Save typed characters in text[]: */ for (i = 0; i = 'a' && c = 'A' && c = '0' && c = 'a' && c = 'A' && c = '0' && c #define VALS 10 /* The number of values to be sorted */ main() { int i, sorted, swaps = 0; float x[VALS], temp; /* Input values: */ printf("Enter %i floating point values:\n", VALS); for (i = 0; i x[i]) { sorted = 0; temp = x[i-1]; x[i-1] = x[i]; x[i] = temp; swaps++; } } } while (!sorted); /* Output sorted values: */ puts("\nIn ascending order, the values are:"); for (i = 0; i #define VALS 10 /* The number of values to be sorted */ main() { int i, sorted, swaps = 0; float x[VALS], temp; /* Input values: */ printf("Enter %i floating point values:\n", VALS); for (i = 0; i x[i]) { sorted = 0; temp = x[i-1]; x[i-1] = x[i]; x[i] = temp; swaps++; } } } while (!sorted); /* Output sorted values: */ puts("\nIn ascending order, the values are:"); for (i = 0; i < VALS; i++) printf("%G\n", x[i]); printf("\n%i swaps were performed.\n", swaps); } bubble.c bubble.c Two dimensional Arrays • Sometimes the data has a 2D structure e.g. a table or image int table [2][3] unsigned char image[640][480] • The array can be initialised by a array of arrays X[0][0] X[0][1] X[1][0] X[1][1] X[0][2] X[1][2] X[i][j] ROW 0 ROW 1 COL 0 COL 1 COL 2 Column index Row index Two dimensional Arrays • Two dimensional arrays are actually stored in a linear fashion, row by row int x[2][3]={{27,19,53},{14,41,59}}; 17 24 3 12 92 18 . X[0][0] X[0][1] X[0][2] X[1][0] X[1][1] X[1][2] ROW 0 ROW 1

xaapie,araye-/tinelsde catdio.hsMultidimensionalarraysarray.buge Hdet12e 812R 17,.You can haveas many subscriptsasainoyou like,though its rare to havemorentpe[4] [2],than three:toea] a/-st y:5doublelarge[10][20][30][40];122, 1++)-200 -/carrota[s] 99Againthearrayisstored linearly,withEo3the RH index varying most rapidly and/* 809 *oro-areaipa[)]-0the LH index most slowlyewretalae : 27[8+0] -?-Think of it like a mileometerparanspe[x] ty] - 13.656]800 */3

3 Multidimensional arrays • You can have as many subscripts as you like, though its rare to have more than three: double large[10][20][30][40]; • Again the array is stored linearly, with the RH index varying most rapidly and the LH index most slowly – Think of it like a mileometer /* BUG ZONE!!! Example: arrays */ #include #define N 2 #define M 5 #define SIZE 17 main() { int carrots[SIZE], parsnips[4][3]; int i, j, n = 2, m = 5; float cabbages[N][M], potatoes[n][m]; /* BUG */ float x = 4.17, y = 5.73; for (i = 1; i #define N 2 #define M 5 #define SIZE 17 main() { int carrots[SIZE], parsnips[4][3]; int i, j, n = 2, m = 5; float cabbages[N][M], potatoes[n][m]; /* BUG */ float x = 4.17, y = 5.73; for (i = 1; i <= SIZE; i++) /* BUG */ carrots[i] = 99; for (i = 0; i < 3; i++) for (j = 0; j < 4; j++) /* BUG */ parsnips[i][j] = 0; carrots[n+m] = 37; carrots[n-m] = 38; /* BUG */ parsnips[x][y] = 13.654; /* BUG */ } array.bug array.bug