banner
NEWS LETTER

数组

Scroll down

数组

稀疏矩阵

  • 结构定义

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    #define MAXSIZE 50  /*非零元素的个数最多为1000*/
    #define ElementType int

    /*稀疏矩阵三元组表的类型定义*/
    typedef struct {
    int row, col; /*该非零元素的行下标和列下标*/
    ElementType e; /*该非零元素的值*/
    } Triple;

    typedef struct {
    int m, n, len; /*矩阵的行数、列数和非零元素的个数*/
    Triple data[MAXSIZE + 1]; /* 非零元素的三元组表。data[0]未用*/
    } TSMatrix;

十字链表

  • 结构定义

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    typedef struct OLNode {
    int row, col; /*非零元素的行和列下标*/
    int value;
    struct OLNode *right; /*非零元素所在行表、列表的后继链域*/
    struct OLNode *down;
    } OLNode, *OLink;

    typedef struct {
    OLink *row_head; /*行、列链表的头指针向量*/
    OLink *col_head;
    int m, n, len; /*稀疏矩阵的行数、列数、非零元素的个数*/
    } CrossList;
  • 创建十字链表

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    void CreateCrossList(CrossList *M, OLNode nodes[], int m, int n, int len) {
    OLNode *p, *q;
    int i, j, k, e;

    M->m = m;
    M->n = n;
    M->len = len;

    //创建行头数组并初始化
    M->row_head = (OLink*)malloc((m+1)*sizeof(OLink));
    for (i = 1; i <= m; ++i) M->row_head[i] = NULL;

    //创建列头数组并初始化
    M->col_head = (OLink*)malloc((n+1)*sizeof(OLink));
    for (i = 1; i <= n; ++i) M->col_head[i] = NULL;

    //根据nodes数组里的每一个数据
    for (k = 0; k < len; ++k) {
    //生成新结点并填入数据
    p = (OLNode *)malloc(sizeof(OLNode));
    p->row = i = nodes[k].row;
    p->col = j = nodes[k].col;
    p->value = e = nodes[k].value;
    p->right = p->down = NULL;

    //将新节点插入到行链表中
    if (M->row_head[i] == NULL) //如果行链表为空。
    M->row_head[i] = p;
    else {
    //寻找行表中的插入位置:工作指针q指向插入位置的前一个结点,然后插入
    for (q = M->row_head[i]; q->right != NULL && q->right->col < j; q = q->right);
    p->right = q->right;
    q->right = p;
    }

    //将新节点插入到列链表中,方法类似于插入到行链表中
    if (M->col_head[j] == NULL) //如果行链表为空。
    M->col_head[j] = p;
    else {
    //寻找行表中的插入位置:工作指针q指向插入位置的前一个结点,然后插入
    for (q = M->col_head[j]; q->down != NULL && q->down->row < i; q = q->down);
    p->down = q->down;
    q->down = p;
    }
    }
    }
其他文章
cover
树与二叉树
  • 24/06/24
  • 09:47
  • 数据结构
cover
  • 24/06/22
  • 09:46
  • 数据结构
目录导航 置顶
  1. 1. 数组
    1. 1.1. 稀疏矩阵
    2. 1.2. 十字链表
请输入关键词进行搜索