首页 数据结构（C++）
  1. 数组
    1.1 一维数组（向量）
    1.2 二维数组（矩阵）
    1.3 三维数组
  2. 特殊矩阵
    2.1 对称矩阵
    2.2 三角矩阵
    2.3 稀疏矩阵
  3. 广义表
    3.1 存储方法 1
    3.2 存储方法 2
  4. 串
    4.1 顺序存储结构
    4.2 链式存储结构

# 一、数组

# 1. 一维数组（向量）

image-20251217161304931

求一维数组中第 i 个元素的起始地址

序号为i的元素起始地址=序号为1的元素起始地址 + (i-1) *每个元素所需的空间


# 2. 二维数组（矩阵）

image-20251217162431695
image-20251217162510787
image-20251217162535131 image-20251217162618035

求二维数组 Amn 中第 i 行 j 列元素的起始地址

LOC(A[i][j]) = LOC(A[0][0]) + i × n + j

也是 起始地址+前面的元素个数*每个元素所需空间


# 3. 三维数组

image-20251217162718820

三维数组元素 A[i][j][k] 的起始地址公式：

LOC(A[i][j][k]) = LOC(A[0][0][0]) + i × (d2 × d3) + j × d3 + k

# 二、特殊矩阵

# 1. 对称矩阵

image-20251226193536570

# 2. 三角矩阵

image-20251226193647955

# 下三角存储（含主对角线）

① 情况划分

  • 若 i ≥ j ：元素直接存储
  • 若 i < j ：用 A[j][i] 代替

② 地址计算公式

第 i 行前面共有：

1 + 2 + … + (i − 1) = (i − 1)i / 2

因此：

LOC(A[i][j]) = LOC(A)
             + (i − 1)i / 2
             + (j − 1)

# 上三角存储（含主对角线）

① 情况划分

  • 若 i ≤ j ：元素直接存储
  • 若 i > j ：用 A[j][i] 代替

② 地址计算公式

前面完整行的元素个数为：

n + (n − 1) + … + (n − i + 2)
= (i − 1)(2n − i + 2) / 2

因此：

LOC(A[i][j]) = LOC(A)
             + (i − 1)(2n − i + 2) / 2
             + (j − i)


# 3. 稀疏矩阵

# 顺序存储类定义

// 稀疏矩阵顺序存储类定义
struct RCV
{
    int row,col;//row 行号  col 列号
    float value;// 矩阵中非零元素的值
};
class SMatrix
{
private:
    RCV *item;// 指向 RCV 类型数组的指针，用于存储稀疏矩阵的所有非零元素
    int r,c,num;//r 矩阵总行数   c 矩阵总列数     num 矩阵中非零元素个数
public:
    SMatrix()
    {
        item=NULL;
        r=0;
        c=0;
        num=0;
    }
    SMatrix(RCV a[],int n,int row,int col);//a [] 是一个三元组
    SMatrix tran();// 普通转置算法
    SMatrix tran1();// 改进后的转置算法
    SMatrix plus(SMatrix &b);
    SMatrix mult(SMatrix &b);
    void prnt();
};

# 构造函数
// 设置三元组表 a、长度 n 及行数 row、列数 col 四个参数
// 创建的三元组表由参数 a、n 确定，而行数、列数分别由参数 row、col 确定。
// 功能：按指定的参数分配存储空间并设置数据成员的初值。
SMatrix::SMatrix(RCV a[],int n,int row,int col)// 构造函数
{
    r=row;
    c=col;
    num=n;
    item=new RCV[num];
    for(int i=0;i<num;++i)
    {
        item[i]=a[i];
    }
}


# 稀疏矩阵的转置算法
稀疏矩阵转置的本质
1️⃣ 数学上的转置
普通矩阵转置规则：
A[i][j] → Aᵀ[j][i]
2️⃣ 稀疏矩阵怎么转置？
由于我们只存非零元素：
每个三元组的 row 和 col 交换即可
(row, col, value)
→
(col, row, value)
image-20251227000350891
⚠️ 数学上已经是转置了，但不规范

稀疏矩阵的默认约定通常要求：
按 row 升序排列
row 相同 → 按 col 升序
这样：
  • 方便输出
  • 方便查找
  • 方便后续运算（加法、乘法）
image-20251227000422431
# 普通转置算法
// 稀疏矩阵的转置操作
/*
功能：返回当前矩阵对象的转置矩阵，按以下过程处理：
(1) 创建一个稀疏矩阵 ×，形成 x 的 r,C,num，并按指定的长度分配存储空间。
(2) 按当前矩阵的列 (即 × 的行) 进行循环处理：对当前矩阵的每一列扫描一次三元组，
找出相应的元素，交换其行号与列号并添加到转置矩阵 × 的三元组表中。
(3) 返回结果矩阵 x。
*/
SMatrix SMatrix::tran()
{
    SMatrix x;
    int k;
    x.r=c;
    x.c=r;
    x.num=num;
    x.item=new RCV[num];
    if(num>0)// 判断是否存在非零元素
    {
        k=0;// 转置矩阵元素计数器
        for(int i=0;i<c;++i)// 遍历原矩阵列号
        {
            for(int j=0;j<num;++j)// 遍历原矩阵非零元素
            {
                if(item[j].col==i)// 如果当前非零元素的列号等于当前列 i
                {
                    x.item[k].row=item[j].col;
                    x.item[k].col=item[j].row;
                    x.item[k].value=item[j].value;
                    k++;
                }
            }
        }
    }
    return x;
}
时间复杂度大

# 快速转置算法（改进）
// 稀疏矩阵快速转置
/*
功能：使用快速转置法计算并返回当前矩阵的转置矩阵，其处理过程为：
(1) 创建一个稀疏矩阵 x， 形成 x 的 r, C, num， 并按指定的长度分配存储空间。
(2) 求当前矩阵中各列非零元的个数，将结果存入数组 rnum。
(3) 求结果矩阵中各行起始位置，将结果存入数组 rstart。
(4) 依次扫描当前矩阵中的三元组表，对每一个三元组行列置换后
按原列号 col 存入 x 中由 rstart [col] 指示的位置，并使其位置加 1。
(5) 返回结果矩阵 x。
*/
SMatrix SMatrix::tran1()
{
    SMatrix x;
    //int rnum [100],rstart [100]; 修改为下面的 * rnum, *rstart
    x.r=c;
    x.c=r;
    x.num=num;
    x.item=new RCV[num];
    
    if(num==0)
    {
        return x;
    }
    //rnum 统计「原始稀疏矩阵」中每一列有多少个非零元素（比如原始矩阵第 0 列有 2 个非零元素，rnum [0] 就等于 2）
    //rstart 记录「转置矩阵」中每一行的第一个非零元素，在 x.item 数组（存转置后非零元素）中的起始下标
    //（比如转置矩阵第 0 行第一个元素在 x.item [0]，第 2 行第一个元素在 x.item [2]）
    int *rnum=new int[c];
    int *rstart=new int[c];
    for(int i=0;i<c;++i)
    {
        rnum[i]=0;
    }
    for(int i=0;i<num;++i)// 当前矩阵各列的非零元素的个数存入 rnum
    {
        rnum[item[i].col]++;// 对应列的计数加 1
    }
    rstart[0]=0;// 转置矩阵第 0 行的第一个非零元素，在 x.item 数组中的起始下标是 0（也就是第一个元素就存在 x.item [0]）
    for(int i=1;i<c;++i)
    {
        rstart[i]=rnum[i-1]+rstart[i-1];    
    }
    for(int i=0;i<num;++i)
    {
        int j=item[i].col;// 确定当前原始元素，在转置矩阵中对应的行号
        x.item[rstart[j]].row=j;// 转置元素的行号 = 原始元素的列号（j）
        x.item[rstart[j]].col=item[i].row;// 转置元素的列号 = 原始元素的行号
        x.item[rstart[j]].value=item[i].value;
        rstart[j]++;
    }
    delete []rnum;
    delete []rstart;
    return x;
}

# 十字链表转置（计算量最小）
struct OLNode// 非零结点结构
{
    int row;
    int col;
    int value;
    OLNode *right;// 指向同行下一个非零元
    OLNode *down;// 指向同列下一个非零元
};
struct CrossMatrix
{
    int r;
    int c;
    int num;
    //rhead [i]：第 i 行的第一个非零结点 	  chead [j]：第 j 列的第一个非零结点
    OLNode **rhead;// 行头指针数组
    OLNode **chead;// 列头指针数组
    CrossMatrix();
    CrossMatrix(int row, int col);
    ~CrossMatrix();
};
CrossMatrix::CrossMatrix()// 构造函数
{
    r = 0;
    c = 0;
    num = 0;
    rhead = nullptr;
    chead = nullptr;
}
CrossMatrix::CrossMatrix(int row, int col)// 构造函数
{
    r = row;
    c = col;
    num = 0;
    rhead = new OLNode*[r];
    chead = new OLNode*[c];
    for(int i = 0; i < r; ++i) 
    {	
        rhead[i] = nullptr;
    }
    for(int j = 0; j < c; ++j) 
    {
        chead[j] = nullptr;
    }
}
CrossMatrix::~CrossMatrix()// 析构函数
{
    if(rhead == nullptr || chead == nullptr) 
    {
		return;
    }
    for(int i = 0; i < r; ++i)
    {
        OLNode *p = rhead[i];
        while(p)
        {
            OLNode *q = p->right;
            delete p;
            p = q;
        }
    }
    delete [] rhead;
    delete [] chead;
}
CrossMatrix CrossMatrix::tran()// 转置算法
{
    CrossMatrix x;
    x.r=c;
    x.c=r;
    x.num=num;
    x.rhead=chead;
    x.chead=rhead;
    return x;
}


# 链式存储
# 带行指针的链式存储结构
不做介绍

# 带列指针的链式存储结构
不做介绍

# 十字链表
image-20251227201351226
image-20251227183043771


# 三、广义表
image-20251227183144028
长度（Length）： 最外层括号里，直接包含的元素个数
  • 只数第一层
  • 不往里拆

深度（Depth）：括号嵌套的最大层数
  • 原子深度 = 0
  • 空表深度 = 1
  • 非空表深度 = 1 + 各元素深度最大值
注意：（a,b) 表的深度是 1，注意区分表的深度和元素的深度

表头（Head）： 最外层的第一个元素
  • 可以是原子
  • 也可以是子表

表尾（Tail）：删掉表头后，剩下的 “表”
注意：表尾一定还是一个表（可能是空表）

image-20251227183158205 image-20251227184559545 image-20251227184636404
# 1. 存储方法 1

image-20251227185209621
class GenList;// 广义表
class GenListNode// 广义表结点
{
    friend class GenList;// 友元类，GenList 可以直接访问 GenListNode 的私有成员
private:
    bool tag;//False 表示原子元素，True 表示表元素
    //union 数据类型：所有成员共享同一块连续的内存空间，同一时间只能有一个成员有效，共用体的大小等于其最大成员的大小
    union
    {
        char data;// 当 tag=false（原子节点）时，该成员有效
        GenListNode *head;// 当 tag=true（表节点）时，该成员有效
    };
    GenListNode *tail;// 存储当前节点的表尾指针
};
class GenList
{
public:
    // 各种广义表的操作
private:
    GenListNode *first;
};


# 2. 存储方法 2
class GenList;// 广义表
class GenListNode// 广义表结点类
{
    friend class GenList;
private:
    bool tag;//False 表示原子元素，True 表示表元素
    union
    {
        char data;
        struct
        {
            GenListNode *head;
            GenListNode *tail;
        };
    };
};
class GenList
{
public:
    // 各种广义表的操作
private:
    GenListNode *first;
};


# 四、串

image-20251228090501199 image-20251228090535937 image-20251228090556480
# 1. 顺序存储结构
// 顺序存储结构类型定义
const int maxlen=100;// 允许的串最大长度；
struct Tstr
{
    int curlen;
    char str[maxlen];
};

# 2. 链式存储结构
image-20251228091138359
struct LNode
{
    char data;
    LNode *next;
};
struct LStr
{
    LNode *head;
    int len;
};