Introduction to Computer Programming (C language) - Chapter 7: Arrays - Võ Thị Ngọc Châu

Nội dung text: Introduction to Computer Programming (C language) - Chapter 7: Arrays - Võ Thị Ngọc Châu

1. Ho Chi Minh City University of Technology Faculty of Computer Science and Engineering Chapter 7: Arrays Introduction to Computer Programming (C language) TS. Võ Thị Ngọc Châu (chauvtn@cse.hcmut.edu.vn, chauvtn@hcmut.edu.vn) 2017 – 2018, Semester 2
2. Course Content C.1. Introduction to Computers and Programming C.2. C Program Structure and its Components C.3. Variables and Basic Data Types C.4. Selection Statements C.5. Repetition Statements C.6. Functions C.7. Arrays C.8. Pointers C.9. File Processing 2
3. References [1] “C: How to Program”, 7th Ed. – Paul Deitel and Harvey Deitel, Prentice Hall, 2012. [2] “The C Programming Language”, 2nd Ed. – Brian W. Kernighan and Dennis M. Ritchie, Prentice Hall, 1988 and others, especially those on the Internet 3
4. Content Introduction One-dimension arrays Memory model of a C array Access to the elements of a C array Arrays of characters for strings Multidimensional arrays Passing arrays to functions Summary 4
5. Introduction – Data Types in C (Recall from Chapter 3) Built-in data types (primitive/fundamental)  char (signed char), unsigned char  short int, unsigned short, int, unsigned int, long int, unsigned long int, long long int, unsigned long long  float, double, long double  void  enum (enumerated data associated with integers) Derived data types  arrays [] of objects of a given type  pointers * to objects of a given type  structures struct containing objects of other types  union containing any one of several objects of various types 5
6. Introduction Given a void main() { double positiveNumber[10] = {2, 1, 3, 10, 8, 3, 4, 5, 9, 12}; set of n int n = 10; Variable declaration positive double minNumber = positiveNumber[0]; for an array of doubles. int iteration = 1; numbers, We haven‟t discussed while (iteration < n) { it, have we??? find the if (minNumber <= positiveNumber[iteration]) iteration = iteration + 1; smallest else { one. minNumber = positiveNumber[iteration]; iteration = iteration + 1; (Chapter 1 – } Real code in C) } } 6
7. Introduction In your exercise for practice, B.6, chapter 3, you are asked to recommend the nearest place from 4 given places to student B based on his/her current location. How did you implement those? What happens if there are 20 places for recommendation? 7
8. Introduction In our real world, our problem is related to not only a single object of interest but also a set of objects of interest.  Example 1: grade a list of submissions of each of you for every chapter  Example 2: recommend the most relevant place to visit from a list of places in a city  Example 3: sort a list of suppliers based on their transaction‟s values  Example 4: find a suitable topic among a list of topics for your assignment  8
9. Introduction Array  A means to represent collections in our real world  A data structure consisting of related data items of the same type  A group of contiguous memory locations that all have the same type An array remains the same size throughout its existence. Suppliers lstSupplier in memory id A C T I V E S F O R value 1 2 3 8 3 4 7 2 9 6 struct supplier lstSupplier[10]; 9 Real world vs. computer‟s world
10. Introduction Array  A means to represent collections in our real world  A data structure consisting of related data items of the same type  A group of contiguous memory locations that all have the same type An array remains the same size throughout its existence. The 1st supplier The 6th supplier The 10th supplier Suppliers lstSupplier in memory id A C T I V E S F O R value 1 2 3 8 3 4 7 2 9 6 struct supplier lstSupplier[10]; 10 Real world vs. computer‟s world
11. One-dimension arrays A one-dimension array is the simplest type of array in C. type_name variable_name[constant_expressionopt] =opt {expression_list}opt;  variable_name: a valid identifier for a collection  type_name: a valid data type Basic data type name, derived data type name, or new name of some existing data type  constant_expressionopt: optional, if specified, an integer expression used for a size of the array showing the number of objects of interest in the collection  expression_list: optional, a list of expressions separated by comma for initialized values 11
12. One-dimension arrays A one-dimension array is the simplest type of array in C. type_name variable_name[constant_expressionopt] =opt {expression_list}opt; Example 1: an array of 15 integer numbers to represent the number of products bought by 15 customers numProduct in memory ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? int numProduct[15]; 12
13. One-dimension arrays A one-dimension array is the simplest type of array in C. type_name variable_name[constant_expressionopt] =opt {expression_list}opt; Example 2: an array of 10 doubles to represent 10 positive numbers positiveNumber in memory 2 1 3 10 8 3 4 5 9 12 double positiveNumber[10]; 13
14. One-dimension arrays A one-dimension array is the simplest type of array in C. type_name variable_name[constant_expressionopt] =opt {expression_list}opt; Example 3: an array of 10 elements of struct supplier to represent 10 suppliers lstSupplier in memory id A C T I V E S F O R value 1 2 3 8 3 4 7 2 9 6 struct supplier lstSupplier[10]; 14
15. Memory model of a C array When defined, an array can be:  A global variable,  A local variable,  A static local variable,  A dynamic local variable, It will be organized with a fixed size in an appropriate corresponding memory segment (.data, .bss, stack, heap). Regardless of its memory segment, an array is a group of contiguous memory locations that all have the same type. Array name is the address of the first location among these contiguous memory locations. positiveNumber in memory positiveNumber is the address of the first double memory location. 2 1 3 10 8 3 4 5 9 12 double positiveNumber[10]; 15
16. Memory model of a C array 8 bytes8 bytes8 bytes8 bytes positiveNumber in memory 2 1 3 10 8 3 4 5 9 12 double positiveNumber[10]; 16
17. Memory model of a C array Array name is the address of the first location among these contiguous memory locations. Therefore, assignment for an entire array is not valid!!! a = {4, 2, 9, -8, 0}; // INVALID!!!!!!!!!!!!!! 17
18. Memory model of a C array intArray in memory 3 0 8 9 -2 int intArray[] = {3, 0, 8, 9, -2}; The compiler determined the size of this array based on the number of initial values 18
19. Access to the elements of a C array Element access is based on index starting from 0 (zero) with name[ ].  Index for the first element is 0: name[0]  Index for the second element is 1: name[1]  Index for the (i+1)-th element is i: name[i]  Index for the n-th element is n-1: name[n-1] positiveNumber in memory 2 1 3 10 8 3 4 5 9 12 positiveNumber[0] positiveNumber[5] positiveNumber[9] double positiveNumber[10]; 19
20. Access to the elements of a C array Element access is based on index with name[ ]. intArray in memory 3 0 8 9 -2 int intArray[] = {3, 0, 8, 9, -2}; 20
21. Access to the elements of a C array Element access is based on index with name[ ].  What happens with intArray[-1]?  What happens with intArray[5]? Unspecified The previous memory of intArray[0] values!!! The next memory of intArray[4]
22. Access to the elements of a C array What happens if an array defined with a given size is initialized with less initial values? Zero-filled bytes: 0, „\0‟ 22
23. Access to the elements of a C array What happens if an array defined with a given size is initialized with more initial values? Unspecified value!!! Not 7 in initialization!!! 23
24. Access to the elements of a C array Element access is based on index starting from 0 (zero) with name[ ]. Each element access with name[ ] plays a role of a single variable of the same type.  Used in any relevant expressions a1[0] == 2 a1[i] > 1  Used in any relevant statements while (a1[2] <= 10) { } a1[i] = a1[i-1] * 5; 24
25. Access to the elements of a C array How many tens have you got for your midterm exams? What is your averaged grade? 25
26. List the frequency of each character in your collection. 26
27. Arrays of characters for strings The C language has no specific data type for strings.  Each string is considered as a one-dimension array of characters ended by „\0‟.  A standard library for strings: size_t strlen(const char *str) char *strcpy(char *dest, const char *src) int strcmp(const char *str1, const char *str2) char *strcat(char *dest, const char *src) char *strtok(char *str, const char *delim) 27
28. Strings and Characters  int toupper(int c)  int ispunct(int c)  int tolower(int c)  int isspace(int c)  int isupper(int c)  int isalnum(int c)  int islower(int c)  int isalpha(int c)  int isdigit(int c)  28
29. Strings and Numbers  double atof(const char *str)  int atoi(const char *str)  long int atol(const char *str)  double strtod(const char *str, char endptr)  long int strtol(const char *str, char endptr, int base)  unsigned long int strtoul(const char *str, char endptr, int base) 29
30. Arrays of characters for strings  strCName is a string defined as an array of 20 characters ended with an additional character „\0‟ located in memory with 21 bytes C o m p u t e r P r o g r a m m i n g \0 index 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
31. Number of bytes in memory size >= length + 1 Number of characters in use, not counting „\0‟ The compiler determined the size of this string based on the number of initial characters C o m p u t e r P r o g r a m m i n g \0 index 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
32. Number of bytes in memory size >= length + 1 Number of characters in use, not counting „\0‟ The compiler determined the size of this string based on the given number of elements in array C P r o g r a m m i n g \0 \0 \0 \0 \0 \0 \0 index 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
33. Arrays of characters for strings char strCName[20] = “C Programming”; strCName is the address of the first char memory location. C P r o g r a m m i n g \0 \0 \0 \0 \0 \0 \0 index 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 length = 13 characters in use size = 20 bytes in memory strCName == &strCName[0] => TRUE type value memory strCName[10] == „i‟ => TRUE char „i‟ i strCName[10] == “i” => FALSE char [] “i” i \0 0 1 strCName = “Programming”; => INVALID for assignment => strcpy( ) strCName == “B Programming” => INVALID for comparison => strcmp( )
34. Arrays of characters for strings Enter your full name and then rewrite your name as “first_name last_name” in English Check if an input name is valid!! 34
35. Full name => First_name Last_name Checked for a valid full name 35
36. Multidimensional arrays In our previous example, a string is tokenized into many substrings based on delimiters.  Input: char aString[50] = “Introduction to Computer Programming”;  Output: char Token_1[50] = “Introduction”; char Token_2[50] = “to”; char Token_3[50] = “Computer”; char Token_4[50] = “Programming”; Can we have a list of a list of of a list? Multidimensional arrays!!! 36
37. Multidimensional arrays More in our real world, example 1 is:  A list of students Each student has a list of submissions, each per chapter. . Each submission includes a list of exercises to be grades. For grading each exercise, we need a three-dimension array of natural numbers. Example 2 is:  A gray-scale image of size 100x100 Each pixel at (i, j) is a positive integer number in [0, 255]. For image processing, we need a two-dimension array of positive integer numbers. Example 3 is related to matrices in your linear algebra which are two-dimension arrays of numbers. 37
38. Multidimensional arrays A multidimensional array is an array. Each element of a multidimensional array is also an array. 1 2 d type_name variable_name[size opt][size opt] [size opt] \ =opt {{{expression_list}, { }, }, { }, }opt; size1, size2, , or sized: optional, if specified, a constant integer expression used for a size of the array at the 1st, 2nd, , or dth dimension {expression_list}: optional, a list of expressions separated by comma for initialized values corresponding to dimensions size1*size2* *sized*sizeof(type_name) bytes are allocated for this array as a group of contiguous memory locations of the same type. 38
39. Multidimensional arrays char aString[4][50]: a list of many different strings from tokenization 39
40. Multidimensional arrays Example 1: Example 2: Example 3: Values Values Values Values Values at row 1 at row 2 at row 4 at row 5 size at size at at row 3 dimension 1 dimension 2 (row) (column) 40
41. Access to an element: name[i1][i2] [id] A value of aMatrix[1][2] A value of aMatrix[3][3] 4 bytes 4 bytes memory 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 index [0][0] [0][1] [0][2] [0][3] [1][0] [1][1] [1][2] [1][3] [2][0] [2][1] [2][2] [2][3] [3][0] [3][1] [3][2] [3][3] [4][0] [4][1] [4][2] [4][3] Access via index at each dimension is enabled and indices start at 0 for all dimensions. Array name is the address of the first memory location: aMatrix == &aMatrix[0][0]
42. Multidimensional arrays Size of the first dimension is determined by the compiler based on the initial values. Some elements have initial values. The rest will get zeros. One-dimensional array 42
43. Multidimensional arrays Generate a square matrix with a unit diagonal  Output square matrix: nxn Print a transpose of a square matrix  Input square matrix: nxn  Output square matrix: nxn Compute a dissimilarity matrix of n objects in a 3D space input from the user  Input data matrix: nx3  Output dissimilarity matrix: nxn 43
44. Generate a square matrix with a unit diagonal a[i][i] = 1; a[i][n-1-i] = 1; 44
45. Print a transpose of a square matrix In the standard library: - void srand(): initialize the random number generator used by the function rand() based on the system time - int rand(): generate a random number in the range of 0 to RAND_MAX (32767) In the standard library: - time_t: a type for storing the calendar time - time_t time(time_t *timer): calculate the current calendar time and encode it into time_t format
46. Compute a dissimilarity matrix of n objects in a 3D space input from the user
47. Compute a dissimilarity matrix of n objects in a 3D space input from the user
48. Passing arrays to functions Recall int a[10] = {2, 3, -1, 0, 4, 7, 9}; a, array name, is the address of the first int memory location. Access to a[5] returns an 2 3 -1 0 4 7 9 0 0 0 int value: 4. index 0 1 2 3 4 5 6 7 8 9 int b[3][5] = {{2, 3, -1, 0, 4}, {7, 9}, {6, 11, -2, 5}}; b, array name, is the address of the first int memory location. Access to b[2] returns the address of b[2][0] for the third row. 2 3 -1 0 4 7 9 0 0 0 6 11 -2 5 0 index [0][0] [0][1] [0][2] [0][3] [0][4] [1][0] [1][1] [1][2] [1][3] [1][4] [2][0] [2][1] [2][2] [2][3] [2][4] Access to b[0][2] returns an int value: -1. 48
49. Passing arrays to functions Pass a value of an element at index i of a one-dimension array a to functions Value passing - unchanged  Call to function func: func(a[i], ) Pass all the values of the elements of a one-dimension array a to functions Address passing - changeable  Call to function func: func(a, ) Pass a value of an element at indices i and j of a two-dimension array b to functions Value passing - unchanged  Call to function func: func(b[i][j], ) Pass a row at index i of a two-dimension array b to functions  Call to function func: func(b[i], ) Address passing - changeable Pass all the values of the elements of a two-dimension array b to functions Address passing - changeable  Call to function func: func(b, ) 49
50. Find the greatest number in Passing arrays anto array functions of integer numbers getMax(a[i-1], a[i]) ? getMaxA(a, 10) ? getMaxA(b[0], 5) ? getMaxA(b[i], 5) ? getMaxM(b, 4, 5) ? 50
51. Find the greatest number in an array of integer numbers It is necessary to specify the actual number of elements present in the array It is not necessary to specify the size of the array. It is necessary to specify the actual number of elements present in the array at each dimension It is required to specify the size of each non-first dimension of the array. 51
52. Change the greatest numbers in an array of integer numbers to RAND_MAX chgMaxA(a, 10, RAND_MAX) ? chgMaxM(b, 4, 5, RAND_MAX) ? 52
53. Change the greatest numbers in an array of integer numbers to RAND_MAX An element nums[i] is changed. This change is recorded in the memory locations of the array during the execution of the called function. Changes remain after the execution of the called function. An element nums[i][j] is changed. This change is recorded in the memory locations of the array during the execution of the called function. Changes remain after the execution of the called function. 53
54. Put them all together Problem 1: String Filtering  Input: a string from a user obtained with gets() “1. Today is Monday, isn‟t it? 234 - go 2 school.”\n  Filtering: remove all the digits and redundant spaces („ ‟, „\t‟) by keeping and/or replacing with a single whitespace „ ‟  Output: a string with no digit and each word separated from each other by a single whitespace „ ‟ “. Today is Monday, isn‟t it? - go school.” 54
55. Put them all together Problem 2: Statistical Descriptive Info.  Input: a one-dimension array of n integer numbers with n is a natural number given by a user int a[10] = {1, -3, 9, 0, 2, 8, 9, 4, 7, 6};  Calculation: calculate the statistical descriptive information about the input n integer numbers: min, median, mean, mode, max  Output: min, median, mean, mode, max min = -3; median = (4+6)/2 = 5.0; mean = 4.3; mode = 9; max = 9 Note: sorting is needed! 55
56. Put them all together Problem 3: Matrix Multiplication  Input: two matrices m1 (r1xc1) and m2 (r2xc2) of floating-point numbers  Calculation: multiply m1 by m2  Output: a resulting matrix m3 (r1xc2) 2 4 0 1 m1 1 2 1 0 0 2 3 1 7 0 0 2 m1xm2 1 1 m3 3 5 m2 1 1 4 1 3 0 56
57. Summary An array is a group of continuous memory locations of the same type.  Its size is unchanged during its existence.  It can be considered as a group of individual variables of the same type. Used in any relevant expressions, statements, functions Definition can be done with initialization. Index-based access starts at zero. One-dimension vs. multidimensional arrays Strings are special one-dimension arrays of characters ended by „\0‟. 57
58. Chapter 7: Arrays 58