5.18⑤ 试设计一个算法,将数组A中的元素
A[0..n-1]循环右移k位,并要求只用一个元素
大小的附加存储,元素移动或交换次数为O(n)。
要求实现以下函数:
void Rotate(Array1D &a, int n, int k);
一维数组类型Array1D的定义:
typedef ElemType Array1D[MAXLEN];
void Rotate(Array1D &a, int n, int k)
/* a[n] contains the elements, */
/* rotate them right circlely by k sits */
{
char temp;
int i, j, m, p;
for(i = 1; i <= k && i <= n; i++){ //求n和k的最大公约数p
if(n % i == 0 && k % i == 0)
p = i;
}
for(i = 0; i < p && p != n; i++){
j = i;
m = (j + k) % n;
temp = a[i];
while(m!=i){
a[i] = temp;
temp = a[m];
a[m] = a[i];
j = m;
m = (j + k) % n;
}// 循环右移一步
a[i] = temp;
}
}
5.21④ 假设稀疏矩阵A和B均以三元组表作为存储结构。
试写出矩阵相加的算法,另设三元组表C存放结果矩阵。
要求实现以下函数:
Status AddTSM(TSMatrix A,TSMatrix B,TSMatrix &C);
/* 三元组表示的稀疏矩阵加法: C=A+B */
稀疏矩阵的三元组顺序表类型TSMatrix的定义:
#define MAXSIZE 20 // 非零元个数的最大值
typedef struct {
int i,j; // 行下标,列下标
ElemType e; // 非零元素值
}Triple;
typedef struct {
Triple data[MAXSIZE+1]; // 非零元三元组表,data[0]未用
int mu,nu,tu; // 矩阵的行数、列数和非零元个数
}TSMatrix;
Status AddTSM(TSMatrix A,TSMatrix B,TSMatrix &C)
/* 三元组表示的稀疏矩阵加法: C=A+B */
{