This is the 13th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021
The exercises in this article are mainly a supplement to the questions in the chapter of The tianqin 19 array. Because there is no running result in the book, I rewrote it myself. Some parts of the code in the book are not readable == if you haven’t bought tian Qin’s book, just read this one.
Compressed storage of matrices
matrix
In o matrix rows and columns in a pit, is when you put the two dimensional array directly to the function, then from the function for the two-dimensional array of rows and columns will happen cross-border access values may be wrong, it is because you passed is the first element of the array of addresses, should be calculated by the participation in the rows and columns to function again.
Matrix transpose
void display(int A[][maxSize],int c,int r){
for(int i=0; i<r; i++){for(int j=0; j<c; j++){ cout<<setw(2)<<A[i][j]; } cout<<endl; }}// Matrix transpose
void matrixReserve(int A[][maxSize],int c,int r){
int B[c][r]={};
cout<<"Reverse the previous array"<<endl;
display(A,c,r);
cout<<"Array after reversal"<<endl;
for(int i=0; i<r; i++){for(int j=0; j<c; j++){ B[j][i]=A[i][j]; }}display(B,c,r);
}
int main(a){
int A[][3] = {1.2.3.4.5.6.7.8.9};
int c=sizeof(A[0) /sizeof(int);
int r=(sizeof(A)/sizeof(int))/c;
matrixReserve(A,c,r);
}
Copy the codeAdding matrices
C[i][j]=A[i][j]+B[i][j]
// matrix addition
void matrixAdd(int A[][2].int B[][2].int m,int n) {
int C[m][2] = {};for(int i=0; i<m; i++){for(int j=0; j<n; j++){ C[i][j]=A[i][j]+B[i][j]; }}display(C,m,n);
}
int main(a){
int A[2] [2] = {1.2.3.4};
int B[2] [2] = {5.6.7.8};
int c=sizeof(A[0) /sizeof(int);
int r=(sizeof(A)/sizeof(int))/c;
matrixAdd(A,B,c,r);
}
Copy the codeMatrix multiplication
C[I][j]= the sum of each element on row I of A multiplied by each element on column J of B; Two matrices can be multiplied only if the number of columns in A is equal to the number of rows in B.
// Matrix multiplication
void matrixMuti(int A[][2].int B[][2].int m,int n) {
int C[m][2] = {};for(int i=0; i<m; i++){for(int j=0; j<n; j++){ C[i][j]=0;
/* Note that h is not necessarily m, but the number of columns in A or the number of rows in B, so it is m */ because m and n are equal
for(int h=0;h<m;h++){
C[i][j]+=A[i][h]*B[h][j];
}
}
}
display(C,m,n);
}
int main(a){
int A[2] [2] = {1.2.3.4};
int B[2] [2] = {5.6.7.8};
int c=sizeof(A[0) /sizeof(int);
int r=(sizeof(A)/sizeof(int))/c;
matrixMuti(A,B,c,r);
/ / 19 and 22
/ / 43 50
}
Copy the codeProblem sets
1. There are multiple zero elements in the n elements of the array. Design an algorithm to move all the non-zero elements in the array to the front of the array A.
The algorithm is to use a pointer J to record the subscript of the last occurrence of non-zero elements, skip 0, and exchange J +1 with the 0 value of this position when the next occurrence of non-zero elements, j+1.
void moveZeroToBottom(int A[maxSize],int length){
int j=- 1; // Records the position of the last non-zero element
for(int i=0; i<length; i++){if(A[i]==0) {continue;
}else{
j++;
inttemp=A[i]; A[i]=A[j]; A[j]=temp; }}displayArr(A,length);
}
int main(a){
int A[maxSize]={0.2.1.3.0.0.3.5.7};
int length=sizeof(A)/sizeof(A[0]);
moveZeroToBottom(A,length); // 2 1 3 3 5 7 0 0 0 0
}
Copy the code2. For floating-point array A[0,…,n-1], use recursive implementation to calculate the maximum value and the sum and average value of all the numbers in the array respectively.
It’s a very basic algorithm, but there’s more to explain. Avg =((n-1)*avg+arr[I])/n I just took the sum of the previous step except for the total length ==.
float findMax(float arr[],float max,int i){
if(i==maxSize){
return max;
}
if(arr[i]>max){
max=arr[i];
}
return findMax(arr,max,i+1);
}
float getsum(float arr[],float sum,int i){
if(i==maxSize){
return sum;
}
return getsum(arr,sum+arr[i],i+1);
}
float getAverage(float arr[],float sum,int i){
if(i==maxSize){
return sum/maxSize;
}
return getAverage(arr,sum+arr[i],i+1);
}
int main(a){
float A[maxSize]={0.2.1.3.8.0.3.5.7};
float max=findMax(A,0.0);
float sum=getsum(A,0.0);
float avg=getAverage(A,0.0);
cout<<max<<endl;; / / 8
cout<<sum<<endl; / / 29
cout<<avg<<endl; / / 3.222222
}
Copy the code3. Try to design an algorithm that moves all the odd numbers in an array before the even numbers without adding additional storage space. The write space is O(n).
The first pointer I stops at an even number, and the last pointer J stops at an odd number. The two values are swapped and traversed until the two Pointers overlap.
void bubbleOdd(int arr[]){
int i=0,j=maxSize- 1;
while(i<j){
while(arr[i]%2= =1&&i<j) i++;
while(arr[j]%2= =2&&i<j) j--;
if(i<j){
inttemp=arr[i]; arr[i]=arr[j]; arr[j]=temp; i++; j--; }}display(arr);
}
int main(a){
int A[maxSize]={0.2.1.3.8.0.3.5.7};
bubbleOdd(A); // 5
}
Copy the code4. Suppose A linear table L with an integer element is placed in A one-dimensional array. An algorithm is designed to divide the array into left and right parts with A[n-1] as the reference. The element pointer in the right half is greater than A[n-1], which is in between. I want the result to still be stored in array A.
It is similar to quicksort, but the first element is used as a reference value after the first and last elements are swapped. Two Pointers I and J, with j moving first and looking for the one smaller than the reference value, are exchanged with the element pointed to by I; And then from the front of the larger than the reference value, put it in the back; Set the position as a reference value until the quantity Pointers meet.
void quickSort(int arr[]){
int i=0;
int j=maxSize- 1;
int temp=arr[j];
arr[j]=arr[i];
arr[i]=temp;
while(i! =j){while(i<j&&arr[j]>temp) j--; // Find a number less than the target value and place it in front
if(i<j){
arr[i]=arr[j];
i++;
}
while(i<j&&arr[i]<=temp) i++; // Find a number greater than the target value and place it in front
if(i<j){
arr[j]=arr[i];
j--;
}
}
arr[i]=temp;
}
Copy the code5. Design an algorithm to count the number of elements with the following characteristics in a given orthopedic matrix A, and output their coordinates and values. The minimum fold in the row where their technology is located is the minimum value in the column, or the maximum system in the row where their technology is located is the maximum value in the column.
Find the minimum value in a row, record the current column, and then check whether it is the minimum value in the column.
void getMin(int A[][3].int c,int r){
int min=A[0] [0];
int minj=0;
int isFind=1;
for(int i=0; i<r; i++){for(int j=0; j<c; j++){if(A[i][j]<min){ min=A[i][j]; minj=j; }}for(int k=0; k<r; k++){if(min>A[k][minj]){
isFind=0;
break; }}if(isFind==1){
cout<<"Find the minimum"<<A[i][minj]<<", the coordinate is"<<i<<","<<minj<<endl;
isFind=0; }}}/ / outputFind the minimum1, the coordinates of0.0
Copy the code5. How to introduce the triplet storage structure characteristics of sparse matrix and realize the basic operation of sparse matrix?
1. Given sparse matrix A. Create its tuple storage structure B.
The triplet storage structure is a sequential structure, and therefore a sequential table. Each node in the table corresponds to a non-zero element of the sparse matrix, which contains three fields, namely the value of the element, row index and column index. In addition, the first element in row zero stores the number of non-zero elements in the matrix, the second element in row zero stores the number of rows in the matrix, and the third element in row zero stores the number of columns in the matrix.
void create(int A[][3].int c, int r,int B[][3]){
int k=1;
for(int i=0; i<r; i++){for(int j=0; j<c; j++){if(A[i][j]! =0){
B[k][0]=A[i][j];
B[k][1]=i;
B[k][2]=j;
k++;
}
}
}
B[0] [0]=k- 1;
B[0] [1]=r;
B[0] [2]=c;
display(B,k,3);
}
int main(a){
int A[3] [3] = {1.2.3.4.5.6.7.8.9};
int B[maxSize][3];
create(A,3.3,B);
}
Copy the codeThe output
1 0 0 2 0 1 0 2 4 1 0 5 1 6 1 2 7 2 0 8 2 1 9 2 2Copy the code2. Find if the given element x is in the matrix.
Search through the triplet found above.
int search(int trimat[][3].int target,int r){
int isFind=0;
for(int i=1; i<r; i++){if(B[i][0]==target){
cout<<"Coordinate is"<<B[i][1] < <","<<B[i][2]<<endl;
isFind=1; }}return isFind;
}
int main(a){
int A[][3] = {1.2.3.4.5.6.7.8.9};
int B[9] [3];
create(A,3.3,B);
search(B,5.9); // the coordinate is 1,1
}
Copy the code6. Assume that the sparse matrix A is represented by triples. Write a function whose transpose matrix B requires that B also be represented by triples.
The transpose of A matrix boils down to the formula A[m][n]=B[n][m]. But the triplet is not that simple, the elements in the triplet are the result of the original matrix stored in row first, so the following program is wrong!!
void reserve(int B[][3].int C[][3].int r){
for(int i=1; i<=r; i++){ C[i][0]=B[i][0];
C[i][1]=B[i][2];
C[i][2]=B[i][1];
}
C[0] [0]=B[0] [0];
C[0] [1]=B[0] [2];
C[0] [2]=B[0] [1];
cout<<Post-transpose<<endl;
display(C,r,3);
}
Copy the codeThe output
// The original triplet 9 3 3 1 0 0 2 0 1 3 0 2 4 1 0 5 1 6 1 2 7 2 0 8 2 1 9 2 2 ---- after inversion is ----- 9 3 3 1 0 0 2 1 0 3 2 0 4 0 1 5 1 1 6 1, 7, 0, 2, 8, 1, 2, 9, 2, 2Copy the codeThe correct way to write it is to find the elements in the ith column of A, place them in the ith row of B, and switch the coordinates between the elements.
void reserve(int B[][3].int C[][3].int r){
int k=1;
for(int i=0; i<3; i++){for(int j=1; j<r; j++){if(B[j][2]==i){
C[k][0]=B[j][0];
C[k][1]=B[j][2];
C[k][2]=B[j][1];
k++;
}
}
}
C[0] [0]=B[0] [0];
C[0] [1]=B[0] [2];
C[0] [2]=B[0] [1];
cout<<Post-transpose<<endl;
display(C,10.3);
}
Copy the codeThe results of
---- is reversed to ----- 9 3 3 1 0 0 4 0 1 7 0 2 2 1 0 5 1 1 8 1 2 3 2 0 6 2 1 9 2 2Copy the code7. Assume sparse matrix. Both A and b are represented by triples. Write A function that computes C=A+ b and C is also represented by triples.
If the matrix addition rule is to add the elements at the corresponding positions, for the matrices A and B under the triplet storage structure, if the elements at the positions are currently needed. The addition of a[I][j] and b[I][j] requires consideration of whether the two elements are non-zero at the same position. (The logic of the algorithm in Wang Dao is quite complicated, so I suggest converting triples into matrices and then adding and then converting triples ==)
void add(int A[][3].int B[][3].int C[][3].int r,int c){
int k=1;
int i=1,j=1;
while(i<=A[0] [0]&&j<=B[0] [0]) {if(A[i][1]==B[j][1]) {// Compare the same row, the smaller columns go into c first
if(A[i][2]<B[j][2]){
C[k][0]=A[i][0];
C[k][1]=A[i][1];
C[k][2]=A[i][2];
++k;
++i;
}else if(A[i][2]>B[j][2]){
C[k][0]=B[j][0];
C[k][1]=B[j][1];
C[k][2]=B[j][2];
++k;
++j;
}else{// If A and B are in the same position, add them to C
int temp=A[i][0]+B[j][0];
if(temp! =0) {// Make sure the number is non-zero
C[k][0]=temp;
C[k][1]=A[j][1];
C[k][2]=A[j][2]; ++k; } ++i; ++j; }}else if(A[i][1]<B[j][1]) {// Store small rows in C first
C[k][0]=A[i][0];
C[k][1]=A[i][1];
C[k][2]=A[i][2];
++k;
++i;
}else{ // The number of rows of A is greater than the number of rows of B
C[k][0]=B[j][0];
C[k][1]=B[j][1];
C[k][2]=B[j][2]; ++k; ++j; }}// If there are still elements left in A and B
while(i<=A[0] [0]){
C[k][0]=A[i][0];
C[k][1]=A[i][1];
C[k][2]=A[i][2];
++k;
++i;
}
while(j<=B[0] [0]){
C[k][0]=B[j][0];
C[k][1]=B[j][1];
C[k][2]=B[j][2];
++k;
++j;
}
C[0] [0]=k- 1;
C[0] [1]=A[0] [1];
C[0] [2]=A[0] [2];
cout<<"Added triplet."<<endl;
display(C,k,3);
}
Copy the codeWhen both matrices are {1,2,3,4,5,6,7,8,9}, the output is as follows:
The triplet of the first matrix is 9 3 3 1 0 0 2 0 1 3 0 2 4 1 0 5 1 1 6 1 2 7 2 0 8 2 1 9 2 2 the triplet of the second matrix is 9 3 3 1 0 0 2 0 1 3 0 2 4 1 0 5 1 1 6 3 3 2 0 0 4 0 16 0 2 8 10 10 1 1 12 12 14 2 0 16 2 1 18 2 2 2Copy the code8. Assume sparse matrices A and B. Write A function that computes C=A*B and requires C also to be A sparse matrix represented by triples.
Matrix multiplication is a common matrix operation. If you multiply two matrices A and B, you get C, and the ith row and the JTH column of C is the sum of the ith row of A multiplied by the JTH column of B. And the dot product of two vectors. A and B can be multiplied only if the number of columns in A is equal to the number of rows in B.
Two vector a = (a1, a2,..., an] and b = (b1, b2,..., bn) of the dot product is defined as: a, b = a1b1 + a2b2 +... + anbn.Copy the codeI’m going to use the two matrices (1 to 9) that I just did, and I’m going to multiply them
The number of positions 0,0 in the matrix is :1* 1+2*4+3*7=30. The number of positions 0,1 is :1*2+2*5+3*8=36... Blogger lazy, not a calculation. Calculate two numbers in your mouth to verify the results of the following triplet algorithmCopy the codeIn the triplet, here we need to define the getValueOfTrimat function to get the value in the triplet according to the subscript in the matrix. It is important to verify that sum cannot be 0, because 0 elements are not counted in triples.
int getValueOfTrimat(int trimat[][3].int r,int c){
for(int i=1; i<=trimat[0] [0]; i++){if(trimat[i][1]==r&&trimat[i][2]==c){
return trimat[i][0]; }}return 0;
}
void multi(int A[][3].int B[][3].int C[][3]){
if(A[0] [1]! =B[0] [2]){
cout<<"You can't multiply matrices."<<endl;
return;
}
int i,j,k=1;
for(i=0; i<A[0] [1]; i++){for(j=0; j<B[0] [2]; j++){int sum=0;
for(int t=0; t<A[0] [1]; t++){ sum+=getValueOfTrimat(A,i,t)*getValueOfTrimat(B,t,j);
}
if(sum! =0){
C[k][0]=sum;
C[k][1]=i;
C[k][2]=j;
k++;
}
}
}
C[0] [0]=k- 1;
C[0] [1]=i;
C[0] [2]=j;
display(C,k,3);
}
Copy the codeThe result is:
The triplet of the first matrix is 9 3 3 1 0 0 2 0 1 3 0 2 4 1 0 5 1 1 6 1 2 7 2 0 8 2 1 9 2 2 the triplet of the second matrix is 9 3 3 1 0 0 2 0 1 3 0 2 4 1 0 5 1 1 6 The result of multiplying two matrices is 9 3 3 30 0 0 36 0 1 42 02 66 10 81 1 1 96 12 102 2 0 126 2 1 150 2 2Copy the codeRefer to the article
- C++ two dimensional array explanation, two dimensional array declaration and initialization
- Matrix multiplication algorithm