C++线性结构四道题

Question

第一题：将矩阵A按“列优先”顺序存储，设每个元素占C个存储单元，已知a0,0的存储地址为D，写出元素ai，j（0=<i<=m-1,0=<j<=n-1）的计算公式。
第二题：写出稀疏矩阵X的三元组表。
X=15 0 0 22 0 -12
0 11 5 0 0 0
0 0 0 -7 0 0
0 0 0 0 0 0
87 0 0 0 0 0
0 0 28 0 0 0
第三题：编写程序求出顺序表中最大元素以及其在表中位置。
第四题：编写一个程序，读入一个英文字母串，将其中的大写字母插入第1队，小写字母插入第2队，然后分别输出这两队中的元素。

Answer 1

第一题：将矩阵A按“列优先”顺序存储，设每个元素占C个存储单元，已知a0,0的存储地址为D，
写出元素ai，j（0=<i<=m-1,0=<j<=n-1）的计算公式。

答：
由题目知：矩阵有 m 行，n 列，
而且矩阵是按“列优先”顺序存储的，也就是先存满一列，在存下一列。

元素 a(i,j) 表示第 j 列第 i 行的元素。

对于元素a(i,j) 所在的第 j 列， 前面还有 i 个元素（编号0,1,,...i-1），

对于元素a(i,j)所在列（第 j 列）之前的列（编号0,1,...,j-1），
每列都已经用 m 个元素填满，因此一共有：j*m 个元素。

所以，元素a(i,j)前面一共有 i+j*m 个元素。
由题目知道，每个元素占 C 个存储单元，因此 a(i,j)之前的元素一共用了：
(i + j*m ) * C 个存储单元。

a(0,0)的存储地址为D，因此轮到 a(i,j)时，它的存储地址为：D + (i + j*m)*C，
也就是从 a(0,0) 后面数个 (i + j*m)*C 存储单元后，就是 a(i,j) 的存储地址了。

###########################分割线###########################

第二题：写出稀疏矩阵X的三元组表。
X=
0 2 3 3 5 6
------------------------
0| 15 0 0 22 0 -12
1| 0 11 5 0 0 0
2| 0 0 0 -7 0 0
3| 0 0 0 0 0 0
4| 87 0 0 0 0 0
5| 0 0 28 0 0 0

所谓稀疏矩阵的三元组，
也就是根据稀疏矩阵中又很多元素的值相同（比如元素的值为0）的特点，
不存储这些元素的信息，而只存储其他不同元素的信息。

存储的信息包括：【元素坐标】，【元素的值】。
对于二维的矩阵，【元素的坐标】可以用【横坐标】，【纵坐标】确定。
【元素的值】的话，对于简单矩阵的，一般就是一个【数字】。

横坐标，纵坐标，数字，就是三元组，用[x,y,value]表示。
下面是给定的矩阵 X 的三元组：
[0,0,15],
[0,3,22],
[0,6,-12],
[1,1,11],
[1,2,5],
[2,3,-7],
[4,1,87],
[5,2,28]

###########################分割线###########################

第三题：编写程序求出顺序表中最大元素以及其在表中位置。

#include <iostream>
using namespace std;

/* 控制当同时有多个数字是最大值的时候，是否都输出
IS_MUTI_MAX_VALUE = 0 ：只输出第一个最大值
IS_MUTI_MAX_VALUE = 1 ：按顺序输出所有最大值

*/
const int IS_MUTI_MAX_VALUE = 0;

int main(int argc, char *argv[])
{
int data[1000],data_amount;
int i,j,max_value_index;

cout<<"输入数据个数：";
cin>>data_amount;

for(i=0,max_value_index=0;i<data_amount;i++)
{
cin>>data[i];
// 确定第一个最大值的位置
if(data[max_value_index]<data[i])
{
max_value_index = i;
}
}
if(IS_MUTI_MAX_VALUE)
{
for(i=0,j=0;i<data_amount;i++)
{
if(data[i]==data[max_value_index])
{
cout << "第"<<(++j)<<"个最大值的位置："<<i<<"，值为："<<data[i]<<endl;
}
}
}
else
{
cout<<"最大值的位置："<<max_value_index<<"，值为："<<max_value_index<<endl;
}

return 0;
}
/*
测试数据：
8
9 -1 5 14 -5 14 8 10

输出结果(单个最大值)：
最大值的位置：3，值为：14

输出结果(多个最大值)：
第 1个最大值的位置：3，值为：14
第 2个最大值的位置：5，值为：14

*/

###########################分割线###########################

第四题：编写一个程序，读入一个英文字母串，
将其中的大写字母插入第1队，小写字母插入第2队，然后分别输出这两队中的元素。

#include <iostream>
#include <stack>
// 字符串最大长度
const int MAX_STRING_LENGTH = 1000;

using namespace std;
int main(int argc, char *argv[])
{
// 大写字母队列
char queue_capital_letter[MAX_STRING_LENGTH];
int queue_capital_letter_top=-1;
// 小写字母队列
char queue_lower_letter[MAX_STRING_LENGTH];
int queue_lower_letter_top=-1;
// 英文字符串
char str[MAX_STRING_LENGTH];

cout<<"输入英文字符串：";
// 输入一行（可以有空格），按回车结束
cin.getline(str,MAX_STRING_LENGTH,'\n') ;
for(int i=0;i<str[i]!='\0';i++)
{
// 大写字母
if(str[i]>='A' && str[i]<='Z')
{
// 入队
queue_capital_letter[++queue_capital_letter_top] = str[i];
}
// 小写字母
else if(str[i]>='a' && str[i]<='z')
{
// 入队
queue_lower_letter[++queue_lower_letter_top] = str[i];
}
}

// 输出大写字母队
cout<<"大写字母队：";
for(int i=0;i<=queue_capital_letter_top;i++)
{
cout<<queue_capital_letter[i]<<" ";
}
cout<<endl;

// 输出小写字母队
cout<<"小写字母队：";
for(int i=0;i<=queue_lower_letter_top;i++)
{
cout<<queue_lower_letter[i]<<" ";
}
cout<<endl;

return 0;
}
/*
测试数据；
Hello,I am Angelfish.Who Are you ?

输出结果：
大写字母队：H I A W A
小写字母队：e l l o a m n g e l f i s h h o r e y o u
*/