Zemdalk's blog

数据结构（4）——第5章：数组和广义表

  • 2022年 04月19日

数据结构笔记。第5章：数组和广义表

使用教材：《数据结构》（C语言版） 严蔚敏 吴伟民 著，清华大学出版社

Part I 数组

I.1 定义和表示

定义：数组是相同类型数据元素的集合。

存储：采用顺序存储结构实现，有静态数组和动态数组。

静态一维数组：

ElemType A[MAX];

动态一维数组：

ElemType *A=(ElemType *)malloc(MAX * sizeof(ElemType));
if(!A) return ERROR;

动态多维数组：

typedef struct{
    ElemType *base;         // 数组内的全部数据
    int dim;                // 数组的维数
    int *bounds;            // 数组各维的大小b_i
    int *constants;         // 数组映象函数常量地址c_i
} Array;

一维数组也被称为向量。二维数组可以用来存储矩阵。二维数组不是线性结构。

映象：由于内存是一维的，而多维数组是多维的，因此有存储顺序的映象方式。

  • 二维数组有两种映象方式：

以行序为主序（C语言）、以列序为主序。

  • n维数组的映象函数：（类行序主序映象）

LOC: location

\[LOC(j_1,j_2,...,j_n)=LOC(0,0,...,0)+\sum_{i=1}^nc_ij_i\]

where $b_i$ is the length of the ith dimension, L is the length of a single element, and $c_i$ is defined recursively as

\[c_n=L,\quad c_{i-1}=b_i\times c_i,\quad 1<i\leq n\]

I.2 基本操作

初始化、取值、赋值

I.3 处理矩阵

I.3.1 特殊矩阵的压缩存储

特殊矩阵：对称矩阵、三对角矩阵（规律性强）；稀疏矩阵（零元素多）。

不存储可以不存储的元素，如对称元素、零元素。

  • 对称矩阵

元素关于主对角线对称。只存储上/下三角矩阵，关键是找到内存位置$k$与元素下标$(i,j)$之间的关系。例如，行序优先存储下三角矩阵：

\[k=\left\{ \begin{aligned} \frac{i(i+1)}{2}+j,\ i\geq j\\ \frac{j(j+1)}{2}+i,\ i<j \end{aligned} \right.\]
  • 三对角矩阵

主对角线和相邻的上下两条对角线之外的元素全为0。

  • 稀疏矩阵

就是有很多0的矩阵。由三元组$(i,j,a_{ij})$确定非零元素。下面重点分析。

I.3.2 稀疏矩阵的压缩存储

  • 三元组顺序表：矩阵转置
  • 行逻辑联接的顺序表：矩阵乘法
  • 十字链表：矩阵加法
  • 三元组表
// 定义三元组（矩阵的非零元）
typedef struct {
    int i, j;
    ElemType e;
} Triple;

// 定义稀疏矩阵
typedef struct {
    Triple data[MAXSIZE + 1];   // 以顺序表存储全部三元组，行序主序
    int mu, nu, tu;             // 矩阵的行数、列数和非零元个数
} TSMatrix;

矩阵转置：

行、列数交换；每个三元组的行、列号交换；重排序。

快速转置算法：预先建立辅助数组num和cpot，num存转置前矩阵每列有多少非零元，cpot存每列第一个非零元在内存中的起始地址。

  • 行逻辑联接的顺序表

在上述三元组表基础上，增加一个数据成员rpos，指示各行第一个非零元的位置。

// 定义三元组（矩阵的非零元）
typedef struct {
    int i, j;
    ElemType e;
} Triple;

// 定义稀疏矩阵
typedef struct {
    Triple data[MAXSIZE + 1];   // 以顺序表存储全部三元组，行序主序
    int rpos[MAXMN + 1];        // 各行第一个非零元在data[]中的位置下标
    int mu, nu, tu;             // 矩阵的行数、列数和非零元个数
} TSMatrix;

矩阵乘法

  • 十字链表
typedef struct OLNode{
    int i,j;
    ElemType e;
    struct OLNode *right, *down;
} OLNode, *Olink;

typedef struct{
    Olink *rhead, *chead;
    int mu,nu,tu;
} CrossList;

矩阵加法

Part II 广义表

II.1 类型定义

表头、表尾、长度、深度。

II.2 存储

II.2.1 表头表尾分析法

typedef enum{ATOM, LIST} ElemTag;
typedef struct GLNode{
    ElemTag tag;
    union{
        AtomType atom;
        struct{
            GLNode *hp, *tp;
        } ptr;
    }
} Glist;

II.2.2 子表分析法

typedef enum{ATOM, LIST} ElemTag;
typedef struct GLNode{
    ElemTag tag;
    union{
        AtomType atom;
        struct GLNode *hp;
    }
    struct GLNode *tp;
} Glist;
搜索