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

blake

1. /* bo5-2.c 三元组稀疏矩阵的基本操作,包括算法5.1(9个) */
   
2. Status CreateSMatrix(TSMatrix *M)
   
3. { /* 创建稀疏矩阵M */
   
4.    int i,m,n;
   
5.    ElemType e;
   
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",&m,&n,&e);
    
16.        k=0;
    
17.        if(m<1||m>(*M).mu||n<1||n>(*M).nu) /* 行或列超出范围 */
    
18.          k=1;
    
19.        if(m<(*M).data[i-1].i||m==(*M).data[i-1].i&&n<=(*M).data[i-1].j) /* 行或列的顺序有错 */
    
20.          k=1;
    
21.      }while(k);
    
22.      (*M).data[i].i=m;
    
23.      (*M).data[i].j=n;
    
24.      (*M).data[i].e=e;
    
25.    }
    
26.    return OK;
    
27. }
    
28. 
    
29. void DestroySMatrix(TSMatrix *M)
    
30. { /* 销毁稀疏矩阵M */
    
31.    (*M).mu=0;
    
32.    (*M).nu=0;
    
33.    (*M).tu=0;
    
34. }
    
35. 
    
36. void PrintSMatrix(TSMatrix M)
    
37. { /* 输出稀疏矩阵M */
    
38.    int i;
    
39.    printf("%d行%d列%d个非零元素。\n",M.mu,M.nu,M.tu);
    
40.    printf("行  列  元素值\n");
    
41.    for(i=1;i<=M.tu;i++)
    
42.      printf("%2d%4d%8d\n",M.data[i].i,M.data[i].j,M.data[i].e);
    
43. }
    
44. 
    
45. Status CopySMatrix(TSMatrix M,TSMatrix *T)
    
46. { /* 由稀疏矩阵M复制得到T */
    
47.    (*T)=M;
    
48.    return OK;
    
49. }
    
50. 
    
51. int comp(int c1,int c2) /* 另加 */
    
52. { /* AddSMatrix函数要用到 */
    
53.    int i;
    
54.    if(c1<c2)
    
55.      i=1;
    
56.    else if(c1==c2)
    
57.      i=0;
    
58.    else
    
59.      i=-1;
    
60.    return i;
    
61. }
    
62. 
    
63. Status AddSMatrix(TSMatrix M,TSMatrix N,TSMatrix *Q)
    
64. { /* 求稀疏矩阵的和Q=M+N */
    
65.    Triple *Mp,*Me,*Np,*Ne,*Qh,*Qe;
    
66.    if(M.mu!=N.mu)
    
67.      return ERROR;
    
68.    if(M.nu!=N.nu)
    
69.      return ERROR;
    
70.    (*Q).mu=M.mu;
    
71.    (*Q).nu=M.nu;
    
72.    Mp=&M.data[1]; /* Mp的初值指向矩阵M的非零元素首地址 */
    
73.    Np=&N.data[1]; /* Np的初值指向矩阵N的非零元素首地址 */
    
74.    Me=&M.data[M.tu]; /* Me指向矩阵M的非零元素尾地址 */
    
75.    Ne=&N.data[N.tu]; /* Ne指向矩阵N的非零元素尾地址 */
    
76.    Qh=Qe=(*Q).data; /* Qh、Qe的初值指向矩阵Q的非零元素首地址的前一地址 */
    
77.    while(Mp<=Me&&Np<=Ne)
    
78.    {
    
79.      Qe++;
    
80.      switch(comp(Mp->i,Np->i))
    
81.      {
    
82.        case  1: *Qe=*Mp;
    
83.                 Mp++;
    
84.                 break;
    
85.        case  0: switch(comp(Mp->j,Np->j)) /* M、N矩阵当前非零元素的行相等,继续比较列 */
    
86.                 {
    
87.                   case  1: *Qe=*Mp;
    
88.                            Mp++;
    
89.                            break;
    
90.                   case  0: *Qe=*Mp;
    
91.                            Qe->e+=Np->e;
    
92.                            if(!Qe->e) /* 元素值为0，不存入压缩矩阵 */
    
93.                              Qe--;
    
94.                            Mp++;
    
95.                            Np++;
    
96.                            break;
    
97.                   case -1: *Qe=*Np;
    
98.                            Np++;
    
99.                 }
    
100.                 break;
     
101.        case -1: *Qe=*Np;
     
102.                 Np++;
     
103.      }
     
104.    }
     
105.    if(Mp>Me) /* 矩阵M的元素全部处理完毕 */
     
106.      while(Np<=Ne)
     
107.      {
     
108.        Qe++;
     
109.        *Qe=*Np;
     
110.        Np++;
     
111.      }
     
112.    if(Np>Ne) /* 矩阵N的元素全部处理完毕 */
     
113.      while(Mp<=Me)
     
114.      {
     
115.        Qe++;
     
116.        *Qe=*Mp;
     
117.        Mp++;
     
118.      }
     
119.    (*Q).tu=Qe-Qh; /* 矩阵Q的非零元素个数 */
     
120.    return OK;
     
121. }
     
122. 
     
123. Status SubtSMatrix(TSMatrix M,TSMatrix N,TSMatrix *Q)
     
124. { /* 求稀疏矩阵的差Q=M-N */
     
125.    int i;
     
126.    for(i=1;i<=N.tu;i++)
     
127.      N.data[i].e*=-1;
     
128.    AddSMatrix(M,N,Q);
     
129.    return OK;
     
130. }
     
131. 
     
132. Status MultSMatrix(TSMatrix M,TSMatrix N,TSMatrix *Q)
     
133. { /* 求稀疏矩阵的乘积Q=M*N */
     
134.    int i,j,h=M.mu,l=N.nu,Qn=0;
     
135.    /* h,l分别为矩阵Q的行、列值,Qn为矩阵Q的非零元素个数，初值为0 */
     
136.    ElemType *Qe;
     
137.    if(M.nu!=N.mu)
     
138.      return ERROR;
     
139.    (*Q).mu=M.mu;
     
140.    (*Q).nu=N.nu;
     
141.    Qe=(ElemType *)malloc(h*l*sizeof(ElemType)); /* Qe为矩阵Q的临时数组 */
     
142.    /* 矩阵Q的第i行j列的元素值存于*(Qe+(i-1)*l+j-1)中，初值为0 */
     
143.    for(i=0;i<h*l;i++)
     
144.      *(Qe+i)=0; /* 赋初值0 */
     
145.    for(i=1;i<=M.tu;i++) /* 矩阵元素相乘，结果累加到Qe */
     
146.      for(j=1;j<=N.tu;j++)
     
147.        if(M.data[i].j==N.data[j].i)
     
148.          *(Qe+(M.data[i].i-1)*l+N.data[j].j-1)+=M.data[i].e*N.data[j].e;
     
149.    for(i=1;i<=M.mu;i++)
     
150.      for(j=1;j<=N.nu;j++)
     
151.        if(*(Qe+(i-1)*l+j-1)!=0)
     
152.        {
     
153.          Qn++;
     
154.          (*Q).data[Qn].e=*(Qe+(i-1)*l+j-1);
     
155.          (*Q).data[Qn].i=i;
     
156.          (*Q).data[Qn].j=j;
     
157.        }
     
158.    free(Qe);
     
159.    (*Q).tu=Qn;
     
160.    return OK;
     
161. }
     
162. 
     
163. Status TransposeSMatrix(TSMatrix M,TSMatrix *T)
     
164. { /* 求稀疏矩阵M的转置矩阵T。算法5.1 */
     
165.    int p,q,col;
     
166.    (*T).mu=M.nu;
     
167.    (*T).nu=M.mu;
     
168.    (*T).tu=M.tu;
     
169.    if((*T).tu)
     
170.    {
     
171.      q=1;
     
172.      for(col=1;col<=M.nu;++col)
     
173.        for(p=1;p<=M.tu;++p)
     
174.          if(M.data[p].j==col)
     
175.          {
     
176.            (*T).data[q].i=M.data[p].j;
     
177.            (*T).data[q].j=M.data[p].i;
     
178.            (*T).data[q].e=M.data[p].e;
     
179.            ++q;
     
180.          }
     
181.    }
     
182.    return OK;
     
183. }

复制代码