C Language_0304 Notes_Array: array operation/initialization/sizeof/how many numbers in the array/new prime number judgment/two-dimensional array/3*3 tic-tac-toe

8.2.1 Array operations

Array integration initialization

  • There are two ways to define and initialize an array:

  1. array of determined size

int number [100] ;//Define an array with an array size of 100
number [cnt] = x;//Assign values ​​to the elements in the array: assign the cnt-th element in the number array to x
  1. array of indeterminate size

int a[] = {2,4,6,7,1,3,5,9,11,13,23,14,32};
  • In the second way, the size of the array is not given, and the initial values ​​of all elements of the array are directly given in braces. This definition method does not need to give the size of the array, and let the compiler count and fill it in for you.

  • On the contrary, if you define the size of the array and enter data less than the size of the array - 1 in curly braces, the compiler will fill the remaining cells with 0 for you.

int a[13]={2};     //2 0 0 0 0 0 0 0 0 0 0 0 0 

Array initialization [improved]

int main(void)
{
    int x;
    const int NUMBER = 10;//define array size
    int count[NUMBER]={0};//Define the array and initialize
    int i;
//for(i=0;i<NUMBER;i++)
//{
//    count[i]=0;
//} 
This commented out code has the same effect as the statement initialized to 0

Initial Data Sparse Array C99

//Positioning of integration initialization

There are several numbers in the array sizeof

  • sizeof: It can give the content size occupied by the entire array, in bytes.

int a[ ]={1,2,3,4,5,6,7,8,9,10,11,12,13}

For array a, sizeof(a)=52 sizeof(a[0])=4

  • Then divide by the byte unit of the type (can be replaced by the size of a single element of the array) to get the size of the array

  • sizeof(a)/sizeof(a[0])

//The advantage of this code is that when we modify the initial data in the array, we don't need to change the traversal code

Array assignment

int a[]={2,4,6,8,10};
int b[]=a;//Can't! ! ! !

Can array a be assigned to array b in this way? can't at all~

Because arrays are special variables (actually const)

To assign the elements of one array to another array, traversal must be used

traverse the array for

  • Usually we use the for loop to traverse the array, when the loop variable is set (i>0; i<array length/13; i++), the largest i in the loop is exactly the largest valid subscript of the array /12

  • Common mistakes:

  • The loop condition is wrongly set to: <= array length

  • After leaving the loop, use the value of i as the subscript of the array element//At this time, the value of i is an invalid subscript of the array/13

Notice:

  • In the search function, when an array is used as a function parameter, because the size of the array cannot be given in []

  • Cannot use sizeof to calculate the number of array elements

  • So another parameter is needed to pass in the array size. Also it doesn't make sense to enter the array size in the function header

int search(int key,int a[10])//Such a definition is meaningless

8.2.2 Prime number table + judge prime number

Tests whether x is prime with a prime number less than x. A table of existing prime numbers is required, since prime numbers are rarer than the whole population of numbers. If you want to construct such a table, if it is a table of 100 prime numbers, the procedure is as follows

#include<stdio.h>
int isPrime(int x, int knownPrimes[], int numberofKnownPrimes);
int main()
{
    const int NUMBER = 10;//define array size 10
    int prime[NUMBER] = { 2 };//Initialized to 2, the first prime number
    int count = 1;//The count variable is 1, there is already a prime number 2
    int i = 3;//Start testing from 3
 
    while (count<NUMBER)
    {
        if (isPrime(i,prime,count))//If a function is used to determine that i is a prime number
        {
            prime[count++] = i;//Add i to the prime number array, and increment the count variable by 1 as the subscript of prime
        }
    //debug code 
        {
            printf("i=%d \tcnt=%d\t",i,count);
            int i;//Local variables, only take effect within this curly brace
            for(i=0;i<NUMBER;i++)
            {
                printf("%d\t",prime[i]);
            }
            printf("\n");
        }
    //tiaoshi        
        i++;//digital step 1
    }
    
    for ( i    = 0; i < NUMBER; i++)
    {
        printf("%d", prime[i]);
        if ((i+1)%5)
        {
            printf("\t");
        }
        else
        {
            printf("\n");
        }
        return 0;
    }
}
int isPrime(int x, int knownPrimes[], int numberofKnownPrimes)
{
    int ret = 1;
    int i;
    for ( i = 0; i < numberofKnownPrimes; i++)
    {
        if (x%knownPrimes[i]==0)
        {
            ret = 0;
            break;
        }
    }
    return ret;
}

Main points:

  1. prime[count++] = i;//

  1. At this time, cnt is no longer a "counter", and it cannot be understood as counting the number of prime numbers that have been found, but a kind of "pointer", which points to the subscript of the array in turn.

  1. cnt++ is the first value and then self-increment

  1. ++a: self-increment first and then value; a++: value first and then self-increment

  1. Add the i-th to the array of prime numbers whose subscript is cnt, and then cnt is incremented to point to the next position of the array

  1. To debug code, add {braces}

  1. You can define your own local variable i in the curly braces, which only takes effect within the curly braces

  1. You can also use the value of the external variable first, and then redefine

//debug code 
        {
            printf("i=%d \tcnt=%d\t",i,count);
            int i;//Local variables, only take effect within this curly brace
            for(i=0;i<NUMBER;i++)
            {
                printf("%d\t",prime[i]);
            }
            printf("\n");
        }

Prime Number Table of New Ideas

  • The previous schemes are to continuously traverse the numbers to determine whether they are prime numbers. Then think about it if we directly construct a table, and the numbers left at the end are all prime numbers. The algorithm is as follows:

  • This method is to traverse multiples. In simple terms, the first number is 2, which is a prime number, and multiples of 2 are deleted. Then the next number is 3, which is a prime number, and multiples of 3 are deleted. The next one is 5, which is a prime number, and multiples of 5 are deleted. Then there is 7, and multiples of 7 are deleted. Then 11...and so on, the last numbers left in this table are all prime numbers.

  • The pseudo code is as shown in the figure: (prime numbers within n)

specific methods

  1. Start assigning all numbers to 1,

  1. Then start to judge the prime number from 2, and assign the subscript of the prime number multiple to 0 (that is, it is not a prime number),

  1. And as a filter condition, it will not be counted when it is not a prime number.

  1. In the final loop, all prime numbers will be traversed and output.

  1. For prime numbers within 25, you will not be able to judge whether 25 is a prime number, but you can only count until 23 is a prime number.

PS: Algorithms are not necessarily the same way of thinking as people~

8.2.3 Two-dimensional arrays

The concept of two-dimensional array

int a[3][5] ;  //It can be understood as a matrix with 3 rows and 5 columns.  a00 - a24

Traversal of two-dimensional array

Unlike a one-dimensional array, this traversal requires two loops

  • a[i][j] is an int variable, representing row i and column j

  • What does a[i,j] mean? //The right side of the comma operator is the result, so it is equivalent to a[j]

Initialization of two-dimensional array

(Positioning is defined from the middle of the middle)

Two-dimensional array example: Tic Tac Toe

#include <stdio.h>
 
int main()
{
    const int SIZE = 3;
    int board[SIZE][SIZE];
    int i,j;
    int num0fX;//X
    int num0f0;//O
    int result = -1;//-1 draw 1 is X win 0 is O win
 
    //read into matrix
    for ( i = 0; i < SIZE; i++)
    {
        for ( j = 0; j < SIZE; j++)
        {
            scanf("%d", &board[i][j]);
        }
    }
 
    //check line
    for ( i = 0; i < SIZE; i++)
    {
        num0f0 = num0fX = 0;
        for ( j = 0; j < SIZE; j++)
        {
            if (board[i][j]==1)
            {
                num0fX++;
            }
            else
            {
                num0f0++;
            }
        }
        if (num0f0==SIZE)
        {
            result = 0;
        }
        else if (num0fX == SIZE) {
            result = 1;
        }
    }
 
    //check column
    for (j = 0; j < SIZE; j++)
    {
        num0f0 = num0fX = 0;
        for (i = 0; i < SIZE; i++)
        {
            if (board[i][j] == 1)
            {
                num0fX++;
            }
            else
            {
                num0f0++;
            }
        }
        if (num0f0 == SIZE)
        {
            result = 0;
        }
        else if (num0fX == SIZE) {
            result = 1;
        }
    }
    //Diagonal
    num0f0 = num0fX = 0;
    for (i = 0; i < SIZE; i++)
    {
            if (board[i][i] == 1)//a11 a22 a33
            {
                num0fX++;
            }
            else
            {
                num0f0++;
            }
        }
        if (num0f0 == SIZE)
        {
            result = 0;
        }
        else if (num0fX == SIZE) {
            result = 1;
        }
    }
//Subdiagonal
 
    num0f0 = num0fX = 0;
    for (i = 0; i < SIZE; i++)
    {
        if (board[i][SIZE-i-1] == 1)
        {
            num0fX++;
        }
        else
        {
            num0f0++;
        }
    }
    
    return 0;
 
}

Tags: C Algorithm data structure

Posted by mridang_agarwal on Sun, 05 Mar 2023 12:08:32 +0530