【数据结构】第三章：栈和队列

本篇笔记课程来源：王道计算机考研 数据结构

一、栈

1. 栈的定义

• 栈（Stack）是只允许在一端进行插入或删除操作的线性表。
• 空栈：空的线性表。
• 栈顶：允许插入和删除的一端，也称栈顶元素。
• 栈底：不允许插入和删除的一端，也称栈底元素。
• 特点：后进先出（Last In First Out）LIFO
• n 个不同元素进栈，出栈元素不同排列的个数为 $\frac{1}{n+1}{C}_{2n}^n$

2. 栈的基本操作

1. InitStack(&S)：初始化栈。构造一个空栈 S，分配内存空间
2. DestroyStack(&L)：销毁栈。销毁并释放栈 S 所占用的内存空间。
3. Push(&S,x)：进栈，若栈 S 未满，则将 x 加入使之称为新栈顶。
4. Pop(&S,&x)：出栈，若栈 S 非空，则弹出栈顶元素，并用 x 返回。
5. GetTop(S,&x)：读栈顶元素。若栈 S 非空，则用 x 返回栈顶元素。

二、顺序栈

1. 顺序栈的实现

• 缺点：栈的大小不可变

• 定义

  #define MaxSize 10
  typedef struct {
      int data[MaxSize];  // 静态数组存放栈中元素
      int top;            // 栈顶指针
  } SqStack;
  

• 初始化

  void InitStack(SqStack &S) {
      S.top = -1;     // 初始化栈顶指针
  }
  

• 判空

  bool StackEmpty(SqStack S) {
      return S.top == -1;
  }
  

2. 顺序栈的基本操作

• 进栈（增）

  bool Push(SqStack &S, int x) {
      if (S.top == MaxSize - 1)
          return false;       // 栈满，报错
      S.top = S.top + 1;      // 指针先加 1
      S.data[S.top] = x;      // 新元素入栈
      return true;
  }
  

• 出栈（删），只是逻辑上删除

  bool Pop(SqStack &S, int &x) {
      if (S.top == -1)
          return false;   // 栈空，报错
      x = S.data[S.top];  // 栈顶元素先出栈
      S.top = S.top - 1;  // 指针再减 1
      return true;
  }
  

• 读栈顶元素（查）

  bool GetTop(SqStack &S, int &x) {
      if (S.top == -1)
          return false;   // 栈空，报错
      x = S.data[S.top];
      return true;
  }
  

3. 两种实现方式对比

• 两种实现方式分别是
  1. 初始化时 top=-1，指向当前可以插入的位置
  2. 初始化时 top=0，指向下一个可以插入的位置

3. 共享栈

• 为了提高内存空间利用率，让两个顺序栈共享同一片空间

• 实现

  #define MaxSize 10
  typedef struct {
  	int data[MaxSize];	// 静态数组存放栈中元素
  	int top0;			// 0 号栈栈顶指针
  	int top1;			// 1 号栈栈顶指针
  } ShStack;
  

• 初始化

  void InitStack(ShStack &S) {
  	S.top0 = -1;
  	S.top1 = MaxSize;
  }
  

• 栈满条件：top0 + 1 == top1

三、链栈

1. 链栈的实现

• 定义

  typedef struct LinkNode {
      int data;           // 数据域
      LinkNode *next;     // 指针域
  } LinkNode, *LiStack;   // 栈类型定义
  

2. 链栈的基本操作

• 基本操作和单链表类似。在链栈中，不带头结点的相对简单。

• 带头结点的链栈

  // 省略链栈定义...
  
  // 初始化
  bool InitStack(LiStack &L) {
      L = (LinkNode *)malloc(sizeof(LinkNode));
      if (!L) return false;
      L->next = NULL;
      return true;
  }
  
  // 销毁
  bool DestroyStack(LiStack &L) {
      LinkNode *p = L->next;
      while (p != NULL) {
          L->next = p->next;
          free(p);
          p = L->next;
      }
      free(L);
      return true;
  }
  
  // 入栈
  bool Push(LiStack &L, int x) {
      LinkNode *p = (LinkNode *)malloc(sizeof(LinkNode));
      if (!p) return false;
      p->data = x;
      p->next = L->next;
      L->next = p;
      return true;
  }
  
  // 出栈
  bool Pop(LiStack &L, int &x) {
      LinkNode *p = L->next;
      if (!p) return false;
      x = p->data;
      L->next = p->next;
      free(p);
      return true;
  }
  
  // 读栈顶元素
  bool GetTop(LiStack &L, int &x) {
      LinkNode *p = L->next;
      if (!p) return false;
      x = p->data;
      return true;
  }
  
  // 判空
  bool StackEmpty(LiStack L) {
      return L->next == NULL;
  }
  

• 不带头结点的链栈

  // 省略链栈定义...
  
  // 初始化
  bool InitStack(LiStack &L) {
      L = NULL;
      return true;
  }
  
  // 销毁
  bool DestroyStack(LiStack &L) {
      while (L != NULL) {
          LinkNode *p = L;
          L = L->next;
          free(p);
      }
      return true;
  }
  
  // 入栈
  bool Push(LiStack &L, int x) {
      LinkNode *p = (LinkNode *)malloc(sizeof(LinkNode));
      if (!p) return false;
      p->data = x;
      p->next = L;
      L = p;
      return true;
  }
  
  // 出栈
  bool Pop(LiStack &L, int &x) {
      if (!L) return false;
      x = L->data;
      LinkNode *p = L;
      L = L->next;
      free(p);
      return true;
  }
  
  // 读栈顶元素
  bool GetTop(LiStack &L, int &x) {
      if (!L) return false;
      x = L->data;
      return true;
  }
  

四、队列

1. 队列的定义

• 队列（Queue）是只允许在一端进行插入，在另一端删除的线性表。
• 空队列：空的线性表。
• 队头：允许删除的一端，最靠近队头的元素称为队头元素。
• 队尾：允许插入的一端，最靠近队尾的元素称为队尾元素。
• 特点：先进先出（First In First Out）FIFO

2. 队列的基本操作

1. InitQueue(&Q)：初始化队列，构造一个空队列 Q。
2. DestroyQueue(&Q)：销毁队列，销毁并释放队列 Q 所占用的内存空间。
3. EnQueue(&Q,x)：入队，若队列 Q 未满，将 x 加入，使之成为新的队尾。
4. DeQueue(&Q,&x)：出队，若队列 Q 非空，删除队头元素，并用 x 返回。
5. GetHead(Q,&x)：读队头元素，若队列 Q 非空，则将队头元素赋值给 x。

3. 双端队列

• 双端队列：只允许从两端插入、两端删除的线性表
• 输入受限的双端队列：只允许从一端插入、两端删除的线性表
• 输出首先的双端队列：只允许从两端插入、一端删除的线性表

五、顺序队列

1. 顺序队列的实现

• 定义有三种方式

  1. 队头和队尾指针初始化时都指向 0，但会浪费一个存储空间

     #define MaxSze 10
     typedef struct {
         int data[MaxSze];
         int front, rear;
     } SqQueue;
     

  2. 定义一个 size 变量存储队列当前长度，初始化时 size = 0，插入成功 size++，删除成功 size--

     #define MaxSze 10
     typedef struct {
         int data[MaxSze];
         int front, rear;
         int size;	// 队列当前长度
     } SqQueue;
     

  3. 定义一个 tag 变量存储最近进行的时删除还是插入，初始化时 tag = 0，插入成功 tag = 1，删除成功 tag = 0

     #define MaxSze 10
     typedef struct {
         int data[MaxSze];
         int front, rear;
         int tag;	// 最近进行的是删除 / 插入
     } SqQueue;
     

• 初始化，front 指向队头元素，rear 指向队尾元素的后一个位置

  void InitQueue(SqQueue &Q) {
      // 初始化时，队头、队尾指针指向 0
      Q.front = Q.rear = 0;
  }
  

  rear 也可以指向最后一个元素：front = 0; rear = n - 1;，类似于顺序栈的第二种实现方式。

• 判空

  bool QueueEmpty(SqQueue Q) {
      return Q.front == Q.rear;
  }
  

2. 顺序队列的基本操作

都是基于第一种实现方式

• 入队（增）

  bool EnQueue(SqQueue &Q, int x) {
      if ((Q.rear + 1) % MaxSze == Q.front)
          return false;                  // 队满报错
      Q.data[Q.rear] = x;                // 将 x 插入队尾
      Q.rear = (Q.rear + 1) % MaxSze;    // 队尾指针加 1 取模
      return true;
  }
  

• 出队（删）

  bool DeQueue(SqQueue &Q, int &x) {
      if (Q.front == Q.rear)
          return false;       // 队空报错
      x = Q.data[Q.front];
      Q.front = (Q.front + 1) % MaxSze;
      return true;
  }
  

• 读队头元素

  bool GetHead(SqQueue Q, int &x) {
      if (Q.front == Q.rear)
          return false;       // 队空报错
      x = Q.data[Q.front];
      return true;
  }
  

• 获取队列元素个数：(rear + MaxSize - front) % MaxSize

3. 三种实现方式对比

六、链队列

1. 链队列的实现

• 定义

  typedef struct LinkNode {   // 链式队列结点
      int data;
      struct LinkNode *next;
  } LinkNode;
  
  typedef struct {            // 链式队列
      LinkNode *front, *rear; // 队列的队头和队尾指针
  } LinkQueue;
  

2. 链队列的基本操作

• 带头结点的链队列

  // 初始化
  void InitQueue(LinkQueue &Q) {
      Q.front = Q.rear = (LinkNode *)malloc(sizeof(LinkNode));
      Q.front->next = NULL;
  }
  
  // 判空
  bool QueueEmpty(LinkQueue Q) {
      return Q.front == Q.rear;
  }
  
  // 入队
  void EnQueue(LinkQueue &Q, int x) {
      LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
      s->data = x;
      s->next = NULL;
      Q.rear->next = s;   // 新结点插入到 rear 之后
      Q.rear = s;         // 修改表尾指针
  }
  
  // 出队
  bool DeQueue(LinkQueue &Q, int &x) {
      if (Q.front == Q.rear)
          return false;           // 空队列
      LinkNode *p = Q.front->next;
      x = p->data;                // 用变量 x 返回队头元素
      Q.front->next = p->next;    // 修改头结点的 next 指针
      if (Q.rear == p)            // 此次时最后一个结点出队
          Q.rear = Q.front;       // 修改 rear 指针
      free(p);
      return true;
  }
  

• 不带头结点

  // 初始化
  void InitQueue(LinkQueue &Q) {
      Q.front = Q.rear = NULL;
  }
  
  // 判空
  bool QueueEmpty(LinkQueue Q) {
      return Q.front == NULL;
  }
  
  // 入队
  void EnQueue(LinkQueue &Q, int x) {
      LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
      s->data = x;
      s->next = NULL;
      if (Q.front == NULL) {      // 在空队列中插入第一个元素
          Q.front = Q.rear = s;   // 插入队头队尾指针
      } else {
          Q.rear->next = s;       // 新结点插入到 rear 结点之后
          Q.rear = s;             // 修改 rear 指针
      }
  }
  
  // 出队
  bool DeQueue(LinkQueue &Q, int &x) {
      if (Q.front == NULL)
          return false;       // 空队列
      LinkNode *p = Q.front;  // p 指向此次出队的结点
      x = p->data;            // 用变量 x 返回队头元素
      Q.front = p->next;      // 修改 front 指针
      if (Q.rear == p) {      // 此次是最后一个结点出队
          Q.front = NULL;     // 修改队首指针
          Q.rear = NULL;      // 修改队尾指针
      }
      free(p);
      return true;
  }
  

七、栈的应用

1. 括号匹配

• 算法思路：依次扫描所有字符，遇到左括号入栈，遇到右括号则弹出栈顶元素检查是否匹配。
• 匹配失败的情况：
  1. 左括号单身
  2. 右括号单身
  3. 左右括号不匹配
• 流程图

• 算法实现

#include <stdio.h>
#include <string.h>

#define MaxSize 10

typedef struct {
    char data[MaxSize];
    int top;
} SqStack;

bool BracketCheck(char str[], int length) {
    // 定义栈
    SqStack stack;
    // 初始化栈
    stack.top = -1;
    // 遍历字符串
    for (int i = 0; i < length; i++) {
        // 如果是左括号入栈
        if (str[i] == '(' || str[i] == '[' || str[i] == '{') {
            stack.data[++stack.top] = str[i];
        }
        // 如果是右括号
        else if (str[i] == ')' || str[i] == ']' || str[i] == '}') {
            // 栈空，右括号单身
            if (stack.top == -1) return false;
            // 出栈
            char symbol = stack.data[stack.top--];
            // 匹配失败
            if (str[i] == ')' && symbol != '(') return false;
            if (str[i] == ']' && symbol != '[') return false;
            if (str[i] == '}' && symbol != '{') return false;
        }
    }
    // 栈空则匹配成功，栈内如果还有元素，则左括号单身
    return stack.top == -1;
}

int main() {
    char str[20];
    gets(str);
    printf("%s", BracketCheck(str, (int)strlen(str)) ? "true" : "false");
}

2. 表达式求值

• 表达式由三部分组成：操作数、运算符、界限符，例如：1+2×(3-4)

• 三种表达式

  1. 中缀表达式：最常见的表达式，如 1+2
  2. 前缀表达式：也称波兰表达式（Polish Notation），如 +12
  3. 后缀表达式：也称逆波兰表达式（Reverse Polish Notation），如 12+

• 互转举例

  中缀表达式	前缀表达式	后缀表达式
  a+b	+ab	ab+
  a+b+c	-+abc	ab+c-
  a+b-c*d	-+ab*cd	ab+cd*-

• 中缀转后缀（手算）
  1. 确定中缀表达式中各个运算符的运算顺序（遵循左优先原则：只要左边的运算符能先计算，就优先算左边的）
  2. 选择下一个运算符，按照【左操作数 右操作数 运算符】的方式组合成一个新的操作数
  3. 如果还有运算符没被处理，就继续 ②

• 中缀转后缀（机算）
  1. 初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。
  2. 从左到右处理各个元素，直到末尾。可能遇到三种情况：
     • ① 遇到操作数：直接加入后缀表达式
     • ② 遇到界限符：遇到 “(” 直接入栈，遇到 “)” 则依次弹出栈内运算符并加入后缀表达式，直到弹出 “(” 为止。注意：“(” 不加入后缀表达式
     • ③ 遇到运算符：依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到 “(” 或栈空则停止。之后再把当前运算符入栈
  3. 按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式。

• 后缀表达式的计算（机算）
  1. 从左往右扫描下一个元素，直到处理完所有元素
  2. 若扫描到操作数，则压入栈，并回到 ①；否则执行 ③
  3. 若扫描到运算符，则弹出两个栈顶元素（先出栈的是右操作数），执行相应运算，运算结果压回栈顶，回到 ①
  4. 若表达式合法，则最后栈中只会留下一个元素，就是最终结果

• 中缀转前缀（手算）
  1. 确定中缀表达式中各个运算符的运算顺序（遵循右优先原则：只要右边的运算符能先计算，就优先算右边的）
  2. 选择下一个运算符，按照【运算符 左操作数 右操作数】的方式组合成一个新的操作数
  3. 如果还有运算符没被处理，就继续 ②

• 前缀表达式的计算（机算）
  1. 从右往左扫描下一个元素，直到处理完所有元素
  2. 若扫描到操作数，则压入栈，并回到 ①；否则执行 ③
  3. 若扫描到运算符，则弹出两个栈顶元素（先出栈的是左操作数），执行相应运算，运算结果压回栈顶，回到 ①
  4. 若表达式合法，则最后栈中只会留下一个元素，就是最终结果

• 中缀表达式的计算（中缀转后缀 + 后缀计算）
  1. 初始化两个栈，操作数栈和运算符栈
  2. 若扫描到操作数，压入操作数栈
  3. 若扫描到运算符或界限符，则按照 “中缀转后缀” 相同的逻辑压入运算符栈（期间也会弹出运算符，每当弹出一个运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应运算，运算结果再压回操作数栈）

• 中缀计算代码实现（仅实现算法，没做错误处理）

#include <cstdio>
#include <cstdlib>
#include <cstring>

// 操作数栈
typedef struct {
    float number[20];
    int top;
} OpStack;

// 运算符栈
typedef struct {
    char cal[20];
    int top;
} CalStack;

void test() {
    // 初始化栈
    OpStack op_stack;
    op_stack.top = -1;
    CalStack cal_stack;
    cal_stack.top = -1;

    // 输入
    char str[100];
    gets(str);

    // 数字寄存器
    char number[20];
    int index = 0;
    // 从左往右扫描
    for (int i = 0; i < strlen(str); i++) {
        // 如果是数字，包含小数点
        if (str[i] >= '0' && str[i] <= '9' || str[i] == '.') {
            // 存入数字寄存器
            number[index++] = str[i];
        } else if (str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/' || str[i] == '(' || str[i] == ')') {
            // 如果数字寄存器有数字
            if (index > 0) {
                // 入操作数栈
                number[index] = '\0';
                op_stack.number[++op_stack.top] = atof(number);
                // 重置数字寄存器
                index = 0;
            }

            // 空运算符栈或遇到左括号，先压入运算符栈
            if (cal_stack.top == -1 || str[i] == '(') {
                cal_stack.cal[++cal_stack.top] = str[i];
                continue;
            }
            // 获取上一个运算符
            char cal = cal_stack.cal[cal_stack.top];
            // 如果前面是左括号，则直接压入运算符栈
            if (cal == '(') {
                cal_stack.cal[++cal_stack.top] = str[i];
                continue;
            }
            // 左右操作数
            float left = 0, right = 0;
            // 循环
            while (true) {
                // 栈空，跳出循环
                if (cal_stack.top == -1) break;
                // 先获取栈顶运算符
                cal = cal_stack.cal[cal_stack.top];
                // 如果遇到左括号，跳出循环
                if (cal == '(') {
                    if (str[i] == ')') cal_stack.top--;
                    break;
                }
                // 如果扫到加减，则弹完，如果扫到乘除，只弹乘除
                if ((str[i] == '*' || str[i] == '/') && (cal == '+' || cal == '-')) break;
                cal_stack.top--;
                // 获取左右操作数
                right = op_stack.number[op_stack.top--];
                left = op_stack.number[op_stack.top--];

                // 运算后压入操作数栈
                switch (cal) {
                    case '+':
                        op_stack.number[++op_stack.top] = left + right;
                        break;
                    case '-':
                        op_stack.number[++op_stack.top] = left - right;
                        break;
                    case '*':
                        op_stack.number[++op_stack.top] = left * right;
                        break;
                    case '/':
                        op_stack.number[++op_stack.top] = left / right;
                        break;
                    default: break;
                }
            }
            // 如果扫到的是不是右括号，则把当前运算符压入运算符栈
            if (str[i] != ')') {
                cal_stack.cal[++cal_stack.top] = str[i];
            }
        }
    }

    // 把表达式最后一个数放入操作数栈
    if (index > 0) {
        number[index] = '\0';
        op_stack.number[++op_stack.top] = atof(number);
    }
    // 扫描结束，把剩余的运算符栈清空
    while (cal_stack.top != -1) {
        char cal = cal_stack.cal[cal_stack.top--];
        float right = op_stack.number[op_stack.top--];
        float left = op_stack.number[op_stack.top--];
        switch (cal) {
            case '+':
                op_stack.number[++op_stack.top] = left + right;
                break;
            case '-':
                op_stack.number[++op_stack.top] = left - right;
                break;
            case '*':
                op_stack.number[++op_stack.top] = left * right;
                break;
            case '/':
                op_stack.number[++op_stack.top] = left / right;
                break;
            default: break;
        }
    }

    // 输出
    for (int i = 0; i <= op_stack.top; i++) {
        printf("%f\n", op_stack.number[i]);
    }
}

int main() {
    test();
    return 0;
}

3. 递归

• 函数调用的特点：最后被调用的函数最先执行结束（LIFO）
• 函数调用时，需要用一个栈存储：
  1. 调用返回地址
  2. 实参
  3. 局部变量
• 适合用递归算法解决：可以把原始问题转换成属性相同，但规模较小的问题
• 递归调用时，函数调用栈可称为 “递归调用栈”
  • 每进入一层递归，就将递归调用所需信息压入栈顶
  • 每退出一层递归，就从栈顶弹出相应信息
• 递归缺点：效率低；太多层递归可能会导致栈溢出；可能包含很多重复计算
• 可以自定义栈将递归算法改造成非递归算法

八、队列的应用

1. 树的层次遍历：在 “树” 章节中会提到
2. 图的广度优先遍历：在 “图” 章节中会提到
3. 处理机调度的先来先服务（FCFS）策略。

九、特殊矩阵的压缩存储

1. 数组的存储结构

1. 一维数组：
   • 各数组元素大小相同，且物理上连续存放
   • 数组元素 a[i] 的存放地址 = LOC + i * sizeof(ElemType) (0 ≤ i）
2. 二维数组：
   • 行优先存储：M 行 N 列的二维数组 b[M][N] 中，b[i][j] 的存储地址 = LOC + (i * N + j) * sizeof(ElemType)
   • 列优先存储：M 行 N 列的二维数组 b[M][N] 中，b[i][j] 的存储地址 = LOC + (j * N + i) * sizeof(ElemType)

2. 特殊矩阵

$$\left(\begin{array}{ccccc}{a}_{1,1}& a_{1,2}& \cdots & a_{1,n-1}& a_{1,n}\\ a_{2,1}& a_{2,2}& \cdots & a_{2,n-1}& a_{2,n}\\ ⋮& ⋮& \ddots & ⋮& ⋮\\ a_{n-1,1}& a_{n-1,2}& \cdots & a_{n-1,n-1}& a_{n,-1n}\\ a_{n,1}& a_{n,2}& \cdots & a_{n,n-1}& a_{n,n}\end{array}\right)$$

1. 对称矩阵
   • 若 n 阶方阵中任意一个元素 $a_{i,j}$ 都有 $a_{i,j}=a_{j,i}$，则该矩阵为对称矩阵。
   • 三个区域 $\{\begin{array}{l}i<j，上三角区\\ i=j，主对角线\\ i>j，下三角区\end{array}$
   • 存储策略：只存储主对角线 + 下三角区（或主对角线 + 上三角区）
   • 数组长度（从 1 开始）：$\frac{(1+n)\times n}{2}$
   • 按行优先的原则，$a_{i,j}$ 是第 $k$（下标从 0 开始） 个元素：$$k=\{\begin{array}{l}\frac{i\times (i-1)}{2}+j-1，i\ge j（下三角区和主对角线元素）\\ \frac{j\times (j-1)}{2}+i-1，i<j（上三角区元素a_{i,j}=a_{j,i}）\end{array}$$
2. 三角矩阵
   • 上三角矩阵：除了主对角线和上三角区，其余元素都相同。
   • 下三角矩阵：除了主对角线和下三角区，其余元素都相同。
   • 存储策略：和对称矩阵相似，并在最后一个位置存储常量 C。
   • 数组长度（从 1 开始）：$\frac{(1+n)\times n}{2}+1$
   • 按行优先的原则，下三角矩阵 $a_{i,j}$ 是第 $k$（下标从 0 开始） 个元素：$$k=\{\begin{array}{ll}\frac{i\times (i-1)}{2}+j-1,& \text{i≥j（下三角区和主对角线元素）}\\ \frac{n\times (n+1)}{2},& \text{i<j（上三角区元素都是 C）}\end{array}$$
   • 按行优先的原则，上三角矩阵 $a_{i,j}$ 是第 $k$（下标从 0 开始） 个元素：$$k=\{\begin{array}{ll}\frac{(i-1)\times (2n-i+2)}{2}+(j-i),& \text{i≥j（下三角区和主对角线元素）}\\ \frac{n\times (n+1)}{2},& \text{i<j（上三角区元素都是 C）}\end{array}$$
3. 三对角矩阵
   • 又称带状矩阵，当 $|i-j|>1$ 时，有 $a_{i,j}=0（1\le i,j\le n）$
   • 存储策略：只存储带状部分。
   • 数组大小：$3n-2$
   • 按行优先的原则，下三角矩阵 $a_{i,j}$ 是第 $k$（下标从 0 开始） 个元素：$$k=\{\begin{array}{ll}2i+j-3,& \text{|i-j|≤1（带状部分）}\\ 0,& \text{|i-j|>1}\end{array}$$
   • 已知数组下标 $k$，求 $i,j$：
     $$(i,j)\{\begin{array}{l}i=\lceil \frac{(k+2)}{3}\rceil \\ j=k-2i+3\end{array}$$
4. 稀疏矩阵
   • 非零元素远远少于矩阵元素的个数
   • 存储策略：
     • ① 顺序存储——三元组 <行，列，值>
     • ② 链式存储——十字链表法：定义行指针数组和列指针数组，指向向下域或向右域的非零元素，每个非零数据节点包含 <行，列，值，指向同列的下一个元素，指向同行的下一个元素>