一、矩阵乘的计算

矩阵其实就是一个二维的表格，那么数据结构中的矩阵其实也是一样的，计算机中可以用矩阵这种形式来存储数据。

总代码：

#include<stdio.h>
#include<stdlib.h>

#define TOTAL_SPACE 5

typedef struct CircleIntQueue
{
    int data[TOTAL_SPACE];
    int head;
    int tail;
}*CircleIntQueuePtr;

CircleIntQueuePtr initQueue()
{
    CircleIntQueuePtr resultPtr=(CircleIntQueuePtr)malloc(sizeof(struct CircleIntQueue));
    resultPtr->head=0;
    resultPtr->tail=0;

    return resultPtr;
}

void enqueue(CircleIntQueuePtr paraPtr,int paraValue)
{
    if((paraPtr->tail+1)%TOTAL_SPACE==paraPtr->head)
    {
        printf("Queue full.\r\n");
        return ;
    }
    paraPtr->data[paraPtr->tail%TOTAL_SPACE]=paraValue;
    paraPtr->tail++;
}

int dequeue(CircleIntQueuePtr paraPtr)
{
    int resultValue;
    if(paraPtr->head==paraPtr->tail)
    {
        printf("No element in the queue.\r\n");
        return -1;
    }

    resultValue=paraPtr->data[paraPtr->head%TOTAL_SPACE];
    paraPtr->head++;

    return resultValue;
}

int queuelength(CircleIntQueuePtr paraPtr)
{
    int length=0;
    for(int i=paraPtr->head;i<paraPtr->tail;i++)
    {
        length++;
    }
    return length;
}
/**
 * Output the queue.
 */
void outputLinkQueue(CircleIntQueuePtr paraPtr)
{
    int i;
    if(paraPtr->head==paraPtr->tail)
    {
        printf("Empty queue.");
        return ;
    }
    printf("Element in the queue:");
    for(i=paraPtr->head;i<paraPtr->tail;i++)
    {
        printf("%d ",paraPtr->data[i%TOTAL_SPACE]);
    }
    printf("\r\n");
}

void testLinkQueue()
{
    printf("---Begin!---\r\n");
    int i=10;
    CircleIntQueuePtr tempPtr =initQueue();
    for(i;i<16;i++)
    {
        enqueue(tempPtr,i);
    }
    outputLinkQueue(tempPtr);
    printf("Length of the queue is %d\r\n",queuelength(tempPtr));

    for(i=0;i<6;i++)
    {
        printf("dequeue gets %d\r\n",dequeue(tempPtr));
    }
    enqueue(tempPtr,8);
    outputLinkQueue(tempPtr);
    printf("---End!---\r\n");
}
int main()
{
    testLinkQueue();
    return 0;
}
 

实现结果：

二、压缩矩阵的转置 

什么是矩阵的压缩存储？其实就是为很多个值相同的元素只分配一个存储空间。对零元素不分配存储空间。

总代码：

#include<stdio.h>
#include<stdlib.h>

typedef int elem;

typedef struct Triple
{
    int i;
    int j;
    elem e;
}Triple,*TriplePtr;

typedef struct CompressedMatrix
{
    int row;//行数
    int col;//列数
    int num;//有效数据个数
    Triple* element;//压缩矩阵
}CompressedMatrix,*CompressedMatrixPtr;

CompressedMatrixPtr initCompressedMatrix(int paraRow,int paraCol,int paraElement,int** paraData)
{
    int i;
    CompressedMatrixPtr resultPtr=(CompressedMatrixPtr)malloc(sizeof(struct CompressedMatrix));
    resultPtr->row=paraRow;
    resultPtr->col=paraCol;
    resultPtr->num=paraElement;
    resultPtr->element=(TriplePtr)malloc(paraElement*sizeof(struct Triple));

    for(i=0;i<paraElement;i++)
    {
        resultPtr->element[i].i=paraData[i][0];
        resultPtr->element[i].j=paraData[i][1];
        resultPtr->element[i].e=paraData[i][2];
    }
    return resultPtr;
}

void printCompressedMatrix(CompressedMatrixPtr paraPtr)
{
    for(int i=0;i<paraPtr->num;i++)
    {
        printf("(%d,%d):%d\r\n",paraPtr->element[i].i,paraPtr->element[i].j,paraPtr->element[i].e);
    }
}

CompressedMatrixPtr transposeCompressedMatrix(CompressedMatrixPtr paraPtr)
{
    int i,tempCol,tempPosition;
    int* tempColCounts=(int*)malloc(paraPtr->col*sizeof(int));
    int* tempOffSet=(int*)malloc(paraPtr->col*sizeof(int));

    for(i=0;i<paraPtr->col;i++)
    {
        tempColCounts[i]=0;
    }

    CompressedMatrixPtr resultPtr=(CompressedMatrixPtr)malloc(sizeof(struct CompressedMatrix));
    resultPtr->row=paraPtr->col;
    resultPtr->col=paraPtr->row;
    resultPtr->num=paraPtr->num;

    resultPtr->element=(TriplePtr)malloc(paraPtr->num*sizeof(struct Triple));

    for(i=0;i<paraPtr->num;i++)
    {
        tempColCounts[paraPtr->element[i].j] ++;
    }
    tempOffSet[0]=0;
    for(i=1;i<paraPtr->col;i++)
    {
        tempOffSet[i]=tempOffSet[i-1]+tempColCounts[i-1];
        printf("tempOffSet[%d]=%d\r\n",i,tempOffSet[i]);
    }
    for(i=0;i<paraPtr->num;i++)
    {
        tempCol=paraPtr->element[i].j;
        tempPosition=tempOffSet[tempCol];
        resultPtr->element[tempPosition].i=paraPtr->element[i].j;
        resultPtr->element[tempPosition].j=paraPtr->element[i].i;
        resultPtr->element[tempPosition].e=paraPtr->element[i].e;

        tempOffSet[tempCol]++;
    }
    return resultPtr;
}

void compressedMatrixTest()
{
    CompressedMatrixPtr tempPtr1,tempPtr2;

    int i,j,tempElement;

    tempElement=4;
    int** tempMatrix1=(int**)malloc(tempElement*sizeof(int*));
    for(i=0;i<tempElement;i++)
    {
        tempMatrix1[i]=(int*)malloc(3*sizeof(int));
    }

    int tempMatrix2[4][3]={{0,0,2},{0,2,3},{2,0,5},{2,1,6}};
    for(i=0;i<tempElement;i++)
    {
        for(j=0;j<3;j++)
        {
            tempMatrix1[i][j]=tempMatrix2[i][j];
        }
    }
    tempPtr1=initCompressedMatrix(2,3,4,tempMatrix1);

    printf("After initialization.\r\n");
    printCompressedMatrix(tempPtr1);

    tempPtr2=transposeCompressedMatrix(tempPtr1);
    printf("After transpose.\r\n");
    printCompressedMatrix(tempPtr2);
}
int main()
{
    compressedMatrixTest();
    return 0;
}
 

测试结果：