基础数据结构【一】————数组

二维数组相乘，矩阵相乘，

#include <iostream>
using namespace std;void MatrixMultiply(int*, int*, int*, int, int, int);
int main()
{int M, N, P;int i, j;//矩阵A部分 cout << "请输入矩阵A的维数(M,N): " << endl;cout << "M= ";cin >> M;cout << "N= ";cin >> N;int* A = new int[M * N];cout << "[请输入矩阵A的各个元素]" << endl;for (i = 0; i < M; i++)for (j = 0; j < N; j++){cout << "a" << i << j << "=";cin >> A[i * N + j];}//矩阵B部分 cout << "请输入矩阵B的维数(N,P): " << endl;cout << "N= ";cin >> N;cout << "P= ";cin >> P;int* B = new int[N * P];cout << "[请输入矩阵B的各个元素]" << endl;for (i = 0; i < N; i++)for (j = 0; j < P; j++){cout << "b" << i << j << "=";cin >> B[i * P + j];}int* C = new int[M * P];MatrixMultiply(A, B, C, M, N, P); //调用函数 cout << "[AxB的结果是]" << endl;for (i = 0; i < M; i++){for (j = 0; j < P; j++)cout << C[i * P + j] << "\t";cout << endl;}system("pause");
}
//进行矩阵相乘 
void MatrixMultiply(int* arrA, int* arrB, int* arrC, int M, int N, int P)
{if (M <= 0 || N <= 0 || P <= 0){cout << "[错误:维数M,N,P必须大于0]" << endl;return;}for (int i = 0; i < M; i++)for (int j = 0; j < P; j++){int Temp;Temp = 0;for (int k = 0; k < N; k++)Temp = Temp + arrA[i * N + k] * arrB[k * P + j];arrC[i * P + j] = Temp;}
}

二维数组，矩阵相加，函数调用

#include <iostream>
using namespace std;const int  ROWS = 3;
const int COLS = 3;
void MatrixAdd(int*, int*, int*, int, int);   //函数原型
int main()
{int A[ROWS][COLS] = { {1,3,5},{7,9,11},{13,15,17} };int B[ROWS][COLS] = { {9,8,7},{6,5,4},{3,2,1} };int C[ROWS][COLS] = { 0 };cout << "[矩阵A的各个元素]" << endl;  //输出矩阵A的内容for (int i = 0; i < ROWS; i++){for (int j = 0; j < COLS; j++)cout << A[i][j] << "\t";cout << endl;}cout << "[矩阵B的各个元素]" << endl;	//输出矩阵B的内容for (int i = 0; i < ROWS; i++){for (int j = 0; j < COLS; j++)cout << B[i][j] << "\t";cout << endl;}MatrixAdd(&A[0][0], &B[0][0], &C[0][0], ROWS, COLS);cout << "[显示矩阵A和矩阵B相加的结果]" << endl;	//输出A+B的内容for (int i = 0; i < ROWS; i++){for (int j = 0; j < COLS; j++)cout << C[i][j] << "\t";cout << endl;}system("pause");
}
void MatrixAdd(int* arrA, int* arrB, int* arrC, int dimX, int dimY)
{if (dimX <= 0 || dimY <= 0){cout << "矩阵维数必须大于0" << endl;return;}for (int row = 1; row <= dimX; row++)for (int col = 1; col <= dimY; col++)arrC[(row - 1) * dimY + (col - 1)] = arrA[(row - 1) * dimY + (col - 1)] + arrB[(row - 1) * dimY + (col - 1)];
}

数组压缩降维

#include <iostream>
using namespace std;
#define ARRAY_SIZE 5  //矩阵的维数 
int getValue(int ,int);
int A[ARRAY_SIZE][ARRAY_SIZE]={ //上三角矩阵的内容 {7, 8, 12, 21, 9}, {0, 5, 14,  17, 6}, {0, 0, 7, 23, 24}, {0, 0, 0,  32, 19}, {0, 0, 0,  0,  8}};  
//一维数组的数组声明 
int B[ARRAY_SIZE*(1+ARRAY_SIZE)/2];  
int main()
{int i=0,j=0;int index;    cout<<"=========================================="<<endl;cout<<"上三角形矩阵："<<endl;for ( i = 0 ; i < ARRAY_SIZE ; i++ ) {for ( j = 0 ; j < ARRAY_SIZE ; j++ ) cout<<"\t"<<A[i][j];cout<<endl;    }//将右上三角矩阵压缩为一维数组 index=0;for ( i = 0 ; i < ARRAY_SIZE ; i++ ) {for ( j = 0 ; j < ARRAY_SIZE ; j++ ) {if(A[i][j]!=0) B[index++]=A[i][j];}}cout<<"=========================================="<<endl;cout<<"以一维数组的方式表示："<<endl;cout<<"\t[";for ( i = 0 ; i < ARRAY_SIZE ; i++ ) {for ( j = i ; j < ARRAY_SIZE ; j++ ) cout<<" "<<getValue(i,j);}cout<<" ]";cout<<endl;    system("pause");
}
int getValue(int i, int j) {int index = ARRAY_SIZE*i - i*(i+1)/2 + j;return B[index];
}

稀疏矩阵，二维数组，内存压缩

#include <iostream>
#include <ctime>
#include <cstdlib>using namespace std;
const int _ROWS = 8;		//定义行数
const int _COLS = 9;		//定义列数
const int _NOTZERO = 8;		//定义稀疏矩阵中不为0的个数int main ()
{  int i,j,tmpRW,tmpCL,tmpNZ;int temp=1;int Sparse[_ROWS][_COLS];		//声明稀疏矩阵int Compress[_NOTZERO][3];		//声明压缩矩阵srand(time(NULL));for (i=0;i<_ROWS;i++)			//将稀疏矩阵的所有元素设为0for (j=0;j<_COLS;j++)Sparse[i][j]=0;tmpNZ=_NOTZERO;for (i=1;i<tmpNZ+1;i++){tmpRW = rand()%_ROWS;tmpCL = rand()%_COLS;if(Sparse[tmpRW][tmpCL]!=0)//避免同一个元素设定两次数值而造成压缩矩阵中有0tmpNZ++;Sparse[tmpRW][tmpCL]=i; //随机产生稀疏矩阵中非零的元素值}cout<<"[稀疏矩阵的各个元素]"<<endl; //输出稀疏矩阵的各个元素for (i=0;i<_ROWS;i++){  for (j=0;j<_COLS;j++)cout<<"["<<Sparse[i][j]<<"] ";cout<<endl;}//开始压缩稀疏矩阵Compress[0][0] = _ROWS;Compress[0][1] = _COLS;Compress[0][2] = _NOTZERO;for (i=0;i<_ROWS;i++)for (j=0;j<_COLS;j++)if (Sparse[i][j] != 0){  Compress[temp][0]=i;Compress[temp][1]=j;Compress[temp][2]=Sparse[i][j];temp++;}cout<<"[稀疏矩阵压缩后的内容]"<<endl; //输出压缩矩阵的各个元素for (i=0;i<_NOTZERO+1;i++){  for (j=0;j<3;j++)cout<<"["<<Compress[i][j]<<"] ";cout<<endl;}system("pause");
}

指针数组与二维字符串数组 ：

由以下运行结果可知，指针数组内存连续不存在内存浪费问题，char name1[4][10]数组缺点就是所有字符类型的内存空间长度都会开辟出来

#include <iostream>
#include <cstdlib>using namespace std;int main()
{const char* name[4] = { "J", "Mo", "Bec", "Bush" };	//一维指针数组 char name1[4][10] = { "J", "Mo", "Bec", "Bush" };//二维字符串数组  int i;cout << "---------- 一维指针数组的存储方式 --------------" << endl;for (i = 0; i < 4; i++){cout << "name[" << i << "] = \"" << name[i] << "\"\t";cout << "所占地址：" << (int*)name[i] << endl; //输出name[i]所占地址   }cout << "------------ 二维字符串数组的存储方式--------------" << endl;for (i = 0; i < 4; i++){cout << "name1[" << i << "] = \"" << name1[i] << "\"\t";cout << "所占地址：" << (int*)name1[i] << endl; //输出name1[i]所占地址  }cout << "------------ 数据类型长度 --------------" << endl;cout << "char = " << sizeof(char) << endl;cout << "int = " << sizeof(int) << endl;cout << "double = " << sizeof(double) << endl;cout << "float = " << sizeof(float) << endl;cout << "uint8_t = " << sizeof(uint8_t) << endl;cout << "uint16_t = " << sizeof(uint16_t) << endl;cout << "size_t = " << sizeof(size_t) << endl;system("pause");return 0;
}

win_x64数据类型                                                               win_x86                                                   

一维数组：记录5个学生分数，并且输出（一维数组的构建与访问）

int main()
{int Score[5] = { 87,66,90,65,70 };          //定义整数数组Score[5], 并设置5个成绩 int count, Total_Score = 0;for (count = 0; count < 5; count++)	     	// 执行 for 循环读取学生成绩 {cout << "第" << count + 1 << "位学生的分数:" << Score[count] << endl;Total_Score += Score[count];	       	//由数组中读取分数并计算总分}cout << "-------------------------" << endl;cout << "5位学生的总分:" << Total_Score << endl;    //输出成绩总分system("pause");return 0;
}

二维数组：记录3个销售员半年的销售成绩，并且求取每个销售员的半年总成绩与每个月3个销售员的月总销售成绩（2维数组的操作与访问）

#include <iostream>
using namespace std;int main()
{int i, j, sum, max = 0, no = 1;int sale[3][6] = { {112,76,95,120,98,68},{90,120,88,112,108,120},{108,99,126,90,76,98} };for (i = 0; i < 3; i++){sum = 0;for (j = 0; j < 6; j++)sum += sale[i][j];//加上每月的业绩金额  cout << "销售员" << i + 1 << "的前半年销售总金额为 " << sum << endl;cout << "------------------------------------" << endl;}for (i = 0; i < 6; i++){sum = 0;for (j = 0; j < 3; j++)sum += sale[j][i];// 加上每月的业绩金额  cout << "所有销售员" << i + 1 << "月的销售总金额为 " << sum << endl;cout << "=====================================" << endl;}system("pause");return 0;
}

二阶行列式（二维数组） 运算

#include <iostream>
using namespace std;
int main()
{int arr[2][2];int sum;cout<<"|a1 b1|"<<endl;cout<<"|a2 b2|"<<endl;cout<<"请输入a1:";cin>>arr[0][0];cout<<"请输入b1:";cin>>arr[0][1];cout<<"请输入a2:";cin>>arr[1][0];cout<<"请输入b2:";cin>>arr[1][1];sum = arr[0][0]*arr[1][1]-arr[0][1]*arr[1][0];//求二阶行列式的值 cout<<"|"<<arr[0][0]<<" "<<arr[0][1]<<"|"<<endl;cout<<"|"<<arr[1][0]<<" "<<arr[1][1]<<"|"<<endl;cout<<"sum="<<sum<<endl;system("pause");return 0;
}

三维数组，及其遍历（求取满足一定条件下的操作，求和，寻找最小值）

#include <iostream>
using namespace std;int main()
{int i, j, k;int sum = 0;int arr[4][3][3] = { {{1,-2,3},  {4,5,-6},   {8,9,2}},{{7,-8,9},  {10,11,12}, {-1,3,2}},{{-13,14,15},{16,17,18},{3,6,7}},{{19,20,21},{-22,23,24},{-6,9,12}} };	//声明并设置数组的元素值  for (i = 0; i < 4; i++){for (j = 0; j < 3; j++){for (k = 0; k < 3; k++){sum += arr[i][j][k];if (arr[i][j][k] < 0)arr[i][j][k] = 0;		// 元素值为负数,则归零cout << arr[i][j][k] << "\t";if (min >= arr[i][j][k])min = arr[i][j][k];	}cout << endl;}cout << endl;}cout << "---------------------------" << endl;cout << "原数组的所有元素值总和=" << sum << endl;cout << "---------------------------" << endl;system("pause");return 0;
}

结构体数组：允许用户自定义数据类型，成为派生数据类型，总而言之，就是可以将一个相关的拥有不同数据类型的数据组合在一起成为一种新的数据类型 // 可声明 变量 数组  指针 甚至其他结构成员等

#include <iostream>
int main()
{struct student{char name[10];int score[3];// 可声明 变量 数组  指针 甚至其他结构成员等};struct student group1[3] = {{"a",81,82,83},{"b",91,92,93},{"name",71,72,73}};for (int i = 0; i < 3; ++i) {std::cout << group1[i].name << " \t" <<"chinese_score = " << group1[i].score[0] << "\t" <<"math_score = " << group1[i].score[1] << "\t" <<"english_score = " << group1[i].score[2] << "\t" << std::endl;std::cout << "-------------------------------" << std::endl;}system("pause");return 0;
}

字符串数组：

#include <iostream>
#include <cstdlib>
#include <cstring>	
#include <cctype>		//包括此判断函数文件using namespace std;int main()
{char Str[6][30] = { "张继    枫桥夜泊",       // 声明并初始化二维字符串数组"================",   // 省略了每个元素之间的大括号"月落乌啼霜满天","江枫渔火对愁眠","姑苏城外寒山寺","夜半钟声到客船" };int i;for (i = 0; i < 6; i++)cout << Str[i] << endl;                   // 输出字符串数组的内容int lower = 0;char string[40];cout << "请输入字符串:";cin.getline(string, 40);			//输入的字符串有40个字符 int len = strlen(string);for (int i = 0; i <= len; i++)if (islower(string[i]) != 0)		//是小写字符则加1	lower++;cout << string << "字符串的小写字符有 " << lower << "个" << endl;system("pause");return 0;
}