m_matrix.c

稀疏矩阵、链表、图、队列、二叉树、多叉树、排序、遗传算法等的实现

/* m_matrix.c - matrix arithmetic */

#include "m_matrix.h"

static int mmerrcode = 0;      /* error code for matrix
                                * library */
static char line[LINELEN];     /* line buffer for file
                                * input */

/* static declarations of functions intended purely for
 * internal use */

/* multiplies the specified row in matrix a by a constant
 * "c" */
static MATRIX_T *
  m_muprow(int row, double c, MATRIX_T * a);

/* subtracts multiples of pivot row from each row below the 
 * pivot to make each column element below the diagonal in
 * column "col" equal to zero */
static void
  set_low_zero(MATRIX_T * t, int col);

/* swaps rows "row" and "swap" in matrix t */
static void
  swaprows(MATRIX_T * t, int row, int swap);

/* function to find the row (on or below the diagonal) in
 * which the maximum element of a column occurs */
static int
  maxelementrow(MATRIX_T * t, int col);

/* function to subtract multiples of the pivot row from all 
 * other rows to force each element in the pivot column to
 * * zero (except the actual pivot element) */
static void
  set_col_zero(MATRIX_T * t, MATRIX_T * v, int col);

/* swap row numbers row and swap in matrices t and v */
static void
  swaprows2(MATRIX_T * t, MATRIX_T * v, int row, int swap);

/*** END OF STATIC FUNCTION DECLARATIONS ***/

/* function to compute index of 1D array corresponding to
 * i,j indices of 2D array 
 * mdx is defined as a function for development
 * and testing; it is commented out and replaced
 * with a macro for production
static int
mdx(MATRIX_T * a, int i, int j)
{
    return i * a->cols + j;
}
 */

#define mdx(a,i,j) (i)*(a)->cols+(j)
/* note use of () around macro arguments for safety */

/* allocates a new matrix, elements not initialized */
MATRIX_T *
m_new(int nrows, int ncols)
{
    double *temp;
    MATRIX_T *m = NULL;
    if ((temp = malloc(nrows * ncols * sizeof(double)))
              == NULL) {
        mmerrcode = ALLOCFAIL;
        return NULL;
    }
    if ((m = malloc(sizeof(MATRIX_T))) == NULL) {
        mmerrcode = ALLOCFAIL;
        free(temp);
        return NULL;
    }
    m->rows = nrows;
    m->cols = ncols;
    m->val = temp;
    return m;
}

/* frees matrix */
void
m_free(MATRIX_T * m)
{
    if ( m == NULL) return;
	 /* not an error; used for recovery in 
	    other matrix library routines */
    free(m->val);
    free(m);
}

char *
m_getline(FILE * fp)
{
    do {
        if (!fgets(line, LINELEN, fp)) {
            mmerrcode = FILEREADFAIL;
            return NULL;
        }
    } while (*line == '#');
    return line;
}

MATRIX_T *
m_fnew(FILE * fp)
{
    int i, j, rows, cols, index;
    char *tok;
    char *lineptr;
    MATRIX_T *a;

    /* get number of rows */
    if (!m_getline(fp)) { return NULL;}
    if (!(tok = strtok(line, ","))) {
        mmerrcode = ROWPARSEFAIL;
        return NULL;
    }
    if (strcmp(tok, "rows")) {
        mmerrcode = ROWPARSEFAIL;
        return NULL;
    }
    if (!(tok = strtok(NULL, ","))) {
        mmerrcode = ROWPARSEFAIL;
        return NULL;
    }
    rows = atoi(tok);
    if (!rows) {
        mmerrcode = ROWPARSEFAIL;
        return NULL;
    }
    /* get number of columns */
    if (!m_getline(fp)) { return NULL;}
    if (!(tok = strtok(line, ","))) {
        mmerrcode = COLPARSEFAIL;
        return NULL;
    }
    if (strcmp(tok, "cols")) {
        mmerrcode = COLPARSEFAIL;
        return NULL;
    }
    if (!(tok = strtok(NULL, ","))) {
        mmerrcode = COLPARSEFAIL;
        return NULL;
    }
    cols = atoi(tok);
    if (!cols) {
        mmerrcode = COLPARSEFAIL;
        return NULL;
    }
    /* allocate new matrix */
    if (!(a = m_new(rows, cols)))
        return NULL;           /* error checking done in
                                * m_new */
    index = 0;
    for (i = 0; i < rows; i++) {
        if (!m_getline(fp)) {
            m_free(a);
            return NULL;
        }
        lineptr = line;
        for (j = 0; j < cols; j++) {
            if (!(tok = strtok(lineptr, ","))) {
                m_free(a);
                return NULL;
            }
            a->val[index] = atof(tok);
            index++;
            lineptr = NULL;    /* NULL arg to strtok after
                                * 1st pass */
        }
    }
    return a;
}

MATRIX_T *
m_add(MATRIX_T * sum, MATRIX_T * a, MATRIX_T * b)
{
    int i, j, index;
    if (sum == NULL || a == NULL || b == NULL) {
        mmerrcode = NULLARG;
        return sum;
    }
    if (a->rows != b->rows) {
        mmerrcode = RMISMATCH;
        return sum;
    }
    if (sum->rows != b->rows) {
        mmerrcode = RMISMATCH;
        return sum;
    }
    if (a->cols != b->cols) {
        mmerrcode = CMISMATCH;
        return sum;
    }
    if (sum->cols != b->cols) {
        mmerrcode = CMISMATCH;
        return sum;
    }
    index = 0;
    for (i = 0; i < sum->rows; i++) {
        for (j = 0; j < sum->cols; j++) {
            sum->val[index] =
                a->val[index] + b->val[index];
            index++;
        }
    }
    return sum;
}

MATRIX_T *
m_sub(MATRIX_T * diff, MATRIX_T * a, MATRIX_T * b)
{
    int i, j, index;
    if (diff == NULL || a == NULL || b == NULL) {
        mmerrcode = NULLARG;
        return diff;
    }
    if (a->rows != b->rows) {
        mmerrcode = RMISMATCH;
        return diff;
    }
    if (diff->rows != b->rows) {
        mmerrcode = RMISMATCH;
        return diff;
    }
    if (a->cols != b->cols) {
        mmerrcode = CMISMATCH;
        return diff;
    }
    if (diff->cols != b->cols) {
        mmerrcode = CMISMATCH;
        return diff;
    }
    index = 0;
    for (i = 0; i < diff->rows; i++) {
        for (j = 0; j < diff->cols; j++) {
            diff->val[index] =
                a->val[index] - b->val[index];
            index++;
        }
    }
    return diff;
}

MATRIX_T *
m_assign(MATRIX_T * a, MATRIX_T * b)
{
    int i, j, index;
    if (a == NULL || b == NULL) {
        mmerrcode = NULLARG;
        return a;
    }
    if (a->rows != b->rows) {
        mmerrcode = RMISMATCH;
        return a;
    }
    if (a->cols != b->cols) {
        mmerrcode = CMISMATCH;
        return a;
    }
    index = 0;
    for (i = 0; i < a->rows; i++) {
        for (j = 0; j < a->cols; j++) {
            a->val[index] = b->val[index];
            index++;
        }
    }
    return a;
}

MATRIX_T *
m_mup(MATRIX_T * prod, MATRIX_T * a, MATRIX_T * b)
{
    int i, j, k;
    if (prod == NULL || a == NULL || b == NULL) {
        mmerrcode = NULLARG;
        return prod;
    }
    if (prod->rows != a->rows) {
        mmerrcode = RMISMATCH;
        return prod;
    }
    if (prod->cols != b->cols) {
        mmerrcode = CMISMATCH;
        return prod;
    }
    if (a->cols != b->rows) {
        mmerrcode = RCMISMATCH;
        return prod;
    }
    for (i = 0; i < a->rows; i++) {
        for (j = 0; j < b->cols; j++) {
            prod->val[mdx(prod,i,j)] = 0.0;
            for (k = 0; k < a->cols; k++) {
                prod->val[mdx(prod,i,j)] +=
                    a->val[mdx(a,i,k)] * b->val[mdx(b,k,j)];
            }
        }
    }
    return prod;
}

MATRIX_T *
m_transpose(MATRIX_T * trans, MATRIX_T * a)
{
    int i, j;
    if (trans == NULL || a == NULL) {
        mmerrcode = NULLARG;
        return trans;
    }
    if (trans->rows != a->cols) {
        mmerrcode = RCMISMATCH;
        return trans;
    }
    if (trans->cols != a->rows) {
        mmerrcode = RCMISMATCH;
        return trans;
    }
    for (i = 0; i < a->rows; i++) {
        for (j = 0; j < a->cols; j++) {
            trans->val[mdx(trans, j, i)] =
                a->val[mdx(a, i, j)];
        }
    }
    return trans;
}

void
tprintf(char *comment, char *nformat,
        MATRIX_T * a, MATRIX_T * b)
{
    int i, j, index;
    if (a == NULL || b == NULL) {
        mmerrcode = NULLARG;
        printf("tprintf NULL argument error\n");
        return;
    }
    printf("%s\n", comment);
    index = 0;
    for (i = 0; i < a->rows; i++) {
        for (j = 0; j < a->cols; j++) {
            printf(nformat, a->val[a->cols * i + j]);
        }
        printf(" ** ");
        for (j = 0; j < a->cols; j++) {
            printf(nformat, b->val[a->cols * i + j]);
        }
        printf("\n");
    }
    printf("\n");
}

MATRIX_T *
m_assign_identity(MATRIX_T * iden)
{
    int i, j, index;
    if (iden == NULL) {
        mmerrcode = NULLARG;
        return iden;
    }
    if (iden->rows != iden->cols) {
        mmerrcode = NOTSQUARE;
        return iden;
    }
    index = 0;
    for (i = 0; i < iden->rows; i++) {
        for (j = 0; j < iden->cols; j++) {
            iden->val[index] = 0.0;
            if (i == j)
                iden->val[index] = 1.0;
            index++;
        }
    }
    return iden;
}

double
m_getij(MATRIX_T * a, int i, int j)
{
    if (a == NULL) {
        mmerrcode = NULLARG;
        return 0.0;
    }
    if (i > a->rows - 1) {
        mmerrcode = INDEXOUTOFRANGE;
        return 0.0;
    }
    if (j > a->cols - 1) {
        mmerrcode = INDEXOUTOFRANGE;
        return 0.0;
    }
    return a->val[mdx(a, i, j)];
}

int
m_putij(MATRIX_T * a, int i, int j, double value)
{
    if (a == NULL) {
        mmerrcode = NULLARG;
        return mmerrcode;
    }
    if (i > a->rows - 1) {
        mmerrcode = INDEXOUTOFRANGE;
        return mmerrcode;
    }
    if (j > a->cols - 1) {
        mmerrcode = INDEXOUTOFRANGE;
        return mmerrcode;
    }
    a->val[mdx(a, i, j)] = value;
    return 0;
}

int
m_getrows(MATRIX_T * a)
{
    if (a == NULL) {
        mmerrcode = NULLARG;
        return mmerrcode;
    }
    return a->rows;
}

int
m_getcols(MATRIX_T * a)
{
    if (a == NULL) {
        mmerrcode = NULLARG;
        return mmerrcode;
    }
    return a->cols;
}

void
m_printf(char *label, char *format, MATRIX_T * a)
{
    int i, j;
    if (a == NULL) {
        printf("m_printf NULL argument error\n");
        return;
    }
    printf("%s\n", label);
    printf("rows = %d, cols = %d\n", a->rows, a->cols);
    for (i = 0; i < a->rows; i++) {
        for (j = 0; j < a->cols; j++) {
            printf(format, a->val[mdx(a,i,j)]);
        }
        printf("\n");
    }
}

void
m_fputcsv(FILE * fp, MATRIX_T * a)
{
    int i, j;
    char *sep;
    char comma[] = ",";
    char nocomma[] = "";
    if (a == NULL) {
        mmerrcode = NULLARG;
        return;
    }
    fprintf(fp, "rows,%d\n", a->rows);
    fprintf(fp, "cols,%d\n", a->cols);
    for (i = 0; i < a->rows; i++) {
        sep = nocomma;
        for (j = 0; j < a->cols; j++) {
            fprintf(fp, "%s%f", sep, a->val[mdx(a,i,j)]);
            sep = comma;
        }
        fprintf(fp, "\n");
    }
}

void