《数据结构-用C语言形貌第三版》课后答案 第五章

撰写匆忙，如有错误，尽情指正

  1．选择题

(1）设有一个二维数组 A [ m ][ n ]，假设 A [0][0］存放地址为644, A [2][2］存放地址为676，每个元素占一个空间，则 A [3][3］的存放地址为（)。
 A .688
 B .678
 C .692
 D .696
   答：
  A[2][2]的地址等于 (2*n+2)*1 +644 = 676 则n = 15
  则A[3][3]的地址等于 （3*n+3)*1+644 = 48+644 = 692
  (2）设有一个10阶的下三角矩阵 A （包括对角线），按照从上到下、从左到右的次序存储到55个一连的存储单元中，每个数组元素占1个字节的存储空间，则 A [5][4］的地址与 A [0][0］的地址之差为（)
 A .10
 B .19
 C .28
 D .55
   答：
  设A[0][0]的地址为 0
  则 到A[5][4]总共有1+2+3+4+5+5 = 20个元素，则 A[5][4]的地址为19+0 = 19
  即地址之差为19
  2．设有一个上三角矩阵

，将其上三角中的元素逐列压缩存储到一个大小为 n ( n +1)/2的一维数组 C 中（下标从1开始），请给出盘算上三角矩阵中任意元素 a ( i < j ）在一维数组 C 中位置的公式。

   答:
  盘算上三角矩阵中前（j-1）列非零元素个数 

  

为第j列第i个元素，则

为第

个元素
  即C[

] = 

  注：此类题即求元素按照要求压缩存储时第k个元素和i,j的关系，用i，j表现k，找出规律即可
  3．设有三对角矩阵 A 将其三条对角线上的元素逐行压缩存储到一个大小为3n-2的一维数组 B 中（下标从1开始），使得 B [ k ]= a ，求：
(1）用 i , j 表现 k 的下标变动公式；
(2）用 k 表现 i , j 的下标变动公式。

   答：
  （1）此问为三对角矩阵的逐行压缩，同样是盘算第k个元素的i,j表现
  分类讨论：
  i = 1时，k = j
  i > 1时，k = 前i-1行元素个数+ 

为第i行第几个元素
  即k = 

 =

  公式中：
  

• 
  为前i-1行元素个数
  
• 
  为第i行第几个元素，这个应该也很好理解，第i行三个非零元素中，第二个元素下标i和j相称，第一个元素和第三个元素i,j相差1
  

  则

  （2）此问已知k求i、j，反过来求解即可
  当k<=2时
  i = 1, j = k;
  当k>2时
  可以知道，k有三种取值

、

、

，显然k和i之间有k除以3后取整的关系
  i = 

  j = 

  综上：

  4．一 n 阶对称矩阵 A 以行序为主序压缩存储在一维数组 B 中，存储其下三角元素（包括对角线），盘算 A [j]与 B[k] 之间的对应关系。

   答：
  关键字：n阶对称矩阵，行序存储，存储下三角
  则i<=j时,按照下三角矩阵压缩存储下标盘算方式
  k = 

  i>j时，交换i、j即可
  则A[j]与k的对照关系
  k = 

  5．在算法5.3（稀疏矩阵一次定位快速转置算法）中，将盘算 position [ col ］的方法稍加改动，使算法只占用一个辅助向量空间

   答：
  在稀疏矩阵的一次定位快速转置算法中，有两个辅助向量空间，分别为num[],position[]
  其中num[]记载每列非零元素个数，用于position[col]的盘算，position[col]代表col列第一个元素在三元组表中的位置，具体算法可以查看讲义
  现在改动position[col]的盘算方法，即利用position[]自己盘算最终的position[]

1. //原算法
2. int num[MAXSIZE],position[MAXSIZE];
4. for(t=1,t<=A.len;t++){
5.     //遍历三元组表计算每列非零元素个数
6.     num[A.data[t].col]++;
7. }
8. position[1] = 1;
9. for(col=2;col<=A.n;col++){
10.     position[col] = position[col-1] + num[col-1];   
11.     //即col列首个元素位置等于col-1列首个元素位置加col-1列非零元素个数
12. }
14. //算法改进
15. //上述position[0]未使用，因此可以加以利用
16. //同样，计算每列非零元素个数
17. int position[MAXSIZE];
18. for(t=1,t<=A.len;t++){
19.     //遍历三元组表计算每列非零元素个数
20.     position[A.data[t].col]++;
21. }
23. position[0] = position[1];
24. position[1] = 1;
25. for(col=2;col<=A.n;col++){
26.     int temp = position[col];     //记录col列元素非零个数
27.     position[col] = position[col-1] + position[0];   
28.     position[0] = temp;
29.     //即col列首个元素位置等于col-1列首个元素位置加col-1列非零元素个数
30. }

复制代码

6．编写算法，实现三元组表表现的两个稀疏矩阵的加法。

   答：
  在三元组表表现中，稀疏矩阵元素按照列优先依次排列，此时遍历两个稀疏矩阵分别判定是否为同行同列然后进行相应利用即可
  若为同行同列，则元素相加，若不为同行同列，则添加非零元素，此时新开辟结果空间（偶然间浪费空间的做法能很好的解决问题，不一定非要进行原地利用）
  具体见代码

1. //三元组表的定义
2. #define MAXSIZE 1000
3. typedef struct {
4.     int i,j;
5.     ElementType elem;
6. }Triple;
8. typedef struct{
9.     Triple data[MAXSIZE];
10.     int m,n,len;
11. }TSMatrix;
13. TSMatrix matrixAdd(TSMatrix A,TSMAtrix B){
14.     TSMatrix C;
15.    
16.     //使用双指针遍历两个矩阵
17.     int i=1, j=1;
18.     int k = 1;
19.     while(i<=A.len && j<=B.len){
20.         //分三种情况，情况分类的依据：i指向的元素在矩阵的位置位于j指向元素的相对位置
21.         //情况1： i指向元素在j指向元素的前面，则将i指向元素复制给结果三元组表 i++
22.         //情况2： i指向元素和j指向元素位置一样，则将两元素相加后复制给结果三元组表 i++, j++
23.         //情况3： i指向元素在j指向元素的后面，则将j指向元素复制给结果三元组表 j++
24.         if[A.date[i].i<B.date[j].i]{
25.             //情况1
26.             C.date[k] = A.date[i];
27.             k++,i++;
28.         }else if(A[i].i = B[j].i){
29.             if(A.date[i].j < B.date[j].j){
30.                 //情况1
31.                 C.date[k] = A.date[i];
32.                 k++,i++;
33.             }
34.             if(A.date[i].j = B.date[j].j){
35.                 //情况2
36.                 C.date[k] = A.date[i];
37.                 C.date[k].elem += B.date[j].elem;
38.                 k++,i++,j++;
39.             }
40.             if(A.date[i].j > B.date[j].j){
41.                 //情况3
42.                 C.date[k] = A.date[j];
43.                 k++,j++;
44.             }
45.         }else{
46.             //情况3
47.             C.date[k] = B.date[j];
48.             k++,j++;
49.         }
50.     }
51.     while(i<=A.len){
52.         C.date[k] = A.date[i];
53.         k++,i++;
54.     }
55.     while(j<=B.len){
56.         C.date[k] = B.date[j];
57.         k++,j++;
58.     }
59.     C.m = A.m;
60.     C.n = A.n;
61.     C.len = k-1;
62. }

复制代码

7．编写算法，实现一个在十字链表中删除非零元素

。

   答：
  望见十字链就头疼