转置矩阵,排序

段梦园 [1**********]069 计本2班 *转置矩阵：

#include

#include

#define OK 1

#define ERROR 0

#define TRUE 1

#define FALSE 0

#define MAXSIZE 100

typedef int Status;

typedef float ElemType;

typedef struct{

int i,j;

ElemType e;

}Triple;

typedef struct{

Triple data[MAXSIZE+1];

int mu,nu,tu;

}TSMatrix;

TSMatrix NewMatrix(int m,int n);

Status InsertElem(TSMatrix *M,int row,int col,ElemType e); Status FindElem(const TSMatrix *M,int row,int col,ElemType *e); Status TransposeSMatrix(const TSMatrix *M,TSMatrix *T); Status FastTransposeSMatrix(const TSMatrix *M,TSMatrix *T); Status MultSMatrix(const TSMatrix *M,const TSMatrix *T,TSMatrix *Q); void PrintSMatrix(const TSMatrix *M);

int main()

{

TSMatrix M=NewMatrix(3,4);

TSMatrix T;

TSMatrix Q;

InsertElem(&M,3,2,16);

InsertElem(&M,2,2,18);

printf("\nM:");

PrintSMatrix(&M);

FastTransposeSMatrix(&M,&T);

printf("\nT(Transpose of M):");

PrintSMatrix(&T);

MultSMatrix(&M,&T,&Q);

printf("\nM*T=");

PrintSMatrix(&Q);

return 0;

}

TSMatrix NewMatrix(int m,int n){

TSMatrix M;

M.mu=m;

M.nu=n;

M.tu=0;

return M;

}

Status InsertElem(TSMatrix *M,int row,int col,ElemType e){

int i,t,p;

if(M->tu>=MAXSIZE){

printf("\nError:There is no space in the matrix;\n");

return ERROR;

}

if(row>M->mu||col>M->nu||row

printf("\nError:Insert position is beyond the arrange.\n"); return ERROR;

}

p=1;

if(M->tu==0){

M->data[p].i=row;

M->data[p].j=col;

M->data[p].e=e;

M->tu++;

return OK;

}

for(t=1;ttu;t++)

if((row>=M->data[t].i)&&(col>=M->data[t].j))

p++;

if(row==M->data[t-1].i && col==M->data[t-1].j){

M->data[t-1].e=e;

return OK;

}

for(i=M->tu;i>=p;i--){

M->data[i+1].i=M->data[i].i;

M->data[i+1].j=M->data[i].j;

M->data[i+1].e=M->data[i].e;

}

M->data[p].i=row;

M->data[p].j=col;

M->data[p].e=e;

M->tu++;

return OK;

}

Status FindElem(const TSMatrix *M,int row,int col,ElemType *e){ int p;

for(p=1;ptu;p++)

if(M->data[p].i==row&&M->data[p].j==col){

*e=M->data[p].e;

return TRUE;

}

return FALSE;

}

Status TransposeSMatrix(const TSMatrix *M,TSMatrix *T){

int col,p,q;

T->mu=M->nu; T->nu=M->mu; T->tu=M->tu;

if(T->tu){

q=1;

for(col=1;colmu;col++)

for(p=1;ptu;p++)

if(M->data[p].j==col){

T->data[q].i=M->data[p].j;

T->data[q].j=M->data[p].i;

T->data[q].e=M->data[p].e;

q++;

}

}

return OK;

}

Status FastTransposeSMatrix(const TSMatrix *M,TSMatrix *T){ int col,t,p,q,*num,*cpot;

T->mu=M->nu; T->nu=M->mu; T->tu=M->tu;

if(T->tu){

num=(int *)malloc(sizeof(int)*M->tu);

cpot=(int *)malloc(sizeof(int)*M->tu);

if(!(num&&cpot)){

printf("Apply for memory error.\n");

exit(0);

}

for(col=1;colnu;col++) num[col]=0;

for(t=1;ttu;t++) ++num[M->data[t].j];

cpot[1]=1;

for(col=2;colnu;col++)

cpot[col]=cpot[col-1]+num[col-1];

for(p=1;ptu;p++){

col=M->data[p].j; q=cpot[col];

T->data[q].i=M->data[p].j;

T->data[q].j=M->data[p].i;

T->data[q].e=M->data[q].e;

++cpot[col];

}

}

return OK;

}

Status MultSMatrix(const TSMatrix *M,const TSMatrix *T,TSMatrix *Q){ int i,j,k,p;

ElemType m,t,s;

if(M->nu!=T->mu){

printf("Sorry,these two matrice can't multiply.\n");

return ERROR;

}

Q->mu=M->mu; Q->nu=T->nu; Q->tu=0;

p=1;

for(i=1;imu;i++){

for(j=1;jnu;j++){

s=0;

for(k=1;knu;k++){

if(FALSE==FindElem(M,i,k,&m))

continue;

if(FALSE==FindElem(T,k,j,&t))

continue;

s+=m*t;

}

if(s!=0){

Q->data[p].i=i;

Q->data[p].j=j;

Q->data[p].e=s;

p++;

Q->tu++;

}

}

}

return OK;

}

void PrintSMatrix(const TSMatrix *M){

int i,j,p=1;

printf("\nsize:%d ר¢ %d\n",M->mu,M->nu); if(!M->tu){

printf("%g\n",0.0);

return;

}

for(i=1;imu;i++){

for(j=1;jnu;j++){

if(i==M->data[p].i && j==M->data[p].j){ printf("%g\t",M->data[p].e); p++;

}else{

printf("%g\t",0.0);

}

}

printf("\n");

}

printf("\n");

}

*插入排序：

#include

using namespace std;

#define MAXSIZE 30

void InsertSort(int r[],int n) {

int i,j;

for(i=2;i

r[0]=r[i]; //r[0]用作哨兵单元 j=i-1;

while(r[0]

{

r[j+1]=r[j]; //记录后移 j--;

}

r[j+1]=r[0];

for(j=1;j

cout

cout

}

}

int main(){

int n,i;

int r[MAXSIZE];

cout > n;

cout

cin >> r[i];

}

InsertSort(r,n);

}

*折半排序：

#include

using namespace std;

#define MAXSIZE 30

void BinaryInsertSort(int r[],int n){ int i, low, high, mid;

for( i = 2; i

r[0] = r[i]; //r[0]用作哨兵单元 low = 1;

high = i-1;

while(low

mid = (low + high)/2; if (r[mid] > r[0]){

high = mid - 1;

}

else{

low = mid + 1;

}

}

for (int j = i - 1; j > high; j-- ) {

r[j+1] = r[j]; //记录后移 }

r[high + 1] = r[0];

for(int j = 1; j

cout

}

}

int main(){

int n,i;

int r[MAXSIZE];

cout > n;

cout

{

cin >> r[i];

}

BinaryInsertSort(r,n);

}

*希尔排序：

#include

using namespace std;

#define MAXSIZE 30

void ShellSort(int r[],int n) {

for (int d = 10; d != 1;) {

d = d/2;

int i,j;

for(i = 1 + d; i

j = i-d;

while( r[0]

{

r[j+d] = r[j];

j -= d;

}

r[j+d]=r[0];

}

for(j = 1; j

{

cout

cout

}

}

int main(){

int n,i;

int r[MAXSIZE];

cout > n;

cout

{

cin >> r[i];

}

ShellSort(r,n);;

}

*归并排序：

#include

#include

using namespace std;

class mergeSort{

public:

int* Ptr;

int len;

mergeSort();

void set();

void Sort(int *arr,int len);

void numDisplay();

} ;

mergeSort() {

Ptr=nullptr;

len=0;

}

void

set(){

int num;

int* ptr(nullptr);

cout

cin>>len;

ptr=new int[len];

for(int i=0;i

cout>num;

*(ptr+i)=num;

}

Ptr=ptr;

}

void Sort(int *arr,int len){

if(len>1) {

int length=len/2;

int* num1(nullptr);

int* num2(nullptr);

num1=new int[length];

num2=new int[len-length];

for(int i=0;i

*(num1+i)=*(arr+i);

for(int i=0,j=length;i

for(int i=0;i

cout

cout

for(int i=0;i

cout

cout

int k=0,i=0,j=0;

while(i

*(arr+k)=*(num1+i); i++;

}

else{

*(arr+k)=*(num2+j);

j++;

}

k++;

}

if(i==length)

for(int temp=j;temp

j++;

}

else

for(int temp=i;temp

i++;

}

for(int h=0;h

cout

cout

}

}

void numDisplay(){

if(Ptr==nullptr)

cout

for(int i=0;i

cout

cout

}

int main(int argc, int* argv[]) { mergeSort T;

T.set();

T.numDisplay();

T.Sort(T.Ptr,T.len);

T.numDisplay();

system("pause");

return 0;

}