数据结构anyview第五章答案

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 */
{