数据结构与算法基础之对称矩阵

学习来源:
数据结构与算法基础（青岛大学-王卓）

地址：

https://www.bilibili.com/video/BV1nJ411V7bd?p=22&spm_id_from=pageDriver

背景:
实现视频里老师的伪代码，并不完全一样，但基本雷同。

更新
2021/7/3
第一次发布

---

代码:

SymmetryMatrix.h

#ifndef _SYMMETRYMATRIX_H_
#define _SYMMETRYMATRIX_H_

typedef struct SymmetryMatrix *SymmetryMatrix;//Matrix object

//Create "n" x "n" symmetry matrix.
SymmetryMatrix Create_SM(unsigned n);

//Destroy matrix.
//The function will set matrix's pointer "sm" with NULL.
void Destroy_SM(SymmetryMatrix *sm_p);

//Set matrix sm's element's value with "val".index("i", "j")
void Set_SM(SymmetryMatrix sm, unsigned i, unsigned j, int val);

//Get matrix sm's element's value.index("i", "j");
int Get_SM(SymmetryMatrix sm, unsigned i, unsigned j);
void Show_SM(SymmetryMatrix sm);

#endif

SymmetryMatrix.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "SymmetryMatrix.h"
#include "CommonFunc.h"

struct SymmetryMatrix
{
    int *array;//Matrix array.
    unsigned n;//nxn Matrix
};

//Caculate the length of matrix array by "n".
inline static unsigned GetLength_SM(unsigned n);


void Show_SM(SymmetryMatrix sm)
{
    NULLPointOut(sm, "Show_SM", "sm");

    unsigned n = sm->n;

    unsigned i, j;
    for(i = 1; i <= n; i++)
    {
        for(j = 1; j <=n; j++)
        {
            printf("%d ", Get_SM(sm, i, j));
        }
        puts("");
    }

    return;
}

int Get_SM(SymmetryMatrix sm, unsigned i, unsigned j)
{
    NULLPointOut(sm, "Get_SM", "sm");

    if(i > sm->n || j > sm->n || i == 0 || j == 0)
    {
        puts("ERROR Get_SM: The i or j is out of the matrix boundary of 'n'");
        exit(-1);
    }
    else if(j > i)
    {
        unsigned tmp;

        tmp = j;
        j = i;
        i = tmp;
    }

    unsigned k = (i * (i - 1) / 2) + (j - 1);

    return sm->array[k];
}

void Set_SM(SymmetryMatrix sm, unsigned i, unsigned j, int val)
{
    NULLPointOut(sm, "Set_SM", "sm");

    if(i > sm->n || j > sm->n || i == 0 || j == 0)
    {
        puts("ERROR Set_SM: The i or j is out of the matrix boundary of 'n'");
        exit(-1);
    }
    else if(j > i)
    {
        unsigned tmp;

        tmp = j;
        j = i;
        i = tmp;
    }

    unsigned k = (i * (i - 1) / 2) + (j - 1);
    sm->array[k] = val;

    return;
}


void Destroy_SM(SymmetryMatrix *sm_p)
{
    NULLPointOut(sm_p, "Destroy_SM", "sm_p");
    NULLPointOut(*sm_p, "Destroy_SM", "sm");
    NULLPointOut((*sm_p)->array, "Destroy_SM", "array");

    free((*sm_p)->array);
    free(*sm_p);

    *sm_p = NULL;

    return;
}

SymmetryMatrix Create_SM(unsigned n)
{
    if(n == 0)
    {
        return NULL;
    }

    unsigned len = GetLength_SM(n);

    int *array = (int *)malloc(len * sizeof(int));
    NULLMallocOut(array, "Create_SM", "array");
    memset(array, 0, len * sizeof(int));

    SymmetryMatrix sm = (SymmetryMatrix)malloc(sizeof(SymmetryMatrix));
    NULLMallocOut(sm, "Create_SM", "sm");

    sm->array = array;
    sm->n = n;

    return sm;
}

inline static unsigned GetLength_SM(unsigned n)
{
    return n * (n + 1) / 2;
}

CommonFunc.h

#ifndef _COMMONFUNC_H_
#define _COMMONFUNC_H_


//If p equal null, exit program and pop a err message.
//The parameter 'func' is error function name.
//The paremeter 'element' is problem variables.
void NULLPointOut(void *p, char *func, char *element);
void NULLMallocOut(void *p, char *func, char *element);

//Index array.
//The "P" is array's head pointer.
//The "index" is your element position in array.
//The "DataSize" is element's type size.
//It returns the address of the element you are looking for.
void * Index(void *P, int index, unsigned DataSize);

//Pointer plus plus and pointer sub sub.
//The "P" is array's head pointer.
//The "DataSize" is element's type size.
void * PointerInc(void *P, unsigned DataSize);
void * PointerDec(void *P, unsigned DataSize);

//Get the distance between A and B.
//return (A - B) / DataSize
//The "DataSize" is element's type size.
long PointerSub(void *A, void *B, unsigned DataSize);


#endif

CommonFunc.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "CommonFunc.h"

long PointerSub(void *A, void *B, unsigned DataSize)
{
    NULLPointOut(A, "PointerSub", "A");
    NULLPointOut(B, "PointerSub", "B");

    if(DataSize == 0)
    {
        puts("PointerSub ERROR: Divide zero error");  
        exit(-1);
    }

    return ((char *)A - (char *)B) / DataSize;
}

void * PointerDec(void *P, unsigned DataSize)
{
    NULLPointOut(P, "PointerDec", "P");

    char *c = (char *)P;
    c = c - DataSize;

    return c;
}

void * PointerInc(void *P, unsigned DataSize)
{
    NULLPointOut(P, "PointerInc", "P");

    char *c = (char *)P;
    c = c + DataSize;

    return c;
}

void NULLPointOut(void *p, char *func, char *element)
{
    if(func == NULL)
    {
        puts("NULLPointOut ERROR: NULL point exception 'func'");
        exit(-1);
    }
    else if(element == NULL)
    {
        puts("NULLPointOut ERROR: NULL point exception 'element'");
        exit(-1);
    }

    if(p == NULL)
    {
        printf("%s ERROR: NULL point exception '%s'\n", func, element);
        exit(-1);
    }

    return;
}

void NULLMallocOut(void *p, char *func, char *element)
{
    NULLPointOut(func, "NULLMallocOut", "func");
    NULLPointOut(element, "NULLMallocOut", "element");

    if(p == NULL)
    {
        printf("%s ERROR: Malloc error '%s'\n", func, element);
        exit(-1);
    }

    return;
}

void * Index(void *P, int index, unsigned DataSize)
{
    NULLPointOut(P, "Index", "P");

    char *c = (char *)P;
    c = c + index * (int)DataSize;

    return c;
}

example.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "SymmetryMatrix.h"


int main(void)
{
    
    SymmetryMatrix sm = Create_SM(5);
    Set_SM(sm, 1, 1, 1);
    Set_SM(sm, 1, 2, 5);
    Set_SM(sm, 1, 3, 1);
    Set_SM(sm, 1, 4, 3);
    Set_SM(sm, 1, 5, 7);
    Set_SM(sm, 2, 1, 5);
    Set_SM(sm, 2, 3, 8);
    Set_SM(sm, 3, 1, 1);
    Set_SM(sm, 3, 2, 8);
    Set_SM(sm, 3, 3, 9);
    Set_SM(sm, 3, 4, 2);
    Set_SM(sm, 3, 5, 6);
    Set_SM(sm, 4, 1, 3);
    Set_SM(sm, 4, 3, 2);
    Set_SM(sm, 4, 4, 5);
    Set_SM(sm, 4, 5, 1);
    Set_SM(sm, 5, 1, 7);
    Set_SM(sm, 5, 3, 6);
    Set_SM(sm, 5, 4, 1);
    Set_SM(sm, 5, 5, 3);

    Show_SM(sm);

    Destroy_SM(&sm);

    return 0;
}