C语言数据结构-bo5-3.c

blake

1. /* bo5-3.c 行逻辑链接稀疏矩阵(存储结构由c5-3.h定义)的基本操作(8个) */
   
2. Status CreateSMatrix(RLSMatrix *M)
   
3. { /* 创建稀疏矩阵M */
   
4.    int i;
   
5.    Triple T;
   
6.    Status k;
   
7.    printf("请输入矩阵的行数,列数,非零元素数：");
   
8.    scanf("%d,%d,%d",&(*M).mu,&(*M).nu,&(*M).tu);
   
9.    (*M).data[0].i=0; /* 为以下比较做准备 */
   
10.    for(i=1;i<=(*M).tu;i++)
    
11.    {
    
12.      do
    
13.      {
    
14.        printf("请按行序顺序输入第%d个非零元素所在的行(1～%d),列(1～%d),元素值：",i,(*M).mu,(*M).nu);
    
15.        scanf("%d,%d,%d",&T.i,&T.j,&T.e);
    
16.        k=0;
    
17.        if(T.i<1||T.i>(*M).mu||T.j<1||T.j>(*M).nu) /* 行、列超出范围 */
    
18.          k=1;
    
19.        if(T.i<(*M).data[i-1].i||T.i==(*M).data[i-1].i&&T.j<=(*M).data[i-1].j) /* 没有按顺序输入非零元素 */
    
20.          k=1;
    
21.      }while(k); /* 当输入有误,重新输入 */
    
22.      (*M).data[i]=T;
    
23.    }
    
24.    for(i=1;i<=(*M).tu;i++) /* 计算rpos[] */
    
25.      if((*M).data[i].i>(*M).data[i-1].i)
    
26.        for(T.i=0;T.i<(*M).data[i].i-(*M).data[i-1].i;T.i++)
    
27.          (*M).rpos[(*M).data[i].i-T.i]=i;
    
28.    for(i=(*M).data[(*M).tu].i+1;i<=(*M).mu;i++) /* 给最后没有非零元素的几行赋值 */
    
29.      (*M).rpos[i]=(*M).tu+1;
    
30.    return OK;
    
31. }
    
32. 
    
33. void DestroySMatrix(RLSMatrix *M)
    
34. { /* 销毁稀疏矩阵M(使M为0行0列0个非零元素的矩阵) */
    
35.    (*M).mu=0;
    
36.    (*M).nu=0;
    
37.    (*M).tu=0;
    
38. }
    
39. 
    
40. void PrintSMatrix(RLSMatrix M)
    
41. { /* 输出稀疏矩阵M */
    
42.    int i;
    
43.    printf("%d行%d列%d个非零元素。\n",M.mu,M.nu,M.tu);
    
44.    printf("行  列  元素值\n");
    
45.    for(i=1;i<=M.tu;i++)
    
46.      printf("%2d%4d%8d\n",M.data[i].i,M.data[i].j,M.data[i].e);
    
47.    for(i=1;i<=M.mu;i++)
    
48.      printf("第%d行的第一个非零元素是本矩阵第%d个元素\n",i,M.rpos[i]);
    
49. }
    
50. 
    
51. Status CopySMatrix(RLSMatrix M,RLSMatrix *T)
    
52. { /* 由稀疏矩阵M复制得到T */
    
53.    *T=M;
    
54.    return OK;
    
55. }
    
56. 
    
57. Status AddSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix *Q)
    
58. { /* 求稀疏矩阵的和Q=M+N */
    
59.    int k,p,q;
    
60.    if(M.mu!=N.mu||M.nu!=N.nu)
    
61.      return ERROR;
    
62.    (*Q).mu=M.mu;
    
63.    (*Q).nu=M.nu;
    
64.    (*Q).tu=0;
    
65.    M.rpos[M.mu+1]=M.tu+1; /* 为方便后面的while循环临时设置 */
    
66.    N.rpos[N.mu+1]=N.tu+1;
    
67.    for(k=1;k<=M.mu;++k) /* 对于每一行，k指示行号 */
    
68.    {
    
69.      (*Q).rpos[k]=(*Q).tu+1;
    
70.      p=M.rpos[k]; /* p指示M矩阵第k行当前元素的序号 */
    
71.      q=N.rpos[k]; /* q指示N矩阵第k行当前元素的序号 */
    
72.      while(p<M.rpos[k+1]&&q<N.rpos[k+1])
    
73.      { /* M,N矩阵均有第k行元素未处理 */
    
74.        if(M.data[p].j==N.data[q].j) /* M矩阵当前元素和N矩阵当前元素的列相同 */
    
75.        {
    
76.          (*Q).data[(*Q).tu+1].e=M.data[p].e+N.data[q].e;
    
77.          if((*Q).data[(*Q).tu+1].e!=0)
    
78.          {
    
79.            ++(*Q).tu;
    
80.            (*Q).data[(*Q).tu].i=k;
    
81.            (*Q).data[(*Q).tu].j=M.data[p].j;
    
82.          }
    
83.          ++p;
    
84.          ++q;
    
85.        }
    
86.        else if(M.data[p].j<N.data[q].j)
    
87.        { /* M矩阵当前元素的列<N矩阵当前元素的列 */
    
88.          ++(*Q).tu;
    
89.          (*Q).data[(*Q).tu].e=M.data[p].e;
    
90.          (*Q).data[(*Q).tu].i=k;
    
91.          (*Q).data[(*Q).tu].j=M.data[p].j;
    
92.          ++p;
    
93.        }
    
94.        else /* M矩阵当前元素的列>N矩阵当前元素的列 */
    
95.        {
    
96.          ++(*Q).tu;
    
97.          (*Q).data[(*Q).tu].e=N.data[q].e;
    
98.          (*Q).data[(*Q).tu].i=k;
    
99.          (*Q).data[(*Q).tu].j=N.data[q].j;
    
100.          ++q;
     
101.        }
     
102.      }
     
103.      while(p<M.rpos[k+1]) /* M矩阵还有k行的元素未处理 */
     
104.      {
     
105.        ++(*Q).tu;
     
106.        (*Q).data[(*Q).tu].e=M.data[p].e;
     
107.        (*Q).data[(*Q).tu].i=k;
     
108.        (*Q).data[(*Q).tu].j=M.data[p].j;
     
109.        ++p;
     
110.      }
     
111.      while(q<N.rpos[k+1]) /* N矩阵还有k行的元素未处理 */
     
112.      {
     
113.        ++(*Q).tu;
     
114.        (*Q).data[(*Q).tu].e=N.data[q].e;
     
115.        (*Q).data[(*Q).tu].i=k;
     
116.        (*Q).data[(*Q).tu].j=N.data[q].j;
     
117.        ++q;
     
118.      }
     
119.    }
     
120.    return OK;
     
121. }
     
122. 
     
123. Status SubtSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix *Q)
     
124. { /* 求稀疏矩阵的差Q=M-N */
     
125.    int i;
     
126.    if(M.mu!=N.mu||M.nu!=N.nu)
     
127.      return ERROR;
     
128.    for(i=1;i<=N.tu;++i) /* 对于N的每一元素,其值乘以-1 */
     
129.      N.data[i].e*=-1;
     
130.    AddSMatrix(M,N,Q); /* Q=M+(-N) */
     
131.    return OK;
     
132. }
     
133. 
     
134. Status MultSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix *Q)
     
135. { /* 求稀疏矩阵乘积Q=M＊N。算法5.3 */
     
136.    int arow,brow,p,q,ccol,ctemp[MAXRC+1];
     
137.    if(M.nu!=N.mu) /* 矩阵M的列数应和矩阵N的行数相等 */
     
138.      return ERROR;
     
139.    (*Q).mu=M.mu; /* Q初始化 */
     
140.    (*Q).nu=N.nu;
     
141.    (*Q).tu=0;
     
142.    M.rpos[M.mu+1]=M.tu+1; /* 为方便后面的while循环临时设置 */
     
143.    N.rpos[N.mu+1]=N.tu+1;
     
144.    if(M.tu*N.tu!=0) /* M和N都是非零矩阵 */
     
145.    {
     
146.      for(arow=1;arow<=M.mu;++arow)
     
147.      { /* 从M的第一行开始，到最后一行，arow是M的当前行 */
     
148.        for(ccol=1;ccol<=(*Q).nu;++ccol)
     
149.          ctemp[ccol]=0; /* Q的当前行的各列元素累加器清零 */
     
150.        (*Q).rpos[arow]=(*Q).tu+1; /* Q当前行的第1个元素位于上1行最后1个元素之后 */
     
151.        for(p=M.rpos[arow];p<M.rpos[arow+1];++p)
     
152.        { /* 对M当前行中每一个非零元 */
     
153.          brow=M.data[p].j; /* 找到对应元在N中的行号(M当前元的列号) */
     
154.          for(q=N.rpos[brow];q<N.rpos[brow+1];++q)
     
155.          {
     
156.            ccol=N.data[q].j; /* 乘积元素在Q中列号 */
     
157.            ctemp[ccol]+=M.data[p].e*N.data[q].e;
     
158.          }
     
159.        } /* 求得Q中第arow行的非零元 */
     
160.        for(ccol=1;ccol<=(*Q).nu;++ccol) /* 压缩存储该行非零元 */
     
161.          if(ctemp[ccol])
     
162.          {
     
163.            if(++(*Q).tu>MAXSIZE)
     
164.              return ERROR;
     
165.            (*Q).data[(*Q).tu].i=arow;
     
166.            (*Q).data[(*Q).tu].j=ccol;
     
167.            (*Q).data[(*Q).tu].e=ctemp[ccol];
     
168.          }
     
169.      }
     
170.    }
     
171.    return OK;
     
172. }
     
173. 
     
174. Status TransposeSMatrix(RLSMatrix M,RLSMatrix *T)
     
175. { /* 求稀疏矩阵M的转置矩阵T */
     
176.    int p,q,t,col,*num;
     
177.    num=(int *)malloc((M.nu+1)*sizeof(int));
     
178.    (*T).mu=M.nu;
     
179.    (*T).nu=M.mu;
     
180.    (*T).tu=M.tu;
     
181.    if((*T).tu)
     
182.    {
     
183.      for(col=1;col<=M.nu;++col)
     
184.        num[col]=0;  /* 设初值 */
     
185.      for(t=1;t<=M.tu;++t) /* 求M中每一列非零元个数 */
     
186.        ++num[M.data[t].j];
     
187.      (*T).rpos[1]=1;
     
188.      for(col=2;col<=M.nu;++col) /* 求M中第col中第一个非零元在(*T).data中的序号 */
     
189.        (*T).rpos[col]=(*T).rpos[col-1]+num[col-1];
     
190.      for(col=1;col<=M.nu;++col)
     
191.        num[col]=(*T).rpos[col];
     
192.      for(p=1;p<=M.tu;++p)
     
193.      {
     
194.        col=M.data[p].j;
     
195.        q=num[col];
     
196.        (*T).data[q].i=M.data[p].j;
     
197.        (*T).data[q].j=M.data[p].i;
     
198.        (*T).data[q].e=M.data[p].e;
     
199.        ++num[col];
     
200.      }
     
201.    }
     
202.    free(num);
     
203.    return OK;
     
204. }

复制代码