学步园

此操作的算法我就不多说了，代码里面叙述得很清楚了。下面就是此程序：

# include <stdio.h><br /> # include <stdlib.h><br /> # define NULL 0<br /> # define OK 1<br /> # define ERROR 0<br /> # define MAXSIZE 100 /* 矩阵中非零元的最大值 */<br /> # define MAXRC 10 /* 矩阵的最大行值 */</p> <p>typedef int status ;</p> <p> /********** 稀疏矩阵的行逻辑链接的顺序表存储表示 **********/</p> <p>typedef struct /* 非零元的三元组 */<br /> {<br /> int i, j ; /* 非零元的行下标和列下标 */<br /> int e ;<br /> }Triple; </p> <p>typedef struct /* 稀疏矩阵的行逻辑链接的顺序表 */<br /> {<br /> Triple data[MAXSIZE+1]; /* 非零三元组表，data[0]未用，以下定义的数组都是从1开始 */<br /> int rpos[MAXRC+1]; /* 代表各行第一个非零元的序号表，其值为data的下标 */<br /> int mu,nu,tu; /* 矩阵的行数、列数、非零元的个数 */<br /> }RLSMatrix; /* R:row L:logic S:sequence */</p> <p> /********* 基本操作的函数原型的声明 *********/</p> <p>status CreateSMatrix_RL(RLSMatrix * matrix);<br /> // 创建一个稀疏矩阵；<br /> // 输入行数、列数，支持乱序输入三元组，并计数；<br /> // 以行为主序进行重新排列，并记录每行起始位置于matrix->rpos[row]；<br /> // 若非零元超过 MAXSIZE或行数超过MAXRC，则返回ERROR，否则OK；</p> <p>void PrintSMatrix_RL(RLSMatrix * matrix);<br /> // 输入矩阵，打印出矩阵的行数、列数、非零元个数，以及整个矩阵；</p> <p>status MultSMatrix_RL(RLSMatrix * M,RLSMatrix * N,RLSMatrix * Q);<br /> // 输入两个稀疏矩阵M和N，并初始化Q，然后计算M*N的值赋给Q；<br /> // 如果M->mu!=N->nu或列数大于MAXRC或者计算出的非零元个数大于MAXSIZE，都返回ERROR,否则OK；<br /> // 计算过程如下：<br /> // 1. 由于矩阵M和Q的行数相等并且C语言以行为主序进行存储，所以以M进行逐行的扫描。<br /> // 2. 使Q的此行逻辑表的序号等于其非零元个数Q.tu+1，以表示其行的首个元素的序号。<br /> // 3. 从行中找到M的非零元，并以它的列值为N的行号，对N进行行的扫描，若存在，则依次计算它们，并把其值累加到一个以N中这个对应非零元的列值为序号的临时数组ctemp[ccol]中。<br /> // 4. 在M的当前行完成扫描后，将ctemp[ccol]不为0的值，压入到Q矩阵的三元组，累加++Q.tu，若Q.tu大于了MAXSIZE，这返回ERROR。 </p> <p>/************ main( ) 函数对矩阵乘法的实现 ************/</p> <p>void main()<br /> {<br /> RLSMatrix * M,* N,* Q;<br /> if(!(M=(RLSMatrix *)malloc(sizeof(RLSMatrix))))<br /> exit(ERROR);<br /> if(!(N=(RLSMatrix *)malloc(sizeof(RLSMatrix))))<br /> exit(ERROR);<br /> if(!(Q=(RLSMatrix *)malloc(sizeof(RLSMatrix))))<br /> exit(ERROR);<br /> if(CreateSMatrix_RL(M)&&CreateSMatrix_RL(N))<br /> {<br /> printf("/nput out M:/n");<br /> PrintSMatrix_RL(M); /* 打印出M */<br /> printf("/nput out N:/n");<br /> PrintSMatrix_RL(N); /* 打印出N */<br /> if(MultSMatrix_RL(M,N,Q))<br /> {<br /> printf("/n/n/n M * N :/n");<br /> PrintSMatrix_RL(Q); /* 计算结果 */<br /> }<br /> else<br /> printf("M.mu and N.nu are not mathing/n");<br /> }<br /> else<br /> printf("input error./n");<br /> }</p> <p>/*********** 基本操作的算法描述 ****************/</p> <p>status CreateSMatrix_RL(RLSMatrix * matrix)<br /> // 创建一个稀疏矩阵；<br /> // 输入行数、列数，支持乱序输入三元组，并计数；<br /> {<br /> int num=0,p,q,min,temp; // 中间变量；<br /> int row;<br /> printf("input the total row and col:/n");<br /> scanf("%d%d",&matrix->mu,&matrix->nu); // 输入行数、列数；<br /> if(matrix->mu>MAXRC)<br /> return ERROR;<br /> printf("row col val/n");<br /> scanf("%d%d%d",&matrix->data[num+1].i,&matrix->data[num+1].j,&matrix->data[num+1].e);<br /> while(matrix->data[num+1].i) // 乱序输入三元组；<br /> {<br /> if(++num>MAXSIZE)<br /> return ERROR;<br /> scanf("%d%d%d",&matrix->data[num+1].i,&matrix->data[num+1].j,&matrix->data[num+1].e);<br /> }<br /> matrix->tu=num; // num的值即为此矩阵的非零元个数；<br /> for(p=1;p<=matrix->tu-1;++p) // 按行为主序依次重新排列非零元<br /> {<br /> min=p; // 使较小的行数、列数的元的序号min为当前值p；<br /> for(q=p+1;q<=matrix->tu;++q) // 开始依次比较；<br /> {<br /> if(matrix->data[min].i>matrix->data[q].i||(matrix->data[min].i==matrix->data[q].i&&matrix->data[min].j>matrix->data[q].j))<br /> min=q; // 在乱序的三元表中，始终保证min是较小的行列数的序号；<br /> }<br /> temp=matrix->data[min].i; // 交换行值；<br /> matrix->data[min].i=matrix->data[p].i;<br /> matrix->data[p].i=temp;<br /> temp=matrix->data[min].j; // 交换列值；<br /> matrix->data[min].j=matrix->data[p].j;<br /> matrix->data[p].j=temp;<br /> temp=matrix->data[min].e; // 交换元素值；<br /> matrix->data[min].e=matrix->data[p].e;<br /> matrix->data[p].e=temp;<br /> }<br /> for(row=1,num=0;row<=matrix->mu;++row) // 记录matrix->rpos[row];<br /> {<br /> matrix->rpos[row]=num+1;<br /> while(matrix->data[num+1].i==row)<br /> ++num;<br /> }<br /> return OK;<br /> }<br /> // 时间复杂度分析：<br /> // 1. 输入非零元：O(tu); 2. 重新排列（最坏情况下）;O(tu*(tu-1)) ; 3. 记录行逻辑表：O(mu)<br /> void PrintSMatrix_RL(RLSMatrix * matrix)<br /> // 输入矩阵，打印出矩阵的行数、列数、非零元个数，以及整个矩阵；<br /> {<br /> int row,col;<br /> int num=0;<br /> printf("/nrow:%d col:%d number:%d/n",matrix->mu,matrix->nu,matrix->tu);<br /> for(row=1;row<=matrix->mu;++row)<br /> {<br /> for(col=1;col<=matrix->nu;++col)<br /> {<br /> if(num+1<=matrix->tu&&matrix->data[num+1].i==row&&matrix->data[num+1].j==col)<br /> {<br /> ++num;<br /> printf("%4d",matrix->data[num].e); /* 当扫描到非零元的行列值与之相等时，输出其值 */<br /> }<br /> else<br /> printf("%4d",NULL); /* 没有非零元的地方补0 */<br /> }<br /> printf("/n"); /* 每行输入完毕后，换行 */<br /> }<br /> }</p> <p>// 时间复杂度：O(mu*nu).</p> <p>status MultSMatrix_RL(RLSMatrix * M,RLSMatrix * N,RLSMatrix * Q)<br /> // 输入两个稀疏矩阵M和N，并初始化Q，然后计算M*N的值赋给Q<br /> {<br /> int arow,brow,ccol;<br /> int * ctemp; /* 以N的列值为序号的临时数组 */<br /> int tp,p,tq,q; /* 中间变量 */<br /> if(M->nu!=N->mu)<br /> return ERROR;<br /> Q->mu=M->mu; /* 初始化Q */<br /> Q->nu=N->nu;<br /> Q->tu=0;<br /> if(!(ctemp=(int *)malloc((N->nu+1)*sizeof(int)))) /* 动态建立累加器 */<br /> exit(ERROR);<br /> if(M->tu*N->tu!=0) /* Q是非零矩阵 */<br /> {<br /> for(arow=1;arow<=M->mu;++arow) /* 逐行扫描 */<br /> {<br /> for(ccol=1;ccol<=N->nu;++ccol)<br /> ctemp[ccol]=0; /* 初始化累加器 */<br /> Q->rpos[arow]=Q->tu+1;<br /> if(arow<M->mu)<br /> tp=M->rpos[arow+1]; /* tp是M下一行的序号 */<br /> else<br /> tp=M->tu+1;<br /> for(p=M->rpos[arow];p<tp;++p) /* 从M的当前行找到元素 */<br /> {<br /> brow=M->data[p].j; /* 对应元在N中的行号 */<br /> if(brow<N->mu)<br /> tq=N->rpos[brow+1]; /* tq是N下一行的行号 */<br /> else<br /> tq=N->tu+1;<br /> for(q=N->rpos[brow];q<tq;++q) /* 以M的对应元的列号为N的行号进行扫描 */<br /> {<br /> ccol=N->data[q].j; /* 提取对应元的列号 */<br /> ctemp[ccol]+=M->data[p].e*N->data[q].e;<br /> /* 两个对应元的值相乘并累加到以列号为序号的累加器中 */<br /> }<br /> }<br /> for(ccol=1;ccol<=Q->nu;++ccol) /* 将此行非零元压缩入Q中 */<br /> {<br /> if(ctemp[ccol])<br /> {<br /> if(++Q->tu>MAXSIZE)<br /> return ERROR;<br /> Q->data[Q->tu].i=arow;<br /> Q->data[Q->tu].j=ccol;<br /> Q->data[Q->tu].e=ctemp[ccol];<br /> }<br /> }<br /> }<br /> }<br /> return OK;<br /> }<br /> // 时间复杂度：O(M->mu*(N->nu+M->nu*N->nu+N->nu));

status CreateSMatrix_RL(RLSMatrix   
* matrix)

这个函数我用
2

种算法进行了编写：第一种不支持乱序输入，而且输入很麻烦。第二种则使得输入很方便、清楚。

所以，我想总结一下函数在声明时，对函数进行说明的流程：

1.  




确定功能，详细描述这个功能，即要达到哪些效果。好的功能能够使程序更加人性化。

2.  




设计算法。

3.  




尽量给出此函数的完整定义。

我觉得确定功能应该是首要工作，因为它是整个思路的方向，所以我放在了第一位，必须认真地对待。