南航数据结构上机作业4---碰撞小球问题，稀疏矩阵快速转置，稀疏矩阵求和

一、调试成功程序及说明 1、碰撞的小球 题目： 1、 数轴上有一条长度为L（L为偶数)的线段，左端点在原点，右端点在坐标L处。有n个不计体积的小球在线段上，开始时所有的小球都处在偶数坐标上，速度方向向右，速度大小为1单位长度每秒; 2、 当小球到达线段的端点（左端点或右端点）的时候，会立即向相反的方向移动，速度大小仍然为原来大小; 3、 当两个小球撞到一起的时候，两个小球会分别向与自己原来移动的方向相反的方向，以原来的速度大小继续移动。 4、 现在，告诉你线段的长度L，小球数量n，以及n个小球的初始位置，请你计算t秒之后，各个小球的位置。

算法思想： 对于本体，由于涉及到多次的比较，判断，所有我使用的数据结构为顺序表，顺序表在访问第i个元素上面比链表的时间复杂度要低。我用一个顺序表来存储他们的位置，用另一个顺序表来存储他们的速度，再用一个顺序表来进行排序。这样我们就在判断速度方向是否改变的时候，只需要判断自己和左边（或者右边，只用选一边进行判断）的位置进行判断，当然端点要额外判断。这样时间复杂度为O(n2+nt)，其中n2来自于对数据的排序（对于选择排序和冒泡排序时间复杂度一样），nt来自与判断位置是否重合（相遇）由于我们开了三个大小为的顺序表，所以我们的空间复杂度为：O(n)。 运行结果：

结果分析： 从结果上来看，答案是正确的，而且有输入的提示信息，方便使用者输入相应的数值。 附源代码：

#include "stdlib.h" #include "math.h" #include "stdio.h" #define N 100 main() { int x[N],v[N],pos[N]; //存储小球的位置信息和速度信息 int i,j,temp; //辅助变量，i:用来进行对小球的位置信息和速度信息的初始化，，，，j,k:后面运动过程中进行改变球的位置信息和速度信息 int n,L,t; //小球的个数n，线段的长度L，以及你需要计算t秒之后小球的位置 printf("请输入小球的个数n，线段的长度L，以及你需要计算t秒之后小球的位置: "); //提示输入信息 scanf("%d %d %d",&n,&L,&t); while(L%2) //判断线段的长度L是否是偶数 { printf("线段的长度L输入错误，L必须是偶数!\n"); printf("请输入线段的长度L: "); scanf("%d",&L); } for(i = 1;i<=n;i++) //初始化小球的位置信息和速度信息 { printf("请输入第%d个小球的初始坐标: ",i); scanf("%d",&x[i]); v[i] = 1; //初始速度全为1 while(x[i]%2) //判断第i+1个小球的初始坐标是否是偶数 { printf("第%d个小球的初始坐标输入错误，L必须是偶数!\n",i); printf("请输入第%d个小球的初始坐标: ",i); scanf("%d",&x[i]); } pos[i] = i; } x[0] = 0;x[n+1] = L;v[0] = 0;v[n+1] = 0;pos[0] = 0;pos[n+1] = n+1; for(i = 1;i<=n;i++) { for(j = i+1;j<=n;j++) { if(x[pos[i]] > x[pos[j]]) { temp = pos[i]; pos[i] = pos[j]; pos[j]= temp; } } } for(j=1;j<=t;j++)//遍历运功过程每秒时间 { for(i = 1;i<=n;i++) x[i] = x[i]+v[i]; for(i = 1;i<=n;i++)//遍历每个小球,判断小球是否运动反向 { if(x[pos[i]] == x[pos[i-1]]) { v[pos[i]] = -v[pos[i]]; v[pos[i-1]] = -v[pos[i-1]]; } if(i == n) if(x[pos[i]] == x[pos[i+1]]) v[pos[i]] = -v[pos[i]]; } } printf("%d秒后：\n",t); for(i = 1;i<=n;i++) printf("第%d个小球的位置为：%d\n",i,x[i]); }

2、 题目：稀疏矩阵的快速转置B=A’ 算法思想： 按照A. data中三元组的次序进行转置，并将转置后的三元组置人B中恰当的位置。如果能预先确定矩阵B中每-列(即A中每一行)的第一 个非零元在B. data中应有的位置，那么在对A. data中的三元组依次作转置时，便可直接放到B. data中怡当的位置上去。为了确定这些位置.在转置前,应先求得A的每一列中非零元的个数，进而求得每一列的第一个非零元在B. data中应有的位置。在此,需要附设num和cpot两个向量。num[col]表示矩阵 A中第col列中非零元的个数,pot[co]指示A中第col列的第一个非零元在b. data中的恰当位置。显然有: cpot[1]=1;cpot[col]=cpot[col-1]+num[col-1] 这里我们相当于空间换时间了，我们多用了俩个辅助向量，空间复杂度为：O(n)，但是时间复杂度降为：O(nu+tu) 运行结果：

结果分析： 运行结果正确，可以快速算出矩阵的转置； 附源程序:

MA reversema(MA *A)//快速转置 { MA B; //矩阵B为矩阵A转置以后的矩阵; int i,col,p; //辅助变量; int num[A->nu+1],cpot[A->nu+1]; //num记录每一列中非0元素的个数，cpot记录该列第一个元素的存储位置 B.mu = A->nu; //初始化矩阵B B.nu = A->mu; //初始化矩阵B B.tu = A->tu; //初始化矩阵B if(A->tu) //如果矩阵A为零矩阵，那么就直接返回B就行了 { for(i = 1;i<=A->nu;i++) //初始化num num[i] = 0; for(i = 1;i<=A->tu;i++) //得到num num[A->T[i].j]++; cpot[1] = 1; //初始化cpot for(i = 2;i<=A->nu;i++) //得到cpot cpot[i] = cpot[i-1] + num[i-1]; for(i = 1;i<=A->tu;i++) //将A中的三元组赋值到对应的B中的三元组中 { col = A->T[i].j; p = cpot[col]; B.T[p].i = A->T[i].j; B.T[p].j = A->T[i].i; B.T[p].data = A->T[i].data; cpot[col]++; } } return B; }

3.题目：稀疏矩阵加法 算法思想： 开一个新的矩阵C，用来存放矩阵A+矩阵B的值，当A中某非0元素和矩阵B中某非0元素的行相等时，我们就返回他们的和给C，否则判断行或者列的大小关系，判断应该把谁先给矩阵C，当然要注意，跳出while循环时，可能有一个还有剩余，要将剩下的赋值过去。 运行结果：

结果分析： 结果运行正确，可以正确算出矩阵A和矩阵B的和 附源程序:

MA addition(MA *A,MA *B) { MA C; //将两个稀疏矩阵相加，并返回结果 int i,j,k; //辅助变量 i = j = k = 1; //赋初值 if(A->mu != B->mu || A->nu != B->nu) //判断矩阵A和矩阵B的维数，以此来看是否可以相加 { printf("矩阵A和矩阵B的维数不完全相同，不可以做加法！"); exit(0); } C.mu = A->mu; //矩阵C初始化 C.nu = A->nu; //矩阵C初始化 while(i<=A->tu&&j<=B->tu) //循环条件，当i和j都没有把矩阵A和矩阵B中非零元素遍历完 { if(A->T[i].i == B->T[j].i) //判断行关系 { if(A->T[i].j == B->T[j].j) //判断列关系 { C.T[k].i = A->T[i].i; C.T[k].j = A->T[i].j; C.T[k].data = A->T[i].data + B->T[j].data; k++; i++; j++; } else if(A->T[i].j < B->T[j].j) { C.T[k].i = A->T[i].i; C.T[k].j = A->T[i].j; C.T[k].data = A->T[i].data; k++; i++; } else { C.T[k].i = B->T[j].i; C.T[k].j = B->T[j].j; C.T[k].data = B->T[j].data; k++; j++; } } else if(A->T[i].i < B->T[j].i) { C.T[k].i = A->T[i].i; C.T[k].j = A->T[i].j; C.T[k].data = A->T[i].data; k++; i++; } else { C.T[k].i = B->T[j].i; C.T[k].j = B->T[j].j; C.T[k].data = B->T[j].data; k++; j++; } } while(i<=A->tu) //如果是j先遍历完了，但是i没有遍历完，那么就将矩阵A中剩余元素赋值给矩阵C { C.T[k].i = A->T[i].i; C.T[k].j = A->T[i].j; C.T[k].data = A->T[i].data; k++; i++; } while(j<=B->tu) //如果是i先遍历完了，但是j没有遍历完，那么就将矩阵B中剩余元素赋值给矩阵C { C.T[k].i = B->T[j].i; C.T[k].j = B->T[j].j; C.T[k].data = B->T[j].data; k++; j++; } C.tu = k-1; //注意，我这里是先赋值，再k++,所以最后k的值比C中非零元素个数多1，所以要减去。 return C; }

二、小结 写完这次作业以后，我收获很多，这道题我以前写过类似的，但是没有想到过每个小球只会和周围的两个球发生碰撞，我以前会采用遍历的方式来做，那么时间复杂度就为：，空间复杂度为：相比于学过数据结构以后的我设计出来的算法，以前的算法时间复杂度太大了，所以感觉学了数据结构以后收获颇丰。 矩阵这里，我以前不会用三元组来表示，都是单纯的用二维数组来做的，那样的话，时间复杂度很高，所以学完了三元组感觉可以提升自己的矩阵处理能力了。 （附上以前写的第一题的代码和结果，当然按照这道题的意思改了改原来的代码）

main() { int x[N],v[N]; //存储小球的位置信息和速度信息 int i,j,k; //辅助变量，i:用来进行对小球的位置信息和速度信息的初始化，，，，j,k:后面运动过程中进行改变球的位置信息和速度信息 int n,L,t; //小球的个数n，线段的长度L，以及你需要计算t秒之后小球的位置 printf("请输入小球的个数n，线段的长度L，以及你需要计算t秒之后小球的位置: "); //提示输入信息 scanf("%d %d %d",&n,&L,&t); while(L%2) //判断线段的长度L是否是偶数 { printf("线段的长度L输入错误，L必须是偶数!\n"); printf("请输入线段的长度L: "); scanf("%d",&L); } for(i = 0;i<n;i++) //初始化小球的位置信息和速度信息 { printf("请输入第%d个小球的初始坐标: ",i+1); scanf("%d",&x[i]); v[i] = 1; //初始速度全为1 while(x[i]%2) //判断第i+1个小球的初始坐标是否是偶数 { printf("第%d个小球的初始坐标输入错误，L必须是偶数!\n",i+1); printf("请输入第%d个小球的初始坐标: ",i+1); scanf("%d",&x[i]); } } for(j = 0;j<t;j++) //不考虑初始位置相同的情况 { for(i = 0;i<n;i++) //找到下一秒小球的位置，对小球位置进行更新 x[i] = x[i]+v[i]; for(i = 0;i<n;i++) { for(k = i+1;k<n;k++) { if(x[i] == x[k]) { v[i] = -v[i]; v[k] = -v[k]; continue; //因为所有小球的初始位置都为偶数，而且线段的长度为偶数，可以证明，不会有三个小球同时相撞 } } if(x[i] == 0||x[i] == L) { v[i] = -v[i]; } } } printf("%d秒后小球的位置坐标为：\n",t); for(i = 0;i < n;i++) printf("第%d个小球的位置为：%d\n",i+1,x[i]); }