W2- Two-dimensional array, Sorting algorithm

## #C Programming (II) - 2 ## Two-dimensional array, Sorting algorithm English: Lei KuoLiang nicolaslouis@mail.fcu.edu.tw Chinese(TW): Wang M.H --- ### This week's course catalog 0. Review 1. Two-dimensional array * Multidimensional array 2. Sort * Bubble sorting --- ## Last week's course review ---- ### One-dimensional array declaration ```c // Declare a size of 5 int array a Int a[5]; // Do not give the array size, directly to the number inside, the computer will automatically determine the array size: Int b[] = {12, 56, 7, 18, -3}; // Given the size of the array, give the value inside // If the number of values inside is smaller than the array size, the insufficient position will be filled with 0. Int c[10] = {12, 56, 7, 18, -3}; ``` ---- Zero the array at the time of declaration: **`int a[10] = {0};`** ---- After the array is declared It is no longer possible to assign values in the way of announcement! ```c int a[5]; a = {12, 56, 7. 18, -3};//ERROR!!!!! a[] = {12, 56, 7. 18, -3};//ERROR!!!!! a[5] = {12, 56, 7. 18, -3};//ERROR!!!!! ``` Can only be assigned one by one ```c int a[5]; a[0] = 12; a[1] = 56; a[2] = 7; a[3] = 18; a[4] = -3; ``` ---- ### Declaration of character array ```c // Declare a character array of size 5 a Char a[5]; // Size is 5, can only put a string of length 4 or less, because the last end to fill the '\0' end character // Do not give the array size, directly give the string, the computer will automatically determine the array size: Char b[] = "hello"; // At this time b size is 6, the content is {'h', 'e', 'l', 'l', 'o', '\0'} // Given the size of the array, give the string //If the string length is smaller than the array size, the insufficient position will complement '\0'. Char c[10] = "hello"; ``` ---- ```c char a[] = "hello"; char b[] = {'h', 'e', 'l', 'l', 'o'}; ``` The difference between the two is that the `'e' of a will add one more ''\0'`. And the array size of a is 6, and the array size of b is 5 ---- After declaring the character array It is no longer possible to assign a string in the way it is declared! ```c char a[5]; a = "hello";//ERROR!!!!! a[] = "hello";//ERROR!!!!! a[5] = "hello";//ERROR!!!!! ``` Alternative: strcpy() of string.h ---- ### Input and output of character array Printf, scanf use %s Scanf reads blank key, tab, newline will end reading ```c Char str[10]; Scanf("%s", str); //Do not use the & address operator because the array name itself is the address Printf("%s\n", str); ``` Gets read a newline ('\n') will end reading Puts will automatically wrap at the end when printed ('\n') ```c char str[10]; gets(str); puts(str); ``` ---- ### Read to EOF ```c while(scanf("%s", a) != EOF) { //... //... } while(gets(a) != NULL) { //... //... } ``` ---- ## string.h | Function | Function | | -------- | -------- | Strlen(char str[]) | Take string length | | strcmp(char str1[], char str2[]) | Compare two strings | Strcpy(char str1[], char str2[]) | Copy str2 to str1 | Strcat(char dest[], char src[]) | Copy src content to the end of dest | --- ## Two-dimensional array ---- Imaginary two-dimensional array **`a[Rows][Column]`** ![](https://i.imgur.com/WrP94nm.png) ---- Actual two-dimensional array Memory is also continuous ![](https://i.imgur.com/0mSbp47.png =650x450) --- ### Two-dimensional array declaration ---- Declare the array format: **`variable type array name [first dimension] [second dimension]; `** For example: Declare an int array a of size 3x4 **`int a[3][4];`** ---- Declare an int array a of size 3x4 And preset values ```c int a[3][4] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}}; ``` ---- If the number of values given is less than the declared size, it will be filled with 0 ```c int a[3][4] = {{1, 2, 3}, {5, 6, 7, 8}, {9, 10}}; //a[0][3] == 0 //a[2][2] == 0 //a[2][3] == 0 ``` ```c int a[3][4] = {{1, 2, 3, 4}, {5, 6, 7, 8}}; //a[2][0] == 0 //a[2][1] == 0 //a[2][2] == 0 //a[2][3] == 0 ``` ---- If you use a one-dimensional format when assigning, it will be stored "in order" ```c int a[3][4] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}; ``` Equivalent to ```c int a[3][4] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}}; ``` ---- Array zeroing: **`int a[3][4] = {{0}};`** ---- The size of the first dimension can also be omitted when declaring The computer will automatically detect ```c int a[][4] = {{1, 2, 3}, {5, 6, 7, 8}, {9, 10}}; //At this time, a is a 3x4 array. ``` But can't omit the size of the second dimension ```c int a[][] = {{1, 2}, {3, 4}, {5, 6}}; //ERROR!! int b[3][] = {{1, 2}, {3, 4}, {5, 6}}; //ERROR!! ``` --- ### Use of two-dimensional arrays ---- Enter the values into the array in sequence, and then output them sequentially ```c int a[5][6]; //Enter in order for(int i = 0; i < 5; i++) for(int j = 0; j < 6; j++) scanf("%d", &a[i][j]); //Sequential output for(int i = 0; i < 5; i++) { for(int j = 0; j < 6; j++) printf("%d ", a[i][j]); printf("\n"); } ``` ---- Verify the continuity of elements in the array ![](https://i.imgur.com/ak8hAYL.png) ---- ### Two-dimensional character array ```c //Declare char str[3][10] = {"Jim", "Hello", "Brian"}; //Enter in order for(int i = 0; i < 3; i++) scanf("%s", str[i]); //Sequential output for(int i = 0; i < 3; i++) printf("%s", str[i]); ``` --- ## Multidimensional array Arrays can not only be two-dimensional ---- ### Multidimensional array declaration ```c int a[2][2][3]; int b[][2][3] = {{{1, 2, 3}, {4, 5, 6}}, {{7, 8, 9}, {10, 11, 12}}}; ``` ```c int a[2][2][3][4]; int b[][2][3][4] = {{{{1, 2}, {3, 4}}, {{5, 6}}}, {{{7, 8}}}, {9, 10}}; ``` Arrays above four dimensions are already too complicated, so they will not be used normally~ --- ### Exercise one * Matrix transpose, convert the input i x j matrix into j x i matrix output * Input will be an i x j matrix, 1 ≦ i, j ≦ 100 ※i, j size must be judged by yourself * Output the matrix after transposition, there must be no blank at the end of each line ---- Sample input ``` 1 2 3 4 5 6 7 8 9 10 11 12 ``` Sample output ``` 1 5 9 2 6 10 3 7 11 4 8 12 ``` --- ### Exercise 2 * Matrix multiplication, multiplying the input p x q matrix with the q x r matrix into a p x r matrix output * The input will have a p x q matrix first, and a blank line will be a q x r matrix, 1 ≦ p, q, r ≦ 10 ※p, q, r size must be judged by yourself * Output a p x r matrix ---- Sample input ``` 1 2 3 4 5 6 1 2 3 4 5 6 ``` Sample output ``` 22 28 49 64 ``` ---- #### HINT Mathematical matrix multiplication, let matrix C = matrix A x matrix B ![](https://i.imgur.com/oQ6qaq7.png) $C_{1,2}= (A_{1,1},A_{1,2})·(B_{1,2},B_{2,2})$ $= A_{1,1}·B_{1,2}+A_{1,2}·B_{2,2}$ $C_{3,3}= (A_{3,1},A_{3,2})·(B_{1,3},B_{2,3})$ $= A_{3,1}·B_{1,3}+A_{3,2}·B_{2,3}$ --- ## Sort Sort the columns from small to large ---- ### Bubble sorting 1. Compare two adjacent elements and exchange if the previous one is larger 2. Repeat the action of 1 until the end, the last element will be the maximum 3. Repeat the action of 1, 2, each time comparing to the last element of the previous round 4. Repeat the above actions until no elements need to be compared ---- Original series **9 5 1 6** ----  9 > 5 **++9 5++ 1 6** ----  9, 5 exchange location **++5 9++ 1 6** ----  9 > 1 **5 ++9 1++ 6** ----  9, 1 exchange location **5 ++1 9++ 6** ----  9 > 6 **5 1 ++9 6++** ----  9, 6 exchange location **5 1 ++6 9++** ----  Second round **5 1 6 ==9==** ----  5 > 1 **++5 1++ 6 ==9==** ----  5, 1 exchange location **++1 5++ 6 ==9==** ----  5 ≦ 6, no exchange location **1 ++5 6++ ==9==** ----  Third round **1 5 ==6 9==** ----  1 ≦ 5, no exchange location **++1 5++ ==6 9==** ----  Sort result **==1 5 6 9==** ---- ```c int num[N]; //After entering the value for(i = N - 1; i > 0; i--) { for(j = 0; j < i; j++) { if(num[j] > num[j + 1]){ //num[j]、num[j + 1]Numerical exchange int tmp = num[j]; num[j] = num[j + 1]; num[j + 1] = tmp; } } } ``` --- ### Exercise 3 * Enter multiple funds, one line of measurement * There is a series of N integers A, 2 ≦ N ≦ 50 in the measurement, and the values in the series A are between ±1000, and at least one odd number and one even number appear. * The first line of each measurement output will be all odd numbers appearing in the series from small to large * The second line of each measurement output will be all the even numbers appearing in the series from large to small * There must be no blank at the end of each line * A blank line after each measurement output ---- Sample input ``` 12 36 33 -10 9 -7 10 5 6 -9 100 0 12 36 12 -1 ``` Sample output ``` -7 9 33 36 12 -10 -9 5 100 10 6 -1 36 12 12 0 ``` --- ### Research: In addition to bubble sorting? When the program is written for a long time, it will actually find that the time efficiency of the bubble sorting method is actually very poor (but it is the easiest to understand). In addition to the bubble sorting method, there are actually many sorting methods, such as insert sorting, cocktail sorting, merge sorting, etc. You might want to check out Google or Wiki, and even remember some sorting methods that are not taught in class. XD --- ### Research: Search Algorithm We recently learned about arrays and can store a lot of values. It is important to sort these values. But in fact, there is another skill that is very important, that is, searching. In the sorted values after sorting, look for the existence of a certain value, and the value appears in the first few. How do you calculate it faster? --- ###### tags: `1082 Ai-Mod-Eng-LKL`